pith. sign in

arxiv: 2606.29240 · v1 · pith:CR2IMPFQnew · submitted 2026-06-28 · 💻 cs.LG · cs.SI

Blackknife: Hard-Label Query-Limited Black-Box Attacks on Heterogeneous Graph Neural Networks

Honglin Gao , Junhao Ren , Lan Zhao , Yue Yang , Jindong Chang , Gaoxi Xiao This is my paper

Pith reviewed 2026-06-30 08:35 UTC · model grok-4.3

classification 💻 cs.LG cs.SI
keywords heterogeneous graph neural networksblack-box attackshard-label queriessurrogate modelgraph structure perturbationevasion attackstopology defenses
0
0 comments X

The pith

Blackknife shows that HGNNs can be evaded by attacks using only hard-label queries and local one-hop neighborhoods.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents Blackknife, a framework that attacks heterogeneous graph neural networks under strict black-box conditions with no access to model internals or the full graph. It builds a surrogate from observable local neighborhoods, relaxes edge changes into continuous weights for optimization, and converts the result into discrete rewirings verified by limited hard labels. A reader would care because deployed HGNN services often expose only query responses and partial structure, making this a realistic test of whether such limited access is enough to break the models. Experiments on ACM, DBLP, and IMDB show the attacks succeed against standard HGNNs and hold up against topology defenses.

Core claim

Blackknife first constructs a local relation-aware surrogate model from observable heterogeneous neighborhoods. It then relaxes discrete edge addition and deletion operations into continuous soft weights and optimizes them through projected gradient descent. Finally, the optimized perturbations are discretized into relation-preserving structural rewiring operations and verified using limited hard-label feedback from the victim model, achieving strong attack success rates on ACM, DBLP, and IMDB datasets against representative HGNN models while remaining effective under topology-based defenses.

What carries the argument

Local relation-aware surrogate model built from one-hop heterogeneous neighborhoods, used to optimize and transfer structural perturbations under hard-label constraints.

If this is right

  • Blackknife achieves strong attack success rates on representative HGNN models across ACM, DBLP, and IMDB datasets.
  • The attacks remain effective when topology-based defense strategies are applied.
  • The method operates without any access to gradients, logits, confidence scores, or the complete graph structure.
  • Edge perturbations are generated by optimizing continuous soft weights then discretizing them into relation-preserving rewirings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If one-hop neighborhoods contain enough relational signal, the same local-surrogate approach could extend to attacks on other graph neural network variants.
  • Service providers might need to add query-rate limits or inject noise into neighborhood views to reduce transfer from such surrogates.
  • The continuous-to-discrete step indicates that gradient-based optimization on relaxed graph edits can produce transferable discrete changes even when only binary labels are available.
  • This line of work could encourage new robustness tests that explicitly restrict attackers to local structure and hard labels rather than full white-box access.

Load-bearing premise

A surrogate model built only from locally observable one-hop heterogeneous neighborhoods can produce perturbations that transfer effectively to the unknown victim HGNN under hard-label feedback.

What would settle it

If the discretized rewirings produced by the surrogate cause no measurable drop in the victim HGNN's accuracy on targeted nodes despite successful optimization and query verification, the transfer claim would fail.

Figures

Figures reproduced from arXiv: 2606.29240 by Gaoxi Xiao, Honglin Gao, Jindong Chang, Junhao Ren, Lan Zhao, Yue Yang.

Figure 1
Figure 1. Figure 1: Overall framework of Blackknife for strict black-box attacks on heterogeneous graph neural networks. The attack objective can be formulated as max Δ 𝟙 [ 𝑓(𝑣𝑝 ∣ 𝐺 ⊕ Δ) ≠ 𝑦𝑝 ] , s.t. Δ ⊆ { (𝑣𝑝 , 𝑣𝑎 , 𝑟) ∣ 𝑣𝑎 ∈ 𝑡𝑎 , 𝑡𝑎 ∈ aux, 𝑟 ∈  } ∪ { (𝑣𝑎 , 𝑣𝑝 , 𝑟) ∣ 𝑣𝑎 ∈ 𝑡𝑎 , 𝑡𝑎 ∈ aux, 𝑟 ∈  } , |Δ| ≤ 𝑐, 𝑞(Δ) ≤ 𝑄. (1) Here, 𝑦𝑝 denotes the true label of the target node 𝑣𝑝 , and 𝑓(𝑣𝑝 ∣ 𝐺⊕Δ) denotes the hard-label … view at source ↗
read the original abstract

Heterogeneous graph neural networks (HGNNs) have achieved strong performance in modeling complex graph-structured data with multiple node and relation types. However, their robustness under realistic black-box adversarial settings remains insufficiently explored. Existing attacks on HGNNs usually assume access to model gradients, soft prediction scores, or the complete graph structure, which is often unavailable when HGNN-based services are deployed as closed systems. In this paper, we propose Blackknife, a hard-label, query-limited, and structure-limited black-box evasion attack framework for heterogeneous graph neural networks. Blackknife assumes no access to the victim model architecture, parameters, gradients, logits, confidence scores, or the full graph structure. Instead, it only relies on locally observable one-hop heterogeneous structures and a small number of hard-label queries. To generate effective perturbations under these strict constraints, Blackknife first constructs a local relation-aware surrogate model from observable heterogeneous neighborhoods. It then relaxes discrete edge addition and deletion operations into continuous soft weights and optimizes them through projected gradient descent. Finally, the optimized perturbations are discretized into relation-preserving structural rewiring operations and verified using limited hard-label feedback from the victim model. Extensive experiments on three benchmark heterogeneous graph datasets, including ACM, DBLP, and IMDB, demonstrate that Blackknife consistently achieves strong attack success rates against representative HGNN models. The results further show that Blackknife remains effective under topology-based defense strategies, revealing the vulnerability of HGNNs to local structure-limited black-box attacks.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes Blackknife, a hard-label query-limited structure-limited black-box evasion attack on heterogeneous graph neural networks. It constructs a local relation-aware surrogate from observable one-hop heterogeneous neighborhoods, relaxes discrete edge addition/deletion to continuous soft weights, optimizes via projected gradient descent, discretizes the result into relation-preserving rewirings, and verifies with a small number of hard-label queries to the victim. Experiments on ACM, DBLP, and IMDB are reported to show strong attack success rates against representative HGNN models and continued effectiveness under topology-based defenses.

Significance. If the transferability result holds under the stated constraints, the work would establish that HGNNs remain vulnerable even when only local one-hop structure and binary label feedback are available, which is relevant to the security of deployed closed HGNN services. The method is presented as a direct empirical construction without fitted parameters or reductions to prior quantities.

major comments (2)
  1. [Method (surrogate and optimization)] The central claim rests on successful transfer of perturbations from a strictly one-hop local surrogate to the unknown victim HGNN under hard-label feedback only. HGNN message passing aggregates over multiple hops and relation types, yet no analysis, ablation, or bound is provided on the distribution shift or decision-boundary mismatch that this locality assumption introduces.
  2. [Experiments] The abstract states that Blackknife 'consistently achieves strong attack success rates' on three datasets, but the provided text supplies no numerical ASR values, query budgets, baseline comparisons, or ablation results. Without these quantitative details the experimental support for the central claim cannot be assessed.
minor comments (2)
  1. [Method] Notation for the soft-weight relaxation and the discretization step should be defined with explicit equations rather than prose description.
  2. [Experiments] The manuscript should clarify the precise query budget used in the hard-label verification phase and whether it is fixed across all experiments.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback. We address the two major comments point by point below, indicating planned revisions where the manuscript requires strengthening.

read point-by-point responses

  1. Referee: [Method (surrogate and optimization)] The central claim rests on successful transfer of perturbations from a strictly one-hop local surrogate to the unknown victim HGNN under hard-label feedback only. HGNN message passing aggregates over multiple hops and relation types, yet no analysis, ablation, or bound is provided on the distribution shift or decision-boundary mismatch that this locality assumption introduces.

    Authors: We agree that the manuscript provides no theoretical analysis, bounds, or dedicated ablation on the distribution shift and decision-boundary mismatch arising from the strict one-hop locality assumption. The framework is presented as an empirical construction. In revision we will add an ablation examining performance when the surrogate is restricted to one-hop versus expanded neighborhoods (where observable) and include a limitations paragraph discussing the locality assumption. revision: yes

  2. Referee: [Experiments] The abstract states that Blackknife 'consistently achieves strong attack success rates' on three datasets, but the provided text supplies no numerical ASR values, query budgets, baseline comparisons, or ablation results. Without these quantitative details the experimental support for the central claim cannot be assessed.

    Authors: The referee correctly observes that the abstract and excerpt contain no specific numerical ASR values, query budgets, baseline comparisons, or ablation results. We will revise the manuscript to include a concise summary of key quantitative results (ASR, query counts, baselines) in the abstract or introduction and ensure all ablation tables are clearly presented. revision: yes

Circularity Check

0 steps flagged

No significant circularity; empirical construction with no derivation chain

full rationale

The paper describes Blackknife as a practical attack pipeline (local surrogate from one-hop neighborhoods, continuous relaxation of edge ops, PGD, discretization, hard-label verification) evaluated empirically on ACM/DBLP/IMDB. No equations, fitted parameters presented as predictions, self-citations used as load-bearing uniqueness theorems, or reductions of outputs to inputs by construction appear in the text. The central claims rest on experimental attack success rates rather than any self-referential mathematical derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No explicit free parameters, axioms, or invented entities are stated in the abstract; the method relies on standard optimization assumptions implicit in PGD and surrogate training.

pith-pipeline@v0.9.1-grok · 5814 in / 1140 out tokens · 29964 ms · 2026-06-30T08:35:07.220788+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 1 canonical work pages · 1 internal anchor

  1. [1]

    Gnn model based on node classification forecasting in social network, in: 2023 International Conference on Artificial Intelligence and Smart Communication (AISC), IEEE

    Awasthi, A., Garov, A.K., Sharma, M., Sinha, M., 2023. Gnn model based on node classification forecasting in social network, in: 2023 International Conference on Artificial Intelligence and Smart Communication (AISC), IEEE. pp. 1039–1043

    2023

  2. [2]

    Node classifica- tion in social networks

    Bhagat, S., Cormode, G., Muthukrishnan, S., 2011. Node classifica- tion in social networks. Social network data analytics , 115–148

    2011

  3. [3]

    Biognn: how graph neural networks can solve biological problems, in: Artifi- cialIntelligenceandMachineLearningforHealthcare:Vol.1:Image and Data Analytics

    Bongini, P., Pancino, N., Scarselli, F., Bianchini, M., 2022. Biognn: how graph neural networks can solve biological problems, in: Artifi- cialIntelligenceandMachineLearningforHealthcare:Vol.1:Image and Data Analytics. Springer, pp. 211–231

    2022

  4. [4]

    Dai, H., Li, H., Tian, T., Huang, X., Wang, L., Zhu, J., Song, L.,

  5. [5]

    Adversarial attack on graph structured data, in: International conference on machine learning, PMLR. pp. 1115–1124

  6. [6]

    Graphneuralnetworksforsocialrecommendation,in:Theworldwide web conference, pp

    Fan, W., Ma, Y., Li, Q., He, Y., Zhao, E., Tang, J., Yin, D., 2019. Graphneuralnetworksforsocialrecommendation,in:Theworldwide web conference, pp. 417–426

    2019

  7. [7]

    Magnn: Metapath aggregatedgraphneuralnetworkforheterogeneousgraphembedding, in: Proceedings of the web conference 2020, pp

    Fu, X., Zhang, J., Meng, Z., King, I., 2020. Magnn: Metapath aggregatedgraphneuralnetworkforheterogeneousgraphembedding, in: Proceedings of the web conference 2020, pp. 2331–2341

    2020

  8. [8]

    Geng, H., Wang, D., Zhuang, F., Ming, X., Du, C., Jiang, T., Guo, H., Liu, R., 2022. Modeling dynamic heterogeneous graph and node importance for future citation prediction, in: Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pp. 572–581

    2022

  9. [9]

    Efficientheterogeneousgraphlearning via random projection

    Hu,J.,Hooi,B.,He,B.,2024. Efficientheterogeneousgraphlearning via random projection. IEEE Transactions on Knowledge and Data Engineering

    2024

  10. [10]

    Heterogeneous graph transformer, in: Proceedings of the web conference 2020, pp

    Hu, Z., Dong, Y., Wang, K., Sun, Y., 2020. Heterogeneous graph transformer, in: Proceedings of the web conference 2020, pp. 2704– 2710

    2020

  11. [11]

    Learning deep neural networks for node classification

    Li, B., Pi, D., 2019. Learning deep neural networks for node classification. Expert Systems with Applications 137, 324–334

    2019

  12. [12]

    Graphsignalprocessing,graphneural network and graph learning on biological data: a systematic review

    Li, R., Yuan, X., Radfar, M., Marendy, P., Ni, W., O’Brien, T.J., Casillas-Espinosa,P.M.,2021. Graphsignalprocessing,graphneural network and graph learning on biological data: a systematic review. IEEE Reviews in Biomedical Engineering 16, 109–135

    2021

  13. [13]

    Ghattack: Generative adversarial attacks on heterogeneous graph neural networks

    Li, S., Liao, X., Zhu, H., Le, J., Chu, L., 2026. Ghattack: Generative adversarial attacks on heterogeneous graph neural networks. IEEE Transactions on Neural Networks and Learning Systems

    2026

  14. [14]

    Indigo:Gnn-based inductive knowledge graph completion using pair-wise encoding

    Liu,S.,Grau,B.,Horrocks,I.,Kostylev,E.,2021. Indigo:Gnn-based inductive knowledge graph completion using pair-wise encoding. Advances in Neural Information Processing Systems 34, 2034–2045

    2021

  15. [15]

    Lv,Q.,Ding,M.,Liu,Q.,Chen,Y.,Feng,W.,He,S.,Zhou,C.,Jiang, J., Dong, Y., Tang, J., 2021. Are we really making much progress? revisiting, benchmarking and refining heterogeneous graph neural networks, in: Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pp. 1150–1160. Honglin Gao et al.:Preprint submitted to ElsevierPage 8...

    2021

  16. [16]

    Towards Deep Learning Models Resistant to Adversarial Attacks

    Madry, A., Makelov, A., Schmidt, L., Tsipras, D., Vladu, A., 2017. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  17. [17]

    Biological network analysis with deep learning

    Muzio, G., O’Bray, L., Borgwardt, K., 2021a. Biological network analysis with deep learning. Briefings in bioinformatics 22, 1515– 1530

  18. [18]

    Biological network analysis with deep learning

    Muzio, G., O’Bray, L., Borgwardt, K., 2021b. Biological network analysis with deep learning. Briefings in bioinformatics 22, 1515– 1530

  19. [19]

    A survey of graph neural networks for social recommender systems

    Sharma, K., Lee, Y.C., Nambi, S., Salian, A., Shah, S., Kim, S.W., Kumar, S., 2024. A survey of graph neural networks for social recommender systems. ACM Computing Surveys 56, 1–34

    2024

  20. [20]

    Finhgnn: A conditional heterogeneousgraphlearningtoaddressrelationalattributesforstock predictions

    Tan, J., Li, Q., Wang, J., Chen, J., 2022. Finhgnn: A conditional heterogeneousgraphlearningtoaddressrelationalattributesforstock predictions. Information Sciences 618, 317–335

    2022

  21. [21]

    Enablinghomogeneous gnns to handle heterogeneous graphs via relation embedding

    Wang,J.,Guo,Y.,Yang,L.,Wang,Y.,2023. Enablinghomogeneous gnns to handle heterogeneous graphs via relation embedding. IEEE Transactions on Big Data 9, 1697–1710

    2023

  22. [22]

    ggatlda: lncrna-disease association prediction based on graph-level graph attention network

    Wang, L., Zhong, C., 2022. ggatlda: lncrna-disease association prediction based on graph-level graph attention network. BMC bioinformatics 23, 1–24

    2022

  23. [23]

    2022–2032

    Wang,X.,Hou,Y.,Chen,Y.,Yang,S.,Zhang,Y.,Wang,Z.,Xiao,J., Yu,W.,Lin,Y.,Xiao,W.,etal.,2019a.Heterogeneousgraphattention network, in: The world wide web conference, pp. 2022–2032

    2022

  24. [24]

    Heterogeneous graph attention network, in: The world wide web conference, pp

    Wang, X., Ji, H., Shi, C., Wang, B., Ye, Y., Cui, P., Yu, P.S., 2019b. Heterogeneous graph attention network, in: The world wide web conference, pp. 2022–2032

    2022

  25. [25]

    Wang, Y., Liu, Z., Fan, Z., Sun, L., Yu, P.S., 2021. Dskreg: Differentiable sampling on knowledge graph for recommendation with relational gnn, in: Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 3513– 3517

    2021

  26. [26]

    3584–3593

    Xiang,S.,Cheng,D.,Shang,C.,Zhang,Y.,Liang,Y.,2022.Temporal and heterogeneous graph neural network for financial time series prediction,in:Proceedingsofthe31stACMinternationalconference on information & knowledge management, pp. 3584–3593

    2022

  27. [27]

    Hgnn:Hierarchicalgraphneuralnetworkfor predictingtheclassificationofprice-limit-hittingstocks

    Xu, C., Huang, H., Ying, X., Gao, J., Li, Z., Zhang, P., Xiao, J., Zhang,J.,Luo,J.,2022. Hgnn:Hierarchicalgraphneuralnetworkfor predictingtheclassificationofprice-limit-hittingstocks. Information Sciences 607, 783–798

    2022

  28. [28]

    Revisiting citation prediction with cluster- aware text-enhanced heterogeneous graph neural networks, in: 2023 IEEE 39th International Conference on Data Engineering (ICDE), IEEE

    Yang, C., Han, J., 2023. Revisiting citation prediction with cluster- aware text-enhanced heterogeneous graph neural networks, in: 2023 IEEE 39th International Conference on Data Engineering (ICDE), IEEE. pp. 682–695

    2023

  29. [29]

    Simpleandefficient heterogeneous graph neural network, in: Proceedings of the AAAI conference on artificial intelligence, pp

    Yang,X.,Yan,M.,Pan,S.,Ye,X.,Fan,D.,2023. Simpleandefficient heterogeneous graph neural network, in: Proceedings of the AAAI conference on artificial intelligence, pp. 10816–10824

    2023

  30. [30]

    Acompre- hensivesurveyofgraphneuralnetworksforknowledgegraphs

    Ye,Z.,Kumar,Y.J.,Sing,G.O.,Song,F.,Wang,J.,2022. Acompre- hensivesurveyofgraphneuralnetworksforknowledgegraphs. IEEE Access 10, 75729–75741

    2022

  31. [31]

    Decoupling the depth and scope of graph neural networks, in: Beygelzimer, A., Dauphin, Y., Liang, P., Vaughan, J.W

    Zeng, H., Zhang, M., Xia, Y., Srivastava, A., Malevich, A., Kannan, R., Prasanna, V., Jin, L., Chen, R., 2021. Decoupling the depth and scope of graph neural networks, in: Beygelzimer, A., Dauphin, Y., Liang, P., Vaughan, J.W. (Eds.), Advances in Neural Information Processing Systems, pp. 21248–21258. URL:https://openreview. net/forum?id=d0MtHWY0NZ

    2021

  32. [32]

    Measuring academic in- fluenceusingheterogeneousauthor-citationnetworks

    Zhao, F., Zhang, Y., Lu, J., Shai, O., 2019. Measuring academic in- fluenceusingheterogeneousauthor-citationnetworks. Scientometrics 118, 1119–1140

    2019

  33. [33]

    Hgattack: Transferable heterogeneous graph adversarial attack, in: 2024 IEEE International Conference on Agents (ICA), IEEE

    Zhao, H., Zeng, Z., Wang, Y., Ye, D., Miao, C., 2024. Hgattack: Transferable heterogeneous graph adversarial attack, in: 2024 IEEE International Conference on Agents (ICA), IEEE. pp. 100–105

    2024

  34. [34]

    Relation structure-aware heterogeneous graph neural network, in: 2019 IEEE international conference on data mining (ICDM), IEEE

    Zhu, S., Zhou, C., Pan, S., Zhu, X., Wang, B., 2019. Relation structure-aware heterogeneous graph neural network, in: 2019 IEEE international conference on data mining (ICDM), IEEE. pp. 1534– 1539

    2019

  35. [35]

    Zhu,Z.,Fan,X.,Chu,X.,Bi,J.,2020. Hgcn:Aheterogeneousgraph convolutional network-based deep learning model toward collective classification, in: Proceedings of the 26th ACM SIGKDD interna- tional conference on knowledge discovery & data mining, pp. 1161– 1171

    2020

  36. [36]

    Adversarial attacksonneuralnetworksforgraphdata,in:Proceedingsofthe24th ACM SIGKDD international conference on knowledge discovery & data mining, pp

    Zügner, D., Akbarnejad, A., Günnemann, S., 2018. Adversarial attacksonneuralnetworksforgraphdata,in:Proceedingsofthe24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2847–2856

    2018

  37. [37]

    Adversarial attacks on neural networks for graph data, in: Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp

    Zügner, D., Günnemann, S., 2018. Adversarial attacks on neural networks for graph data, in: Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2847–2856. Honglin Gao et al.:Preprint submitted to ElsevierPage 9 of 9

    2018