DynLP: Parallel Dynamic Batch Update for Label Propagation in Semi-Supervised Learning

S M Shovan; Arindam Khanda; S M Ferdous; Sajal K. Das; Mahantesh Halappanavar

cs.DCApr 8, 2026

DynLP: Parallel Dynamic Batch Update for Label Propagation in Semi-Supervised Learning

Authors: S M Shovan, Arindam Khanda, S M Ferdous, Sajal K. Das, Mahantesh Halappanavar

Organizations: Missouri University of Science and Technology, Rolla, MO, USA · Pacific Northwest National Laboratory, USA

Abstract

Semi-supervised learning aims to infer class labels using only a small fraction of labeled data. In graph-based semi-supervised learning, this is typically achieved through label propagation to predict labels of unlabeled nodes. However, in real-world applications, data often arrive incrementally in batches. Each time a new batch appears, reapplying the traditional label propagation algorithm to recompute all labels is redundant, computationally intensive, and inefficient. To address the absence of an efficient label propagation update method, we propose DynLP, a novel GPU-centric Dynamic Batched Parallel Label Propagation algorithm that performs only the necessary updates, propagating changes to the relevant subgraph without requiring full recalculation. By exploiting GPU architectural optimizations, our algorithm achieves on average 13x and upto 102x speedup on large-scale datasets compared to state-of-the-art approaches.

Figures & tables

Panel of Figure 1 — Figure 1. Evolution of the label-propagation algorithm over six iterations.

Panel of Figure 2 — Figure 2. CUDA Kernel design for sparsification and connected component finding

Figure 3. Block level granularity to process nodes in the frontier list

Panel of Figure 4 — Figure 4. Memory latency hiding

Method	Incremental	Decremental	Parallelism	Update	Target graph	Memory Optim.
ItLP ( Zhu et al., 2003a )	✓	✗	✗	✗	Dense	Compression
CAGNN ( Zhu et al., 2020 )	✓	✗	✓	✗	Dense	Compression
A2LP ( Zhang et al., 2020 )	✓	✗	✓	✗	Sparse	KNN
StLP ( Wagner et al., 2018 )	✓	✓	✓	✗	Dense	N/A
Approx StLP ( Ponte et al., 2024 )	✓	✓	✓	✗	Dense	Sparse Inverse
DynLP [this work]	✓	✓	✓	✓	Sparse	CSR

Table 1. Baseline methods compared with DynLP .

Dataset	$\|V\|$	$\|E\|$
IMDB Review ( Maas et al., 2011 )	50,000	125K
ImageNet ( Deng et al., 2009 )	50,000	125K
Yelp Review ( mhamine, n.d. )	6,990,280	17M
Amazon Household Review ( Hou et al., 2024 )	25,600,000	64M
Amazon Book Review ( Hou et al., 2024 )	29,500,000	73M
Random Dataset	50,000,000	{75M,62M,175M}

Table 2. Dataset description

Panel of Figure 5 — Figure 5. Iterations and execution time of DynLP across datasets.

Panel of Figure 6 — Figure 6. Impact of $\delta$ on DynLP

Panel of Figure 7 — Figure 7. Iteration and speedup comparison between DynLP and ItLP as vertex count varies.

Panel of Figure 8 — Figure 8. Speedup comparison between DynLP and StLP

Panel of Figure 9 — Figure 9. Performance comparison with machine learning methods

Dataset	ItLP	StLP	DynLP	CAGNN
IMDB	652.25	3,196.41	439.21	8,545.53
Yelp	18,283.94	23,182.12 ( $\gamma=10$ )	3,712.82	40,853.31
Household	678,939.29	-	18,232.38	-
Book	783,925.09	-	19,927.31	-

Table 3. Execution time comparison across datasets.

Method	50K		500K		5M
	T(ms)	A	T(ms)	A	T(ms)	A
ItLP	1,120	100	4,738	100	11,929	100
StLP	1,637	100	–	–	–	–
StLP ( $\gamma=0.1$ )	5,637	72.9	–	–	–	–
StLP ( $\gamma=1.0$ )	3,989	83.5	–	–	–	–
StLP ( $\gamma=10.0$ )	1,563	56.3	5,989	54.2	21,637	49.5

Table 4. Performance comparison on random graph with varied batch sizes (T: Execution time, A: Accuracy)

Method	Accuracy		Speedup		Max Graph Size
	Avg	Max	Avg	Max	Node	Degree
ItLP	100	100	13	102	50M	7
StLP	100	100	7	39	50K	5
StLP ( $\gamma$ )	70	83	7	7	7M	5
CAGNN	76	88	32	32	5M	5
A2LP	56	58	1,935	1,935	50K	5

Table 5. Comparison summary table

Graph-Based Label Propagation

See all 16 papers

F\textsuperscript{2}LP-AP: Fast & Flexible Label Propagation with Adaptive Propagation Kernel
Apr 22, 2026Yutong Shen, Ruizhe Xia, Jingyi Liu +1Graph-Based Semi-Supervised Learning Semi-Supervised Learning
Beijing University of Technology
Algebraic Multigrid Acceleration for Efficient Label Spreading
Aug 26, 2026Antonia van Betteray, Jonathan Klees, Miriam Schäfers +1Graph-Based Semi-Supervised Learning
Osnabrück University, Institute for Computer Science, Osnabrück, Germany · Ruhr University Bochum, Institute for Computer Science, Bochum, Germany
SLeDGe: Semi-Supervised Learning on Data Streams with Graph Structure Learning
Jun 19, 2026Heechan Moon, Kijung ShinGraph Structure Learning Graph-Based Semi-Supervised Learning
KAIST, Seoul, Republic of Korea

Apr 22, 2026J/K move · Enter open · S save

F\textsuperscript{2}LP-AP: Fast & Flexible Label Propagation with Adaptive Propagation Kernel

Yutong Shen, Ruizhe Xia, Jingyi Liu, Yinqi Liu

Beijing University of Technology

Graph-Based Semi-Supervised Learning Semi-Supervised Learning Node Classification Graph Heterophily Graph-Based Label Propagation

Open paper AskPDF arXiv

Semi-supervised node classification is a foundational task in graph machine learning, yet state-of-the-art Graph Neural Networks (GNNs) are hindered by significant computational overhead and reliance on strong homophily assumptions. Traditional GNNs require expensive iterative training and multi-layer message passing, while existing training-free methods, such as Label Propagation, lack adaptability to heterophilo-us graph structures. This paper presents \textbf{F

^2

LP-AP} (Fast and Flexible Label Propagation with Adaptive Propagation Kernel), a training-free, computationally efficient framework that adapts to local graph topology. Our method constructs robust class prototypes via the geometric median and dynamically adjusts propagation parameters based on the Local Clustering Coefficient (LCC), enabling effective modeling of both homophilous and heterophilous graphs without gradient-based training. Extensive experiments across diverse benchmark datasets demonstrate that \textbf{F

^2

LP-AP} achieves competitive or superior accuracy compared to trained GNNs, while significantly outperforming existing baselines in computational efficiency.

Abstract

Graph-Based Label Propagation

Explore similar work

F\textsuperscript{2}LP-AP: Fast & Flexible Label Propagation with Adaptive Propagation Kernel

Algebraic Multigrid Acceleration for Efficient Label Spreading

SLeDGe: Semi-Supervised Learning on Data Streams with Graph Structure Learning