PaperlayerView exact revision on arXiv

Source-linked AI summary

Single Node Injection Attack against Graph Neural Networks

Shuchang Tao, Qi Cao, Huawei Shen, Junjie Huang, Yunfan Wu, Xueqi Cheng

arXiv:2108.13049v2cs.LGcs.CR

TL;DR

Existing node-injection attacks may use excessive injected nodes, while a single-node test-time evasion attack faces challenges from discrete graph structure and coupled node features. The paper develops OPTI and a reusable G-NIA model; G-NIA performs comparably to OPTI, outperforms state-of-the-art methods, and is approximately 500 times faster at inference.

  • Problem

    Existing node-injection attacks overlook extremely limited settings where multiple injected nodes may be perceptible, leaving single-node test-time evasion comparatively unexplored.

    Source: §1 · pp. 1–2

  • Method

    The authors use OPTI to explore attack performance and propose G-NIA, a parametric model that jointly generates injected edges and attributes while reusing learned attack information at inference.

    Source: §1 · p. 2

  • Results

    G-NIA performs comparably to OPTI and significantly outperforms state-of-the-art methods; it is approximately 500 times faster than OPTI at inference.

    Source: §1 · p. 2, §7 · p. 9

  • Takeaways & Limitations

    The reported results confirm the feasibility of single-node injection evasion and show G-NIA balancing attack performance with inference efficiency.

    Source: §1 · p. 2, §7 · p. 9

    The authors leave open whether injected nodes are detectable by defenses and whether G-NIA works on robust GNNs.

    Source: §7 · p. 9

Abstract

from arXiv · show

Node injection attack on Graph Neural Networks (GNNs) is an emerging and practical attack scenario that the attacker injects malicious nodes rather than modifying original nodes or edges to affect the performance of GNNs. However, existing node injection attacks ignore extremely limited scenarios, namely the injected nodes might be excessive such that they may be perceptible to the target GNN. In this paper, we focus on an extremely limited scenario of single node injection evasion attack, i.e., the attacker is only allowed to inject one single node during the test phase to hurt GNN's performance. The discreteness of network structure and the coupling effect between network structure and node features bring great challenges to this extremely limited scenario. We first propose an optimization-based method to explore the performance upper bound of single node injection evasion attack. Experimental results show that 100%, 98.60%, and 94.98% nodes on three public datasets are successfully attacked even when only injecting one node with one edge, confirming the feasibility of single node injection evasion attack. However, such an optimization-based method needs to be re-optimized for each attack, which is computationally unbearable. To solve the dilemma, we further propose a Generalizable Node Injection Attack model, namely G-NIA, to improve the attack efficiency while ensuring the attack performance. Experiments are conducted across three well-known GNNs. Our proposed G-NIA significantly outperforms state-of-the-art baselines and is 500 times faster than the optimization-based method when inferring.

1 INTRODUCTION

Existing node-injection attacks may use excessive injected nodes, while changing existing graph data can require high authority; this paper studies evasion with one test-time injected node. It proposes OPTI to assess attack performance and G-NIA to reuse learned attack strategies at inference.

1 INTRODUCTION

  • The attack setting permits one malicious node at test time, avoiding the need to include malicious nodes in training or train on an unknown label.The authors describe this evasion setting as difficult to detect and low in cost.Source: §1 · pp. 1–2
  • OPTI successfully attacks 100%, 98.60%, and 94.98% of nodes across three public datasets with one injected node and one edge.The authors use these results to confirm the feasibility of single-node injection evasion attacks.Source: §1 · p. 2
  • OPTI uses Gumbel-Top-k to optimize the injected node’s continuous or discrete attributes and discrete edges, but must be re-optimized for each attack.The optimization also discards information learned in each run, hindering generalization.Source: §1 · p. 2
  • G-NIA uses a model-based framework that jointly models attributes and edges, using malicious attributes to guide edge generation and retaining attack information for inference.The study evaluates G-NIA across three GNNs and reports that it can also operate in a black-box scenario.Source: §1 · p. 2
  • On Reddit and ogbn-products, G-NIA achieves misclassification rates of 99.9% and 98.8% when injecting one node and one edge.The authors report that it significantly outperforms state-of-the-art methods across GNN models and network datasets.Source: §1 · p. 2
  • G-NIA performs comparably to OPTI while inference is approximately 500 times faster.Both methods significantly outperform state-of-the-art methods on all three datasets.Source: §1 · p. 2

2 RELATED WORK

Prior graph attacks often modify existing nodes, while node-injection work leaves gaps in handling injected attributes and extremely limited, practical evasion settings. The paper frames single-node injection evasion and proposes G-NIA to address effectiveness and efficiency together.

2.1 Adversarial Attacks on Graphs

  • Existing graph attacks modify structure or attributes, while node injection avoids changing the original graph; NIPA omits injected attributes and AFGSM is limited to GCN and continuous-attribute graphs.The paper notes a lack of methods that jointly consider injected-node attributes and structure.Source: §2.1 · p. 2

2.2 Attack in the Extremely Limited Scenario

  • The cited single-node attack changes an existing node’s attributes, which the paper says requires high authority and is difficult to apply.The authors describe a practical method for extremely limited graph attacks as still lacking.Source: §2.2 · pp. 2–3
  • The paper addresses these gaps with a single-node injection evasion setting and G-NIA, aiming to combine attack effectiveness and efficiency.Source: §2.1 · p. 2, §2.2 · p. 3

3 PRELIMINARIES

The preliminaries introduce node classification and GNN feature transformation and aggregation. The attack definition then formalizes test-time injection of one node, with constrained edges and attributes, to induce target-node misclassification.

3 PRELIMINARIES

  • Node classification assigns labels to unlabelled nodes in an attributed graph using a classifier that outputs class probabilities.The graph is described by nodes, edges, and a feature matrix.Source: §3.1 · p. 3

3.1 GNN for Node Classification

  • A typical GNN layer transforms input features and aggregates the transformed features over the graph; GCN is given as an example.Source: §3.1 · p. 3

3.2 Problem Definition

  • Single-node injection evasion aims to misclassify original target nodes by adding one node at test time without modifying original nodes or edges.The attacked GNN is trained on the original graph; the injected graph adds the malicious node, its edges, and its attributes.Source: §3.2 · p. 3
  • The injected-edge budget is constrained, and attribute values are bounded for continuous graphs or limited by maximum L0 norm for discrete graphs.Source: §3.2 · p. 3
  • Figure 2 compares misclassification rates for Clean, AFGSM, and OPTI on GCN across three datasets.Source: Figure 2 · p. 3
  • The attack relies on feature propagation, so injected attributes and edges must be generated together despite discrete edges and differing continuous or discrete attribute challenges.The paper states that no existing node-injection method handles both kinds of attributed graphs.Source: §3.2 · p. 3

4 OPTIMIZATION-BASED NODE INJECTION ATTACK

OPTI jointly optimizes an injected node’s attributes and edges through a surrogate GNN to explore the performance upper bound of single-node injection evasion. It attacks nearly all target nodes with one injected node and one edge, but requires a separate costly optimization for every attack.

4.1 Optimization-based Approach

  • OPTI initializes the malicious node’s attributes and edges as free variables, then jointly optimizes them against a surrogate GNN until convergence.Joint optimization is intended to capture the coupling between attributes and edges; Gumbel-Top-k aids optimization of discrete variables.Source: §4.1 · pp. 3–4

4.2 Attack Performance

  • 100%, 98.60%, and 94.98% of nodes are misclassified by OPTI on Reddit, ogbn-products, and Citeseer, respectively, with one injected node and one edge.OPTI significantly outperforms AFGSM on all three datasets.Source: §4.2 · p. 4
  • OPTI is case-by-case: each attack requires a distinct, computationally expensive optimization, with no learned knowledge saved for reuse.Source: §4.2 · p. 4

5 GENERALIZABLE NODE INJECTION ATTACK

G-NIA replaces per-attack optimization with a reusable model intended to retain OPTI’s attack performance while generalizing to unseen nodes. It generates malicious attributes and edges jointly, using target and class representations to guide the attack.

5.1 Generalization in Graph Adversarial Attack

  • G-NIA models the optimization process parametrically so learned knowledge can be saved and reused on unseen test nodes, assuming they follow an independent and identical distribution.Its stated generalization criterion includes both test-time performance and efficiency.Source: §5.1 · p. 4, §5.2 · p. 4

5.2 Framework of Generalizable Node Injection Attack Model

  • The framework has attribute generation, edge generation, and optimization components; at inference, it generates attributes and edges before attacking target nodes with the resulting graph.Source: §5.2 · p. 4

5.3 Attribute Generation

  • Attribute generation uses target-node representations and representations of the true and likely misclassified classes to produce the injected node’s attributes.The class representations come from the surrogate GNN’s feature-transformation weights.Source: §5.3 · p. 5
  • G-NIA supports high-dimensional attribute generation for both discrete and continuous graphs, whereas AFGSM handles only discrete attributes and NIPA cannot generate attributes.Source: §5.3 · p. 5

5.4 Edge Generation

  • Edge generation scores candidate nodes within the target nodes and their first-order neighborhoods, then selects up to the injected-edge budget.This candidate scope places selected nodes at least two hops from the targets.Source: §5.4 · p. 5

5.4.1 Jointly modeling.

  • G-NIA uses generated malicious attributes, alongside target and class representations, to score candidate edges and jointly model injected attributes and edges.Gumbel-Top-k discretizes the edge scores; the method also applies it to high-dimensional discrete attributes without affecting training stability.Source: §5.4.1 · p. 5

5.5 Optimization

  • The generated adversarial graph is evaluated with a surrogate GNN, and its attack loss guides training through iterative gradient descent until convergence.Source: §5.5 · p. 6

6 EXPERIMENTS

Experiments evaluate G-NIA on social, co-purchasing, and citation networks, using three GNNs and single- or multiple-target attack settings. The study compares it with random, heuristic, and state-of-the-art attack baselines.

6.1.1 Datasets.

  • Reddit and ogbn-products experiments use largest connected components of random 12k- and 55k-node subgraphs, respectively; Citeseer also uses its largest connected component.Reddit has continuous word-vector attributes; ogbn-products has continuous product-description vectors; Citeseer has discrete bag-of-words attributes.Source: §6.1.1 · p. 6

6.1.2 Baseline Methods.

  • The baselines include Random, MostAttr, PrefEdge, NIPA, and AFGSM, with AFGSM described as outperforming Nettack and Metattack in prior results.MostAttr samples attributes from the class most likely to be misclassified; PrefEdge uses preferential attachment, and NIPA is adapted from poisoning to evasion.Source: §6.1.2 · p. 6

6.1.3 Experimental Configuration.

  • Experiments cover GCN, GAT, and APPNP with an 80/20 train-test split; G-NIA trains on training targets and is evaluated on test targets.For single-target attacks, the injected node is limited to one edge; multiple-target attacks use a dataset-dependent edge budget and graph-consistent attributes.Source: §6.1.3 · pp. 6–7

6.2 Performance of Single Target Attack

In single-target attacks, G-NIA matches or exceeds the baselines across three datasets and three GNNs, with near-total misclassification on continuous-attribute graphs. Its performance on discrete Citeseer varies by model and setup.

6.2 Performance of Single Target Attack

  • With one injected node and one edge, the single-target experiments compare G-NIA with heuristic and state-of-the-art baselines across three benchmark datasets and three GNNs.The clean-graph misclassification rate is included as a lower bound.Source: §6.2 · p. 7
  • AFGSM performs best among the baselines, while NIPA performs well on continuous-attribute graphs but is similar to Random on discrete Citeseer after attribute discretization.The authors attribute the Citeseer difference from NIPA's original paper to discretizing attributes to avoid outliers.Source: §6.2 · p. 7
  • G-NIA outperforms or matches the state-of-the-art baseline on all datasets across GCN, GAT, and APPNP.It performs especially strongly on continuous-attribute graphs; on Citeseer it beats AFGSM for GCN and GAT but ties it for APPNP.Source: §6.2 · p. 7
  • 99.90% and 98.76% misclassification rates on Reddit and ogbn-products, respectively, were achieved by G-NIA on GCN.For GAT and APPNP, G-NIA's misclassification rate exceeds 91%.Source: §6.2 · p. 7
  • 100%, 98.60%, and 86.97% misclassification rates on Reddit, ogbn-products, and Citeseer, respectively, were achieved by OPTI on GCN in this setting.G-NIA performs comparably to OPTI on all three datasets without per-attack re-optimization.Source: §6.2 · p. 7

6.3 Performance of Multiple Targets Attack

In multiple-target attacks, G-NIA misclassifies most target nodes on Reddit and ogbn-products and outperforms all baselines on all three datasets. Citeseer remains more difficult to attack than the continuous-attribute graphs.

6.3 Performance of Multiple Targets Attack

  • Each multiple-target group contains three targets within at most two hops, and the attacker must misclassify all of them using one injected node.The reported GCN evaluation uses 2,959 Reddit groups, 2,620 ogbn-products groups, and 578 Citeseer groups; OPTI is omitted due to computational cost.Source: §6.3 · pp. 7–8
  • AFGSM is the strongest baseline on all datasets, while G-NIA outperforms every baseline in the multiple-target setting.On Citeseer, several heuristic baselines and NIPA fall below Clean; the authors suggest the increased edge budget without a larger attribute budget may contribute.Source: §6.3 · p. 8
  • 92.62%, 95.42%, and 63.51% of target nodes were misclassified by G-NIA on Reddit, ogbn-products, and Citeseer, respectively.G-NIA outperforms all baselines on each dataset.Source: §6.3 · p. 8
  • The authors report that G-NIA has a substantial advantage on continuous-attribute graphs, while Citeseer remains more challenging despite G-NIA outperforming AFGSM.They note that the discrete graph's smaller attribute budget makes it more difficult to attack.Source: §6.3 · p. 8

6.4 Black-box Attack

The black-box evaluation tests whether attacks generated using a surrogate GCN transfer to unknown GNN models. G-NIA exceeds 90% misclassification on the continuous-attribute graphs, while Citeseer remains a more difficult case.

6.4 Black-box Attack

  • The black-box setup gives the attacker no access to the victim model's type, parameters, or outputs; attacks use a surrogate GCN and are evaluated on GAT and APPNP.The comparison is limited to G-NIA, AFGSM, and NIPA.Source: §6.4 · p. 8
  • Over 90% misclassification rates were achieved by G-NIA on Reddit and ogbn-products in the black-box setting, significantly outperforming all baselines.On Citeseer, AFGSM's misclassification rate is one percentage point higher than G-NIA's.Source: §6.4 · p. 8
  • The authors identify room for improvement on discrete data, despite G-NIA maintaining its advantages on continuous-attribute graphs against unknown GNN models.This reported qualification concerns the black-box setting.Source: §6.4 · p. 8

6.5 Efficiency Analysis

G-NIA cuts inference time relative to per-attack optimization, while case studies show injected-node attributes mixing with original nodes. The studies cover efficiency on Reddit and attribute visualizations on Reddit and ogbn-products.

6.5 Efficiency Analysis

  • OPTI takes about 1.17 seconds per attack, tens or hundreds of times longer than other methods because it optimizes separately for each attack.The efficiency experiment evaluates single-target attack on GCN on Reddit.Source: §6.5 · p. 8
  • For each attack, G-NIA generates the injected node’s attributes and edges in 0.00253 seconds, nearly 500 times faster than OPTI; across all test data, G-NIA takes 5 seconds versus OPTI’s 2333 seconds.Source: §6.5 · p. 8

6.6 Case Study

  • In four sampled single-target cases across Reddit and ogbn-products, injected attributes mix with original nodes; Figure 4 marks injected nodes red and original nodes blue.The authors interpret the visualizations as evidence that the injected node looks similar to existing nodes and is imperceptible and undetectable.Source: §6.6 · p. 9, Figure 4 · p. 9

6.7 Ablation Study

Ablations on Reddit show that removing attribute generation, edge generation, or joint modeling damages G-NIA's attack performance, with attribute generation most important.

6.7 Ablation Study

  • 62% misclassification rate for G-NIA w/o Joint demonstrates the importance of jointly modeling attributes and edges.The ablation replaces the attribute guidance input to edge generation with an all-zero vector.Source: Figure 5 · p. 9, §6.7 · p. 9
  • Removing attribute generation causes the worst performance, making attribute generation the most important component in the ablation.G-NIA w/o Attr replaces attribute generation with a random strategy.Source: §6.7 · p. 9
  • Removing edge generation also damages performance, with G-NIA w/o Edge losing half of the attack performance.The ablation replaces edge generation with a random strategy.Source: §6.7 · p. 9

7 CONCLUSIONS

The paper concludes that G-NIA balances attack performance and efficiency for single-node injection evasion, outperforming state-of-the-art baselines. It identifies detection and robustness as open questions.

7 CONCLUSIONS

  • Across the reported experiments, G-NIA performs comparably to OPTI while being much more efficient without re-optimization, and outperforms state-of-the-art baselines.Experiments cover GCN, GAT, and APPNP on three datasets.Source: §7 · p. 9
  • With one injected node, G-NIA attacks single-target and multiple-target tasks and can also carry out black-box attacks.Source: §7 · p. 9
  • Whether defenses can detect G-NIA's injected node and whether it works against adversarially or robustly trained GNNs remain future questions.Source: §7 · p. 9

Related papers

Loading 2108.13049v2…