PaperlayerView exact revision on arXiv

Source-linked AI summary

Unnoticeable Backdoor Attacks on Graph Neural Networks

Enyan Dai, Minhua Lin, Xiang Zhang, Suhang Wang

arXiv:2303.01263v1cs.CRcs.LG

TL;DR

Existing graph backdoor attacks may require large poisoned-node budgets and their triggers can be detected and pruned. The paper proposes UGBA, which selects poisoned nodes and generates adaptive triggers. Experiments report stronger attacks under defenses and across multiple GNN architectures.

  • Problem

    Existing graph backdoor attacks may require many poisoned nodes for effectiveness, and their triggers can be detected and pruned.

    Source: §1 · pp. 1–2

  • Method

    UGBA deliberately selects poisoned nodes and uses an adaptive trigger generator to obtain effective, less noticeable triggers.

    Source: §1 · p. 2

  • Results

    UGBA outperforms baseline backdoor methods on large-scale datasets and achieves over 90% ASR under pruning defenses while maintaining high clean accuracy.

    Source: §6.2.1 · p. 7

  • Takeaways & Limitations

    Experiments indicate UGBA can backdoor different GNN architectures with limited attack budgets and triggers that withstand the evaluated defenses.

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

    The attacker is assumed to have access to training data but not the target GNN architecture, and poisoning is constrained by trigger-size and poisoned-node budgets.

    Source: §3.2.1 · p. 3, §4 · p. 4

Abstract

from arXiv · show

Graph Neural Networks (GNNs) have achieved promising results in various tasks such as node classification and graph classification. Recent studies find that GNNs are vulnerable to adversarial attacks. However, effective backdoor attacks on graphs are still an open problem. In particular, backdoor attack poisons the graph by attaching triggers and the target class label to a set of nodes in the training graph. The backdoored GNNs trained on the poisoned graph will then be misled to predict test nodes to target class once attached with triggers. Though there are some initial efforts in graph backdoor attacks, our empirical analysis shows that they may require a large attack budget for effective backdoor attacks and the injected triggers can be easily detected and pruned. Therefore, in this paper, we study a novel problem of unnoticeable graph backdoor attacks with limited attack budget. To fully utilize the attack budget, we propose to deliberately select the nodes to inject triggers and target class labels in the poisoning phase. An adaptive trigger generator is deployed to obtain effective triggers that are difficult to be noticed. Extensive experiments on real-world datasets against various defense strategies demonstrate the effectiveness of our proposed method in conducting effective unnoticeable backdoor attacks.

1 INTRODUCTION

GNN message passing makes graph structure central to prediction, but existing graph attacks can be costly or impractical at scale. The paper motivates limited-budget backdoors and proposes UGBA to select poisoned nodes and generate harder-to-detect triggers.

1 INTRODUCTION

  • GNNs use message passing to aggregate information from neighboring nodes, preserving node features and local graph topology for prediction tasks.The introduction names semi-supervised node classification and graph classification as examples.Source: §1 · p. 1
  • Existing graph manipulation attacks may require O(N^2) time and space and can be impractical when attackers cannot control existing nodes.They optimize edges for target nodes, whereas altering links or attributes of existing individuals may be infeasible.Source: §1 · p. 1
  • Graph backdoors poison training nodes with triggers and target labels so that triggered test nodes are predicted as the target class.The paper notes that generated triggers can be attached at inference without additional optimization.Source: §1 · pp. 1–2, Figure 1 · p. 2
  • Earlier graph backdoor methods may need many poisoned nodes and use triggers that edge pruning can detect and remove.The paper links detectability to trigger edges that do not preserve the homophily of real-world graphs.Source: §1 · p. 2
  • UGBA selects crucial representative nodes for poisoning and uses an adaptive generator to produce powerful triggers similar to target nodes.The proposed framework aims to use a limited poisoned-node budget while making triggers less noticeable.Source: §1 · p. 2

2 RELATED WORKS

The related work reviews GNN message passing and prior attacks, then distinguishes UGBA through adaptive, similarity-aware triggers and clustering-based poisoned-node selection.

2.1 Graph Neural Networks

  • GNNs recursively aggregate and combine neighboring-node features, while later work explores self-supervision, fairness, robustness, explainability, and heterophilic graphs.GCN is described as averaging neighbor and center representations before a nonlinear transformation.Source: §2.1 · p. 2

2.2 Attacks on Graph Neural Networks

  • GNN attacks include poisoning that perturbs training graphs before training [45] [46] and evasion that perturbs test-stage inputs after training [1] [3] [12] [26] [28] [33]; backdoors attach triggers and target labels to training samples, misleading trigger-embedded test samples [39].Zhang et al. [39] propose injecting randomly generated universal subgraph triggers into some training samples.Source: §2.2 · p. 2
  • UGBA differs from prior methods by generating adaptive triggers that preserve feature similarity across linked nodes and selecting poisoned nodes through clustering to reduce budget needs.The passage contrasts these aspects with prior trigger generators, node selection, and label-preserving triggers.Source: §2.2 · p. 3

3 PRELIMINARY ANALYSIS

The preliminary analysis describes the inductive node-classification threat setting and graph backdoor process, then examines why prior methods need larger budgets and remain vulnerable to pruning.

3 PRELIMINARY ANALYSIS

  • The preliminary-analysis section examines graph backdoor attacks and their unnoticeability issues.It sets up the assessment of poisoned-node budget and trigger detection developed in the subsequent subsections.Source: §3 · p. 3

3.1 Notations

  • The paper studies semi-supervised inductive node classification, where test nodes are outside the training graph.The notation section defines the attributed graph through its nodes, edges, and node attributes.Source: §3.1 · p. 3

3.2.1 Threat Model

  • The threat model assumes attackers can access training data and poison nodes within a budget, but do not know the target GNN architecture.Attackers can attach triggers to target test nodes at inference, while clean nodes should retain normal predictions.Source: §3.2.1 · p. 3

3.2.2 General Framework of Graph Backdoor Attacks

  • In the general backdoor process, training nodes receive triggers and target labels, teaching the GNN to predict triggered test nodes as the target class.The passage identifies SBA’s designed subgraphs [39] and GTA’s learned sample-specific triggers as prior approaches.Source: §3.2.2 · p. 3

3.3.2 Detection of Triggers

  • On OGB-arxiv, pruning and pruning plus label discarding sharply reduce existing attacks’ ASR while having negligible impact on clean accuracy.The defenses filter the lowest 10% of cosine-similarity edges; Table 2 reports averages over five runs.Source: Table 2 · p. 3, §3.3.2 · p. 4

3.3 Unnoticeability of Graph Backdoor Attacks

  • The analysis frames unnoticeability around poisoned-node budget and trigger detectability, arguing that large-scale graphs may require many poisoned samples.Its proposed defenses use edge pruning and label discarding to target dissimilar trigger links and associated labels.Source: §3.3 · p. 3, §3.3.2 · pp. 3–4

3.3.1 Size of Poisoned Nodes

  • Existing methods, especially SBA-Gen and SBA-Samp, perform poorly with budgets of 80 or 240 poisoned nodes on OGB-arxiv; the analysis attributes this to handcrafted triggers or random selection.GTA also selects poisoned nodes randomly, so the budget may be poorly utilized.Source: §3.3.1 · p. 3, Table 1 · p. 3

4 PROBLEM FORMULATION

The formulation targets effective graph backdoors under a poisoned-node budget, requiring selected nodes and adaptive triggers that remain difficult to detect. It specifies an inductive setting in which target nodes are unavailable during optimization.

4 PROBLEM FORMULATION

  • The formulation addresses two challenges: using a limited poisoned-sample budget effectively and generating powerful, difficult-to-detect triggers.It imposes a cosine-similarity threshold that can be tuned by dataset.Source: §4 · p. 4
  • Generated triggers should resemble poisoned or target nodes, and their internal edges should connect similar nodes to reduce vulnerability to pruning.The formulation defines cosine similarity between node features and a dataset-tunable threshold.Source: §4 · p. 4
  • The attacker learns an adaptive trigger generator and selects a budget-limited set of nodes so a trained GNN predicts triggered test nodes as the target class.The target GNN architecture is unavailable to the attacker and may use different defenses.Source: §4 · p. 4
  • In the inductive setting, target nodes are unavailable during optimization, so the candidate set is all unlabeled nodes V\V_L.A clean node prediction uses its clean computation graph, while trigger attachment produces the corresponding triggered prediction.Source: §4 · p. 4

5 METHODOLOGY

UGBA separates poisoning into representative-node selection and adaptive trigger learning, using a surrogate GCN to optimize attack effectiveness under unnoticeability constraints.

5 METHODOLOGY

  • UGBA selects representative poisoned nodes, learns adaptive triggers, and uses a surrogate GCN in a bi-level optimization framework.The framework separates node selection from trigger-generator learning because jointly optimizing them is challenging and computationally expensive.Source: §5 · p. 4

5.1 Poisoned Node Selection

  • A label-trained GCN captures node attributes and structure, then per-class clustering selects representative nodes while the score balances cluster representativeness and node degree.Top-scoring nodes are selected in each cluster to satisfy the attack budget.Source: §5.1 · p. 5

5.2 Adaptive Trigger Generator

  • An MLP generates trigger features and structure from each target node’s features, while a differentiable loss encourages high similarity between connected nodes.Generated trigger features are linked to selected poisoned nodes, which receive the target label; at inference, triggers are attached to test nodes.Source: §5.2 · p. 5

5.3 Optimization Algorithm

  • Alternating optimization uses inner surrogate-model updates with the generator fixed, then uses the updated surrogate parameters in the outer optimization.The inner iterations approximate the surrogate’s optimized parameters, and first-order approximation reduces the cost of computing generator gradients.Source: §5.3 · p. 6

6 EXPERIMENTS

UGBA is evaluated on four real-world graphs for inductive node classification, against backdoor and node-injection attacks under multiple defenses. It generally outperforms baselines, including under pruning defenses, while ablations, similarity analyses, and sensitivity tests examine its components and behavior.

6.1.1 Datasets.

  • Experiments cover Cora, Pubmed, Flickr, and OGB-arxiv, comparing UGBA with backdoor attacks, node-injection attacks, pruning defenses, and robust GNNs.The evaluation uses inductive node classification; attackers cannot access test nodes during poisoning.Source: §6.1.1 · p. 6, §6.1.2 · p. 6, §6.1.3 · p. 6

6.2.1 Comparisons with baseline backdoor attacks.

  • Under Prune and Prune+LD, UGBA achieves over 90% ASR while maintaining high clean accuracy; without defense, it outperforms baselines, especially on large-scale datasets.The reported ASR averages attacks on three GNN architectures, supporting transferability.Source: §6.2.1 · p. 7, Table 4 · p. 7

6.2.2 Comparisons with baseline node injection attacks.

  • With 160 poisoned nodes among 169K OGB-arxiv nodes, UGBA outperforms node-injection attacks by 30%.UGBA also effectively attacks robust GNNs.Source: §6.2.2 · p. 7, Table 5 · p. 7

6.3 Impacts of the Sizes of Poisoned Nodes

  • As the poisoned-node budget increases, all compared methods’ ASR rises, but UGBA consistently outperforms baselines, with wider gaps at smaller budgets.Under Prune+LD, UGBA remains promising while baselines obtain nearly 0% ASR.Source: §6.3 · p. 7, Figure 4 · p. 8

6.4 Ablation Studies

  • UGBA outperforms the random-node-selection variant across defense settings and has lower ASR variance; under Prune+LD, it also outperforms variants without the unnoticeable constraint.The authors attribute these differences to representative node selection and the constraint guiding generation of unnoticeable triggers.Source: §6.4 · p. 8

6.5 Similarity Analysis

  • UGBA’s generated trigger edges have cosine similarities that disguise them as clean edges, unlike GTA’s low-similarity trigger edges.The authors say GTA’s low similarities imply higher risk of trigger removal by their defenses.Source: §6.5 · p. 8

6.6 Parameter Sensitivity Analysis

  • For Prune+LD against GCN, the similarity threshold needs to exceed 0.2 on Pubmed and 0.8 on OGB-arxiv; with a proper threshold, high ASR is generally achieved when β ≤ 1.The authors suggest setting the threshold according to a dataset’s average edge similarity.Source: §6.6 · p. 8, Figure 6 · p. 8

7 CONCLUSION AND FUTURE WORK

The paper concludes that UGBA combines poisoned-node selection with an adaptive generator and unnoticeable constraint to conduct graph backdoor attacks with limited budgets. Its experiments demonstrate attacks on various target GNNs and under defenses; future work includes other tasks and defenses.

7 CONCLUSION AND FUTURE WORK

  • UGBA uses representative, diverse poisoned nodes and an adaptive trigger generator with an unnoticeable constraint and bi-level optimization to attack varied GNNs, including with defenses.The paper identifies extending beyond node classification and studying defenses against unnoticeable graph backdoors as future work.Source: §7 · p. 8

Algorithm 1 Algorithm of UGBA.

UGBA selects poisoned nodes, trains a trigger generator through bi-level optimization on a surrogate GCN, then attaches generated triggers to the selected nodes to form the poisoned graph.

Algorithm 1 Algorithm of UGBA.

  • UGBA selects the top-scoring poisoned nodes and assigns them the target-class label.Selection uses the node scores defined by Eq. (5).Source: A TRAINING ALGORITHM · p. 10

A TRAINING ALGORITHM

  • The trigger generator is trained on a surrogate GCN through bi-level optimization, updating lower- and upper-level models by gradient descent.The updates follow Eqs. (11) and (12).Source: A TRAINING ALGORITHM · p. 10
  • After training, the generator creates a trigger for each poisoned node and attaches it to produce the poisoned graph.Source: A TRAINING ALGORITHM · p. 10

B IMPLEMENTATION DETAILS

The implementation uses a two-layer GCN surrogate and a two-layer MLP trigger generator, with hyperparameters selected through validation-set grid search.

B IMPLEMENTATION DETAILS

  • The surrogate is a 2-layer GCN and the adaptive trigger is a 2-layer MLP, both with hidden dimension 32.The inner-iteration step N is 5; β and T are selected by validation-set grid search.Source: B IMPLEMENTATION DETAILS · p. 10

C ADDITIONAL EXPERIMENTS

On Pubmed, UGBA outperforms GBAST in attack success rate (ASR) without defense and retains high attack performance under Prune+LD.

C ADDITIONAL EXPERIMENTS

  • Under Prune+LD, UGBA still shows high attack performance, whereas GBAST cannot bypass the defense.The authors report similar observations on other datasets and target GNN models.Source: C ADDITIONAL EXPERIMENTS · p. 10
  • UGBA’s clustering-based poisoned-sample selection is contrasted with GBAST’s degree- and closeness-centrality selection.Source: C ADDITIONAL EXPERIMENTS · p. 10
  • UGBA achieves much higher ASR than GBAST without defense on Pubmed.The comparison reports ASR for GCN under different defense settings.Source: Table 6 · p. 10, C ADDITIONAL EXPERIMENTS · p. 10

D DETAILS OF COMPARED METHODS

The compared attacks differ in trigger construction and poisoned-node selection. UGBA’s attack success rate rises with trigger size, but remains stable and high at size 2.

D DETAILS OF COMPARED METHODS

E IMPACTS OF TRIGGER SIZE

  • UGBA’s ASR increases as trigger size grows, yet remains stable and high with trigger size 2 across settings on OGB-arxiv.The authors report similar observations on other datasets; the comparison covers three defense strategies.Source: Table 7 · p. 10, E IMPACTS OF TRIGGER SIZE · p. 10

F TIME COMPLEXITY ANALYSIS

UGBA’s poisoning-stage computation is linear in graph size under the stated complexity analysis. Experiments report short training time and an average of 0.0017 seconds to attack each target node at test time.

F TIME COMPLEXITY ANALYSIS

  • Poisoned-node clustering costs approximately O(Kh|V|), while each optimization iteration costs O((N+1)hd|V|).K is the number of clusters, h the embedding dimension, d the average node degree, and N the number of inner iterations.Source: F TIME COMPLEXITY ANALYSIS · pp. 10–11
  • Training time is reported as very short and increasing linearly with complexity; attacking each target node takes 0.0017 seconds on average.Models were trained for 200 epochs on an A6000 GPU with 48G memory.Source: Table 11 · p. 11, F TIME COMPLEXITY ANALYSIS · p. 11
  • UGBA can use mini-batches to further reduce per-iteration computation, and generating a test-time trigger costs O(h).Source: F TIME COMPLEXITY ANALYSIS · p. 11

Related papers

Loading 2303.01263v1…