Research map / Graph learning / GNN architectures
Graph Coarsening with Message-Passing Guarantees
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 new oriented propagation matrix Q S Q^+ for message passing on coarsened graphs, with guarantees linking spectral (RSA) coarsening error to GNN message-passing and SGC training error.
Problem
Naive message passing on a spectrally coarsened graph does not guarantee that GNN outputs or training on the coarsened graph stay close to those on the original graph, even when the coarsening has good spectral (RSA) guarantees.
Approach
Define the coarsened propagation matrix as S_c = Q S Q^+ (rather than f_S(A_c)), which is generally asymmetric even for symmetric S, so that lifted message passing equals Pi S Pi and its error is bounded by the RSA constant; this yields provable bounds for SGC training on coarsened graphs.
Key results
- On Cora with SGC at coarsening ratio r=0.3, the proposed propagation matrix reaches 81.8±0.1% accuracy vs 79.3±0.1% for naive f_S(A_c) and 81.6% on the full graph.
- On Citeseer with GCNconv at r=0.7, the proposed matrix reaches 70.0±1.0% vs 67.1±3.1% for naive coarsened propagation.
- Synthetic random geometric graph experiments show the proposed matrix has significantly lower message-passing error, correlated with the RSA constant, unlike other choices.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use proposed propagation Q S Q+ instead of the strongest reported baseline | SGC · Cora PCC, r=0.3 | accuracy (%): 79.9 -> 81.8 | Helped |
| Use proposed propagation Q S Q+ instead of the strongest reported baseline | SGC · Cora PCC, r=0.5 | accuracy (%): 78.7 -> 80.3 | Helped |
| Use proposed propagation Q S Q+ instead of the strongest reported baseline | SGC · Cora PCC, r=0.7 | accuracy (%): 77.3 -> 78.5 | Helped |
| Use proposed propagation Q S Q+ instead of naive propagation | SGC · Citeseer PCC, r=0.3 | accuracy (%): 74.1 -> 73.9 | Hurt |
| Use proposed propagation Q S Q+ instead of the strongest reported baseline | SGC · Citeseer PCC, r=0.5 | accuracy (%): 72.8 -> 74.6 | Helped |
| Use proposed propagation Q S Q+ instead of the strongest reported baseline | SGC · Citeseer PCC, r=0.7 | accuracy (%): 72.5 -> 74.2 | Helped |
| Use proposed propagation Q S Q+ instead of the strongest reported baseline | GCNconv · Cora PCC, r=0.3 | accuracy (%): 81.9 -> 82.1 | Helped |
| Use proposed propagation Q S Q+ instead of the strongest reported baseline | GCNconv · Cora PCC, r=0.5 | accuracy (%): 80.4 -> 79.8 | Hurt |
| Use proposed propagation Q S Q+ instead of the strongest reported baseline | GCNconv · Cora PCC, r=0.7 | accuracy (%): 78.6 -> 78.2 | Hurt |
| Use proposed propagation Q S Q+ instead of the strongest reported baseline | GCNconv · Citeseer PCC, r=0.3 | accuracy (%): 72.1 -> 72.8 | Helped |
| Use proposed propagation Q S Q+ instead of the strongest reported baseline | GCNconv · Citeseer PCC, r=0.5 | accuracy (%): 70.7 -> 72.0 | Helped |
| Use proposed propagation Q S Q+ instead of the strongest reported baseline | GCNconv · Citeseer PCC, r=0.7 | accuracy (%): 69.3 -> 70.0 | Helped |
Surprising findings
- The proposed propagation matrix is generally asymmetric even when S is symmetric, so guarantees require oriented message passing on the coarsened graph.
- Training on some coarsened graphs sometimes outperforms training on the full graph (e.g., SGC Citeseer r=0.3 at 74.1 vs 73.6 full graph), attributed to homophily merging same-label nodes.
Limitations
- Guarantees hold rigorously only for linear SGC; the activation assumptions are not satisfied by ReLU-based GCN in general.
- The adapted Loukas coarsening algorithm is computationally costly, limiting experiments to small/medium graphs like Cora and Citeseer.
- Experiments restricted to principal connected components of Cora and Citeseer, making comparisons with other reported results harder.
Experimental setup
Datasets: Cora Citeseer Random geometric graph (synthetic)
Benchmarks: Cora Citeseer
Metrics: node classification accuracy message-passing error norm ||S^k x - Q^+ S_c^k x_c||_L
Baselines: naive coarsened propagation f_S(A_c) diagonal-corrected propagation (Huang et al.-style) Diffpool-style Q S Q^T symmetric lifting (Q^+)^T S Q^+ full graph training
Builds on: Loukas restricted spectral approximation coarsening Simplified Graph Convolution (SGC) GCNconv APPNP
Closest papers by meaning
- Taxonomy of reduction matrices for Graph Coarsening (NeurIPS 2025 · similarity 0.89)
- Accurate and Scalable Graph Neural Networks via Message Invariance (ICLR 2025 · similarity 0.88)
- Spectral Graph Sparsification Preserves Representation Geometry in Graph Neural Networks (NeurIPS 2026 · similarity 0.88)
- Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification (ICML 2025 · similarity 0.88)
- Probabilistic Graph Rewiring via Virtual Nodes (NeurIPS 2024 · similarity 0.87)
- Towards Dynamic Message Passing on Graphs (NeurIPS 2024 · similarity 0.87)
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.