Blackknife attacks HGNNs with hard-label, query-limited black-box method

A new adversarial attack method called Blackknife targets heterogeneous graph neural networks (HGNNs) under the most restrictive black-box settings. Unlike prior attacks that require model gradients, soft prediction scores, or complete graph structure, Blackknife operates with only hard-label outputs (final predicted class) and locally observable one-hop heterogeneous neighborhoods. This makes it highly realistic for attacking closed HGNN-based services where only the final prediction is exposed.

To generate effective perturbations under such strict constraints, the authors first construct a local relation-aware surrogate model from the attacker's limited view. They then relax discrete edge addition/deletion into continuous soft weights and optimize them using projected gradient descent. After optimization, perturbations are discretized into relation-preserving structural rewiring operations, validated via limited hard-label queries to the victim model. This contrasts with earlier white-box or soft-score attacks, making Blackknife the first to address hard-label, query-limited attacks specifically for heterogeneous graphs.

Extensive evaluation on three benchmark datasets—ACM, DBLP, and IMDB—demonstrates that Blackknife consistently achieves strong attack success rates against representative HGNN models (e.g., HAN, HGT). The method remains effective even when the victim deploys topology-based defense strategies, highlighting a significant blind spot in current HGNN robustness research. The work underscores the need for more resilient graph neural architectures in real-world deployments where attackers have minimal information.