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

The gist The proposed Blackknife framework is a hard-label, query-limited, and structure-limited black-box evasion attack designed for heterogeneous graph neural networks.

Problem Definition

In this work, we consider structure perturbations on edges between the target primary node and nodes of auxiliary types Given a heterogeneous graph G = (, , X), a trained node classification model f, and a target node vp ∈ p of the primary type tp, the goal of an untargeted evasion attack is to modify the graph structure after model training such that the prediction of vp becomes incorrect The attack objective can be formulated as max Δ∱ 1 [f(vp G ⊕ Δ∱) ≠ yp], s.t. Δ∱ ⊆ [(vp, va, r) ∣ va ∈ ta, ta ∈ aux, r ∈ ]∪[(va, vp, r) ∣ va ∈ ta, ta ∈ aux, r ∈ ], Δ∱ ≤ c, q(Δ∱) ≤ Q

Methodology: Blackknife Framework

Blackknife is a novel black-box evasion attack framework for heterogeneous graph neural networks tailored for strict information constraints The framework consists of three main stages: Local Surrogate Construction, Gradient-Guided Structural Rewiring, and Hard-Label Verification

1. Local Surrogate Construction

The first stage involves extracting locally observable subgraphs around attacked primary nodes and using these subgraphs to train a heterogeneous surrogate model For a target node vp ∈ A, its locally visible node set is defined as loc(vp) = [vp] ∪ [va ∣ va ∈ ta, ta ∈ aux, (vp, va, r) ∈  or (va, vp, r) ∈ ] The corresponding local subgraph is then induced by loc(vp) while preserving the original node types, edge types, and node features Our surrogate model is inspired by the relation-aware message passing mechanism of RGCN and is denoted as gθ After L layers of relation-aware message passing, the prediction of the surrogate model for a primary node vp is given by ̂yp = softmax (Wo h(L)p), We then train the surrogate model for node classification on the locally observable primary nodes: θ∗ = arg min θ ∑ vp∈A ce (gθ(vp Gloc), yp),

Methodology: Gradient-Guided Structural Rewiring

The second stage uses the trained local surrogate model to optimize structural rewiring operations For each attacked primary node vp, we first construct a set of candidate edge deletions and a set of candidate edge additions These discrete rewiring operations are relaxed into a continuous optimization problem by introducing a continuous selection variable si ∈ [0, 1] and defining the corresponding soft edge weight as wi(si) = bi + (1 − 2bi)si On the soft graph, Blackknife computes the logits of vp using the trained surrogate model and maximizes an untargeted margin objective: ðf(vp) = max k≠yp zk(vp) − zyyp(vp), Blackknife updates the continuous selection vector si through projected gradient descent: s(t+1) = Π (s(t) + ηt∇s f(vp) ∇s f(vp)2), After PGD optimization, Blackknife discretizes the continuous vector s into an edge modification set Δ∱

Methodology: Hard-Label Verification

The final stage involves verifying the generated candidates using hard-label feedback from the victim model Blackknife then applies the selected edge modifications to the original graph and obtains the perturbed graph The attacker queries the victim model to obtain the final predicted label of the attacked node on the perturbed graph If the predicted label returned by the victim model is different from the ground-truth label, a successful perturbation is found and stops immediately The verification process is constrained by the query budget Q, as Blackknife can query the victim model at most Q times

Experimental Results

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 On DBLP, Blackknife consistently outperforms all available baselines across the evaluated victim models On IMDB, Blackknife further demonstrates strong attack effectiveness, achieving very high ASR on HAN, HGT, and SimpleHGN Table 3 reports the attack success rates under budget c = 3

Defense Resistance

Table 4 reports the defense results on HGT under budget c = 3 and defense threshold 0.01 Overall, Blackknife shows strong resistance against different defense strategies On ACM and DBLP, Blackknife consistently achieves the highest defended attack success rates under pruning, first-order proximity, and second-order proximity defenses This indicates that the perturbations generated by Blackknife are not easily removed by simple structural filtering Overall, the results demonstrate that Blackknife can preserve a relatively high attack success rate even after defensive filtering

Conclusion

In this paper, we propose Blackknife, a hard-label, querylimited, and structure-limited black-box attack framework for heterogeneous graph neural networks By combining local surrogate learning, gradient-guided structural rewiring, and hard-label verification, Blackknife can generate effective relation-preserving perturbations under strict black-box constraints Experiments on three benchmark heterogeneous graph datasets show that Blackknife consistently degrades the performance of representative HGNN victim models and outperforms baseline attacks The results under different defense strategies further demonstrate its robustness and reveal the vulnerability of existing HGNNs to local structural rewiring attacks Future work plans to extend Blackknife beyond node classification to other heterogeneous graph learning tasks, such as link prediction and recommendation Another important direction is to study a stricter structure-free blackbox setting, where the attacker cannot access any graph structure and can only rely on hard-label queries from the victim model.

References

[1] 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

[5] Fan, W., Ma, Y., Li, Q., He, Y., Zhao, E., Tang, J., Yin, D., 2019. Graph neural networks for social recommendation, in: The world wide web conference, pp. 417–426

[35] Zügner, D., Akbarnejad, A., 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.

1. A new adversarial evasion attack framework, Blackknife, can be developed for heterogeneous graph neural networks (HGNNs) that operates under strict black-box constraints: Blackknife assumes no access to the victim model architecture, parameters, gradients, logits, confidence scores, or the complete graph structure. This allows attackers to generate effective perturbations by only relying on locally observable one-hop heterogeneous structures and a small number of hard-label queries.

2. The improved system can perform structural rewiring operations that are relation-preserving while targeting specific node types: the optimized soft selection vector still corresponds to a valid relation-preserving rewiring operation. This ensures that the generated perturbations maintain the basic type semantics of the heterogeneous graph, leading to more semantically meaningful attacks.

3. The system can learn attack guidance from limited local data through a surrogate model: "Blackknife first trains a local heterogeneous surrogate model using the observable one-hop neighborhood of the target nodes, so that the attacker can estimate useful structural perturbation directions without relying on white-box information from the victim model. This enables effective attacks even when the attacker cannot access the gradients, logits, confidence scores, or internal representations of the victim model."

4. The system can perform continuous optimization for structural changes using a surrogate's output: Blackknife then relaxes discrete candidate edge additions and deletions into learnable soft edge weights and optimizes them through projected gradient descent on the surrogate model. This provides a mechanism to jointly search for deletion and addition operations on the local surrogate model, rather than ranking individual edges independently.

5. The system can verify structural modifications using minimal feedback: Finally, only a small number of selected perturbation candidates are verified through hard-label queries to the victim model, stopping once misclassification is achieved or the query budget is exhausted. This allows for an attack that remains consistent with the strict black-box setting while ensuring effectiveness.