Source-linked AI summary
Scalable Attack on Graph Data by Injecting Vicious Nodes
Jihong Wang, Minnan Luo, Fnu Suya, Jundong Li, Zijiang Yang, Qinghua Zheng
TL;DR
Existing GCN attacks can be hard to scale and often assume attackers can modify existing nodes, although attackers may only be able to add new ones. This paper proposes AFGSM for injection-only attacks; it reports faster execution than adapted baselines without sacrificing similar attack performance.
Problem
Prior GCN attacks are often computationally expensive on large graphs and assume attackers can manipulate existing nodes, motivating efficient attacks that inject vicious nodes instead.
Source: §1 · p. 2Method
AFGSM attacks by injecting vicious nodes while leaving the original graph unchanged, using an approximation strategy to generate perturbations efficiently.
Source: §1 · p. 3Results
AFGSM generates perturbations much more efficiently than adapted baseline attacks while maintaining similar attack performance.
Source: §1 · p. 3Takeaways & Limitations
GCNs remain vulnerable in the injection-only setting, and AFGSM outperforms baselines in attack effectiveness and efficiency.
Source: §6 · p. 19The reported testing boundary includes sampled Reddit subgraphs and tests performed on the authors’ machine.
Source: §5.3 · p. 16
Abstract
from arXiv · showhide
Recent studies have shown that graph convolution networks (GCNs) are vulnerable to carefully designed attacks, which aim to cause misclassification of a specific node on the graph with unnoticeable perturbations. However, a vast majority of existing works cannot handle large-scale graphs because of their high time complexity. Additionally, existing works mainly focus on manipulating existing nodes on the graph, while in practice, attackers usually do not have the privilege to modify information of existing nodes. In this paper, we develop a more scalable framework named Approximate Fast Gradient Sign Method (AFGSM) which considers a more practical attack scenario where adversaries can only inject new vicious nodes to the graph while having no control over the original graph. Methodologically, we provide an approximation strategy to linearize the model we attack and then derive an approximate closed-from solution with a lower time cost. To have a fair comparison with existing attack methods that manipulate the original graph, we adapt them to the new attack scenario by injecting vicious nodes. Empirical experimental results show that our proposed attack method can significantly reduce the classification accuracy of GCNs and is much faster than existing methods without jeopardizing the attack performance.
1 Introduction
Prior GCN attacks face both scalability challenges and an assumption that attackers can alter existing nodes, unlike the practical setting where attackers may only add new accounts or nodes. The paper proposes AFGSM for injection-only attacks and reports that it is faster than adapted baselines while maintaining similar attack performance.
1 Introduction
- Existing GCN attacks are difficult to scale to large graphs and commonly assume attackers can manipulate existing nodes, which may not be possible in practice.The paper frames the resulting problem as efficiently changing a specific target node’s prediction by injecting vicious nodes.Source: §1 · p. 2
- The injection-only setting poses challenges from discrete graph data, poisoning attacks that must remain effective after retraining, and the high complexity of adapted methods.The paper notes that the transductive setting can make the perturbed test input part of training, yielding a computationally expensive bi-level optimization problem.Source: §1 · pp. 2–3
- AFGSM is proposed to modify and inject vicious nodes efficiently, while the original nodes remain unchanged.Existing attacks are adapted to the injection setting as comparison baselines.Source: §1 · p. 3
- AFGSM generates perturbations much more efficiently than baseline attacks while maintaining similar attack performance, with evaluation across five benchmark datasets and three types of graph models.The tested models include two state-of-the-art graph neural networks and one unsupervised network embedding model.Source: §1 · p. 3
2 Related Work
Prior graph attacks target structural goals or graph-learning models, but most manipulate existing nodes and are not designed for vicious-node injection. This paper situates its approach against image attacks, graph attacks, and an earlier injection method.
2 Related Work
- Image-domain attacks such as FGSM, C&W, and PGD cannot be applied directly to this setting because graph data are discrete.The cited methods are discussed as developments in image adversarial attacks, not as suitable baselines here.Source: §2 · p. 4
- Earlier graph-structure attacks changed spreading, shortest paths, or PageRank, but were not designed for graph-learning algorithms.The passage cites Chaoji et al. (2012), Israeli and Wood (2002), Phillips (1993), and Csji et al. (2014).Source: §2 · p. 4
- Most graph-learning attacks manipulate existing nodes, while Sun et al. (2019) injects vicious nodes using reinforcement learning, which the paper describes as too complex for large graphs.The paper is motivated to develop an injection-specific strategy with lower computational cost.Source: §2 · pp. 4–5
3 Problem Definition
The paper defines an attributed graph and the semi-supervised GCN setting, then formulates an attack that injects nodes while leaving the original graph unchanged. Its method specifies feature and edge perturbations, an attack objective, and constraints on the injected graph.
3.1 Notation and Preliminary
- The notation treats a graph as nodes, edges, and binary node features, with labels available for only a subset of nodes.The GCN is trained by minimizing cross-entropy on labeled nodes.Source: §3.1 · p. 5
3.2 Problem Definition and Methodology
- The attack targets a specific node by injecting new vicious nodes, while perturbations are limited to their features and their edges to original or injected nodes.The original adjacency matrix and node features remain unchanged.Source: §3.2 · pp. 5–6
- The attack is formulated as bi-level optimization: retrain the GCN on the perturbed graph, then optimize the perturbation against that model.The outer variables are the injected-node connections and features, while the inner problem finds model weights on the perturbed graph.Source: §3.2 · p. 6
- The attack loss seeks a perturbed graph that assigns the target node to a new class while maximizing its distance from the ground-truth class in log-probabilities or logits.A surrogate loss is used to generate perturbations, and the paper says its simplification enables an approximate optimal solution for efficiency.Source: §3.2 · p. 6
- The constraint conditions include a sparsity budget on the number of vicious edges.The passage identifies the ℓ0-norm constraint as a widely used way to constrain perturbations.Source: §3.2 · p. 6
- Injected-node features cannot introduce feature co-occurrence pairs absent from original nodes, and each injected node’s feature count is constrained to the original-node mean.The paper uses these conditions to limit conspicuous feature patterns and unusually sparse or dense injected nodes.Source: §3.2 · pp. 6–7
4 The Proposed Framework
The framework adapts existing attacks to a node-injection setting and introduces AFGSM, which approximates the model to derive efficient closed-form choices for injected-node features and edges. Its stated complexity comparison ranks AFGSM as the most efficient of the compared methods.
4 The Proposed Framework
- The framework addresses the discrete graph optimization problem with an efficient injection-based attack and states that its algorithms can be generalized to directed graphs.AFGSM assumes that degree changes to original nodes can be ignored after injecting one vicious node in large-scale graphs.Source: §4 · p. 7, §4.2 · p. 9
4.1 Adapting Existing Methods for the New Scenario
- Nettack, FGSM, and Meta-attack are adapted by constraining perturbations to the new injection setting; existing methods can use one-time or sequential injection.Meta-attack is adjusted to target a specific node, while Nettack scores candidate edges and Meta-attack selects edges and features by meta-gradient.Source: §4.1 · pp. 7–8
4.2 Approximate Fast Gradient Sign Method (AFGSM)
- AFGSM sequentially injects vicious nodes and uses an approximation that makes the target output linear in their feature and edge variables, enabling approximate closed-form choices.The feature solution is calculated once, while the edge solution is updated as nodes are injected sequentially.Source: §4.2 · pp. 8, 9, 11
4.3 Comparison of Complexity
- AFGSM is ranked most efficient in time complexity, followed by Nettack, FGSM, and Meta-attack.The comparison states that experimental results also substantiate this complexity ordering.Source: §4.3 · p. 11
5 Experiments
The experiments evaluate attacks under different injection strategies, graph sizes, and capability restrictions. AFGSM remains effective while reducing computational cost, with performance varying by attack strategy and available perturbations.
5.1 Experimental Setup
- Experiments use five datasets, including a Reddit subgraph of nearly 150K nodes, and inject vicious nodes only into the unlabeled test set.The largest connected component is used, and target-node results are averaged over five retraining runs with different random seeds.Source: §5.1 · p. 12
5.2 Adapting Existing Methods to the New Scenario
- Under one-time injection, all attacks perform best when 100% of vicious nodes initially connect to the target, while Meta-attack performs best overall.The comparison uses a shared budget of 10 nodes and 20 edges; Meta-attack’s higher-order gradients provide more information but its complexity prevents scaling to DBLP and Pubmed.Source: Table 2 · p. 12, §5.2 · p. 13
5.3 Attack by AFGSM and its adaptive variant.
- On small graphs, adaptive retraining improves FGSM and AFGSM, whose adaptive variants approach Meta-attack; AFGSM preserves FGSM-like attack effectiveness with lower complexity.For GCN on Citeseer, AFGSM lowers accuracy from 89.2% to 22.4%, while AFGSM-ada lowers it to 10.4%.Source: §5.3 · p. 15, Table 4 · p. 15
- On large DBLP and Pubmed graphs, AFGSM performs close to FGSM, adaptive variants perform better, and Meta-attack cannot scale to graphs with 10K+ nodes.FGSM and FGSM-ada also cannot scale to graphs with more than 30K nodes; on a 150K-node Reddit subgraph, AFGSM reduces GCN accuracy, but transfer to Deepwalk is relatively low.Source: §5.3 · pp. 15–16, Table 5 · p. 17, Table 6 · p. 17
- 3,000 times higher than AFGSM, Meta-attack’s execution time on DBLP grows to a level that prevents scaling beyond 13K nodes.AFGSM’s execution time remains relatively stable as graph size grows.Source: §5.3 · p. 17
5.4 Edge-only perturbation and Indirect perturbation
- With edge-only perturbation, AFGSM still succeeds, but restricting attacks to edges significantly limits performance compared with attacks that also perturb features.Vicious nodes receive randomly sampled features in this setting.Source: §5.4 · pp. 17–18, Figure 4 · p. 18
- Indirect AFGSM still fools the victim model without direct target connections, but is much less successful than when direct connections are allowed.The study evaluates this restricted setting as AFGSM-in.Source: Figure 5 · p. 18, §5.4 · p. 19
6 Conclusion
The paper studies attacks on GCNs when adversaries can only inject vicious nodes. It proposes AFGSM and reports that GCNs remain vulnerable in this setting, with AFGSM outperforming baselines in attack effectiveness and efficiency.
6 Conclusion
- AFGSM significantly outperforms baselines in attack effectiveness and efficiency.The reported evaluation verifies that GCNs remain vulnerable under the injection-only attack setting.Source: §6 · p. 19
- The paper considers a practical attack setting in which adversaries may only inject vicious nodes into GCNs.Source: §6 · p. 19
- The paper proposes AFGSM to generate reliable adversarial perturbations efficiently.Source: §6 · p. 19