Graph Label Denoising via Neighborhood Agreement–Guided Expectation Maximization

Abstract

Graph Neural Networks are susceptible to label noise, in which message-passing mechanisms serve as conduits for propagating erroneous supervision. Current mitigation techniques typically recover clean labels via heuristics that lack theoretical grounding, which often leads to ineffective denoising. To tackle the issue, we propose NAEM, a latent label estimation framework that models clean labels as latent variables by integrating neighborhood agreement into the Expectation-Maximization (EM) paradigm. To overcome the posterior collapse problem in standard EM under severe noise, we design a structure-aware E-step that leverages neighborhood agreement as a structural prior. This mechanism acts as a dynamic confidence gate based on local consensus to prevent the model from overfitting to noise. Simultaneously, by explicitly modeling the noise transition matrix in the M-step, NAEM decouples noise dynamics from semantic representation learning. Extensive experiments on five benchmark datasets demonstrate that NAEM consistently outperforms SOTA methods under varying noise conditions, validating the effectiveness of our framework.