mlsanityData to 7 Oct 2026

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

arXiv 2405.20652 ↗First posted 31 May 2024cs.LGcited by 8

Not on the map. Why?

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

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

Builds on

32 of 44 references.

References · 32

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2017Inductive Representation Learning on Large Graphscited by 6,284
  5. 2016Layer Normalizationcited by 5,579
  6. 2018How Powerful are Graph Neural Networks?cited by 4,355
  7. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  8. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  9. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  10. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
  11. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
  12. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
20 more
  1. 2021How Attentive are Graph Attention Networks?cited by 818
  2. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
  3. 2019Multi-scale Attributed Node Embeddingcited by 543
  4. 2021Beyond Low-frequency Information in Graph Convolutional Networkscited by 361
  5. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 332
  6. 2021Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methodscited by 309
  7. 2021Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networkscited by 182
  8. 2022Graph Neural Networks for Graphs with Heterophily: A Surveycited by 175
  9. 2022Revisiting Heterophily For Graph Neural Networkscited by 169
  10. 2020Graph Clustering with Graph Neural Networkscited by 163
  11. 2018Contextual Stochastic Block Modelscited by 134
  12. 2022Not too little, not too much: a theoretical analysis of graph (over)smoothingcited by 106
  13. 2021Dirichlet Energy Constrained Learning for Deep Graph Neural Networkscited by 97
  14. 2023Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothingcited by 67
  15. 2022A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networkscited by 49
  16. 2023Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphscited by 25
  17. 2023Towards Deep Attention in Graph Neural Networks: Problems and Remediescited by 24
  18. 2021Label-Wise Graph Convolutional Network for Heterophilic Graphscited by 17
  19. 2022ResNorm: Tackling Long-tailed Degree Distribution Issue in Graph Neural Networks via Normalizationcited by 15
  20. 2024Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspectivecited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 5; 2026: 2.

8 papers.

  1. 2024Rethinking Reconstruction-based Graph-Level Anomaly Detection: Limitations and a Simple Remedycited by 13
  2. 2025Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsificationcited by 7
  3. 2025A Signed Graph Approach to Understanding and Mitigating Oversmoothing in GNNscited by 2
  4. 2025Preference-driven Knowledge Distillation for Few-shot Node Classificationcited by 1
  5. 2025GraphTorque: Torque-Driven Rewiring Graph Neural Networkcited by 0
  6. 2025ATLAS: Adaptive Topology-based Learning at Scale for Homophilic and Heterophilic Graphscited by 0
  7. 2026Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigationcited by 0
  8. 2026Graph Cascades: Contagion-Based Mesoscopic Rewiring for Structure-Aware Graph Machine Learningcited by 0