# Blackknife: Query-Free Black-Box Rewiring Attacks on Heterogeneous Graph Neural Networks

arXiv: https://arxiv.org/abs/2606.29240 · HTML: https://mlsanity.com/paper/2606.29240/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 29 references that are in the map.
- First posted on arXiv 28 Jun 2026.

## Builds on (most cited first, 13 of 13)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [Heterogeneous Graph Transformer](https://mlsanity.com/paper/2003.01332/) (2020)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Are we really making much progress? Revisiting, benchmarking, and refining heterogeneous graph neural networks](https://mlsanity.com/paper/2112.14936/) (2021)
- [Decoupling the Depth and Scope of Graph Neural Networks](https://mlsanity.com/paper/2201.07858/) (2022)
- [A Survey of Graph Neural Networks for Social Recommender Systems](https://mlsanity.com/paper/2212.04481/) (2022)
- [DSKReG: Differentiable Sampling on Knowledge Graph for Recommendation with Relational GNN](https://mlsanity.com/paper/2108.11883/) (2021)
- [Efficient Heterogeneous Graph Learning via Random Projection](https://mlsanity.com/paper/2310.14481/) (2023)
- [Modeling Dynamic Heterogeneous Graph and Node Importance for Future Citation Prediction](https://mlsanity.com/paper/2305.17417/) (2023)
- [Enabling Homogeneous GNNs to Handle Heterogeneous Graphs via Relation Embedding](https://mlsanity.com/paper/2209.11414/) (2022)
- [HGAttack: Transferable Heterogeneous Graph Adversarial Attack](https://mlsanity.com/paper/2401.09945/) (2024)

## Abstract (arXiv)

Heterogeneous graph neural networks (HGNNs) perform well on graphs with multiple node and relation types, but their robustness to attacks with restricted structural access remains insufficiently understood. We propose Blackknife, a query-free, strict black-box evasion attack that observes only the one-hop structures of the attacked nodes, their ground-truth labels, and raw features within the permitted action space. No victim-model outputs are used to train the surrogate, generate perturbations, or select attacks.Blackknife trains a shared surrogate using only observable edges and relation types, then optimizes structural perturbations through continuous relaxation and projected gradient ascent. Each rewiring operation deletes one edge and adds another of the same relation type, preserving the target node's total degree and degree for each relation type. A cosine-similarity penalty and an adaptive structural classifier further regularize the perturbations through bilevel optimization. Experiments on different datasets demonstrate competitive attack success rates across five victim architectures and three defense settings. The results expose HGNN vulnerabilities under jointly restricted graph access and query-free attack generation.