Research map / Graph learning / GNN architectures
PANDA: Expanded Width-Aware Message Passing Beyond Rewiring
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 PANDA, a message passing paradigm that selectively widens high-centrality nodes and handles four edge types between low- and high-width nodes, avoiding graph rewiring to mitigate over-squashing.
Problem
Over-squashing in message passing GNNs, where long-range information is compressed through bottleneck nodes; existing rewiring methods alter graph topology, which can distort domain semantics and cause over-smoothing.
Approach
Instead of rewiring edges, select top-k high-centrality nodes and give them a larger hidden width; four neighbour aggregators handle low-low, high-high, low-to-high (linear projection) and high-to-low (learned dimension selection) messages, preserving the original topology.
Key results
- PANDA-GCN reaches 80.69% on Reddit-Binary vs 68.26% for GCN without rewiring and 70.33% for FoSR, the best rewiring baseline shown.
- PANDA-GIN reaches 91.055% on Reddit-Binary, 72.56% on IMDB-Binary and 88.75% on Mutag, the highest in the GIN table.
- PANDA-GCN outperforms R-GCN on all six graph classification datasets (e.g., 85.75 vs 69.25 on Mutag).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply PANDA width-aware message passing instead of FoSR | GCN · Reddit-Binary | accuracy: 70.330\std{0.727} -> 80.690\std{0.721} | Helped |
| Apply PANDA width-aware message passing instead of CT-Layer | GCN · IMDB-Binary | accuracy: 52.146\std{0.415} -> 63.760\std{1.012} | Helped |
| Apply PANDA width-aware message passing instead of FoSR | GCN · Mutag | accuracy: 80.000\std{1.574} -> 85.750\std{1.396} | Helped |
| Apply PANDA width-aware message passing instead of SDRF | GCN · Enzymes | accuracy: 28.367\std{1.174} -> 31.550\std{1.230} | Helped |
| Apply PANDA width-aware message passing instead of FoSR | GCN · Proteins | accuracy: 73.420\std{0.811} -> 76.000\std{0.774} | Helped |
| Apply PANDA width-aware message passing instead of CT-Layer | GCN · Collab | accuracy: 52.146\std{0.415} -> 68.400\std{0.452} | Helped |
| Apply PANDA width-aware message passing instead of Last Layer FA | GIN · Reddit-Binary | accuracy: 90.220\std{0.475} -> 91.055\std{0.402} | Helped |
| Apply PANDA width-aware message passing instead of FoSR | GIN · IMDB-Binary | accuracy: 71.210\std{0.919} -> 72.560\std{0.917} | Helped |
| Apply PANDA width-aware message passing instead of Last Layer FA | GIN · Mutag | accuracy: 83.450\std{1.742} -> 88.750\std{1.570} | Helped |
| Apply PANDA width-aware message passing instead of Last Layer FA | GIN · Enzymes | accuracy: 47.400\std{1.387} -> 46.200\std{1.410} | Hurt |
| Apply PANDA width-aware message passing instead of FoSR | GIN · Proteins | accuracy: 75.107\std{0.817} -> 75.759\std{0.856} | Helped |
| Apply PANDA width-aware message passing instead of Last Layer FA | GIN · Collab | accuracy: 75.056\std{0.406} -> 75.110\std{0.210} | No clear effect |
Surprising findings
- Random expansion of nodes performs comparably to centrality-based selection on Mutag, suggesting centrality matters less on small graphs.
- PANDA runs slower than plain GCN in forward pass (e.g., 41.3 vs 11.5 ms on Reddit-Binary), and betweenness/load centrality can take ~950 s on Reddit-Binary.
Limitations
- Theoretical justification of higher width reducing over-squashing is only informal; authors state more research is needed.
- Added computational cost from centrality computation and four message types; high-dimensional dimension selection adds overhead.
- Evaluation focuses on TUDataset graph classification with small graphs; the authors acknowledge limited breadth of tasks.
Experimental setup
Datasets: Reddit-Binary IMDB-Binary Mutag Enzymes Proteins Collab Cora Citeseer Texas Cornell Wisconsin Squirrel
Benchmarks: Reddit-Binary IMDB-Binary Mutag Enzymes Proteins Collab Cora Citeseer Texas Cornell Wisconsin Squirrel
Metrics: mean test accuracy 95% confidence interval effective resistance correlation Dirichlet energy runtime
Baselines: No rewiring (None) DIGL Fully adjacent layers SDRF FoSR BORF GTR CT-Layer R-GCN
Builds on: GCN GIN R-GCN FoSR DIGL
Closest papers by meaning
- Locality-Aware Graph Rewiring in GNNs (ICLR 2024 · similarity 0.91)
- The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisited (ICLR 2025 · similarity 0.91)
- Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification (ICML 2025 · similarity 0.91)
- Probabilistic Graph Rewiring via Virtual Nodes (NeurIPS 2024 · similarity 0.89)
- GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring (ICLR 2025 · similarity 0.89)
- Probabilistically Rewired Message-Passing Neural Networks (ICLR 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.