Research map / Graph learning / GNN architectures
Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks
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.
Defines expected adversarial robustness for attributed graphs, derives upper bounds for GCN/GIN under node feature attacks, and proposes GCORN (orthonormal-weight GCN) plus a stratified-sampling estimator of expected vulnerability.
Problem
Existing GNN defenses are mostly heuristic and worst-case focused, with little theory on robustness to node feature attacks; worst-case evaluation ignores attack variability and likelihood.
Approach
Define an expected (average-case) adversarial vulnerability over graph neighborhoods, bound it via the product of weight-matrix norms (Lipschitz-style plus Markov inequality), and enforce near-orthonormal weights via an iterative differentiable projection (GCORN) to reduce that bound; estimate expected robustness by uniform sampling in the feature ball.
Key results
- Under random (psi=1.0) feature attacks on Cora, GCORN reaches 57.6% attacked accuracy vs 41.7% for GCN and 53.7% for AirGNN.
- Under PGD feature attack on CiteSeer, GCORN reaches 65.6% vs 52.3% for GCN and 62.1% for ParsevalR.
- GCORN outperforms other structural defenses in 8 of 12 structural attack settings (Mettack, PGD, DICE) in the paper's comparison.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GCORN instead of the strongest listed baseline | GCN · Node classification under feature attacks: Cora, CiteSeer, PubMed, CS, OGBN-Arxiv; Random (ψ = 0.5 and ψ = 1.0) and PGD | attacked accuracy: 73.5 $\pm$ 1.9 -> 77.1 $\pm$ 1.8; 65.1 $\pm$ 0.8 -> 67.8 $\pm$ 1.4; 71.8 $\pm$ 0.8 -> 73.1 $\pm$ 1.1; 88.2 $\pm$ 0.9 -> | Helped |
| Use GCORN instead of the strongest listed baseline | GCN · Node classification under Nettack: Cora, CiteSeer, CS | attacked accuracy: 67.5 $\pm$ 2.5 -> 68.3 $\pm$ 1.4; 71.7 $\pm$ 1.4 -> 77.5 $\pm$ 2.5; 76.7 $\pm$ 1.4 -> 78.3 $\pm$ 1.4 | Helped |
| Use GCORN instead of the strongest listed baseline | GCN · Node classification under Nettack: PubMed and OGBN-Arxiv | attacked accuracy: 71.7 $\pm$ 3.8 -> 70.8 $\pm$ 1.4; 56.7 $\pm$ 1.4 -> 55.8 $\pm$ 1.4 | Hurt |
| Use GCORN instead of GCN | GCN · Structural attacks: Mettack, PGD, and DICE on Cora, CiteSeer, PubMed, and CoraML | attacked accuracy | Mixed |
| Apply orthonormalization to GCN weight matrices during training | GCN · Feature-based adversarial attacks | expected robustness | Helped |
Surprising findings
- Baseline orthonormalization via Parseval regularization can negatively affect performance, motivating the iterative projection instead.
- GCN-k underperforms plain GCN on OGBN-Arxiv under random attack (52.8% vs 68.2%).
Limitations
- The robustness bound relies on Markov inequality and sup-norm/product-of-norms bounds that may be loose.
- Structural attack results are mixed; GCORN loses to baselines on some settings (e.g., PubMed under Mettack and DICE).
- Authors note the ablation on projection order and iterations is only in the appendix and the iterative method's convergence depends on a scaling condition.
Experimental setup
Datasets: Cora CiteSeer PubMed CS OGBN-Arxiv CoraML
Benchmarks: Cora CiteSeer PubMed CS OGBN-Arxiv CoraML
Metrics: attacked classification accuracy estimated adversarial vulnerability certified accuracy
Baselines: GCN GCN-k RobustGCN AirGNN Parseval regularization GNN-Jaccard GNN-SVD GNNGuard
Builds on: GCN GIN Parseval regularization Bjorck orthonormalization
Closest papers by meaning
- Adversarial Robust Generalization of Graph Neural Networks (ICML 2025 · similarity 0.91)
- Robust Graph Neural Networks via Unbiased Aggregation (NeurIPS 2024 · similarity 0.91)
- Enhancing Graph Classification Robustness with Singular Pooling (NeurIPS 2025 · similarity 0.90)
- On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective (NeurIPS 2025 · similarity 0.90)
- If You Want to Be Robust, Be Wary of Initialization (NeurIPS 2024 · similarity 0.90)
- Refine then Classify: Robust Graph Neural Networks with Reliable Neighborhood Contrastive Refinement (AAAI 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.