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

• URL: http://arxiv.org/abs/2604.06596v1
• Date: Wed, 08 Apr 2026 02:29:49 GMT
• Title: DynLP: Parallel Dynamic Batch Update for Label Propagation in Semi-Supervised Learning
• Abstract summary: Semi-supervised learning aims to infer class labels using only a small fraction of labeled data.<n>In graph-based learning, this is typically achieved through label propagation to predict labels of unlabeled nodes.<n>In real-world applications, data often arrive incrementally in batches.
• Score: 10.048367797959896
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• PaSta: Noisy Node Classification with Partial Label Learning [58.43127707101144]
  We propose a novel Partial label-based Self-training framework to overcome the limitations of existing methods.<n>PaSta achieves an average improvement of 1.1% in classification performance under various noise settings.
  arXiv  Detail & Related papers  (2026-08-26T04:40:23Z)
• Echoless Label-Based Pre-computation for Memory-Efficient Heterogeneous Graph Learning [70.73716819236627]
  Heterogeneous Graph Neural Networks (HGNNs) are widely used for deep learning on heterogeneous graphs.<n>HGNNs require repetitive message passing during training, limiting efficiency for large-scale real-world graphs.<n>We propose pre-computation-based HGNNs that only perform message passing once during preprocessing.
  arXiv  Detail & Related papers  (2025-11-14T08:53:39Z)
• Keep It on a Leash: Controllable Pseudo-label Generation Towards Realistic Long-Tailed Semi-Supervised Learning [88.48555005545694]
  We propose a Controllable Pseudo-label Generation (CPG) framework to expand the labeled dataset with reliable pseudo-labels from the unlabeled dataset.<n>CPG operates through a controllable self-reinforcing optimization cycle.<n>CPG achieves consistent improvements, surpassing state-of-the-art methods by up to $textbf15.97%$ in accuracy.
  arXiv  Detail & Related papers  (2025-10-05T01:52:19Z)
• Label merge-and-split: A graph-colouring approach for memory-efficient brain parcellation [3.2506898256325933]
  Whole brain parcellation requires inferring hundreds of segmentation labels in large image volumes. We introduce label merge-and-split, a method that first greatly reduces the effective number of labels required for learning-based whole brain parcellation.
  arXiv  Detail & Related papers  (2024-04-16T13:47:27Z)
• ERASE: Error-Resilient Representation Learning on Graphs for Label Noise Tolerance [53.73316938815873]
  We propose a method called ERASE (Error-Resilient representation learning on graphs for lAbel noiSe tolerancE) to learn representations with error tolerance. ERASE combines prototype pseudo-labels with propagated denoised labels and updates representations with error resilience. Our method can outperform multiple baselines with clear margins in broad noise levels and enjoy great scalability.
  arXiv  Detail & Related papers  (2023-12-13T17:59:07Z)
• Adaptive Anchor Label Propagation for Transductive Few-Shot Learning [18.29463308334406]
  Few-shot learning addresses the issue of classifying images using limited labeled data. We propose a novel algorithm that adapts the feature embeddings of the labeled data by minimizing a differentiable loss function. Our algorithm outperforms the standard label propagation algorithm by as much as 7% and 2% in the 1-shot and 5-shot settings respectively.
  arXiv  Detail & Related papers  (2023-10-30T20:29:31Z)
• Learning from Label Proportions: Bootstrapping Supervised Learners via Belief Propagation [18.57840057487926]
  Learning from Label Proportions (LLP) is a learning problem where only aggregate level labels are available for groups of instances, called bags, during training. This setting arises in domains like advertising and medicine due to privacy considerations. We propose a novel algorithmic framework for this problem that iteratively performs two main steps.
  arXiv  Detail & Related papers  (2023-10-12T06:09:26Z)
• All Points Matter: Entropy-Regularized Distribution Alignment for Weakly-supervised 3D Segmentation [67.30502812804271]
  Pseudo-labels are widely employed in weakly supervised 3D segmentation tasks where only sparse ground-truth labels are available for learning. We propose a novel learning strategy to regularize the generated pseudo-labels and effectively narrow the gaps between pseudo-labels and model predictions.
  arXiv  Detail & Related papers  (2023-05-25T08:19:31Z)
• Adaptive Label Smoothing To Regularize Large-Scale Graph Training [46.00927775402987]
  We propose the adaptive label smoothing (ALS) method to replace the one-hot hard labels with smoothed ones. ALS propagates node labels to aggregate the neighborhood label distribution in a pre-processing step, and then updates the optimal smoothed labels online to adapt to specific graph structure.
  arXiv  Detail & Related papers  (2021-08-30T23:51:31Z)
• Noise-robust Graph Learning by Estimating and Leveraging Pairwise Interactions [123.07967420310796]
  This paper bridges the gap by proposing a pairwise framework for noisy node classification on graphs. PI-GNN relies on the PI as a primary learning proxy in addition to the pointwise learning from the noisy node class labels. Our proposed framework PI-GNN contributes two novel components: (1) a confidence-aware PI estimation model that adaptively estimates the PI labels, and (2) a decoupled training approach that leverages the estimated PI labels.
  arXiv  Detail & Related papers  (2021-06-14T14:23:08Z)
• Semantics through Time: Semi-supervised Segmentation of Aerial Videos with Iterative Label Propagation [16.478668565965243]
  This paper makes an important step towards automatic annotation by introducing SegProp. SegProp is a novel iterative flow-based method, with a direct connection to spectral clustering in space and time. We introduce Ruralscapes, a new dataset with high resolution (4K) images and manually-annotated dense labels every 50 frames. Our novel SegProp automatically annotates the remaining unlabeled 98% of frames with an accuracy exceeding 90%.
  arXiv  Detail & Related papers  (2020-10-02T15:15:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.