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, new data often arrives in batches, and stale data often becomes irrelevant. 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 13 x and upto 102 x speedup on large-scale datasets compared to state-of-the-art approaches.
Recommended Citation
S. M. Shovan et al., "DynLP: Parallel Dynamic Batch Update For Label Propagation In Graph-based Semi-Supervised Learning," Proceedings of the International Conference on Supercomputing, pp. 740 - 751, Association for Computing Machinery, Jul 2026.
The definitive version is available at https://doi.org/10.1145/3797905.3807875
Department(s)
Computer Science
Publication Status
Open Access
Keywords and Phrases
GPU; label propagation; semi-supervised learning
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2026 The Author(s), All rights reserved.
Creative Commons Licensing
This work is licensed under a Creative Commons Attribution 4.0 License.
Publication Date
05 Jul 2026
Comments
Pacific Northwest National Laboratory, Grant 2104078