Research map / Graph learning / GNN architectures
Improving the Effective Receptive Field of Message-Passing Neural Networks
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.
Shows that MPNN effective receptive field decays exponentially with distance and proposes IM-MPNN, which wraps standard MPNN backbones (GCN, GINE, GatedGCN, GAT) in an interleaved multiscale hierarchy built from Graclus coarsening with scale-mix layers, improving long-range benchmarks.
Problem
Message-passing neural networks have a limited effective receptive field and suffer from over-squashing, so long-range dependencies are poorly captured in graph learning.
Approach
Analyze MPNN ERF via binomial/diffusion arguments showing exponential decay of distant-node influence, then build a multiscale architecture that runs message passing on repeatedly coarsened graphs (Graclus pairing) and mixes information between adjacent scales, so long-range signals travel in fewer hops, at roughly linear cost.
Key results
- On PascalVOC-SP, IM-GatedGCN (3 scales) reaches 0.4332 test F1 vs 0.3880 for GatedGCN, and COCO-SP improves from 0.2922 to 0.3501 test F1.
- On City-Networks, IM-GCN improves accuracy over GCN by roughly +10% to +16.5% across Paris, Shanghai, Los Angeles and London.
- On heterophilic benchmarks, IM-CO-GNN(Σ,Σ) reaches 92.08 on Roman-Empire and 80.49 on Questions, the best reported in the table.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add interleaved multiscale processing with 3 scales to GatedGCN | GatedGCN · PascalVOC-SP | Test F1: 0.3880$_{\pm 0.0040}$ -> 0.4332$_{\pm 0.0045}$ | Helped |
| Add interleaved multiscale processing with 3 scales to GatedGCN | GatedGCN · COCO-SP | Test F1: 0.2922$_{\pm 0.0018}$ -> 0.3501$_{\pm 0.0033}$ | Helped |
| Increase IM-GCN scales from 3 to 4 (ablation) | IM-GCN · PascalVOC-SP | Test F1: 0.2910$_{\pm 0.0058}$ -> 0.2929$_{\pm 0.0058}$ | No clear effect |
| Increase IM-GINE scales from 3 to 4 (ablation) | IM-GINE · COCO-SP | Test F1: 0.2475$_{\pm 0.0017}$ -> 0.2472$_{\pm 0.0037}$ | No clear effect |
| Add interleaved multiscale processing with 3 scales to GCN | GCN · Peptides-func | Test AP: 0.6860$_{\pm 0.0050}$ -> 0.6942$_{\pm 0.0083}$ | No clear effect |
| Increase IM-GCN scales from 1 to 2 (ablation) | IM-GCN · Peptides-struct | Test MAE: 0.2453$_{\pm 0.0009}$ -> 0.2473$_{\pm 0.0018}$ | Hurt |
| Add interleaved multiscale processing with 3 scales to GatedGCN | GatedGCN · Peptides-struct | Test MAE: 0.2477$_{\pm 0.0009}$ -> 0.2454$_{\pm 0.0014}$ | Helped |
| Add interleaved multiscale processing with 4 scales to GCN | GCN · Shanghai | Test accuracy: 52.4$_{\pm 0.3}$ -> 67.8$_{\pm 0.1}$ | Helped |
| Add interleaved multiscale processing with 4 scales to GCN | GCN · Los Angeles | Test accuracy: 45.9$_{\pm 1.0}$ -> 62.4$_{\pm 0.3}$ | Helped |
| Add interleaved multiscale processing to CO-GNN(μ, μ) | CO-GNN(μ, μ) · Minesweeper | Test score: 97.31$_{\pm0.41}$ -> 97.39$_{\pm0.35}$ | No clear effect |
| Add interleaved multiscale processing to CO-GNN(Σ, Σ) | CO-GNN(Σ, Σ) · Roman-Empire | Test score: 91.57$_{\pm0.32}$ -> 92.08$_{\pm0.33}$ | Helped |
| Add interleaved multiscale processing to CO-GNN(μ, μ) | CO-GNN(μ, μ) · Amazon-Ratings | Test score: 54.17$_{\pm0.37}$ -> 54.43$_{\pm0.41}$ | No clear effect |
Surprising findings
- Peptides-func and Peptides-struct are only slightly affected by the multiscale configuration, with gains that are small or within noise for some scales.
- IM-GCN with 1 scale underperforms GCN on Peptides-struct MAE only marginally, and IM-GatedGCN with 1-2 scales underperforms GatedGCN on Peptides-func.
Limitations
- Number of scales is a hyperparameter requiring empirical tuning, with no automatic selection rule.
- Improvements on Peptides datasets are small and mostly within standard deviation.
- Heterophilic results are benchmarked against numbers taken from prior work rather than re-run under identical protocols.
Experimental setup
Datasets: PascalVOC-SP COCO-SP Peptides-func Peptides-struct City-Networks Roman-Empire Amazon-ratings Minesweeper Tolokers Questions OGBN Arxiv graph transfer tasks (ring, crossed-ring, clique-path)
Benchmarks: Long Range Graph Benchmark City-Networks heterophilic node classification benchmarks graph transfer OGBN Arxiv
Metrics: F1 AP MAE accuracy runtime per epoch parameter count
Baselines: GCN GINE GatedGCN GAT Graph U-Net DRew CO-GNN Exphormer GPS FSGNN
Builds on: Graclus Graph U-Net GCN GatedGCN GINE
Closest papers by meaning
- Probabilistically Rewired Message-Passing Neural Networks (ICLR 2024 · similarity 0.88)
- Probabilistic Graph Rewiring via Virtual Nodes (NeurIPS 2024 · similarity 0.88)
- On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning (NeurIPS 2025 · similarity 0.88)
- Mitigating Over-squashing without Rewiring: A Sheaf Effective Resistance Perspective (NeurIPS 2026 · similarity 0.86)
- Accurate and Scalable Graph Neural Networks via Message Invariance (ICLR 2025 · similarity 0.86)
- Locality-Aware Graph Rewiring in GNNs (ICLR 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.