# Resurrecting Label Propagation for Graphs with Heterophily and Label Noise

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 36 references that are in the map.
- First posted on arXiv 25 Oct 2023.

## Builds on (most cited first, 21 of 21)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Co-teaching: Robust Training of Deep Neural Networks with Extremely Noisy Labels](https://mlsanity.com/paper/1804.06872/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Making Deep Neural Networks Robust to Label Noise: a Loss Correction Approach](https://mlsanity.com/paper/1609.03683/) (2016)
- [Knowledge Graphs](https://mlsanity.com/paper/2003.02320/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [Predicting multicellular function through multi-layer tissue networks](https://mlsanity.com/paper/1707.04638/) (2017)
- [Self-Adaptive Training: beyond Empirical Risk Minimization](https://mlsanity.com/paper/2002.10319/) (2020)
- [A Topological Filter for Learning with Label Noise](https://mlsanity.com/paper/2012.04835/) (2020)
- [NRGNN: Learning a Label Noise-Resistant Graph Neural Network on Sparsely and Noisily Labeled Graphs](https://mlsanity.com/paper/2106.04714/) (2021)
- [To Smooth or Not? When Label Smoothing Meets Noisy Labels](https://mlsanity.com/paper/2106.04149/) (2021)
- [Robust Training of Graph Neural Networks via Noise Governance](https://mlsanity.com/paper/2211.06614/) (2022)
- [Distillation ≈ Early Stopping? Harvesting Dark Knowledge Utilizing Anisotropic Information Retrieval For Overparameterized Neural Network](https://mlsanity.com/paper/1910.01255/) (2019)
- [Learning on Graphs under Label Noise](https://mlsanity.com/paper/2306.08194/) (2023)

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

- [A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directions](https://mlsanity.com/paper/2401.09769/) (2024)
- [Rethinking the impact of noisy labels in graph classification: A utility and privacy perspective](https://mlsanity.com/paper/2406.07314/) (2024)
- [Delving into Instance-Dependent Label Noise in Graph Data: A Comprehensive Study and Benchmark](https://mlsanity.com/paper/2506.12468/) (2025)
- [Flexible Diffusion Scopes with Parameterized Laplacian for Heterophilic Graph Learning](https://mlsanity.com/paper/2409.09888/) (2024)
- [FedRGL: Robust Federated Graph Learning for Label Noise](https://mlsanity.com/paper/2411.18905/) (2024)
- [NodeReg: Mitigating the Imbalance and Distribution Shift Effects in Semi-Supervised Node Classification via Norm Consistency](https://mlsanity.com/paper/2503.03211/) (2025)
- [Piecewise Constant Spectral Graph Neural Network](https://mlsanity.com/paper/2505.04808/) (2025)
- [Identifying and Correcting Label Noise for Robust GNNs via Influence Contradiction](https://mlsanity.com/paper/2601.17469/) (2026)
- [Multi-Label Node Classification with Label Influence Propagation](https://mlsanity.com/paper/2607.00671/) (2026)
- [Hypergraph Contrastive Learning for both Homophilic and Heterophilic Hypergraphs](https://mlsanity.com/paper/2511.18783/) (2025)
- [Ftextsuperscript2LP-AP: Fast & Flexible Label Propagation with Adaptive Propagation Kernel](https://mlsanity.com/paper/2604.20736/) (2026)
- [A Near-Linear-Time Solver for Graph p-Laplacian Semi-Supervised Learning via Continuation in p](https://mlsanity.com/paper/2607.03503/) (2026)

## Abstract (arXiv)

Label noise is a common challenge in large datasets, as it can significantly degrade the generalization ability of deep neural networks. Most existing studies focus on noisy labels in computer vision; however, graph models encompass both node features and graph topology as input, and become more susceptible to label noise through message-passing mechanisms. Recently, only a few works have been proposed to tackle the label noise on graphs. One significant limitation is that they operate under the assumption that the graph exhibits homophily and that the labels are distributed smoothly. However, real-world graphs can exhibit varying degrees of heterophily, or even be dominated by heterophily, which results in the inadequacy of the current methods. In this paper, we study graph label noise in the context of arbitrary heterophily, with the aim of rectifying noisy labels and assigning labels to previously unlabeled nodes. We begin by conducting two empirical analyses to explore the impact of graph homophily on graph label noise. Following observations, we propose a efficient algorithm, denoted as R2LP. Specifically, R2LP is an iterative algorithm with three steps: (1) reconstruct the graph to recover the homophily property, (2) utilize label propagation to rectify the noisy labels, (3) select high-confidence labels to retain for the next iteration. By iterating these steps, we obtain a set of correct labels, ultimately achieving high accuracy in the node classification task. The theoretical analysis is also provided to demonstrate its remarkable denoising effect. Finally, we perform experiments on ten benchmark datasets with different levels of graph heterophily and various types of noise. In these experiments, we compare the performance of R2LP against ten typical baseline methods. Our results illustrate the superior performance of the proposed R2LP.