Research map / Graph learning / GNN architectures
Graph rewiring and scalable message passing
Rewire graphs and add virtual nodes to improve message passing.
72 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in GNN architectures, keyword cluster “message passing · equivariant · mpnns”
State History Benchmarks Tried Checklist Preprints Who Export
Where it stands
Leveling off Several papers from 2025–26 still report on 6 tracked benchmarks, but the best result has barely moved since 2024.
29 papers in 2023–24 and 28 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic held steady, from 6.1% to 5.5%.
What looks settled
- Citeseer (accuracy): best up to 2024 77.31, best in 2025–26 74.82 from 3 papers, at most 0.2% better, if at all.
- Mutag (accuracy): best up to 2024 98.4, best in 2025–26 81 from 2 papers, at most 0.2% better, if at all.
- Proteins (accuracy): best up to 2024 80.7, best in 2025–26 73.9 from 2 papers, at most 0.2% better, if at all.
- Cora (accuracy): best up to 2024 88.37, best in 2025–26 86.8 from 2 papers, at most 0.2% better, if at all.
- Chameleon (accuracy): best up to 2024 75.2, best in 2025–26 63.2 from 2 papers, at most 0.2% better, if at all.
- Collab (accuracy): best up to 2024 86.72, best in 2025–26 80.7 from 2 papers, at most 0.2% better, if at all.
How this is decided
A benchmark is tracked when at least four papers of this approach report their own method on the same dataset and metric in at least two different years. Its record is the best number reported up to 2024 compared with the best reported in 2025–26: still improving means at least 1% better, flat means at most 0.2% better with at least two papers from 2025–26 trying. Numbers on a different scale from the rest (a fraction among percentages) and far outliers are left out. Results come from different papers with different setups, so they are signals, not head-to-head comparisons. The share of papers is counted at ICML, NeurIPS, ICLR, CVPR and AAAI.
How it got here
Most cited paper of each year
- 2016 · Metadata-conscious anonymous messaging (ICML 2016 · 6 citations)
- 2020 · Conv-MPN: Convolutional Message Passing Neural Network for Structured Outdoor Architecture Reconstruction (CVPR 2020 · 68 citations)
- 2021 · Hybrid Message Passing With Performance-Driven Structures for Facial Action Unit Detection (CVPR 2021 · 64 citations)
- 2022 · Understanding over-squashing and bottlenecks on graphs via curvature (ICLR 2022 · 34 citations)
- 2023 · DropMessage: Unifying Random Dropping for Graph Neural Networks (AAAI 2023 · 64 citations)
- 2024 · TextGT: A Double-View Graph Transformer on Text for Aspect-Based Sentiment Analysis (AAAI 2024 · 49 citations)
- 2025 · Faithful and Accurate Self-Attention Attribution for Message Passing Neural Networks via the Computation Tree Viewpoint (AAAI 2025 · 2 citations)
- 2026 · Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs (AAAI 2026 · 1 citation)
Earliest papers here
- Metadata-conscious anonymous messaging (ICML 2016 · 6 citations)
- Conv-MPN: Convolutional Message Passing Neural Network for Structured Outdoor Architecture Reconstruction (CVPR 2020 · 68 citations)
- Message Passing Attention Networks for Document Understanding (AAAI 2020 · 63 citations)
Benchmark records
The best number each year that beat every earlier one, among papers of this approach reporting their own method. Numbers are extracted by AI from each paper's text; check the paper before citing.
Citeseer · accuracy (higher is better)
7 papers, 2022–2025 · flat since 2024
| Year | Best so far | Set by |
|---|---|---|
| 2022 | 73.3 | Self-Supervised Graph Neural Networks via Diverse and Interactive Message Passing (AAAI 2022 · 14 citations) |
| 2023 | 77.31 | Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing (ICLR 2023 · 18 citations) |
Mutag · accuracy (higher is better)
7 papers, 2022–2025 · flat since 2024
| Year | Best so far | Set by |
|---|---|---|
| 2022 | 91.5 | Self-Supervised Graph Neural Networks via Diverse and Interactive Message Passing (AAAI 2022 · 14 citations) |
| 2024 | 98.4 | Probabilistically Rewired Message-Passing Neural Networks (ICLR 2024 · 4 citations) |
Proteins · accuracy (higher is better)
7 papers, 2023–2025 · flat since 2024
| Year | Best so far | Set by |
|---|---|---|
| 2023 | 75.78 | Understanding Oversquashing in GNNs through the Lens of Effective Resistance (ICML 2023 · 5 citations) |
| 2024 | 80.7 | Probabilistically Rewired Message-Passing Neural Networks (ICLR 2024 · 4 citations) |
Cora · accuracy (higher is better)
6 papers, 2022–2025 · flat since 2024
| Year | Best so far | Set by |
|---|---|---|
| 2022 | 83.3 | Self-Supervised Graph Neural Networks via Diverse and Interactive Message Passing (AAAI 2022 · 14 citations) |
| 2023 | 88.37 | Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing (ICLR 2023 · 18 citations) |
Chameleon · accuracy (higher is better)
5 papers, 2023–2025 · flat since 2024
| Year | Best so far | Set by |
|---|---|---|
| 2023 | 72.28 | Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing (ICLR 2023 · 18 citations) |
| 2024 | 75.2 | Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs (ICML 2024 · 0 citations) |
Collab · accuracy (higher is better)
5 papers, 2023–2025 · flat since 2024
| Year | Best so far | Set by |
|---|---|---|
| 2023 | 77.45 | Understanding Oversquashing in GNNs through the Lens of Effective Resistance (ICML 2023 · 5 citations) |
| 2024 | 86.72 | Towards Dynamic Message Passing on Graphs (NeurIPS 2024 · 3 citations) |
What has been tried
53 papers here report 552 measured changes (a component added, removed or swapped, compared with a baseline): helped 67%, no clear effect 7%, hurt 20%, mixed 6%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| replace Transformer layers with TextGINConv | Restaurant, Laptop, Twitter · Accuracy | 85.17 -> 80.07; 78.64 -> 74.68; 76.51 -> 74.89 | Hurt | TextGT: A Double-View Graph Transformer on Text for Aspect-Based Sentiment Analysis (AAAI 2024 · 49 citations) |
| add unified smoothing to label smoothing | Cora, L/C=20 · ECE (M=20) | % -> 0.0715 | Helped | Moderate Message Passing Improves Calibration: A Universal Way to Mitigate Confidence Bias in Graph Neural Networks (AAAI 2024 · 5 citations) |
| Use the Simple gradient estimator rather than Gumbel SoftSub-ST or I-MLE | Zinc - Edge · MAE | 0.153 ±0.003; 0.151 ±0.001 -> 0.139 ±0.001 | Helped | Probabilistically Rewired Message-Passing Neural Networks (ICLR 2024 · 4 citations) |
| Use MPLP+ walk-level features instead of MPLP node-level structural features | USAir, NS, PB, Yeast, C.ele, Power, Router, E.coli · Hits@50 | Mixed | Pure Message Passing Can Estimate Common Neighbor for Link Prediction (NeurIPS 2024 · 4 citations) | |
| Use proximity measurement instead of attention | three graph-classification benchmarks (datasets unnamed in excerpt) · performance | Helped | Towards Dynamic Message Passing on Graphs (NeurIPS 2024 · 3 citations) | |
| Remove contribution adjustment from GAtt | Cora, Citeseer, and Pubmed · Pearson correlation for Δ_PC | 0.8477 -> 0.7708; 0.8624 -> 0.6392; 0.8516 -> 0.8058; 0.8711 -> 0.6671; 0.8812 -> 0.7683; 0.8489 -> 0.4197 | Hurt | Faithful and Accurate Self-Attention Attribution for Message Passing Neural Networks via the Computation Tree Viewpoint (AAAI 2025 · 2 citations) |
| add learnable boundary coefficients instead of fixed constants | CS · ACC (%) | 94.14 ± 0.26 -> 95.78 ± 0.21 | Helped | Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models (NeurIPS 2025 · 2 citations) |
| Use centrality-based node expansion instead of random node expansion | Reddit-Binary · accuracy | 72.000\std{0.850} -> 80.690\std{0.721} | Helped | PANDA: Expanded Width-Aware Message Passing Beyond Rewiring (ICML 2024 · 2 citations) |
| Use aggressive bounds tightening instead of static bounds tightening | Cora · avg-time (s) | 0.17 -> 0.46 | Hurt | Verifying message-passing neural networks via topology-based bounds tightening (ICML 2024 · 2 citations) |
| Use two sampled virtual nodes instead of one fully connected virtual node | ZINC · MAE | 0.074 ±0.002 -> 0.067 ±0.001 | Helped | Probabilistic Graph Rewiring via Virtual Nodes (NeurIPS 2024 · 2 citations) |
| Remove gradients from the additional message-passing terms | Yelp-2018, Gowalla, Amazon-book · NDCG@20 | 6.36 -> 6.16; 9.88 -> 9.87; 8.13 -> 7.80 | Hurt | How Does Message Passing Improve Collaborative Filtering? (NeurIPS 2024 · 2 citations) |
| add hierarchical positional encoding | PATTERN · accuracy | 0.8511 -> 0.8738 | Helped | Best of Both Worlds: Advantages of Hybrid Graph Sequence Models (ICML 2025 · 1 citation) |
What reviewers will expect
Datasets and baselines named in the 21 papers of this approach from 2025–2026 that have a full-text summary. Leaving out the common ones is a frequent review question.
Datasets
- Cora · 7 of 21 papers
- Citeseer · 7 of 21 papers
- Pubmed · 5 of 21 papers
- Peptides-Func · 5 of 21 papers
- Texas · 4 of 21 papers
- Wisconsin · 4 of 21 papers
- peptides-struct · 4 of 21 papers
- Cornell · 3 of 21 papers
Baselines
- GCN · 10 of 21 papers
- GIN · 5 of 21 papers
- Exphormer · 5 of 21 papers
- GAT · 5 of 21 papers
- GatedGCN · 4 of 21 papers
- GRIT · 4 of 21 papers
- GraphGPS · 3 of 21 papers
- GINE · 3 of 21 papers
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 57 papers; from OpenAlex and the papers' affiliations).
- University of Oxford · 5 papers
- University of Cambridge · 5 papers
- Fudan University · 3 papers
- Zhejiang University · 3 papers
- Shanghai Jiao Tong University · 3 papers
- Universität Stuttgart · 3 papers
- NEC · 3 papers
- Google · 3 papers
- University of Notre Dame · 3 papers
- Chinese Academy of Sciences · 2 papers
Use it
Download BibTeX of 38 key papersOpen the topic in the interactive map
Get alerts. Describe your idea in scime atlas and save it (free scime account): you get a weekly email when new preprints land close to it.
Related approaches
Same keyword cluster
- Expressive equivariant message passing (109 papers)
- Structural GNN variants (65 papers)
- Equivariant networks for molecules (43 papers)
Elsewhere in the topic
- Graph structure learning (201 papers)
- GNN generalization theory (187 papers)
- Simple and scalable GNNs (131 papers)
- Robustness, privacy, and fairness of GNNs (94 papers)
- Theory of graph convolutional networks (83 papers)
- Deep graph convolution and simplification (82 papers)
- Physics-inspired GNNs (81 papers)
- Weisfeiler-Leman expressivity hierarchies (66 papers)
Benchmark numbers, ablations and baseline numbers are extracted by AI from each paper's full text and can be wrong; the paper is the authority. Data: results index of 2026-11-02, citation counts from OpenAlex (2026-10-09).