Research map / Graph learning / GNN architectures
Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic 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.
Shows signed message passing (SMP) can yield undesirable multi-hop updates and oversmoothing in multi-class settings, and proposes M2M-GNN, a multiset-to-multiset message passing scheme that uses soft-label chunks to keep heterophilic neighbor embeddings separate.
Problem
Signed message passing (SMP), widely used for heterophilic graphs, has unexamined limitations: undesirable cumulative updates for multi-hop neighbors and vulnerability to oversmoothing in multi-class graphs.
Approach
Replace the multiset-to-element (m-2-e) weighted-sum aggregator of SMP with a multiset-to-multiset (m-2-m) scheme that partitions neighbor embeddings into class-specific chunks via learned soft labels (attention) and concatenates the chunk messages, with a regularizer to diversify attention across chunks.
Key results
- M2M-GNN achieves the best average rank (1.7) across 11 datasets, with top-3 accuracy on every dataset.
- M2M-GNN reaches 89.19% on Texas and 89.01% on Wisconsin, versus 87.84% and 88.43% for the best SMP-based baseline ACM-GCN.
- In the oversmoothing study, SMP-based GNNs (FAGCN, Goal, GPR-GNN) degrade substantially as depth grows from 2 to 64 layers while M2M-GNN stays relatively stable, peaking at K=32 on Cora.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use M2M-GNN instead of ACM-GCN | Node classification · Texas | accuracy (%): 87.84 -> 89.19 | Helped |
| Use M2M-GNN instead of ACM-GCN | Node classification · Wisconsin | accuracy (%): 88.43 -> 89.01 | Helped |
| Use M2M-GNN instead of Ordered GNN | Node classification · Cornell | accuracy (%): 87.03 -> 86.48 | Hurt |
| Use M2M-GNN instead of Ordered GNN | Node classification · Actor | accuracy (%): 37.99 -> 36.72 | Hurt |
| Use M2M-GNN instead of Ordered GNN | Node classification · Squirrel | accuracy (%): 62.44 -> 63.60 | Helped |
| Use M2M-GNN instead of Ordered GNN | Node classification · Chameleon | accuracy (%): 72.28 -> 75.20 | Helped |
| Use M2M-GNN instead of Goal | Node classification · Cora | accuracy (%): 88.75 -> 88.12 | Hurt |
| Use M2M-GNN instead of ACM-GCN | Node classification · Citeseer | accuracy (%): 77.32 -> 77.20 | Hurt |
| Use M2M-GNN instead of Ordered GNN | Node classification · Pubmed | accuracy (%): 90.15 -> 90.35 | Helped |
| Use M2M-GNN instead of Goal | Node classification · Penn94 | accuracy (%): 84.18 -> 85.94 | Helped |
| Use M2M-GNN instead of GAT | Node classification · Amazon-rating | accuracy (%): 49.09 -> 49.18 | Helped |
| Add regularization loss L_reg (ablation) | M2M-GNN · Wisconsin and Pubmed | mixing score and node classification accuracy | Helped |
Surprising findings
- Even with all one-hop propagation coefficients desirable, the cumulative multi-hop propagation matrix of SMP can be undesirable when there are more than two classes.
- In the multi-class CSBM setting, SMP class-mean separation shrinks exponentially with depth, whereas in the binary case it does not.
Limitations
- Analysis of SMP's limitations relies on linear models and CSBM assumptions; extension to non-linear models is only discussed in the appendix.
- Attention soft labels tend to collapse to one chunk without the regularizer, and the number of chunks must be tuned (best when equal to number of classes).
- Interpretability of individual neighbor contributions is reduced compared to graph attention networks, as acknowledged in the impact statement.
Experimental setup
Datasets: Texas Wisconsin Cornell Actor Squirrel Chameleon Cora Citeseer Pubmed Penn94 Amazon-ratings
Benchmarks: Texas Wisconsin Cornell Actor Squirrel Chameleon Cora Citeseer Pubmed Penn94 Amazon-ratings
Metrics: node classification accuracy average rank
Baselines: GCN GAT MLP ACM-GCN GPR-GNN FAGCN GGCN Goal AERO-GNN Ordered GNN H2GCN DMP
Builds on: FAGCN GCN Contextual Stochastic Block Model
Closest papers by meaning
- Understanding and Enhancing Message Passing on Heterophilic Graphs via Compatibility Matrix (NeurIPS 2025 · similarity 0.91)
- GAMMA: Gated Multi-hop Message Passing for Homophily-Agnostic Node Representation in GNNs (NeurIPS 2025 · similarity 0.91)
- A Practical, Progressively-Expressive GNN (NeurIPS 2022 · similarity 0.90)
- How Powerful are K-hop Message Passing Graph Neural Networks (NeurIPS 2022 · similarity 0.89)
- Accurate and Scalable Graph Neural Networks via Message Invariance (ICLR 2025 · similarity 0.89)
- On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks (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.