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 752 papers

A Label Noise Robust Algorithm for Graph Data using Neighborhood Label Distribution
Oct 16, 2026Pintu Kumar, Nandyala HemachandraGraph Neural Networks Noisy-Label Learning
Indian Institute of Technology Bombay
Particle Competition and Cooperation for Robust Graph Convolutional Network Learning Under Label Noise
Sep 18, 2026Fabricio BreveLearning with Noisy Labels Graph Neural Networks
São Paulo State University - UNESP, Rio Claro - SP, Brazil
Towards Trustworthy Hypergraph Neural Networks under Label Noise
Aug 5, 2026Mengyao Zhou, Zhiheng Zhou, Xiao Han +1Graph Structure Learning Hypergraph Neural Networks
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

Oct 16, 2026J/K move · Enter open · S save

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

Pintu Kumar, Nandyala Hemachandra

Indian Institute of Technology Bombay

Graph Neural Networks Noisy-Label Learning Node Classification

Open paper AskPDF arXiv

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.

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