Label Ensemble Perspective for Reduced-Complexity Graph Node Classification under Label Noise

Rui Zhao; Bin Shi; Zhiming Liang; Jianfei Ruan; Kai Sun; Bo Dong; Lu Lin

cs.LGNov 17, 2024

Label Ensemble Perspective for Reduced-Complexity Graph Node Classification under Label Noise

Authors: Rui Zhao, Bin Shi, Zhiming Liang, Jianfei Ruan, Kai Sun, Bo Dong, Lu Lin

Organizations: School of Computer Science and Technology, Xi’an Jiaotong University, China · Ministry of Education Key Laboratory of Intelligent Networks and Network Security, China · Shaanxi Province Key Laboratory of Big Data Knowledge Engineering, China · School of Distance Education, Xi’an Jiaotong University, China ·

Abstract

Graph Neural Networks (GNNs) have been widely employed for semi-supervised node classification tasks on graphs. However, the performance of GNNs is significantly affected by label noise, that is, a small amount of incorrectly labeled nodes can substantially misguide model training. Mainstream solutions define node classification with label noise (NCLN) as a reliable labeling task, often introducing node similarity with quadratic computational complexity to more accurately assess label reliability. To this end, in this paper, we introduce the Label Ensemble Graph Neural Network (LEGNN), a lower complexity method for robust GNNs training against label noise. LEGNN reframes NCLN as a label ensemble task, gathering informative multiple labels instead of constructing a single reliable label, avoiding high-complexity computations for reliability assessment. Specifically, LEGNN conducts a two-step process: bootstrapping neighboring contexts and robust learning with gathered multiple labels. In the former step, we apply random neighbor masks for each node and gather the predicted labels as a high-probability label set. This mitigates the impact of inaccurately labeled neighbors and diversifies the label set. In the latter step, we utilize a partial label learning based strategy to aggregate the high-probability label information for model training. Additionally, we symmetrically gather a low-probability label set to counteract potential noise from the high-probability label set. Extensive experiments on six datasets demonstrate that LEGNN achieves strong classification performance while maintaining computational efficiency. Moreover, it exhibits good scalability on datasets with over one hundred thousand nodes and one million edges.

Figures & tables

Figure 1: Comparison of our label ensemble method with existing reliable labeling methods. Node colors represent labels; symbols “✓” and “×” indicate correct and incorrect labels, respectively. Intuitively, our method avoids directly mistaking erroneous labels as correct by label ensemble. In (b), RTGNN [ 29 ] and Confidence are reliable labeling strategies, with experimental details consistent with those in Section 5.5 .

Figure 2: The overall framework of LEGNN. Nodes are colored differently to indicate their distinct labels, with white representing target nodes to be labeled. LEGNN first generates a masked graph by bootstrapping the neighborhood context. It then infers label probabilities on the masked graph to identify high- and low-probability label sets for the target nodes. Here, the nodes, whose labels match the label with the highest predicted probability for the target node, are masked as “H”, while the node with the lowest predicted probability for the target node marked as “L”. Finally, robust model training is performed using the PLL-based strategy with these two label sets.

Dataset	Nodes	Edges	Features	$C$	Actual Noise Rate(%)
					Sym					Pair				IDN
					10%	20%	30%	40%	50%	10%	20%	30%	40%	10%	20%	30%	40%	50%
Cora	2,485	5,068	1,433	7	8.94	22.58	32.52	42.14	53.66	12.90	18.70	27.82	36.59	8.13	19.96	27.64	39.92	50.41
Citeseer	2,110	3,668	3,703	6	5.71	24.70	33.33	41.57	56.19	12.11	20.00	28.50	35.24	7.62	20.95	28.57	36.19	48.57
Pubmed	19,717	44,338	500	3	11.68	19.15	27.41	39.23	51.27	10.45	17.26	29.52	39.59	11.17	18.27	31.47	44.67	51.78
IGB	100,000	547,416	1,024	19	9.98	20.10	29.49	39.72	50.23	10.08	19.68	29.51	38.91	10.24	20.12	29.35	39.71	49.83

Table 1: Statistics of datasets.

C

denotes number of classes.

Dataset	Method	Clean	Sym-20%	Sym-50%	Pair-20%	Pair-40%	IDN-20%	IDN-50%
Cora	GCN	81.32 ± 1.15	71.47 ± 1.66	53.05 ± 3.89	76.00 ± 1.11	58.08 ± 1.51	74.88 ± 0.97	50.96 ± 4.87
	Self-training	78.21 ± 1.53	72.52 ± 1.42	53.46 ± 3.29	76.03 ± 0.97	58.56 ± 1.99	75.63 ± 0.67	53.27 ± 4.46
	Forward	81.50 ± 1.20	72.19 ± 0.83	52.54 ± 4.66	75.20 ± 1.55	57.75 ± 1.25	75.40 ± 1.21	52.81 ± 4.19
	CP	79.97 ± 1.31	68.58 ± 1.50	47.81 ± 2.11	73.69 ± 0.09	53.50 ± 1.85	72.54 ± 0.89	50.64 ± 4.35
	Coteaching+	78.21 ± 1.53	67.87 ± 1.91	51.07 ± 4.44	72.88 ± 2.50	52.76 ± 6.17	72.20 ± 1.26	46.37 ± 2.66
	NRGNN	81.31 ± 0.89	80.02 ± 0.77	64.72 ± 2.26	79.50 ± 1.85	66.06 ± 2.88	79.58 ± 1.13	62.61 ± 1.81

Table 2: Classification accuracy (%)

\pm

standard deviation under different noise settings.

Dataset	Method	Clean	Sym-20%	Sym-50%	Pair-20%	Pair-40%	IDN-20%	IDN-50%
IGB	GCN	67.65 ± 0.27	65.94 ± 0.14	57.30 ± 4.36	66.22 ± 0.40	59.57 ± 0.76	65.58 ± 0.38	63.02 ± 0.41
	Self-training	67.63 ± 0.29	67.12 ± 0.24	64.52 ± 0.40	66.29 ± 0.41	59.54 ± 0.86	67.15 ± 0.38	64.51 ± 0.45
	Forward	67.22 ± 0.29	66.28 ± 0.47	63.82 ± 0.46	66.01 ± 0.46	59.96 ± 3.51	66.54 ± 0.52	63.51 ± 0.60
	CP	66.79 ± 0.17	64.66 ± 0.42	61.31 ± 0.70	64.59 ± 0.53	56.26 ± 0.90	64.69 ± 0.38	60.45 ± 0.76
	Coteaching+	66.71 ± 0.25	66.30 ± 0.35	64.02 ± 0.36	65.44 ± 0.29	58.53 ± 0.77	66.45 ± 0.31	63.95 ± 0.68
	NRGNN	63.02 ± 1.38	64.79 ± 0.88	63.82 ± 0.49	63.03 ± 1.15	58.11 ± 2.50	63.81 ± 0.76	63.12 ± 0.29

Table 3: Classification accuracy (%)

\pm

standard deviation on large-scale datasets.

GCN	Self-training	Forward	CP	Coteaching+	NRGNN	RTGNN	ProCon	LEGNN
25.07±1.73	27.86±1.92	26.95±1.31	25.27±1.64	25.65±0.98	30.70±0.92	32.72±0.86	36.41 ± 0.36	39.60±1.14

Table 4: The average classification accuracy and standard deviation (%) across five trials for C1mG.

Panel of Figure 3 — Figure 3: The average classification accuracy decreases as the number of labels decreases. Experiments were conducted on the Citeseer dataset, with the left figure representing the Sym-50% noise and the right figure representing the Pair-40% noise. The error bars of standard deviation are shaded in each plot.

	$k$	$2k$	$3k$	$4k$	$5k$
Citeseer	6.54%	12.74%	18.43%	23.88%	29.16%
Pubmed	1.57%	3.06%	4.51%	5.96%	7.36%

Table 5: Comparison of edge construction performance for NRGNN.

	Cora	Citeseer	Pubmed	IGB	OGBN	Total Time Complexity	Space Complexity
GCN (backbone)	3.19	3.02	3.80	3.92	3.89	$O(TLd^{2}N+TLd\|E\|)$	$O(LdN+\|E\|+Ld^{2})$
NRGNN	28.81	30.10	181.01	1109.01	1889.33	$O((F+\log N+TLd)N^{2}+T(Ld^{2}+Kd+C)N+(N+TLd)\|E\|)$	$O(N^{2}+(Ld+K+C)N+\|E\|+Ld^{2})$
RTGNN	92.68	73.30	585.22	3521.11	2602.06	$O((F+\log N)N^{2}+T[Ld^{2}+K(Ld+C)+\log N]N+T(Ld+C)\|E\|)$	$O(N^{2}+(Ld+K)N+\|E\|+Ld^{2})$
ProCon	33.37	34.53	39.27	463.54	1780.37	$O(N^{3}+FN^{2}+T(Ld^{2}+Cd+K+I)N+TLd\|E\|)$	$O(N^{2}+(Ld+K+C)N+\|E\|+Ld^{2})$
LEGNN	5.05	4.81	8.48	60.27	29.40	$O((T+RM_{e})(Ld^{2}+C)N+(T+RM_{e})Ld\|E\|)$	$O((Ld+C)N+\|E\|+Ld^{2})$

Table 6: Average runtime (seconds) over five trials, total time complexity, and space complexity. The shortest time excluding GCN is in bold .

N

|E|

L

, and

C

denote node, edge, GNN layer, and class counts;

F

and

d

denote input and hidden dimensions;

T

denotes training epochs, including initialization.

R

and

M_{e}

denote LEGNN’s label generation rounds and masks per round.

K

denotes per-node neighbor/negative-sampling budgets in NRGNN/RTGNN or peer count in ProCon;

I

denotes ProCon’s GMM iterations. Bounds assume uniform-width GNNs and dense two-hop computation in ProCon; space excludes shared input features.

Method	0.1			0.2			0.3			0.4			0.5
Method	P	R	F1	P	R	F1	P	R	F1	P	R	F1	P	R	F1
RTGNN	85.71	18.48	30.41	85.52	15.12	25.69	80.85	12.61	21.81	75.83	8.63	15.49	75.73	9.76	17.30
Propagation	42.84	75.45	54.65	44.82	77.73	56.86	41.74	74.88	53.60	43.98	75.55	55.60	38.90	66.26	49.02
LEGNN	66.84	80.71	73.12	69.61	78.15	73.63	64.67	75.21	69.54	67.17	77.39	71.92	63.54	72.70	67.81

Table 7: Label construction performance (%) across noise rates: Precision (P), Recall (R), and F1-score.

Method	Sym-10%	Sym-20%	Sym-30%	Sym-40%	Sym-50%
LEGNN	79.99 $\pm$ 0.65	79.65 $\pm$ 0.39	77.85 $\pm$ 1.74	74.54 $\pm$ 4.29	72.70 $\pm$ 5.41
Confidence	75.04 $\pm$ 0.77	73.87 $\pm$ 1.01	68.55 $\pm$ 3.01	67.29 $\pm$ 3.37	57.79 $\pm$ 2.97

Table 8: Comparison of clean label coverage.

Metric	LEGNN	w/o low-prob.	w/o high-prob.	w/o gathering	w/o gather.&low-prob.	GCN
Accuracy (%)	69.62 $\pm$ 3.69	67.06 $\pm$ 3.99	31.54 $\pm$ 2.19	55.49 $\pm$ 1.86	55.47 $\pm$ 1.91	46.78 $\pm$ 0.70

Table 9: Ablation experiments on model components.

	Sym-20%	Sym-50%	Pair-20%	Pair-40%	Running Time
LEGNN	74.70±0.87	69.62±3.69	73.38±1.64	64.82±2.20	4.81
LEGNN-N	75.96±0.28	69.58±3.13	74.56±0.96	67.43±1.99	23.12
LEGNN-W	75.18±0.63	66.84±2.66	75.65±0.47	70.93±2.69	24.44
LEGNN-S	75.49±0.95	66.65±3.67	75.65±0.38	72.23±2.30	19.79

Table 10: The average classification accuracy and standard deviation (in percentage) with different maskings.

		Sym-20%	Sym-50%	Pair-20%	Pair-40%
Cora	GCN	71.47±1.66	53.05±3.89	76.00±1.11	58.08±1.51
	LEGNN-GCN	79.95±1.56	67.93±3.81	79.64±1.00	67.55±0.64
	GAT	72.12±3.08	56.37±5.88	69.05±2.18	53.75±1.78
	LEGNN-GAT	79.08±0.86	68.86±2.75	79.86±1.86	69.43±3.45
	GraphSAGE	70.99±1.80	54.83±5.13	71.11±3.70	55.42±2.80
	LEGNN-GraphSAGE	78.30±0.90	67.45±4.52	78.99±0.96	66.07±4.01

Table 11: The average classification accuracy and standard deviation (expressed in percentage) across five trials of different backbones. Results superior to the baseline are marked with underscores, while the best results are highlighted in bold .

Figure 4: The average accuracy (%) across five trials with different parameters on Citeseer.

	Noise Rate					Graph Density					Class Imbalance
	10%	20%	30%	40%	50%	0.9	0.7	0.5	0.3	0.1	0.1	0.2	0.3	0.4	0.5
Accuracy (%)	76.72	76.06	74.98	75.24	70.02	75.55	73.99	72.09	67.56	64.23	75.84	74.45	73.91	67.16	59.47
Optimal Mask Rate	0.2	0.9	0.3	0.1	0.2	0.5	0.6	0.6	0.2	0.3	0.1	0.5	0.4	0.7	0.7
Optimal Mask Times	25	10	15	25	20	20	5	5	5	5	30	20	15	25	20

Table 12: Optimal setting of mask times and mask rate on Citeseer under different conditions.

		Sym-20%	Sym-50%	Pair-20%	Pair-40%	IDN-20%	IDN-50%
Cora	Before	0.0072	0.0390	0.0117	0.0140	0.0053	0.0027
Cora	Ensemble	0.0008	0.0020	0.0068	0.0087	0.0069	0.0024
Citeseer	Before	0.0042	0.0079	0.0191	0.0126	0.0039	0.0053
Citeseer	Ensemble	0.0034	0.0045	0.0151	0.0110	0.0019	0.0048
Pubmed	Before	0.0100	0.0014	0.0003	0.0041	0.0208	0.0030
Pubmed	Ensemble	0.0092	0.0063	0.0001	0.0011	0.0081	0.0072

Table 13: The variances before and after label ensemble operation.

Graph Neural Networks

Graph Neural Networks learn from graph-structured data by combining information across connected nodes, edges, and larger structures.

See all 751 papers

Oct 16, 2026

A Label Noise Robust Algorithm for Graph Data using Neighborhood Label Distribution

Graph Convolutional Networks (GCNs) have demonstrated exceptional performance on graph-structured data. However, their success heavily relies on the availability of clean labels, an assumption that often fails in real-world scenarios. The learnability of GCNs is intrinsically linked to the neighborhood structure of nodes, making it critical to understand how this structure changes in the presence of label noise. In this work, we investigate how the neighborhood label distribution of a node changes under label noise. We mathematically derive that label noise smooths this distribution, which inherently increases its entropy and severely decreases interclass distinguishability. To address this challenge, we propose Leave-one-out Entropy Node Screening (LENS), an end-to-end framework that identifies noisy nodes by measuring the reduction in neighborhood entropy when a specific node is removed. LENS further incorporates a relabeling mechanism to recover and preserve valuable feature information instead of entirely discarding the identified noisy nodes. Crucially, the end-to-end computational overhead of LENS is remarkably low. Extensive evaluations demonstrate that our algorithm achieves state-of-the-art node classification accuracy while executing an order of magnitude faster than existing noise-robust approaches.

Pintu Kumar, Nandyala Hemachandra

Indian Institute of Technology Bombay

Graph Neural Networks Noisy-Label Learning Node Classification

Ask PDF

Sep 18, 2026

Particle Competition and Cooperation for Robust Graph Convolutional Network Learning Under Label Noise

Graph Convolutional Networks (GCNs) are highly sensitive to label noise, since corrupted supervision can propagate through the graph and degrade learned node representations. This work proposes PCC+GCN, a hybrid framework that uses Particle Competition and Cooperation (PCC) as a graph-based label-refinement stage before GCN training. PCC identifies suspicious labeled nodes through particle domination dynamics and determines whether their labels should be preserved, removed, or reassigned before GCN training. The framework also allows the graph used by PCC to be augmented with feature-based

k

-nearest-neighbor edges, while the GCN itself is trained on the original graph structure and node features. The proposed method was evaluated on ten graph datasets from the NoisyGL benchmark under conventional Uniform, Pair, and Random label noise, as well as under instance-dependent label noise. A detailed hyperparameter analysis was also conducted on Cora, CiteSeer, and PubMed. Under conventional noise, PCC+GCN achieved the highest overall average accuracy and the best average rank among the evaluated methods, with an average gain of

1.67

percentage points over the baseline GCN across the clean setting and all noisy scenarios. Under instance-dependent noise, PCC+GCN remained competitive with the best-performing robust methods while requiring substantially lower execution time, being the fastest robust method on eight of the ten datasets. The results indicate that PCC-based label refinement provides an effective and computationally efficient preprocessing strategy for improving GCN robustness under noisy supervision.

Fabricio Breve

São Paulo State University - UNESP, Rio Claro - SP, Brazil

Learning with Noisy Labels Graph Neural Networks Noisy-Label Learning

Ask PDF

Aug 5, 2026

Towards Trustworthy Hypergraph Neural Networks under Label Noise

Hypergraph neural networks (HGNNs) have demonstrated remarkable capabilities in processing complex higher-order relationships. However, their performance is highly dependent on labeled data, making them vulnerable to label noise. Despite advances in learning with label noise (LLN) and graph learning with label noise (GLN), noisy-label learning on hypergraphs remains underexplored. In this paper, we present a systematic study of hypergraph node classification under label noise. First, we adapt representative LLN and GLN methods to hypergraphs and evaluate them under a unified benchmark, revealing the limitations of existing robust learning strategies for hypergraphs. Building on this, we propose a new hypergraph robust framework, HyperTrust, which first estimates hyperedge trustworthiness through a pretraining-based, entropy-aware strategy, and then incorporates the HyperedgeBoost module to enhance reliable supervision by connecting unlabeled nodes to trustworthy hyperedges, as well as the HyperedgePrune module to suppress noisy propagation by removing untrustworthy node-hyperedge incidences. Finally, two modules work collaboratively to adjust the hypergraph structure and generate final predictions. Extensive experiments and theoretical analysis demonstrate the effectiveness and robustness of HyperTrust on multiple hypergraph datasets under various noisy settings. Our work provides a unified benchmark and an effective solution for hypergraph learning with label noise and lays a foundation for future research in this direction.

Mengyao Zhou, Zhiheng Zhou, Xiao Han +1

Academy of Mathematics and Systems Science, Chinese Academy of Sciences and also with the University of Chinese Academy of Sciences, Beijing 100190, China · School of Mathematics and Statistics, Shandong University, Weihai, Shandong 264209, China · School of Artificial Intelligence, Beihang University, Beijing 100191,China

Graph Structure Learning Hypergraph Neural Networks Learning with Noisy Labels Hypergraph Learning

Ask PDF

Abstract

Graph Neural Networks

Explore similar work

A Label Noise Robust Algorithm for Graph Data using Neighborhood Label Distribution

Particle Competition and Cooperation for Robust Graph Convolutional Network Learning Under Label Noise

Towards Trustworthy Hypergraph Neural Networks under Label Noise