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

Abstract

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.