mlsanityData to 14 Oct 2026

Revisiting the Message Passing in Heterophilous Graph Neural Networks

arXiv 2405.17768 ↗First posted 28 May 2024cs.LG cs.SIcited by 5

Not on the map. Why?

Abstract (arXiv)

Graph Neural Networks (GNNs) have demonstrated strong performance in graph mining tasks due to their message-passing mechanism, which is aligned with the homophily assumption that adjacent nodes exhibit similar behaviors. However, in many real-world graphs, connected nodes may display contrasting behaviors, termed as heterophilous patterns, which has attracted increased interest in heterophilous GNNs (HTGNNs). Although the message-passing mechanism seems unsuitable for heterophilous graphs due to the propagation of class-irrelevant information, it is still widely used in many existing HTGNNs and consistently achieves notable success. This raises the question: why does message passing remain effective on heterophilous graphs? To answer this question, in this paper, we revisit the message-passing mechanisms in heterophilous graph neural networks and reformulate them into a unified heterophilious message-passing (HTMP) mechanism. Based on HTMP and empirical analysis, we reveal that the success of message passing in existing HTGNNs is attributed to implicitly enhancing the compatibility matrix among classes. Moreover, we argue that the full potential of the compatibility matrix is not completely achieved due to the existence of incomplete and noisy semantic neighborhoods in real-world heterophilous graphs. To bridge this gap, we introduce a new approach named CMGNN, which operates within the HTMP mechanism to explicitly leverage and improve the compatibility matrix. A thorough evaluation involving 10 benchmark datasets and comparative analysis against 13 well-established baselines highlights the superior performance of the HTMP mechanism and CMGNN method.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 34 of its 44 references that are in the map. First posted on arXiv 28 May 2024.

Builds on

34 of 44 references.

References · 34

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  5. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  6. 2020LightGCN: Simplifying and Powering Graph Convolution Network for Recommendationcited by 1,139
  7. 2018Pitfalls of Graph Neural Network Evaluationcited by 1,007
  8. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 993
  9. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  10. 2020Simple and Deep Graph Convolutional Networkscited by 860
  11. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 826
  12. 2019Neural Graph Collaborative Filteringcited by 661
22 more
  1. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 595
  2. 2019Multi-scale Attributed Node Embeddingcited by 548
  3. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 443
  4. 2021Beyond Low-frequency Information in Graph Convolutional Networkscited by 362
  5. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 343
  6. 2018Learning Word Vectors for 157 Languagescited by 280
  7. 2020Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networkscited by 260
  8. 2020Graph Neural Networks with Heterophilycited by 202
  9. 2021Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networkscited by 182
  10. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  11. 2022Finding Global Homophily in Graph Neural Networks When Meeting Heterophilycited by 179
  12. 2021Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learningcited by 177
  13. 2022Graph Neural Networks for Graphs with Heterophily: A Surveycited by 175
  14. 2022Revisiting Heterophily For Graph Neural Networkscited by 169
  15. 2019Graph Wavelet Neural Networkcited by 131
  16. 2021Interpreting and Unifying Graph Neural Networks with An Optimization Frameworkcited by 131
  17. 2020Node Similarity Preserving Graph Convolutional Networkscited by 112
  18. 2020A Unified View on Graph Neural Networks as Graph Signal Denoisingcited by 110
  19. 2021Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patternscited by 95
  20. 2021GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophilycited by 84
  21. 2023Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothingcited by 67
  22. 2024A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directionscited by 13

Built on by

Cited by year

Citing papers per year: 2024: 2; 2025: 3.

5 papers.

  1. 2024The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challengescited by 29
  2. 2025Reasoning-Enhanced Domain-Adaptive Pretraining of Multimodal Large Language Models for Short Video Content Governancecited by 16
  3. 2024Making Classic GNNs Strong Baselines Across Varying Homophily: A Smoothness-Generalization Perspectivecited by 2
  4. 2025Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theorycited by 2
  5. 2025ParaGate: Parasitic-Driven Domain Adaptation Transfer Learning for Netlist Performance Predictioncited by 0