PaperlayerView exact revision on arXiv

Source-linked AI summary

TDGIA:Effective Injection Attacks on Graph Neural Networks

Xu Zou, Qinkai Zheng, Yuxiao Dong, Xinyu Guan, Evgeny Kharlamov, Jialiang Lu, Jie Tang

arXiv:2106.06663v2cs.LGcs.CR

TL;DR

Graph injection attacks target a realistic constraint: adversaries add nodes rather than changing existing graph data, often in black-box, inference-only settings. TDGIA combines topology-based edge selection with smooth feature optimization; it reports a 118% increase in damage over the best KDD-CUP 2020 attack. Its stated scope centers on first-level neighborhood information.

  • Problem

    Graph injection attacks must fool GNNs without modifying existing graph links or attributes, under black-box and inference-stage constraints that make edge selection and feature generation challenging.

    Source: §1 · p. 1

  • Method

    TDGIA analyzes GNN topological vulnerability, selects existing attachment nodes through topological defective edges, and uses smooth optimization to generate injected-node features.

    Source: §1 · p. 2

  • Results

    8.08% damage versus 3.7% for the best KDD-CUP 2020 attack (u1234) is a 118% increase, using injected nodes equal to 1% of target nodes.

    Source: §1 · p. 2

  • Takeaways & Limitations

    TDGIA achieves the best attack performance among the compared baselines across varied defense GNNs, including the KDD-CUP 2020 champion, with only a few injected nodes.

    Source: §7 · p. 9

    The paper focuses on first-level graph neighborhoods and leaves higher-level neighborhood information for future attack designs.

    Source: §7 · p. 9

Abstract

from arXiv · show

Graph Neural Networks (GNNs) have achieved promising performance in various real-world applications. However, recent studies have shown that GNNs are vulnerable to adversarial attacks. In this paper, we study a recently-introduced realistic attack scenario on graphs -- graph injection attack (GIA). In the GIA scenario, the adversary is not able to modify the existing link structure and node attributes of the input graph, instead the attack is performed by injecting adversarial nodes into it. We present an analysis on the topological vulnerability of GNNs under GIA setting, based on which we propose the Topological Defective Graph Injection Attack (TDGIA) for effective injection attacks. TDGIA first introduces the topological defective edge selection strategy to choose the original nodes for connecting with the injected ones. It then designs the smooth feature optimization objective to generate the features for the injected nodes. Extensive experiments on large-scale datasets show that TDGIA can consistently and significantly outperform various attack baselines in attacking dozens of defense GNN models. Notably, the performance drop on target GNNs resultant from TDGIA is more than double the damage brought by the best attack solution among hundreds of submissions on KDD-CUP 2020.

1 INTRODUCTION

Graph injection attacks address settings where an adversary can add nodes and links but cannot alter existing graph data, a more practical constraint than graph modification. TDGIA selects existing nodes for attachment and optimizes injected-node features, and it substantially outperforms the best KDD-CUP 2020 attack in the reported comparison.

1 INTRODUCTION

  • GIA injects new nodes and links rather than modifying existing data, which can be difficult to change in real settings such as citation graphs.The introduction identifies fake-paper publication as one way to inject nodes into a citation graph.Source: §1 · p. 1
  • Black-box, inference-stage GIA poses two challenges: selecting connections to existing nodes and generating injected-node features from scratch.The paper notes that prior competition attacks produced relatively limited performance drops and no principled models emerged.Source: §1 · p. 1
  • TDGIA uses topological defective edge selection to identify helpful original nodes, then smooth adversarial optimization to generate injected-node features.The method injects nodes sequentially around selected nodes and optimizes features to reduce target-model performance.Source: §1 · p. 2, TDGIA · p. 2
  • TDGIA uses evasion rather than poison attacks, scales to large graphs beyond NIPA, consumes topology more generally than AFGSM, and is tested against top KDD-CUP 2020 defenses.The paper contrasts those evaluations with earlier attacks tested only on weaker defenses such as raw GCN.Source: §1 · p. 2
  • 8.08% damage versus 3.7% for the best KDD-CUP 2020 attack (u1234) is a 118% increase, with TDGIA injecting only 1% of target nodes.The paper also reports consistent outperformance over baselines and says ablations support both TDGIA modules.Source: §1 · p. 2, Figure 1 · p. 2

2 RELATED WORKS

Prior graph-adversarial work includes attacks that modify graph structure or attributes, while graph injection instead adds vicious nodes. Earlier injection methods NIPA and AFGSM use poison settings, requiring model retraining after injection.

Adversarial Attacks on Neural Networks

  • Earlier neural-network adversarial examples used delicate image perturbations to alter predictions, with FGSM among the subsequent attack methods [8].The cited overview also notes adversarial attacks in NLP and speech recognition,.Source: §2 · p. 3

Adversarial Attacks on GNNs

  • Graph-modification attacks include reinforcement-learning structure changes, Nettack’s constrained edge-and-feature perturbations, and Meta-attack’s small-scale poison changes [26].Nettack uses a greedy approximation, while Meta-attack uses meta-learning.Source: §2 · p. 3

Graph Injection Attacks

  • NIPA uses reinforcement learning for graph injection, while AFGSM [19] linearizes the model approximately to generate perturbations efficiently; both use poison settings requiring retraining.The passage distinguishes these methods from inference-stage evasion attacks.Source: §2 · p. 3

KDD-CUP 2020 Graph Adversarial Attack & Defense

  • KDD-CUP 2020’s graph attack track used black-box evasion: attackers could inject at most 500 nodes into a citation network with over 600,000 nodes and millions of links.The competition received hundreds of attack and defense submissions.Source: §2 · p. 3

Graph Injection Attacks

  • Evasion injection occurs only during inference, unlike poison attacks that retrain the target model on the attacked graph.The paper identifies this inference-only setting with the KDD-CUP 2020 track.Source: §2 · p. 3

3 PROBLEM DEFINITION

The section distinguishes graph modification, which changes existing data, from graph injection, which adds nodes while preserving the original graph. It defines the black-box and evasion setting and describes a transfer-attack process that separates edge generation from feature optimization for scalability.

3 PROBLEM DEFINITION

  • Graph modification attack (GMA) minimizes correct target-node predictions by changing the original graph, subject to a bound on structural and feature modifications.The modification budget is intended to keep the changes slight.Source: §3 · p. 3
  • Graph injection attack (GIA) adds N_I nodes while keeping the original nodes’ edges and attributes unchanged, with budgets on injected-node count, degree, and feature norms.The construction includes injected-node adjacency, links between original and injected nodes, and injected-node features.Source: Graph Injection Attack · p. 3

The Attack Settings of GIA

  • The paper follows black-box evasion: the attacker lacks access to the target model and attacked-node labels, and attacks only at inference rather than retraining the model.The dataset scale motivates scalable attacks relevant to larger real-world graphs.Source: Graph Injection Attack · pp. 3–4

The GIA Process

  • Because the target model is inaccessible, GIA trains a surrogate, attacks it, and transfers the attack to one or more target models.This follows transfer-attack approaches cited by the paper.Source: Graph Injection Attack · p. 4
  • For large-scale graphs, GIA separates generation of links between original and injected nodes from optimization of injected-node features, reducing complexity.The paper focuses on GNNs as target models, following community convention [19] [26].Source: Graph Injection Attack · p. 4

4 GNNS UNDER GRAPH INJECTION ATTACK

This section analyzes GNN vulnerability under graph injection attacks and shows that permutation-invariant models that use graph structure are attackable.

4.1 The Vulnerability of GNNs under GIA

  • GIA-attackable means a node’s prediction can change after nodes are injected; every permutation-invariant, non-structural-ignorant model has this property.Non-structural-ignorant models can give different predictions when graph structure changes despite identical node features.Source: §4.1 · p. 4

4.2 Topological Vulnerability of GNN Layers

  • A GNN layer aggregates information from t-hop neighbors, so injection can alter those neighborhoods and perturb the target node’s embedding.The analysis treats the aggregation as a weighted average and describes t-hop injection as a way to exploit this topological vulnerability.Source: §4.2 · pp. 4–5

5 THE TDGIA FRAMEWORK

TDGIA uses topological vulnerability analysis to guide graph injection attacks. It selects where to connect injected nodes, optimizes their features, and carries out the attack in sequential batches.

5 THE TDGIA FRAMEWORK

  • TDGIA combines topological defective edge selection with smooth adversarial optimization to inject nodes and learn their features for attacking GNNs.Its two steps select important original nodes for connections, then optimize injected-node features with a smooth loss function.Source: §5 · p. 5

5.1 Topological Defective Edge Selection

  • TDGIA links injected nodes to existing nodes with higher λv scores, which indicate greater likelihood of attack; the edge-selection strategy generalizes to multi-layer GNNs.The score combines topological vulnerability weights; the paper states that the selection strategy remains applicable to general GNNs.Source: §5.1 · p. 5

5.2 Smooth Adversarial Optimization

  • Smooth feature optimization minimizes an attack loss while avoiding gradient explosion as the probability of correct classification approaches zero.The smooth loss is used to stabilize optimization, and Smoothmap remaps features smoothly within the allowed range.Source: §5.2 · p. 6

5.3 Overall attack process of TDGIA

  • TDGIA injects nodes in batches, selecting edges and optimizing features at each step, using a surrogate model under the black-box setting.The stated overall complexity is O(ΔSBT), where ΔS is optimization epochs and B is the number of sequential-injection batches.Source: §5.3 · p. 6

6 EXPERIMENTS

Experiments evaluate TDGIA on large citation and social datasets against established GNN defenses, measuring weighted accuracy reduction and transferability. TDGIA outperforms baseline attacks on KDD-CUP and generalizes to Reddit and ogbn-arxiv; ablations examine its edge selection, optimization, surrogate model, and injection scale.

6.1 Basic Settings

  • The experiments use KDD-CUP, ogbn-arxiv, and Reddit, with budgets of 500 injected nodes and degree 100 per dataset.Weighted average accuracy weights more robust defenses more heavily; average accuracy and Top-3 defense average are also reported.Source: §6.1 · p. 7

6.2 Attack & Defense Settings

  • For black-box transfer attacks, the experiments use a GCN with LayerNorm as the surrogate and evaluate injected nodes on fixed defense models.The defense sets comprise 12 KDD-CUP submissions and seven representative models for Reddit and ogbn-arxiv.Source: §6.2 · p. 7

6.3 Performance of TDGIA

  • More than 8% weighted average accuracy reduction on KDD-CUP defenses: TDGIA significantly outperforms all baselines across 12 submissions.On Reddit and ogbn-arxiv, it also leads in weighted average accuracy reduction against seven representative defense models.Source: §6.3 · p. 7, Table 4 · p. 8, Table 5 · p. 8

6.4 Ablation Studies

  • Topological defective edge selection almost doubles weighted accuracy reduction versus uniform or random edge selection.Figure 3 compares edge-selection methods under smooth adversarial optimization on KDD-CUP.Source: §6.4 · p. 8, Figure 3 · p. 8
  • Smooth adversarial optimization prevents gradient explosion and vanishing and improves the attack performance of FGSM, AFGSM, and TDGIA.Figure 3 compares smooth optimization with inverse KL-divergence minimization on KDD-CUP.Source: Smooth Adversarial Optimization · p. 8, Figure 3 · p. 8
  • TDGIA transfers to all listed defense GNNs across KDD-CUP and ogbn-arxiv, with GCN the best surrogate and RobustGCN the most robust defense.The proposed explanation for GCN's transferability is that many GNN variants are designed based on GCN.Source: Smooth Adversarial Optimization · pp. 8–9, Figure 4 · p. 8, Figure 5 · p. 9
  • At every tested injection magnitude, TDGIA exceeds FGSM by more than 10% in weighted average accuracy reduction on ogbn-arxiv and KDD-CUP.With 2,000 injected nodes, several defenses' accuracy falls below 10%; this is under 5% of target nodes and 1.4% of ogbn-arxiv or 0.4% of KDD-CUP graph size.Source: Smooth Adversarial Optimization · p. 9, Figure 6 · p. 9

7 CONCLUSION

TDGIA combines topological defective edge selection with smooth adversarial feature optimization and achieves the best attack performance among the compared methods. The conclusion also identifies first-level neighborhood focus as a scope boundary and points to future work using higher-level information.

7 CONCLUSION

  • TDGIA combines topological defective edge selection with smooth adversarial optimization to attack a variety of defense GNNs, including under black-box and evasion settings.The paper reports that it achieves the best attack performance compared with various baselines, including the KDD-CUP 2020 champion solution.Source: §7 · p. 9
  • The attack design mainly uses first-level neighborhood information; the authors identify higher-level neighborhood information as future work.The authors also report that GCN as the surrogate model achieves the best results among the GNN variants.Source: §7 · p. 9
  • The authors report continuing their graph-robustness research with the Graph Robustness Benchmark, published at NeurIPS 2021.They also created a website for attack and defense submissions.Source: §7 · p. 9

A APPENDIX

The appendix follows the citation index used in the main article.

A APPENDIX

  • The appendix follows the citation index used in the main article.This note states the appendix's citation-numbering convention.Source: A APPENDIX · p. 11

A.1 Reproducibility Details

The appendix records the training, attack, and evaluation setup for TDGIA, along with details of the datasets and defense models. It specifies surrogate-model training and describes several model configurations used in the experiments.

A.1 Reproducibility Details

  • The appendix introduces the experimental details and gives an input transformation through a two-layer fully connected network with hidden size 128, followed by 10 propagation steps.The provided passage does not identify the model associated with this transformation.Source: §A.1 · p. 11
  • Surrogate and defense models were trained separately using different random seeds; models used Adam, a 0.001 learning rate, and 0.1 dropout for 10,000 epochs.The selected final model had the highest validation accuracy, checked every 20 epochs; KDD-CUP evaluations used submitted candidate models and parameters directly.Source: §A.1 · p. 11
  • The defense-model descriptions include SGCN with two SGC layers, k=4, and LayerNorm, and TAGCN with three hidden layers and propagation factor k=3.SGCN uses an initial transformation to 140 dimensions and layer channels of 120 and 100; TAGCN uses 128 channels per hidden layer.Source: §A.1 · p. 11
  • The described GraphSAGE model has four 70-dimensional hidden layers and aggregates neighborhoods using the L2 norm of neighborhood features.The passage describes the selected configuration as a representative GraphSAGE method.Source: §A.1 · p. 11
  • RobustGCN is described as encoding node-representation means and variation using random feature perturbations, with three 150-dimensional hidden layers.GIN is described as aggregating self-connected and neighborhood features with different weights, using four 144-dimensional hidden layers.Source: §A.1 · p. 11
  • TDGIA used batch-based smooth adversarial optimization, adding batches equal to 20% of the injection budget and optimizing each for 2,000 epochs.The passage also gives settings for r_in, λ_v, k1, k2, α, Adam learning rate, and feature initialization.Source: §A.1 · p. 11
  • The appendix specifies evaluation weight vectors for KDD-CUP and for ogbn-arxiv and Reddit, and notes that Figure 6 uses the same models and weights as ogbn-arxiv.It also reports transforming Reddit dimensions 0 and 1 with f(x)=0.025 × log(x), and using 1,157,799 unique bidirectional links for ogbn-arxiv after removing duplicates.Source: §A.1 · p. 11

A.2 Generalizing Topological Properties of Single-Layer GNN to Multi-Layer GNNs

The appendix extends the topological perturbation analysis from single-layer to multi-layer GNNs. It concludes that the perturbation depends on edge-weight changes across layers, allowing the topological defective edge selection strategy to generalize.

A.2 Generalizing Topological Properties of Single-Layer GNN to Multi-Layer GNNs

  • For multi-layer GNNs, the perturbation depends only on edge-weight changes across layers, which generalizes topological defective edge selection to these models.The passage states this result for GIA, assuming Δw_u,t is small and the weights for nodes outside G are zero.Source: §A.2 · pp. 11–12
  • The single-layer analysis likewise finds that the perturbation depends only on edge-weight changes across layers.This result is presented as the basis for extending the argument to multi-layer GNNs.Source: §A.2 · p. 11
  • The multi-layer result is derived by induction, using an expression for the perturbation at layer k in terms of the previous layer's p function.The passage states that the expression holds at k=1 and is extended to k=n+1.Source: §A.2 · pp. 11–12

A.3 Proof of Lemma 4.1

The proof assumes a model distinguishes graphs with identical features but different structures, then constructs injected graphs that are equivalent under permutation. This contradicts the assumed non-attackability and establishes that the model is GIA-attackable.

A.3 Proof of Lemma 4.1

  • Assuming M is non-structural-ignorant, the proof takes graphs with the same features but different adjacency matrices that produce different model outputs.Source: §A.3 · p. 12
  • The proof injects nodes with the same features into the two graphs in different ways.Source: §A.3 · p. 12
  • Because M is permutation invariant, the resulting injected graphs have equal outputs, contradicting the assumed difference and establishing that M is GIA-attackable.Source: §A.3 · p. 12

Related papers

Loading 2106.06663v2…