Research map / Graph learning / GNN architectures
Analysis of Corrected Graph Convolutions
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.
Gives spectral, non-asymptotic partial and exact classification guarantees for k rounds of graph convolution with the principal eigenvector removed, in the two-class contextual SBM, showing removal avoids oversmoothing.
Problem
Oversmoothing in multi-round graph convolutions degrades node classification; there are no rigorous classification guarantees for many convolution rounds in the contextual stochastic block model.
Approach
Remove the principal eigenvector component from the (normalized or unnormalized) adjacency so repeated convolutions converge to the second eigenvector, which captures the class bipartition; analyze partial and exact linear classification of the resulting corrected convolutions via spectral perturbation and path-counting moment bounds.
Key results
- Each round of corrected convolution reduces misclassification error exponentially up to a saturation level set by graph signal strength, for partial classification.
- Exact linear separability achieved with separability threshold improved exponentially up to O(log n / log log n) corrected convolutions.
- On real datasets (Cora, CiteSeer, PubMed), corrected convolutions keep accuracy much higher than uncorrected GCN as layers increase, while uncorrected accuracy degrades.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Remove the principal eigenvector component from graph convolutions | GCN · Synthetic CSBM node classification | accuracy | Helped |
| Remove the principal eigenvector component using the corrected normalized adjacency | GCN · Cora, CiteSeer, PubMed | accuracy | Helped |
| Remove the principal eigenvector component using the corrected unnormalized adjacency | GCN · Cora, CiteSeer, PubMed | accuracy | Helped |
| Add another corrected unnormalized graph convolution before the error reaches saturation | Corrected graph convolution · Two-class CSBM partial classification | misclassification error | Helped |
| Add corrected graph convolutions after the error reaches saturation | Corrected graph convolution · Two-class CSBM partial classification | misclassification error | No clear effect |
Surprising findings
- Uncorrected convolution accuracy decreases with more layers, whereas corrected convolutions retain or improve accuracy.
Limitations
- Exact classification analysis only for the unnormalized corrected matrix; normalized case left to future work.
- Analysis restricted to balanced classes and Gaussian features; unbalanced classes may break the second-eigenspace argument.
- Theory assumes p above log^2 n / n and linear classifier on a two-class CSBM.
Experimental setup
Datasets: Cora CiteSeer PubMed synthetic CSBM data
Benchmarks: Cora CiteSeer PubMed synthetic CSBM
Metrics: classification accuracy
Baselines: GCN (uncorrected convolution) PairNorm
Builds on: contextual stochastic block model graph convolutional network PairNorm
Closest papers by meaning
- Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Models (ICML 2025 · similarity 0.89)
- HoloNets: Spectral Convolutions do extend to Directed Graphs (ICLR 2024 · similarity 0.88)
- Graph Neural Networks Do Not Always Oversmooth (NeurIPS 2024 · similarity 0.87)
- Learning to Approximate Adaptive Kernel Convolution on Graphs (AAAI 2024 · similarity 0.86)
- On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective (NeurIPS 2025 · similarity 0.86)
- Unitary Convolutions for Learning on Graphs and Groups (NeurIPS 2024 · similarity 0.86)
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.