Source-linked AI summary
Towards More Practical Adversarial Attacks on Graph Neural Networks
Jiaqi Ma, Shuangrui Ding, Qiaozhu Mei
TL;DR
The paper addresses black-box GNN attacks when attackers can access and manipulate only a small subset of nodes, without model parameters or predictions. It derives a structural, PageRank-like node-importance strategy from GNN–random-walk connections and adds a greedy correction for diminishing misclassification returns. The corrected strategy significantly outperforms competing attacks on real-world data, including with perturbations to 1% of nodes.
Problem
Existing attack setups do not adequately model attackers who can access and manipulate only a small subset of nodes under limited model knowledge.
Method
The paper selects attack nodes using a model-independent importance score linked to GNN backward propagation and random walks, then applies a greedy correction for diminishing misclassification returns.
Results
The proposed GC-RWCS strategy significantly outperforms competing strategies and can decrease node-classification accuracy by up to 33.5%.
Takeaways & Limitations
GNNs remain vulnerable under highly restricted black-box attacks using only graph structure, even when the same perturbation is added to features of 1% of nodes.
Takeaways & Limitations
The attack construction assumes limited global gradient information and uses a fixed perturbation vector based on domain knowledge.
Abstract
from arXiv · showhide
We study the black-box attacks on graph neural networks (GNNs) under a novel and realistic constraint: attackers have access to only a subset of nodes in the network, and they can only attack a small number of them. A node selection step is essential under this setup. We demonstrate that the structural inductive biases of GNN models can be an effective source for this type of attacks. Specifically, by exploiting the connection between the backward propagation of GNNs and random walks, we show that the common gradient-based white-box attacks can be generalized to the black-box setting via the connection between the gradient and an importance score similar to PageRank. In practice, we find attacks based on this importance score indeed increase the classification loss by a large margin, but they fail to significantly increase the mis-classification rate. Our theoretical and empirical analyses suggest that there is a discrepancy between the loss and mis-classification rate, as the latter presents a diminishing-return pattern when the number of attacked nodes increases. Therefore, we propose a greedy procedure to correct the importance score that takes into account of the diminishing-return pattern. Experimental results show that the proposed procedure can significantly increase the mis-classification rate of common GNNs on real-world data without access to model parameters nor predictions.
1 Introduction
The paper studies practical black-box GNN attacks when attackers can access only a subset of nodes and manipulate only a few of them. It exploits GNN structural biases to select attack nodes without model parameters or predictions, then corrects importance scores to improve misclassification.
- 1 Introduction: The proposed setup restricts attackers to a subset of accessible nodes and a small attack budget, without access to model parameters or predictions.This targets realistic settings such as attackers controlling only a few non-celebrity accounts.
- 1 Introduction: The attack uses GNN structural inductive biases as information for node selection under black-box constraints.The method focuses on selecting nodes first, then altering their attributes or edges under a per-node budget.
- 1 Introduction: Gradient-based white-box attacks are generalized through a PageRank-like importance score derived from the connection between GNN backward propagation and random walks.The resulting score can identify influential nodes without querying model parameters or predictions.
- 1 Introduction: The paper finds that importance-score attacks substantially increase classification loss but do not similarly increase misclassification, motivating a greedy correction for diminishing returns.The correction explicitly accounts for the misclassification-rate pattern as more nodes are attacked.
- 1 Introduction: Experiments on three benchmark datasets and popular GNN models empirically verify the effectiveness of the proposed practical attack method.The contribution list identifies empirical verification across three benchmark datasets.
2 Related Work
Related work studies graph adversarial attacks across tasks, attack timing, target structures, and attacker knowledge. This paper adds a local node-access constraint and formally uses exposed graph structure for attacks without model queries.
- 2 Related Work: Existing graph attacks span node-level and graph-level classification, poisoning and evasion settings, and perturbations to node features or graph edges.The paper focuses on node-level classification.
- 2 Related Work: Prior work is categorized by attacker knowledge into white-box, black-box, and intermediate settings involving different access to models, data, labels, or queries.The supplied passage introduces this knowledge-based categorization but does not enumerate all categories fully.
- 2 Related Work: This work imposes a local access constraint that prohibits perturbing top nodes and limits the number of nodes that can be changed.The constraint is presented as more realistic for practical attacks.
- 2 Related Work: GNN structural inductive biases arise from graph structure and weight sharing, and prior theory relates GNN behavior to Weisfeiler-Lehman tests or random walks.The paper examines these biases for their negative security implications rather than only their architectural benefits.
- 2 Related Work: Unlike query-based strategies that learn graph edits through trial-and-error interaction, the paper formally connects structural properties to attack strategies without model queries.The approach treats exposed graph structure as an attack information source.
3 Principled Black-Box Attack Strategies with Limited Node Access
The paper derives black-box node-selection strategies from GNN structure and random walks under limited access, then corrects their loss-based importance scores for diminishing returns in mis-classification.
- 3.2 White-Box Adversarial Attacks with Limited Node Access: The attack setup limits the attacker to selecting at most r nodes, with attacked nodes constrained to degree at most m and perturbed by a fixed feature-noise vector.The analysis focuses on node selection rather than optimizing the perturbation itself.
- 3.2 White-Box Adversarial Attacks with Limited Node Access: For an L-layer GCN, the expected first-order loss change from perturbing node i is related to the sum of the i-th column of the L-step random-walk transition matrix.This connection follows under the stated label-distribution and model assumptions.
- 3.3 Adaptation from the White-Box Setup to the Black-Box Setup: The black-box strategy RWCS ranks accessible nodes by I_i = sum_j[M^L]_{ji}, a random-walk column-sum importance score similar to PageRank.Unlike PageRank, RWCS uses the finite L-step transition matrix rather than a stationary random walk with restart.
- 3.3 Adaptation from the White-Box Setup to the Black-Box Setup: RWCS significantly increases classification loss, but its mis-classification gains diminish as perturbation strength becomes larger or more nodes are added.The paper identifies this as a discrepancy between loss and mis-classification rate.
- 3.4 Diminishing-Return of Mis-classification Rate and its Correction: Because the mis-classification-rate function is approximately submodular, the paper adds two greedy correction steps to RWCS for iterative node selection.The approximately submodular structure motivates a constant-approximation greedy procedure.
4 Experiments
Experiments evaluate restricted black-box attacks on three citation networks and show that GC-RWCS most effectively reduces node-classification accuracy. The results also expose a divergence between increasing classification loss and saturated mis-classification rates.
- Experiment setup: The evaluation uses 40 random dataset splits and compares Degree, Betweenness, and PageRank centrality baselines under restricted node access.The attack budget is fixed at 1% of each graph, with perturbations designed using limited global feature-gradient information.
- Verifying the discrepancy between loss and mis-classification rate: RWCS increases classification loss nearly linearly with perturbation strength, but its accuracy decrease quickly saturates as λ grows.GC-RWCS decreases accuracy most as λ increases despite increasing classification loss the least.
- Full experiment results: GC-RWCS achieves the best attack performance in almost all settings, significantly outperforming the second-best strategy in nearly every case.The comparison covers GCN, JKNetConcat, and JKNetMaxpool across Citeseer, Cora, and Pubmed.
- Full experiment results: 70%: GC-RWCS achieves a 70% larger accuracy decrease than the Random baseline in most cases.The table caption states that lower accuracy indicates stronger attacks and that results average 40 independent trials.
5 Conclusion
The paper introduces a highly restricted black-box attack setting and uses GCN–random-walk connections to design GC-RWCS. Experiments show that GC-RWCS significantly outperforms competing strategies under the same constraints.
- 5 Conclusion: GC-RWCS corrects the diminishing-return effect of mis-classification rate and significantly outperforms competing attack strategies under the same restricted setup.The strategy is based on theoretical analysis connecting GCNs and random walks.
- 5 Conclusion: The proposed setup restricts attackers to limited node access, yet GNN structural inductive biases still make models vulnerable to black-box attacks.The conclusion characterizes this as a highly restricted and realistic setting.
Broader Impact
The paper highlights both security risks and defensive value arising from attacks that use only graph structure. It warns that graph-based platforms may be exposed while arguing that transparency can support detection and defense.
- Broader Impact: Graph structure alone can enable executable attacks without access to model-training information, raising accountability concerns for graph-based machine learning.The stated concern is especially relevant to applications on real-world social networks.
- Broader Impact: The demonstrated attack capability alerts technology companies that graph-based platforms may be vulnerable, while transparency may help practitioners detect and defend against it.The passage frames this as a potential negative impact and a basis for better defenses.
A.1 Proof of Proposition 1
The proof derives gradients of the loss with respect to node features and connects GCN computation to random walks under an explicit path-activation assumption. This establishes the analytical basis for the importance-based attack strategy.
- A.1 Proof of Proposition 1: Under the stated assumption that computation-graph paths activate independently with probability ρ, an L-layer averaging GCN is linked to random-walk behavior.The assumption and lemma are attributed to Xu et al.; W_l denotes the learnable parameters at layer l.
- A.1 Proof of Proposition 1: The proof starts by differentiating the loss with respect to the feature vector X_i of node i.The logits are H=f(X), and H_j and y_j denote the output and true label for node j.
- A.1 Proof of Proposition 1: The derivation substitutes the random-walk relationship into the node-feature perturbation expression to obtain the importance-related quantity used in the analysis.The proof evaluates the perturbation term at the node-specific attack transformation and then simplifies it using constants independent of the node index.
- A.1 Proof of Proposition 1: The loss-gradient components distinguish correct predictions from misclassified predictions through class-dependent cases for the output derivative.The cases assign different values depending on whether the predicted class matches the true label.
A.2 Proofs for the Results in Section 3.4
The proofs establish submodularity properties for vulnerable-node coverage functions, including reductions to singleton vulnerable sets and maximum coverage.
- A constructive procedure forms each basic vulnerable set by retaining nonempty minimal vulnerable subsets, and the proof establishes its uniqueness.
- The proof shows that when each basic vulnerable set is empty or contains only singleton sets, the resulting function h is submodular.
- For nonempty vulnerable sets, gi(S)=1 exactly when Bi is empty or contains a subset of S, linking vulnerability to basic vulnerable sets.
- Maximizing h under a cardinality limit becomes a maximum coverage problem when the number of nodes with empty vulnerable sets is constant.
- Nodes with empty vulnerable sets can be removed without affecting the relevant vulnerable functions or proofs.
- The general proof replaces vulnerable sets with singleton-based sets, yielding a submodular approximation that matches the original function on sets of size at most one.
B.1 Additional Dataset Details
The experiments use the Deep Graph Library versions of Cora, Citeseer, and Pubmed, with dataset statistics summarized in Table 2.
- Experiments use the Deep Graph Library versions of Cora, Citeseer, and Pubmed.
- Table 2 summarizes the datasets’ statistics, excluding self-loops from the reported edge counts.
B.2 Additional Experiment Results
Additional experiments show that GC-RWCS remains effective across baselines, perturbation settings, model architectures, and synthetic data, while mis-classification exhibits diminishing returns as perturbations increase.
- GC-RWCS decreases node-classification accuracy by up to 33.5% and achieves a 70% larger decrease than Random in most cases.
- GC-RWCS performance varies by typically within 2% across L values from 3 to 7, indicating limited sensitivity to this hyper-parameter.
- The attack strategy generalizes from GCN to GAT, with additional results reported for GAT models.
- GC-RWCS performs well on two synthetic datasets with N = 3000 nodes and D = 10 features, assuming attackers know some important features.
- Increasing the number of perturbed features J produces a diminishing-return effect on the mis-classification rate.