mlsanityData to 7 Oct 2026

Simplifying Node Classification on Heterophilous Graphs with Compatible Label Propagation

arXiv 2205.09389 ↗First posted 19 May 2022cs.LG cs.SIcited by 7

Not on the map. Why?

Abstract (arXiv)

Graph Neural Networks (GNNs) have been predominant for graph learning tasks; however, recent studies showed that a well-known graph algorithm, Label Propagation (LP), combined with a shallow neural network can achieve comparable performance to GNNs in semi-supervised node classification on graphs with high homophily. In this paper, we show that this approach falls short on graphs with low homophily, where nodes often connect to the nodes of the opposite classes. To overcome this, we carefully design a combination of a base predictor with LP algorithm that enjoys a closed-form solution as well as convergence guarantees. Our algorithm first learns the class compatibility matrix and then aggregates label predictions using LP algorithm weighted by class compatibilities. On a wide variety of benchmarks, we show that our approach achieves the leading performance on graphs with various levels of homophily. Meanwhile, it has orders of magnitude fewer parameters and requires less execution time. Empirical evaluations demonstrate that simple adaptations of LP can be competitive in semi-supervised node classification in both homophily and heterophily regimes.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 34 of its 54 references that are in the map. First posted on arXiv 19 May 2022.

Builds on

34 of 54 references.

References · 34

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  5. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  6. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  7. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
  8. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  9. 2018Pitfalls of Graph Neural Network Evaluationcited by 994
  10. 2020Simple and Deep Graph Convolutional Networkscited by 857
  11. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
  12. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
22 more
  1. 2019Multi-scale Attributed Node Embeddingcited by 543
  2. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 442
  3. 2018Deep Learning on Graphs: A Surveycited by 393
  4. 2021Beyond Low-frequency Information in Graph Convolutional Networkscited by 361
  5. 2021Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methodscited by 309
  6. 2019PairNorm: Tackling Oversmoothing in GNNscited by 297
  7. 2020SIGN: Scalable Inception Graph Neural Networkscited by 283
  8. 2020Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networkscited by 253
  9. 2020Graph Neural Networks with Heterophilycited by 202
  10. 2020Combining Label Propagation and Simple Models Out-performs Graph Neural Networkscited by 199
  11. 2021Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networkscited by 182
  12. 2022Graph Neural Networks for Graphs with Heterophily: A Surveycited by 175
  13. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  14. 2022How to Find Your Friendly Neighborhood: Graph Attention Design with Self-Supervisioncited by 102
  15. 2020Unifying Graph Convolutional Neural Networks and Label Propagationcited by 98
  16. 2020Scattering GCN: Overcoming Oversmoothness in Graph Convolutional Networkscited by 57
  17. 2021Boost then Convolve: Gradient Boosting Meets Graph Neural Networkscited by 42
  18. 2016Graph-based semi-supervised learning for relational networkscited by 10
  19. 2020Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learningcited by 9
  20. 2019Rethinking Kernel Methods for Node Representation Learning on Graphscited by 7
  21. 2014Semi-Supervised Learning with Heterophilycited by 4
  22. 2020Factorized Graph Representations for Semi-Supervised Learning from Sparse Datacited by 3

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 1; 2024: 3; 2025: 2.

7 papers.

  1. 2024Harnessing Large Language Models as Post-hoc Correctorscited by 7
  2. 2024A Comprehensive Graph Pooling Benchmark: Effectiveness, Robustness and Generalizabilitycited by 6
  3. 2023Hetero2Net: Heterophily-aware Representation Learning on Heterogenerous Graphscited by 4
  4. 2022GLINKX: A Scalable Unified Framework For Homophilous and Heterophilous Graphscited by 0
  5. 2024Graph as a feature: improving node classification with non-neural graph-aware logistic regressioncited by 0
  6. 2025Learning from Heterophilic Graphs: A Spectral Theory Perspective on the Impact of Self-Loops and Parallel Edgescited by 0
  7. 2025ATLAS: Adaptive Topology-based Learning at Scale for Homophilic and Heterophilic Graphscited by 0