PaperlayerView exact revision on arXiv

Source-linked AI summary

Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation

Binghui Wang, Jinyuan Jia, Xiaoyu Cao, Neil Zhenqiang Gong

arXiv:2008.10715v3cs.CR

TL;DR

Edge additions and deletions can fool GNNs, while prior certificates target specific models or lack tight general guarantees. This paper extends randomized smoothing to graph structure and proves tight certificates for any GNN; evaluations include 0.49 certified accuracy for Cora GCN under 15 edge edits.

  • Problem

    Structural edge additions or deletions can fool GNNs, while prior certificates either target specific GNNs or lack formally proved tight guarantees in general.

    Source: §1 · p. 1

  • Method

    The paper extends randomized smoothing to binary graph structures, derives tight perturbation certificates for any GNN, and computes them using probability bounds and optimization.

    Source: §1 · p. 1

  • Results

    The guarantee applies to node and graph classification; Cora GCN achieves certified accuracy of 0.49 when at most 15 edges are added or deleted.

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

  • Takeaways & Limitations

    The authors identify incorporating information from a given GNN as a future direction for improving the certificate.

    Source: §6 · p. 7

    The certification setting treats node features and training nodes as constants, covering structural perturbations rather than changes to those inputs.

    Source: §2.2 · p. 2

Abstract

from arXiv · show

Graph neural networks (GNNs) have recently gained much attention for node and graph classification tasks on graph-structured data. However, multiple recent works showed that an attacker can easily make GNNs predict incorrectly via perturbing the graph structure, i.e., adding or deleting edges in the graph. We aim to defend against such attacks via developing certifiably robust GNNs. Specifically, we prove the certified robustness guarantee of any GNN for both node and graph classifications against structural perturbation. Moreover, we show that our certified robustness guarantee is tight. Our results are based on a recently proposed technique called randomized smoothing, which we extend to graph data. We also empirically evaluate our method for both node and graph classifications on multiple GNNs and multiple benchmark datasets. For instance, on the Cora dataset, Graph Convolutional Network with our randomized smoothing can achieve a certified accuracy of 0.49 when the attacker can arbitrarily add/delete at most 15 edges in the graph.

1 INTRODUCTION

The paper addresses gaps in certifying GNNs against edge additions and deletions by deriving tight guarantees for any GNN and evaluating the approach on node and graph classification benchmarks.

1 INTRODUCTION

  • Prior certificates either target specific GNNs or lack formally proved tight guarantees in general.The paper frames this as a gap in certifying robustness against structural perturbations.Source: §1 · p. 1
  • The practical certification method estimates probability bounds with simultaneous confidence intervals, then solves an optimization problem for the certified perturbation size.The confidence-interval method is attributed to [21].Source: §1 · pp. 1–2
  • Cora GCN certified accuracy is 0.55, 0.50, and 0.49 at 5, 10, and 15 edge edits; MUTAG GIN reaches 0.45, 0.45, and 0.40.The evaluations cover node and graph classification benchmarks.Source: §1 · p. 2
  • The paper proves tight structural-robustness guarantees for any GNN classifier in both node and graph classification.It extends randomized smoothing to binary graph structures and derives the certificate using a novel partition of the structure space and the Neyman–Pearson Lemma [36].Source: §1 · pp. 1–2

2 BACKGROUND

The background distinguishes node-level from graph-level prediction and defines the structural attack setting, holding node features and training nodes fixed.

2.1 Node Classification vs. Graph Classification

  • Node classification predicts labels for unlabeled nodes using the graph and labeled training nodes, whereas graph classification predicts one label for the entire graph.Graph classifiers can be trained on labeled graphs.Source: §2.1 · p. 2

2.2 Adversarial Structural Perturbation

  • The structural attack setting allows edge additions or deletions while treating node features and training nodes as constants.A classifier is represented as a function of the binary graph-structure vector.Source: §2.2 · p. 2
  • The perturbation vector marks changed entries in the structure vector, and its L0 magnitude counts modified node pairs.The structure vector may encode all node-pair connections or, for a node-specific attack, that node’s connections to the others.Source: §2.2 · p. 2

3 CERTIFIED ROBUSTNESS

The section extends randomized smoothing to binary graph structures and derives certificates for how many edge changes a smoothed classifier can tolerate. It also establishes tightness and describes how to compute the certificate in practice.

3.1 Randomized Smoothing with Binary Noise

  • For each graph-structure bit, binary noise preserves its connection status with probability β and changes it with probability 1−β; the smoothed classifier predicts the most probable label across noisy inputs.The certificate concerns perturbations δ with bounded ℓ0 size and guarantees the smoothed prediction for the perturbed structure.Source: §3.1 · p. 2

3.2.1 Overview.

  • The method bounds the probability of the top label on a perturbed graph below and the runner-up label above, then searches for the largest perturbation size where the bounds preserve the ordering.It constructs regions in binary structure space to apply the Neyman-Pearson Lemma.Source: §3.2.1 · p. 3, §3.2.2 · p. 3

3.2.3 Deriving the certified perturbation size.

  • The certified perturbation size K is obtained by optimizing probability bounds, and the tightness result shows that beyond K some consistent base classifier can change its prediction or tie.The guarantee applies to any base node or graph classifier; under the stated noise distribution and without assumptions on the base classifier, no larger perturbation can be certified.Source: §3.2.3 · pp. 3–4
  • Theorem 2 establishes tightness: for perturbations larger than K, a base classifier consistent with the assumed bounds exists whose smoothed prediction changes or ties, under the theorem’s stated conditions.Those conditions require pA ≥ pB, pA + pB ≤ 1, and pA + (|C| − 1)·pB ≥ 1.Source: §3.2.3 · p. 3
  • The certificate depends on pA, pB, and β; tighter probability bounds yield a larger K, while this setting cannot certify a perturbation larger than K.The theorems apply to any base node or graph classifier and, more broadly, to any base classifier taking binary features as input.Source: §3.2.3 · p. 4

3.3 Certification in Practice

  • The practical procedure estimates probability bounds pA and pB from noisy-classifier samples with confidence at least 1−α, then solves the optimization problem for K.The samples form a multinomial distribution over labels, and the procedure iteratively finds the largest k satisfying the constraint.Source: §3.3 · p. 4

4 EVALUATION

The evaluation tests randomized smoothing across node and graph classification datasets and examines how its parameters affect certified accuracy. Results show that larger sample counts improve certified accuracy, while noise and confidence settings shape the robustness trade-offs.

4.1 Experimental Setup

  • The evaluation uses GCN and GAT on Cora, Citeseer, and Pubmed for node classification, and GIN on MUTAG, PROTEINS, and IMDB for graph classification.The node datasets are citation graphs; the graph datasets cover mutagenic compounds, proteins, and movie-genre actor networks.Source: §4.1 · p. 4, (c) IMDB · p. 5

(c) IMDB

  • Node-classification training samples 20 nodes per class and tests on 100 nodes; graph classification trains on 90% of graphs and tests on the remaining 10%.Defaults are β=0.7, confidence level 1−α=99.9%, and d=10,000; node certificates consider edges incident to the target node.Source: (c) IMDB · p. 5

4.2 Experimental Results

  • Larger β raises accuracy without attacks but makes certified accuracy fall faster as perturbation size increases; at β=0.5, certified accuracy is independent of perturbation size.At β=0.5, uniform graph sampling removes structural information, leaving the smoothed GNN to use node features.Source: §4.2 · p. 6
  • Higher confidence levels slightly lower certified accuracy by loosening probability-bound estimates and reducing certified perturbation sizes, with negligible differences once confidence is sufficiently high.Figure 4 compares smoothed GCN and GIN across confidence levels.Source: §4.2 · p. 6, Figure 4 · p. 6
  • Increasing d raises certified accuracy because tighter probability-bound estimates yield larger certified perturbation sizes.Figure 5 compares smoothed GCN and GIN across sample counts.Source: §4.2 · p. 6, Figure 5 · p. 6
  • On Cora, smoothed GCN achieves certified accuracies of 0.55, 0.50, and 0.49 against at most 5, 10, and 15 edge changes, respectively, with d=50K.On MUTAG, smoothed GIN achieves certified accuracies of 0.45, 0.45, and 0.40 at the same perturbation sizes and sample count.Source: §4.2 · p. 6

5 RELATED WORK

Prior certification methods address different model classes and perturbations, while randomized smoothing offers scalable, model-agnostic guarantees. For graph structure, earlier certificates were often restricted to particular GNNs or lacked a formal tightness proof.

5.1 Non-graph Data

  • Non-smoothing certification techniques include SAT/SMT, mixed-integer and linear programming, semidefinite programming, dual optimization, abstract interpretation, and layerwise relaxation.These methods are described as unscalable to large neural networks and/or applicable only to specific architectures.Source: §5.1 · p. 6
  • Randomized smoothing certificates for non-graph inputs include Gaussian- or Laplacian-noise guarantees, a tight L2 guarantee using the Neyman-Pearson Lemma [36], and top-k certification.The approach is described as scalable to large neural networks and applicable to any base classifier.Source: §5.1 · pp. 6–7

5.2 Graph Data

  • Prior graph certifications cover node-feature changes or structural perturbations, but structural methods were limited to specific GNNs, including PageRank-based models or GCNs.Some earlier structural certificates used dualization and convex-envelope tools for GCN graph classification.Source: §5.2 · p. 7
  • Earlier randomized smoothing work for graph structure certified community detection [22] or GNNs in sparse settings [3], but did not formally prove tightness of its multi-class certificate.The paper states its tightness proof applies to the equal-flip-probability special case of [3].Source: §5.2 · p. 7

6 CONCLUSION AND FUTURE WORK

The paper concludes that randomized smoothing for binary data yields tight structural-robustness guarantees for any GNN classifier in both node and graph classification. It identifies using information about a given GNN to improve the guarantees as future work.

6 CONCLUSION AND FUTURE WORK

  • The proposed randomized-smoothing certificate applies to any GNN classifier for node and graph classification under structural perturbation and is tight without assumptions on the GNN.The authors identify incorporating information about a given GNN to further improve the guarantee as future work.Source: §6 · p. 7

7 PROOFS

The proofs use a discrete Neyman-Pearson argument to establish a certificate, construct a classifier showing tightness, and count binary structures by their distances from clean and perturbed graphs.

7.1 Proof of Lemma 1

  • The binary Neyman-Pearson lemma compares probability mass in likelihood-ratio regions to bound how a function’s output probability changes between two distributions.For the proof, regions A and B have probabilities p_A and p_B under X, respectively.Source: §7.1 · p. 7

7.2 Proof of Theorem 1

  • Theorem 1’s certificate K is the largest perturbation size k for which the probability of Y falling in A exceeds its probability of falling in B for every perturbation δ of the specified size.This condition ensures the smoothed prediction for class c_A remains ahead of c_B.Source: §7.2 · p. 8

7.3 Proof of Theorem 2

  • The tightness proof constructs a base classifier consistent with the theorem’s probability conditions but whose smoothed classifier need not predict c_A beyond K.It partitions the remaining binary inputs into disjoint regions C_i with probability at most p_B for each other class, then assigns labels by region.Source: §7.3 · p. 8

7.4 Computing Pr(X∈R(m)) and Pr(Y∈R(m))

  • To compute region probabilities, R(w,v) groups binary vectors by their Hamming distances from s and s⊕δ; its size is derived for perturbations with ||δ||_0=k.The calculation also gives the probability of each vector in R(w,v) under X as β^(n−w)(1−β)^w.Source: §7.4 · p. 8

Related papers

Loading 2008.10715v3…