Graph Label Denoising via Neighborhood Agreement–Guided Expectation Maximization

1 Introduction

Graph Neural Networks (GNNs) have emerged as the dominant paradigm for representation learning on graph-structured data, demonstrating exceptional performance in node classification [Kipf and Welling, 2016; Velikovi et al., 2018]. Despite their success, GNNs often struggle in real-world settings due to unavoidable label noise from unreliable annotations or malicious attacks. While label noise is a well-studied topic in computer vision, its impact on graphs is more severe and complex due to the non-i.i.d. nature of the data. This message-passing paradigm transforms GNNs into effective spreaders of label noise. Unlike i.i.d. (independent and identically distributed) data, where noise is localized, graph edges facilitate the propagation of erroneous signals. Thus, a single noisy node can significantly compromise the learned representations of its clean neighbors through topological aggregation [NT et al., 2019a; Dai et al., 2021]. This topological dependency causes a cascading effect, where a few noisy labels can pollute large areas of the graph, significantly reducing model generalization.

∗Corresponding author

To mitigate this issue, recent research has adapted strategies from the i.i.d. domain, predominantly categorizing into sample selection and label correction. Sample selection methods, such as TSS [Wu et al., 2024] and CLNode [Wei et al., 2023], employ heuristics like the small-loss criterion to segregate clean nodes from noisy ones. While effective in low-noise regimes, these methods suffer from data starvation and confirmation bias as noise rates increase, leading the model to overfit early while discarding informative hard samples. Conversely, label correction approaches, such as NRGNN [Dai et al., 2021] and RTGNN [Qian et al., 2023], attempt to rectify noisy labels via neighborhood smoothing. However, these methods often apply graph smoothing indiscriminately based on the naive homophily assumption. As illustrated in Figure 1(a), we contend that employing noisedominated neighborhoods to refine node labels does not eliminate the noise within the graph; rather, it merely produces smoother noise.

A critical oversight in current methods is the formulation of the Clean Labelas a deterministic target to be recovered via a selection or smoothing paradigm. However, since ground truth is intrinsically unobservable under noisy conditions, we propose that it should be rigorously modeled as a Latent Variable within a probabilistic generative paradigm. We redefine the graph noisy learning task as maximum likelihood estimation via the EM algorithm [Dempster et al., 1977]. However, a major limitation of standard EM in noisy environments is its susceptibility to posterior collapse, which is particularly pronounced in graph learning since the topologydependent noise propagation pattern. As GNNs recursively encode noisy signals from neighbors into node representations, the model learns to interpret this noise as a valid structural pattern, resulting in self-reinforcing bias. The posterior converges towards the noisy observations ˜ Y with misleadingly high confidence. To alleviate posterior collapse on graph data, we integrate Neighborhood Agreement (NA) into the EM framework. NA acts as an informative structural prior to guide and refine the posterior estimation rather than serving as a hard constraint.

We propose NAEM, a structure-aware Neighborhood Agreement EM framework that provides a principled solution for denoising graph labels, as shown in Figure 1(b). Unlike heuristic approaches, NAEM maximizes the Expected Complete-Data Log-Likelihood of the observed noisy graph data. First, we design a structure-aware E-step that produces a refined posterior explicitly incorporating the neighborhood agreement mechanism. In detail, we leverage an adaptive agreement gate to refine inference based on structural consistency. It retains instance-level predictions for nodes aligned with their local neighbors, while adjusting inconsistent nodes towards the direction of neighborhood consensus, thereby mitigating overfitting to noisy labels. Moreover, during the corresponding adaptive M-step, we simultaneously optimize the GNN parameters and the noise transition matrix through iterative refinement. NAEM effectively disentangles corruption patterns from semantic features by explicitly modeling the noise transition process, facilitating robust representation learning across varied noise environments. Extensive experiments on five benchmark datasets show our method consistently outperforms baselines and enjoys great scalability under various noise conditions. Supplementary material is available at Zenodo 1 .

Our main contributions are in the following three-fold:

• We propose a probabilistic generative framework, named NAEM, that reformulates graph label noise learning as a latent variable estimation problem. We derive a unified optimization target with theoretical convergence guarantees.
• We design a structure-aware E-step that integrates Neighborhood Agreement as a structural prior. Through an adaptive gating mechanism, we dynamically refine the posterior to curb noisy signal propagation.
• Extensive experiments on five benchmark datasets demonstrate that NAEM consistently outperforms baselines under various noise conditions, and comprehensive analysis confirms the effectiveness and robustness of our framework.

1 https://doi.org/10.5281/zenodo.20098669

2 RelatedWork

2.1 Label Noise Learning on I.I.D. Data

Traditional independent and identically distributed label noise learning follows three paradigms: estimating the noise transition matrix, such as the S-model [Goldberger and BenReuven, 2017]; selecting clean samples based on the smallloss assumption, such as Co-teaching [Han et al., 2018] and JoCoR [Wei et al., 2020]; and employing robust objective functions, such as SCE [Wang et al., 2019]. However, these methods struggle with graph data where noise spreads through edges, as they overlook properties that depend on topology.

2.2 Label Noise Learning on Graphs

Graph noise learning in research is mainly categorized into sample selection, label correction, and representation learning.

Sample Selection Strategies

Similar to i.i.d. methods, these strategies train GNNs using only the estimated clean label set. CLNode [Wei et al., 2023] employs a curriculum learning strategy, while TSS [Wu et al., 2024] and RTGNN [Qian et al., 2023] utilize topology identification criteria and collaborative learning mechanisms, respectively. However, sample selection often leads to data insufficiency and degraded generalization performance when facing a severe noise setting.

Label Correction and Propagation

Conversely, these methods correct noise through smoothing or constraints. NRGNN [Dai et al., 2021], Union-NET [Li et al., 2021], and CGNN [Yuan et al., 2023] use naive neighborhood aggregation, while other methods incorporate structural guidelines such as community clustering [Zhang et al., 2020], pairwise interactions [Du et al., 2021], and backward loss correction [NT et al., 2019b]. However, random aggregation of noisy neighborhoods tends to produce smoother noise rather than clear signals, thereby enhancing confirmation bias.

Robust Representation and Contrastive Learning

Recent studies enhance GNN robustness by utilizing graph contrastive learning [Zhu et al., 2024; Li et al., 2024] or energy-based detection and prototype alignment [Chen et al., 2024; Li et al., 2025]. Although these methods enhance the robustness of features, they do not provide a unified probabilistic framework for inferring labels. Unlike existing works treating noisy labels as deterministic targets, our NAEM framework models the true label as a latent variable.

3 Methodology

In this section, we present the proposed NAEM framework to mitigate graph label noise, as illustrated in Figure 2. Specifically, we formulate the noisy node classification problem as a likelihood maximization task involving a latent variable. Then, we incorporate a structure-aware prior during the inference stage to rectify the posterior estimation within the EM paradigm, followed by an adaptive maximization stage to decouple noise patterns from semantic representations.

3.1 ProblemFormulation

Let G = (V, E) denote an undirected graph where V = {v1, . . . , vN} is the set of N nodes and E is the set of edges. Let X ∈ RN×d be the node feature matrix and A ∈ {0, 1}N×N be the adjacency matrix. The node set V can be split into labeled set VL and unlabeled set VU, where usually |VL| ≪ |VU| in graph node classification task. The class set is C = {1, . . . ,K}.

The observed labeled set VL may be corrupted in the realworld settings. We represent the observed noisy labels as ˜ YL = {˜ yi | vi ∈ VL}, where ˜ yi ∈ C. We also assume that the latent clean labels, represented as Y = {yi | vi ∈ V}, are unobservable. The goal is to learn a robust GNN classifier fθ that can accurately predict the clean labels Y for both VL and VU under noisy supervision from ˜ YL.

3.2 Probabilistic Generative Framework

In contrast to sample selection paradigms, we model the label correction as a probabilistic inference problem. To estimate clean label, we establish a generative process connecting the latent clean Y and the noisy observation ˜ Y conditioned on graph data X and A.

Latent Label Generation. The clean label yi is generated based on node features X and graph structure A, and is implemented by the GNN parameters θ:

where fθ(·)k denotes the predicted probability for class k. Noisy Label Generation. Given the latent clean label yi, the observed noisy label ˜ yi is produced via a noise transition process. We adopt a class-dependent noise model defined by a transition matrix T ∈ [0, 1]K×K , following standard assumptions for graph label noise learning [Wang et al., 2024]:

where Tjk represents the probability that clean label j is corrupted into noisy label k. Our goal is to jointly infer the posterior distribution of the latent true labels Y and learn the robust classifier θ by maximizing the marginal likelihood:

As direct maximization is intractable, we employ the EM algorithm to maximize the Expected Complete-Data LogLikelihood (Q-function):

where Θ = {θ, T} and q(t) i (j) is the posterior estimate at iteration t. Detailed derivation in Supplementary Sec. A.1.

Standard EM estimates the posterior q(Y ) relying solely on the current model prediction Pθ and transition matrix T. Nevertheless, this phenomenon is especially harmful in graph learning because of the so-called topology-dependent noise propagation. Compared to i.i.d. data, where noise is typically associated with specific samples, the recursive messages that flow through GNNs may unintentionally carry misleading signal information from noisy neighbors into the node representations. This creates a self-reinforcing cycle where the model is led to believe that label noise is a valid structural pattern. As a result, the graph classifier fθ is more likely to overfit noisy labels with misleadingly high confidence, and the posterior collapses to the noisy observations, and hence it loses its ability to correct errors. To mitigate this, we introduce Neighborhood Agreement as a structural prior to calibrate the posterior inference in the E-step.

3.3 Structure-Aware E-Step

In the E-step, our objective is to estimate the posterior distribution of the clean labels q(t) (yi = j) ≈ P(yi = j | ˜ yi, xi,A). To prevent the posterior from being dominated by noisy supervision, we inject the graph structure as an inductive bias.

Initialization and Evidence Decomposition

Before the iterative process, we initialize the model parameters θ(0) via a warm-up phase using the standard crossentropy loss on ˜ YL for a few epochs. The transition matrix T(0) employs a diagonally dominant random initialization.

At iteration t, we decompose the evidence for the latent label yi into the instance-level posterior and the neighborhood consensus.

First, the instance-level posterior qbase represents the standard Bayesian update for node i, conditioning on its observed noisy label ˜ yi. It integrates the predictive distribution from the GNN classifier (acting as the latent prior) and the noise transition probability (acting as the observation likelihood):

The posterior remains heavily anchored to the current parameters θ(t) , rendering it susceptible to the bias of noisy labels during early training.

Second, we introduce the neighborhood consensus qneighbor to rectify potential biases in qbase. The proposed mechanism diverges from feature aggregation by enforcing explicit posterior smoothing within the label space, grounded in the graph homophily assumption. Pooling instance-level posteriors from neighboring nodes establishes a structural prior:

where N(i) = {vj ∈ V | Aij = 1} denotes the set of immediate neighbors of node vi.

Neighborhood Consistency and Posterior Refinement

To evaluate the reliability of the instance-level posterior, we compute the Neighborhood Agreement (NA) score Si ∈ [0, 1] for node i via the normalized cosine similarity between the two evidence views:

where qbase,i and qneighbor,i denote the probability vectors of q(t) base (yi) and q(t) neighbor (yi), respectively. A high Si signifies that the GNN prediction aligns with the local topology, typical of reliable samples, whereas a low agreement suggests a conflict indicative of label noise. Dynamic regulation of the neighborhood consensus influence relies on the computation of an adaptive agreement gate αi. Mapping Si to a confidence weight wi precedes the derivation of αi:

Here, τhigh and τlow are agreement thresholds determining the trust interval, and λNA is agreement strength controlling the maximum strength of the structural prior. The gating mechanism αi dynamically adjusts the mixing ratio by retaining the instance-level posterior for high-agreement nodes (wi ≈ 1) or enforcing neighborhood consensus correction as the coefficient approaches λNA under low-agreement conditions (wi ≈ 0). We derive the refined posterior q(t) NA(yi) via convex combination:

Finally, we apply a momentum coefficient hyperparameter, denoted as γ, to update the model to ensure stability:

3.4 Adaptive M-Step for Joint Optimization

In the M-step, we maximize the Q-function with respect to GNN parameters θ and transition matrix T given q(t) , decoupling semantic learning from noise modeling, as θ and T appear in separate terms in Eq. (4).

Robust Representation Learning (Updating θ)

The optimization for θ corresponds to minimizing the expected risk with respect to the latent labels. This is equivalent to minimizing a posterior-weighted cross-entropy loss:

Supervision of the GNN relies on the corrected latent distribution through the substitution of noisy one-hot targets ˜ yi with refined soft labels q(t) .

Noise Transition Estimation (Updating T)

NAEM explicitly learns the class-dependent noise pattern T to decouple noise patterns from semantic features. Maximizing the Q-function with respect to T under the constraint ∑k Tjk = 1 yields a weighted closed-form solution. To mitigate random outliers, Bayesian Sample Reweighting assigns each sample a transition-model reliability score ri, which estimates the posterior probability that the sample is generated by the structured transition process rather than a uniform outlier component; its closed-form definition and derivation are provided in the supplementary material, Sec. A.2. This leads to the Weighted Closed-Form Solution for the update rule at iteration t + 1:

Here I(·) denotes the indicator function. The symbol ri is distinct from the neighborhood-agreement confidence wi in Eq. (8). The estimation mechanism aggregates the fractional counts of estimated true labels j flipping to observed labels k weighted by sample reliability to approximate the noise transition probability. Algorithm details and complexity analysis are provided in Supplementary Sec. A.3; NAEM preserves the O(|E|d +Nd2 ) complexity inherent to the backbone GNN.

4 Experiment

We evaluate the effectiveness of the proposed NAEM framework by addressing the following research questions:

• RQ1: Does NAEM outperform state-of-the-art baselines on node classification tasks under various noise settings?

RQ2: Can NAEM mitigate noise propagation and maintain accuracy under incorrect supervision?

RQ3: How does each component contribute to the overall performance of the framework?

RQ4: Does the Neighborhood Agreement strategy effectively prevent posterior collapse and enhance latent label inference?

4.1 Experimental Setup

Datasets

We evaluate NAEM on five benchmarks: Cora, Citeseer, Pubmed [Sen et al., 2008], Amazon-Computers, and Amazon-Photos [Shchur et al., 2018], with OGBN-Arxiv [Hu et al., 2020] and Flickr used for scalability and heterophily evaluation. Dataset details are available in Supplementary Sec. B.1.

Noise Injection

We follow standard protocols [Wang et al., 2024; Li et al., 2025] to inject synthetic label noise into the training set: Uniform Noise (UN): Uniformly flips the true label to another class with probability η. Formally, for ∀j ̸= i, p(˜ y = j | Y = i) = η c-1 , where c represents the number of classes. Pair Noise (PN): Flips the true label to its corresponding pair class with probability η. We test noise rates η ∈ {10%, 20%, 30%, 40%, 50%} for both types.

Baselines

We compare NAEM against baselines from three categories: Standard GNNs: GCN [Kipf and Welling, 2016], GAT [Velikovi et al., 2018].

Label Noise Learning (I.I.D.): S-model [Goldberger and Ben-Reuven, 2017], Co-teaching [Han et al., 2018], JoCoR [Wei et al., 2020], SCE [Wang et al., 2019].

Graph Label Noise: NRGNN [Dai et al., 2021], RTGNN [Qian et al., 2023], CP [Zhang et al., 2020], DGNN [NT et al., 2019b], Union-NET [Li et al., 2021], PIGNN [Du et al., 2021], CLNode [Wei et al., 2023], RNCGLN [Zhu et al., 2024], CGNN [Yuan et al., 2023], CRGNN [Li et al., 2024], TSS [Wu et al., 2024], ERASE [Chen et al., 2024], R2LN [Cheng et al., 2024], ProCon [Li et al., 2025].

To ensure a fair and rigorous comparison, for baselines included in the NoisyGL benchmark [Wang et al., 2024], we report the results directly from the original paper. For recent methods not covered by NoisyGL, we reproduce their results using their official implementations, strictly adhering to the experimental settings of NoisyGL. Implementation specifics of our method, including hyperparameter grid search ranges and optimization setups, are detailed in Supplementary Sec. B.2.

4.2 Performance Comparison (RQ1)

Main Result

Table 1 reports the test accuracy (mean ± std over 10 runs). NAEM consistently outperforms all baselines on five datasets under 30% noise. For instance, on Amazon-Computers (30%

uniform noise), NAEM surpasses the runner-up CLNode by 4.65% (84.96% vs. 80.31%). Furthermore, NAEM demonstrates superior robustness against pair noise; on Citeseer (30% pair noise), it achieves 61.54%, significantly exceeding GCN (53.66%) and RTGNN (48.39%). Additionally, lower standard deviations confirm the stability of our principled probabilistic framework in modeling latent labels. Additional scalability results on the large-scale OGBN-Arxiv benchmark are provided in Supplementary Sec. B.4. The comparison with baselines demonstrates good scalability of our method on large-scale datasets.

Robustness against Varying Noise Rates

To evaluate model robustness, we varied noise rates from 0% to 50% as shown in Figure 3. NAEM consistently outperforms baselines in both settings. Under Uniform Noise, NAEM exhibits remarkable stability, widening the performance gap as noise intensity increases. In the more challenging Pair Noise scenarios, while all methods degrade due to structured label flipping, NAEM maintains a distinct lead over SOTA competitors. Competitive performance on clean data (0% noise) confirms that our method effectively handles noise without compromising the clean signal. To further test robustness beyond homophilic graphs, we report supplementary results on the heterophilic Flickr benchmark in Supplementary Sec. B.3. Comprehensive results on five datasets are detailed in Supplementary Sec. B.8.

4.3 Analysis of Noise Propagation (RQ2)

To verify noise mitigation, we analyze performance across five subgroups [Wang et al., 2024]: Accuracy of Correct (ACLT) and Incorrect (AILT) Labeled Training nodes, as well as Accuracy of Unlabeled Correct Supervised (AUCS), Incorrect Supervised (AUIS), and Unsupervised (AUU) nodes.

Table 2 presents results on Cora and Amazon-Computers under 30% uniform noise. NAEM demonstrates superior accuracy maintenance under incorrect supervision, evidenced by significantly higher scores in AILT and AUIS compared to baselines. High AILT indicates that our framework effectively corrects noisy labels during EM rather than overfitting. Crucially, the substantial margin on AUIS confirms that the Neighborhood Agreement mechanism successfully blocks erroneous signal propagation from incorrect neighbors. Furthermore, robust AUU performance demonstrates effective global representation learning without direct supervision.

.

4.4 Ablation Studies (RQ3)

Table 3 compares NAEM against three variants to assess module contributions:

w/o Agreement (Standard EM) removes the structural prior qneighbor, reverting to a standard EM algorithm. Its significant performance drop, particularly on Cora (12.09% decrease under Pair Noise), confirms that standard EM suffers from posterior collapse in a graph without structural guidance.

w/o T-Estimation fixes the transition matrix T to the initial matrix. While effective on uniform noise, it fails on pair noise (2.38% drop on Pubmed), underscoring the need for adaptive noise modeling.

w/o Latent Variable replaces the soft posterior q(Y ) with hard pseudo-labels. Consistent degradation verifies that modeling uncertainty via soft assignments is crucial.

The full NAEM framework consistently achieves the best performance. Additional ablation studies on GNN backbones (GCN, GAT, GraphSAGE) are in Supplementary Sec. B.5, confirming that our framework consistently enhances performance across various architectures and datasets.

4.5 Quantitative Analysis (RQ4) Quality of Latent Posterior

To verify NAEM recovers latent ground truth rather than overfitting, we monitor Correction Accuracy, which is defined as the accuracy of hard labels inferred from posterior q(Y ) against true labels on initially corrupted nodes. Figure 4 compares NAEM with Standard EM on AmazonPhotos. Standard EM displays a characteristic rise-and-fall pattern that peaks mid-training before degrading, signifying posterior collapse as the model overfits noisy supervision. Conversely, NAEM sustains high accuracy following a rapid ascent. Under 40% Pair Noise, NAEM maintains accuracy near 0.7, whereas the baseline remains below 0.1. This validates Neighborhood Agreement as a structural regularizer: by calibrating uncertainty via consensus, NAEM prevents posterior degeneration toward noise, enabling iterative refinement toward ground truth. Qualitatively, t-SNE visualization in Supplementary Sec. B.6 demonstrates that NAEM learns more compact, discriminative representations than baselines, aligning noisy nodes with true semantic clusters.

Noise Transition Matrix Estimation

To validate whether NAEM can capture the underlying noise patterns, we compare the learned transition matrix ˆT with the ground truth TGT on the Amazon-Photos dataset under 20% Pair and Uniform noise. Figure 5 visualizes these matrices as heatmaps. For Pair noise, while NAEM underestimates the absolute noise magnitude, it correctly captures the structured pairwise flipping pattern via the dominant offdiagonal elements. Similarly, under uniform noise, the model successfully estimates the dispersed noise distribution. This ability to reconstruct the true noise dynamics allows NAEM to decouple corruption from semantic features, thereby explaining away systematic biases in the labels and ensuring robust learning. Sensitivity analyses for Ewarm, λNA, γ, τhigh, and τlow are provided in Supplementary Sec. B.7, confirming NAEM's robustness across broad hyperparameter settings.

5 Conclusion

We presented NAEM, a probabilistic framework that treats graph label denoising as latent variable inference rather than heuristic sample selection or indiscriminate smoothing. By integrating Neighborhood Agreement into EM, NAEM calibrates posterior uncertainty, mitigates topology-dependent noise propagation, and jointly estimates the noise transition matrix to disentangle corruption from semantic representations. Extensive experiments demonstrate consistent robustness under diverse noise settings. Future work will study open-set noise and broader heterophilic regimes.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No. U2433212), in part by the Fundamental Research Funds for the Central Universities, and in part by the State Key Laboratory of Complex & Critical Software Environment.