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 this http URL 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.

Machine Learning (cs.LG); Social and Information Networks (cs.SI)

arXiv:2606.29240 [cs.LG]

(or arXiv:2606.29240v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2606.29240 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.