Research map / Adversarial robustness and security / Attacks on text and graphs

Adversarial Robust Generalization of Graph Neural Networks

ICML 2025 · Adversarial robustness and security › Attacks on text and graphs · approach: Graph neural network robustness

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Derives a high-probability adversarial generalization bound for general GNNs in transductive node classification via covering numbers, instantiates it for GCN, APPNP and GCNII, and checks the architecture-dependent factors empirically with an adversarial training algorithm.

Problem

Adversarial generalization of GNNs for node classification is poorly understood theoretically, because message passing couples perturbations across nodes and transductive settings break standard inductive analyses.

Approach

Bounds the covering number of the adversarial loss class by covering the perturbation set and then bounding the covering number of the perturbed GNN class over the entire perturbed feature matrix, yielding a GNN-architecture-dependent transductive adversarial generalization gap.

Key results

• Generalization gap of GCN increases with depth L on Cora, while GCNII shows a slowly decreasing gap as depth grows, consistent with the theory.
• Normalized graph filters (symmetric and random-walk) yield smaller adversarial generalization gaps than the unnormalized filter A+I.
• GCNII and APPNP show smaller generalization gaps than GCN; larger APPNP gamma and GCNII alpha reduce the gap, and weight norm regularization reduces it.

Measured effects reported in the paper

Limitations

• Analysis covers only feature perturbations (L-infinity), not structural/topology attacks, which are deferred to future work.
• Generalization gap is approximated by an accuracy gap rather than the theoretical quantity directly.
• Bound depends on assumptions such as bounded weights and Lipschitz activations, and the bound is not evaluated numerically.

Experimental setup

Datasets: Citeseer Cora Pubmed DBLP CS CoraFull

Benchmarks: Citeseer Cora Pubmed DBLP CS CoraFull

Metrics: generalization gap (adversarial train accuracy minus adversa

Baselines: GCN APPNP GCNII

Builds on: Rademacher complexity transductive bounds (Tang & Liu 2023) covering number adversarial generalization (Mustafa et al. 2022) PGD adversarial training

Closest papers by meaning

• Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks (ICLR 2024 · similarity 0.91)
• If You Want to Be Robust, Be Wary of Initialization (NeurIPS 2024 · similarity 0.90)
• Generalization of Graph Neural Networks Is Robust to Model Mismatch (AAAI 2025 · similarity 0.89)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.89)
• A Simple and Yet Fairly Effective Defense for Graph Neural Networks (AAAI 2024 · similarity 0.89)
• Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations (CVPR 2025 · similarity 0.89)