Efficient, Direct, and Restricted Black-Box Graph Evasion Attacks to Any-Layer Graph Neural Networks via Influence Function

1 INTRODUCTION

• Existing optimization-based attacks can require GNN parameters, target only two-layer models, and incur intensive computation.For multi-layer targets, they often attack a surrogate two-layer model and transfer the attack; the authors describe this strategy as insufficiently effective.Source: §1 · p. 2
• The influence-based attack is designed for any-layer GNNs without internal model information beyond the target node’s neighbors.The authors report comparable performance to state-of-the-art white-box attacks, with a 5–50x speedup on two-layer GCN/SGC and effective attacks on multi-layer models.Source: §1 · p. 2
• On Cora, four-edge perturbations achieved 93% attack success versus 80% for the surrogate-model attack.The paper also reports comparable performance to state-of-the-art white-box attacks and a 5–50x speedup against two-layer GCN/SGC.Source: §1 · p. 2

2 RELATED WORK

• Related work distinguishes targeted evasion, which aims for a specified target label, from untargeted evasion, which aims for any different label.Nettack is described as a targeted attack against two-layer GCNs; existing black-box attacks are also noted, while this paper’s attack requires only the target node’s neighbors.Source: §2 · p. 2

3 BACKGROUND AND PROBLEM DEFINITION

• GCN and SGC are considered for node classification, with SGC described as a linearized version of GCN.The GNN takes the graph and labeled nodes as input and predicts labels for unlabeled nodes.Source: §3 · p. 3
• Label propagation iteratively spreads labels to unlabeled nodes based on node-pair similarity, such as graph connectivity.The passage describes LP as a semi-supervised node-classification method without training.Source: §3 · p. 3
• A direct targeted attack changes at most Δ edges incident to the target node to make a trained GNN predict a specified target label.The attacker may add or delete edges between the target node and other nodes, but cannot change edges among other nodes.Source: §3 · p. 3
• Both LP and GNNs use iterative propagation, but LP propagates labels without model parameters while GNNs propagate features using layer-specific parameter matrices.The text contrasts LP with GNN feature propagation and notes that Nettack is inefficient, requires model parameters, and is limited to two-layer GNNs.Source: §3 · p. 3

4.1.1 Motivation.

• LP’s iterative process motivates the approach because it resembles GNN propagation while avoiding model parameters; the paper considers targeted attacks for simplicity.The authors define label influence on LP and feature-label influence on GNNs to connect the two processes.Source: §4.1.1 · pp. 3–4

4.1.2 Influence function.

• For GCNs and SGCs, feature-label influence equals LP label influence up to a constant multiplier, linking node-label changes to GNN outputs.The two influences describe how perturbing a node’s input changes another node’s output.Source: §4.1.2 · p. 4

4.2 Reformulate Evasion Attacks to Any-Layer GNNs as Calculating Label Influence on LP

• Theorem 4.2 reformulates the attack objective as label influence on LP, under an assumption that non-target-label nodes within K hops have negligible feature-label influence.The reformulation applies to any-layer GNNs and needs only the target’s K-hop neighbors and their labels, which may be estimated by querying the model.Source: §4.2 · pp. 4–5

4.3 Efficient Calculation of Label Influence

• The attack selects candidate edges by iteratively choosing the change that yields the largest positive gap between label-influence terms, up to the perturbation budget.It considers adding edges to target-label nodes and removing edges to nodes with the target node’s label.Source: §4.3 · p. 5
• Exact label-influence calculation can be costly because changing an edge requires recalculating normalized weights along affected paths, so the authors propose an approximation.The cost concern arises with large candidate sets or many edge weights to recalculate.Source: §4.3 · p. 5

5.2 Results on Attacking Two-layer GNNs

• 5-50x speedup over Nettack across three graphs accompanies comparable attack performance, with slightly lower success at budgets below 4 and nearly the same performance above 4.Figure 1 compares attack success rates and Figure 2 compares running times across attack budgets on three graphs.Source: §5.2 · p. 6, Figure 1 · p. 6, Figure 2 · p. 6
• 1-2 orders of magnitude greater efficiency accompanies an attack-success-rate difference below 2% between approximate and exact label influence.The authors report similar performance for approximate- and exact-influence attacks across all cases.Source: §5.2 · pp. 5–6
• Less than 2% separates Ours-KL and Ours-UL in attack success rate, and their running times are almost the same.The authors attribute the similar estimated and true labels to accurate GNN predictions on unlabeled nodes.Source: §5.2 · p. 6
• More than 0.5 of generated attack edges are added edges in all cases; the authors suggest adding target-label connections may be more effective than removing same-label connections.Figure 3 tracks the added-edge fraction against attack budget.Source: §5.2 · p. 6, Figure 3 · p. 6
• Lower-degree and higher-centrality target nodes are easier to attack, while attack success shows no obvious relationship with graph size.At budget 4, all target nodes of degree ≤ 4 succeed; success rates for the largest- and smallest-centrality groups also differ across the reported GNNs.Source: §5.2 · p. 7

5.3 Results on Attacking Multi-layer GNNs

• At attack budget 6, our attacks achieve ≥90% success in all four-layer GCN/SGC cases and exceed surrogate attacks by more than 10% in almost all cases.Figure 4 reports attack success rate and running time for four-layer GCN across the three graphs.Source: §5.3 · p. 7, Figure 4 · p. 7
• Less than 25 s per target node on Pubmed contrasts with about 85 s for the surrogate model in the four-layer experiments.These are average running times across the reported cases.Source: §5.3 · p. 7
• At attack budget 6, attacks transfer to GAT and JK-Net, increasing classification errors by at least 60% on all three graphs.Transfer is strongest between GCN and SGC, which the authors describe as sharing similar architectures.Source: §5.3 · p. 7, Table 1 · p. 7

Comparing with more attack baselines

• At budget 2, IG-FGSM's success rates are 0.29 against GCN and 0.32 against SGC, versus Nettack's 0.85 and 0.65; our method runs in 0.1s.The reported IG-FGSM runtimes are 62s against GCN and 55s against SGC; Nettack takes 1.5s and 2.5s, respectively.Source: Table 3 · p. 8, §6 · p. 8

Comparing with black-box attacks

• Against black-box attack [39], our method is more effective on Cora and Citeseer, especially at small budgets; [39] could not run on Pubmed due to limited GPU memory.The comparison allows [39] an unrestricted number of queries to estimate its best success rate for each budget.Source: Table 4 · p. 8, §6 · p. 8

Attack performance on a large-scale dataset

• On OGB-arxiv, Ours-KL achieves 73% attack success against GCN and 95% against SGC at budget 6, while Nettack runs out of memory.The study uses 100 correctly classified test nodes; Nettack's OOM is attributed to dense model weights and intensive matrix-matrix multiplication.Source: §6 · pp. 7–8

Defending against our attack

• At four modified edges, defense [38] achieves certified accuracy of about 0.50, 0.55, and 0.70 on the three datasets, but cannot certify robustness above 13 edges.Certified accuracy measures the fraction of target nodes predicted accurately under any modification of the specified number of edges.Source: Figure 5 · p. 8, §6 · p. 8

7 CONCLUSION

• The attack connects GNN feature-label influence to label influence on label propagation, then uses an efficient algorithm to calculate label influence.It applies to any-layer GNNs without requiring knowledge of internal model parameters.Source: §7 · p. 8
• The attack achieves comparable performance to state-of-the-art white-box attacks and a 5–50x speedup against two-layer GCNs.Source: §7 · p. 8
• The authors report that the attack is effective on multi-layer GNNs and transferable to other GNNs.Source: §7 · p. 8

Ethical considerations

• The authors describe potential misuse for evading malicious-user detection, while noting the work may inspire more robust GNNs.They state that datasets and code are publicly available and that the work is mainly for research purposes.Source: §7 · p. 9

Algorithm 2 (Label) influence-based targeted evasion attack

• The algorithm takes adjacency matrix A, layer K, target node v, target label c, and budget Δ, and outputs a success indicator.Source: Algorithm 2 (Label) influence-based… · p. 10
• It initializes the modified adjacency matrix and selects two candidate node sets from A before the budgeted attack loop.Source: Algorithm 2 (Label) influence-based… · p. 10
• During the loop, label-influence scores guide whether an edge incident to the target is added or removed; the algorithm then checks whether the target is misclassified.Source: Algorithm 2 (Label) influence-based… · p. 10

Proof of Theorem 4.1

• The proof focuses on GCN because SGC is a special case, and it derives feature-label influence from Lemma 1's Equation (8).Source: Proof of Theorem 4.1 · p. 10
• GCN and LP have similar iteration processes, except that LP has no model parameters, which are constant for a trained GCN.Source: Proof of Theorem 4.1 · p. 10
• The proof establishes a relationship between feature-label influence in GNNs and label influence in LP.Source: Proof of Theorem 4.1 · p. 10

• The attack objective is deduced from Assumption 1 into the form given in Equation (9).Source: Proof of Theorem 4.2 · p. 11
• The quantities identified after the attack are feature-label influences for the target and the compared node.Source: Proof of Theorem 4.2 · p. 11
• The relationship in Equation (15) lets the objective be expressed in terms of label influence.Source: Proof of Theorem 4.2 · p. 11

• Adding a candidate edge creates new paths from the target through that candidate, while deleting one removes existing paths through it.Source: Efficient Label Influence Calculation · p. 11
• The affected added and deleted paths lie within the candidate node’s (K−1)-hop neighborhood in the clean graph.Source: Efficient Label Influence Calculation · p. 11
• Each label influence is split into an approximate clean-graph constant and an approximate contribution localized to candidate nodes’ (K−1)-hop neighborhoods.Source: Efficient Label Influence Calculation · p. 11
• For edge additions and removals, the clean-graph constant is computed once and each candidate edge’s approximate influence can be computed in advance.Source: Efficient Label Influence Calculation · p. 12
• For removals, the approximation assumes degrees stay fixed except at the target, whose degree decreases by one.Source: Efficient Label Influence Calculation · p. 12

EXAMPLE OF CALCULATING INFLUENCE

• In the example, target v has label y_v, with three candidate additions and two candidate deletions on the illustrated graph.The example uses K=2 and two node classes.Source: EXAMPLE OF CALCULATING INFLUENCE · p. 12

Adding an edge.

• The exact total influence for adding edge (v,u7) is −0.2766; the approximate constant and edge-specific terms are close to their exact values.The approximate values are −0.3032 versus exact −0.3102, and 0.0299 versus exact 0.0336.Source: Adding an edge · p. 13
• The addition calculation ignores the degree change at u7 but accounts for the target’s degree increasing by one.Source: Adding an edge · p. 13

Deleting an edge.

• The deletion approximation ignores the degree change at u3 while accounting for the target’s degree decreasing by one.Source: Deleting an edge · p. 13
• For deleting edge (v,u3), the approximate constant and edge-specific influences are close to the exact values.The respective pairs are −0.5304 versus −0.5423 and −0.2656 versus −0.2860.Source: Deleting an edge · p. 13

• More than 80% of total influence comes from nodes sharing the target’s label across three datasets, validating Assumption 1 in the tested settings.The analysis covers 100 targets per dataset and K=2, 3, and 4; Table 6 reports the fractions.Source: More Experimental Results · p. 13, Table 6 · p. 14
• Figures 7 and 8 compare attack success rate and running time against attack budget per target for two-layer SGC on three graphs.Source: Figure 7 · p. 14, Figure 8 · p. 14
• Figure 9 reports the fraction of added edges for attacks against two-layer GCN and SGC as the per-target budget varies.Source: Figure 9 · p. 14
• Figure 10 reports attack success rate and running time for attacks against four-layer SGC on three graphs.Source: Figure 10 · p. 15
• Tables 7–9 cover transferability to other GNNs and comparisons with IG-FGSM [42] and a black-box attack [39].Table 7 specifies a budget of 6 for transferability experiments.Source: Table 7 · p. 15, Table 8 · p. 15, Table 9 · p. 15