# Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs

arXiv: https://arxiv.org/abs/2405.20652 · HTML: https://mlsanity.com/paper/2405.20652/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 44 references that are in the map.
- First posted on arXiv 31 May 2024.

## Builds on (most cited first, 30 of 32)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [Graph Neural Networks for Graphs with Heterophily: A Survey](https://mlsanity.com/paper/2202.07082/) (2022)
- [Revisiting Heterophily For Graph Neural Networks](https://mlsanity.com/paper/2210.07606/) (2022)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Not too little, not too much: a theoretical analysis of graph (over)smoothing](https://mlsanity.com/paper/2205.12156/) (2022)
- [Dirichlet Energy Constrained Learning for Deep Graph Neural Networks](https://mlsanity.com/paper/2107.02392/) (2021)
- [Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing](https://mlsanity.com/paper/2302.01524/) (2023)
- [A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2212.10701/) (2022)
- [Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs](https://mlsanity.com/paper/2306.07608/) (2023)
- [Towards Deep Attention in Graph Neural Networks: Problems and Remedies](https://mlsanity.com/paper/2306.02376/) (2023)
- [Label-Wise Graph Convolutional Network for Heterophilic Graphs](https://mlsanity.com/paper/2110.08128/) (2021)

## Built on by (most cited first, 8 of 8)

- [Rethinking Reconstruction-based Graph-Level Anomaly Detection: Limitations and a Simple Remedy](https://mlsanity.com/paper/2410.20366/) (2024)
- [Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification](https://mlsanity.com/paper/2506.16110/) (2025)
- [A Signed Graph Approach to Understanding and Mitigating Oversmoothing in GNNs](https://mlsanity.com/paper/2502.11394/) (2025)
- [Preference-driven Knowledge Distillation for Few-shot Node Classification](https://mlsanity.com/paper/2510.10116/) (2025)
- [GraphTorque: Torque-Driven Rewiring Graph Neural Network](https://mlsanity.com/paper/2507.21422/) (2025)
- [ATLAS: Adaptive Topology-based Learning at Scale for Homophilic and Heterophilic Graphs](https://mlsanity.com/paper/2512.14908/) (2025)
- [Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation](https://mlsanity.com/paper/2605.10975/) (2026)
- [Graph Cascades: Contagion-Based Mesoscopic Rewiring for Structure-Aware Graph Machine Learning](https://mlsanity.com/paper/2606.05046/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have gained significant attention as a powerful modeling and inference method, especially for homophilic graph-structured data. To empower GNNs in heterophilic graphs, where adjacent nodes exhibit dissimilar labels or features, Signed Message Passing (SMP) has been widely adopted. However, there is a lack of theoretical and empirical analysis regarding the limitations of SMP. In this work, we unveil some potential pitfalls of SMP and their remedies. We first identify two limitations of SMP: undesirable representation update for multi-hop neighbors and vulnerability against oversmoothing issues. To overcome these challenges, we propose a novel message passing function called Multiset to Multiset GNN(M2M-GNN). Our theoretical analyses and extensive experiments demonstrate that M2M-GNN effectively alleviates the aforementioned limitations of SMP, yielding superior performance in comparison