Research map / Graph learning / GNN architectures
On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective
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.
Proposes a distribution-aware, probabilistic framework for embedding stability of graph filters and GCNNs under edge perturbations, and an attack (Prob-PGD) that maximizes expected embedding perturbation.
Problem
Existing stability analyses of graph convolutional networks consider only worst-case edge perturbations and ignore the statistics of node signals, which can be overly pessimistic for inference-time robustness.
Approach
Define embedding stability as the expected squared embedding perturbation over a signal distribution, which equals a second-moment-matrix-weighted filter perturbation norm <K, E^T E>; extend to multilayer GCNN bounds and use this objective to design a projected-gradient edge attack (Prob-PGD).
Key results
- On Cora, Prob-PGD reduces GCN accuracy to 77.88% vs 78.47% for Wst-PGD and 78.30% for Random, while inducing embedding perturbation of 106 vs 97 (Wst-PGD).
- On MUTAG, Prob-PGD reduces GCN accuracy to 42.89% vs 69.21% for Wst-PGD, with embedding perturbation 3.09 vs 1.95.
- Prob-PGD induces the largest embedding perturbation in 8 of 9 dataset-architecture cases in the downstream table.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Prob-PGD instead of the strongest listed baseline attack | pre-trained GCN · MUTAG | accuracy (%): 69.21\text{ $\pm2.37$} -> 42.89\text{ $\pm4.86$} | Helped |
| Use Prob-PGD instead of the strongest listed baseline attack | pre-trained GIN · MUTAG | accuracy (%): 70.53\text{ $\pm4.82$} -> 76.58\text{ $\pm8.02$} | Hurt |
| Use Prob-PGD instead of the strongest listed baseline attack | pre-trained SGC · MUTAG | accuracy (%): 68.16\text{ $\pm1.42$} -> 41.58\text{ $\pm3.87$} | Helped |
| Use Prob-PGD instead of the strongest listed baseline attack | pre-trained GCN · ENZYMES | accuracy (%): 52.58\text{ $\pm3.56$} -> 44.25\text{ $\pm2.09$} | Helped |
| Use Prob-PGD instead of the strongest listed baseline attack | pre-trained GIN · ENZYMES | accuracy (%): 39.75\text{ $\pm3.29$} -> 36.75\text{ $\pm4.62$} | Helped |
| Use Prob-PGD instead of the strongest listed baseline attack | pre-trained SGC · ENZYMES | accuracy (%): 48.75\text{ $\pm4.27$} -> 40.75\text{ $\pm3.83$} | Helped |
| Use Prob-PGD instead of the strongest listed baseline attack | pre-trained GCN · Cora | accuracy (%): 78.47\text{ $\pm0.44$} -> 77.88\text{ $\pm0.33$} | Helped |
| Use Prob-PGD instead of the strongest listed baseline attack | pre-trained GIN · Cora | accuracy (%): 73.76\text{ $\pm2.07$} -> 56.67\text{ $\pm4.57$} | Helped |
| Use Prob-PGD instead of the strongest listed baseline attack | pre-trained SGC · Cora | accuracy (%): 78.30\text{ $\pm0.33$} -> 77.49\text{ $\pm0.29$} | Helped |
Surprising findings
- On Cora, Prob-PGD barely changes GCN and SGC accuracy despite larger embedding perturbation, while it strongly degrades GIN accuracy (56.67% vs 73.76%).
- Gap between attack methods narrows in deeper GCN layers, possibly due to loose bounds and oversmoothing.
Limitations
- Analysis is restricted to evasion attacks and edge perturbations; permutation equivariance is not explicitly addressed.
- Multilayer bound loosens with depth, so the advantage over baselines narrows in deeper layers.
- Attack is task-agnostic and does not directly optimize downstream loss, so accuracy degradation is not always larger than baselines (e.g., Cora with SGC/GCN).
Experimental setup
Datasets: MUTAG ENZYMES Cora Stochastic block model Barabasi-Albert Watts-Strogatz Random Sensor Network Zachary karate club
Benchmarks: MUTAG ENZYMES Cora
Metrics: expected embedding perturbation (Frobenius norm) classification accuracy
Baselines: Random Wst-PGD DICE
Builds on: Graph convolutional networks SGC Wst-PGD worst-case embedding stability analysis DICE contextual stochastic block model
Closest papers by meaning
- Convergence and Stability of Graph Convolutional Networks on Large Random Graphs (NeurIPS 2020 · similarity 0.94)
- Limitless Stability for Graph Convolutional Networks (ICLR 2023 · similarity 0.92)
- A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.90)
- Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks (ICLR 2024 · similarity 0.90)
- Unitary Convolutions for Learning on Graphs and Groups (NeurIPS 2024 · similarity 0.89)
- Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspective (ICML 2024 · 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.