Research map / Graph learning / GNN architectures
Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNs
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.
Theoretically analyzes how residual connections and BatchNorm prevent oversmoothing in linearized GNNs, shows centering distorts the graph signal, and proposes GraphNormv2 with a learnable centering projection that improves node and graph classification.
Problem
Oversmoothing in GNNs causes node representations to collapse to a low-dimensional subspace as depth grows; it is unclear theoretically how residual connections and normalization layers prevent this and how the centering step of normalization affects message passing.
Approach
Characterizes linearized GNNs with initial residual connections (reachable subspace = Krylov subspace of initial features) and BatchNorm (convergence to top-k eigenspace of centered message-passing operator), shows centering alters the structural eigenvectors, and introduces GraphNormv2 whose centering is a learnable projection onto top-k eigenvectors plus the all-ones direction.
Key results
- GraphNormv2 with GIN achieves 84.9% on MUTAG and 86.5% on Cora versus 82.5% and 85.9% for other baselines (GCN/GIN tables).
- With 20-layer GCN on Cora, GraphNormv2 reaches 84.8% vs 84.0% for BatchNorm and 46.0% with no normalization.
- In linear deep GCN (256 layers), PairNorm collapses in rank while BatchNorm, PowerEmbed and GraphNormv2 keep rank above 2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GraphNormv2 instead of GraphNorm | GCN · MUTAG | accuracy: 81.1 \pm 4.7 -> 82.6 \pm 4.6 | Helped |
| Use GraphNormv2 instead of GraphNorm | GCN · PROTEINS | accuracy: 71.4 \pm 3.6 -> 72.6 \pm 2.6 | Helped |
| Use GraphNormv2 instead of GraphNorm | GCN · PTC-MR | accuracy: 58.1 \pm 4.8 -> 56.5 \pm 4.8 | Hurt |
| Use GraphNormv2 instead of GraphNorm | GCN · Cora | accuracy: 85.1 \pm 0.8 -> 85.8 \pm 0.5 | Helped |
| Use GraphNormv2 instead of GraphNorm | GCN · CiteSeer | accuracy: 89.1 \pm 0.7 -> 89.5 \pm 0.6 | No clear effect |
| Use GraphNormv2 instead of GraphNorm | GCN · ogbn-arxiv | accuracy: 68.3 \pm 0.2 -> 68.3 \pm 0.3 | No clear effect |
| Use GraphNormv2 instead of GraphNorm | GIN · MUTAG | accuracy: 83.7 \pm 4.2 -> 84.9 \pm 3.6 | Helped |
| Use GraphNormv2 instead of GraphNorm | GIN · PROTEINS | accuracy: 72.6 \pm 2.4 -> 71.0 \pm 3.6 | Hurt |
| Use GraphNormv2 instead of GraphNorm | GIN · PTC-MR | accuracy: 59.1 \pm 5.1 -> 60.1 \pm 5.5 | Helped |
| Use GraphNormv2 instead of GraphNorm | GAT · MUTAG | accuracy: 81.2 \pm 4.8 -> 81.6 \pm 3.8 | Mixed |
| Use GraphNormv2 instead of GraphNorm | GAT · PROTEINS | accuracy: 71.9 \pm 2.4 -> 71.0 \pm 2.6 | Hurt |
| Use GraphNormv2 instead of GraphNorm | GAT · PTC-MR | accuracy: 60.3 \pm 5.4 -> 59.5 \pm 4.4 | Hurt |
Surprising findings
- GraphNormv2 performs weaker with GAT, which the authors attribute to asymmetric and time-varying attention operators outside the analysis scope.
- PairNorm's centering prevents rank collapse in the non-linear GCN, though it collapses in the linear case.
Limitations
- Theory is for linearized GNNs with i.i.d. Gaussian weights; non-linear case left open.
- GraphNormv2 gains are weak in several settings and it underperforms with GAT.
- Analysis does not cover asymmetric or time-varying message passing such as attention.
Experimental setup
Datasets: MUTAG PROTEINS PTC-MR Cora CiteSeer ogbn-arxiv
Benchmarks: MUTAG PROTEINS PTC-MR Cora CiteSeer ogbn-arxiv
Metrics: accuracy rank mu_v oversmoothing measure
Baselines: BatchNorm PairNorm GraphNorm PowerEmbed GroupNorm
Builds on: GCNII GraphNorm PairNorm APPNP PowerEmbed
Closest papers by meaning
- Curriculum-Enhanced Residual Soft An-Isotropic Normalization for Over-Smoothness in Deep GNNs (AAAI 2024 · similarity 0.90)
- Deep Graph Neural Networks via Posteriori-Sampling-based Node-Adaptative Residual Module (NeurIPS 2024 · similarity 0.89)
- On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning (NeurIPS 2025 · similarity 0.89)
- Graph Neural Networks Do Not Always Oversmooth (NeurIPS 2024 · similarity 0.88)
- Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence (ICML 2025 · similarity 0.88)
- Locality-Aware Graph Rewiring in GNNs (ICLR 2024 · similarity 0.88)
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.