Research map / Graph learning / GNN architectures
Towards Dynamic Message Passing on Graphs
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 N2, a GNN with dynamic message passing where graph nodes and learnable pseudo nodes move in a shared state space and their measured proximities define evolving pathways, achieving linear complexity via a single recurrent layer.
Problem
Message passing in GNNs over-relies on input topology, causing over-smoothing and over-squashing, while existing global alternatives either use uniform pseudo-node pathways (bottlenecks) or dense pairwise relations (quadratic cost).
Approach
Embed graph nodes and learnable pseudo nodes in a common state space where proximity (piecewise weighted inner products) defines edge weights; nodes move via displacements produced by a shared recurrent layer, so pathways are dynamic and global message passing through pseudo nodes costs linear time.
Key results
- On OGB-molpcba, N2 reaches 33.90% average precision with 516K parameters, versus Graphormer's 31.39% with 119.5M parameters.
- On small-scale graph classification, N2 achieves the best accuracy on all five benchmarks, e.g., 83.52% on NCI1 and 86.72% on COLLAB.
- On node classification, N2 reaches 58.69% on arXiv-year and 79.55% ROC-AUC on OGB-proteins, while OGB-arXiv (70.01%) trails SGFormer (72.63%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use proximity measurement instead of attention (ablation) | N² · three graph-classification benchmarks (datasets unnamed in excerpt) | performance | Helped |
| Remove pseudo-node adaptation (ablation) | N² · three benchmarks (names not specified in excerpt) | accuracy | Hurt |
| Remove local message passing (ablation) | N² · node classification benchmarks | accuracy | Hurt |
| Remove global message passing (ablation) | N² · graph-classification benchmarks | accuracy | Hurt |
| Add specially distinguished messages rather than pass node states directly (ablation) | N² · questions | score: 76.01 -> 78.07 | Helped |
| Add specially distinguished messages rather than pass node states directly (ablation) | N² · amazon-ratings | score: 47.79 -> 50.25 | Helped |
| Add specially distinguished messages rather than pass node states directly (ablation) | N² · AmazonPhoto | score: 93.80 -> 95.75 | Helped |
| Use pseudo-node message passing instead of dense message passing (ablation) | N² · IMDB-B | accuracy: 77.94 -> 79.95 | Helped |
| Use pseudo-node message passing instead of dense message passing (ablation) | N² · IMDB-M | accuracy: 56.41 -> 57.31 | Helped |
| Use pseudo-node message passing instead of dense message passing (ablation) | N² · PROTEINS | accuracy: 76.94 -> 77.53 | Helped |
| Increase the number of pseudo nodes (ablation) | N² · PROTEINS | accuracy | Mixed |
| Use multiple recurrent layers instead of one shared layer when recursive steps exceed 8 (ablation) | N² · amazon-ratings and AmazonPhoto | performance | Helped |
Surprising findings
- Pseudo nodes outperform dense message passing on IMDB-B, IMDB-M, and PROTEINS, which the authors attribute to pseudo nodes acting as information filters.
- Accuracy degrades when the number of pseudo nodes is too large (e.g., 256 on PROTEINS), which the authors attribute to exceeding the optimization capacity.
Limitations
- Performance degrades as the number of recursive steps grows.
- Only a simple recurrent update mechanism was studied.
- Only a subset of GNN neurons are embedded in the common state space; bridging all neurons remains open.
Experimental setup
Datasets: OGB-molpcba PROTEINS NCI1 COLLAB IMDB-BINARY IMDB-MULTI CoauthorCS CoauthorPhysics AmazonPhoto AmazonComputers questions amazon-ratings
Benchmarks: OGB-molpcba PROTEINS NCI1 COLLAB IMDB-BINARY IMDB-MULTI CoauthorCS CoauthorPhysics AmazonPhoto AmazonComputers questions amazon-ratings
Metrics: accuracy average precision ROC-AUC mean absolute error training accuracy Dirichlet energy
Baselines: GCN GIN GraphSAGE DiffPool TopKPool SAGPool StructPool SEP GMT Graphormer SAN GraphGPS
Builds on: DyN Graphormer GraphGPS GNNs with a single pseudo node
Closest papers by meaning
- Cooperative Graph Neural Networks (ICML 2024 · similarity 0.89)
- Beyond Message Passing: Neural Graph Pattern Machine (ICML 2025 · similarity 0.89)
- Expressive Power of Temporal Message Passing (AAAI 2025 · similarity 0.89)
- Recurrent Graph Neural Networks and Their Connections to Bisimulation and Logic (AAAI 2024 · similarity 0.89)
- Accurate and Scalable Graph Neural Networks via Message Invariance (ICLR 2025 · similarity 0.89)
- Probabilistic Graph Rewiring via Virtual Nodes (NeurIPS 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.