Label Propagation for Graph Label Noise
Yao Cheng Caihua Shan Yifei Shen Xiang Li Siqiang Luo Dongsheng Li
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 major
limitation is that they assume the graph is homophilous and the labels are
smoothly distributed. Nevertheless, real-world graphs may contain varying
degrees of heterophily or even be heterophily-dominated, leading to the
inadequacy of 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 simple yet efficient algorithm,
denoted as LP4GLN. Specifically, LP4GLN 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 conduct experiments on 10
benchmark datasets under varying graph heterophily levels and noise types,
comparing the performance of LP4GLN with 7 typical baselines. Our results
illustrate the superior performance of the proposed LP4GLN.