Graph-Based Label Propagation

Follow this topic Ask about this topic

Latest papers

16 papers3 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Oct 14, 2026

Revisiting Simple Baselines for Relational Deep Learning

Relational deep learning has emerged as a powerful paradigm for learning end-to-end predictive models over relational databases by representing them as temporal heterogeneous graphs. Recent advances based on graph neural networks and Transformers have achieved strong performance across diverse domains. However, the effectiveness of simpler relational baselines remains underexplored, making it difficult to assess how much architectural complexity is needed to achieve strong predictive performance. Motivated by the observation that predictive signals arise from target attributes, relational attributes, and historical labels, we revisit how effectively these signals can be exploited using simple propagation methods. We adapt fixed low-pass feature propagation to relational entity graphs and train an MLP for prediction. The resulting predictions are further refined using Correct-and-Smooth, a graph-based label propagation algorithm that incorporates historical labels over task-specific meta-graphs connecting target entities. Across classification and regression tasks on RelBench, an MLP trained on neighborhood-filtered features outperforms one using only target-entity features on most tasks and recovers a substantial portion of the performance of heterogeneous GNNs. Correct-and-Smooth provides further gains from historical labels, although applying it requires a separately constructed meta-graph because connections among target entities are not directly specified by the relational entity graph. Together, our studies revisit the effectiveness of established propagation methods as simple RDL baselines while identifying canonical meta-graph construction as a key challenge for effective label propagation.

Viet The Nguyen, Vijay Prakash Dwivedi, Gunther Gust

University of Würzburg · Seamless Labs, Inc. · Stanford University

Graph-Based Label Propagation Relational Deep Learning

Oct 9, 2026

What Egocentric Video Embeddings Encode and How to Combine Them with Inertial Sensors for Human Activity Recognition

Egocentric video and body-worn inertial sensors are increasingly recorded together, and the video is usually encoded by pretrained models. What these embeddings represent when the camera sits on the head, and how they should be combined with inertial sensing, has received little attention. Across VideoMAEv2, CLIP, DINOv2 and the egocentric VC-1, the leading principal directions of the embedding are dominated by where the camera looks. Measured head orientation explains them on Ego-Exo4D for egocentric (R^2 0.49-0.70) but not exocentric cameras, and the scene layout explains them on WEAR. The part that the limbs' inertial signals predict separates activities across people. In a set-level probe, the rest separates exercise sets within a participant but not activities across people. This is consistent with separate roles: the video finds the clips of the same set, and the inertial classifier labels them. On WEAR, with temporal order removed and one random limb per one-second clip, we propagate inertial predictions over a within-participant video graph whose leading components are removed. This raises subject-wise cross-validated macro-F1 from 0.648 to 0.852. In our comparisons, propagation helps only over the video graph, and fusing the modalities in one classifier, or adding inertial edges to the graph, performs worse.

Kansuke Habano

Independent Researcher, Japan

Graph-Based Label Propagation Human Activity Recognition Egocentric Video Understanding Multimodal Sensor Fusion Video Understanding

Sep 28, 2026

Propagate, Then Sharpen: Post-Hoc Refinement of Frozen Node Classifiers

We study post-hoc refinement of frozen node classifiers: given only the graph

G

and class distributions

Q

predicted by a frozen model, can we improve accuracy without access to node features, model parameters, or gradients? APPNP answers this by propagating logits with a restart towards the initial predictions, minimizing the anchored Dirichlet energy. Instead, we consider the Potts energy, and decompose it into a Dirichlet term, which penalizes disagreement between neighbouring nodes, and a Gini term, which penalizes indecision within each node. This decomposition motivates Propagate, Then Sharpen (PtS), which alternates between propagation of class probabilities and node-wise, mass-preserving sharpening, with only one additional hyperparameter selected using labelled validation nodes. Across nine homophilic graphs, with a frozen MLP backbone, PtS improves mean test accuracy over independently tuned APPNP by

1.71

percentage points on clean inputs and

3.90

under severe Gaussian feature corruption. Gains over APPNP become smaller, but remain positive with frozen GCN and GraphSAGE backbones. Sharpening also removes most of the accuracy loss of deep propagation: on clean inputs without restart, accuracy falls by

2.2

points between

2

and

100

propagation steps under PtS, compared with

33.8

for APPNP.

Preben Johnsen Bentdal, Nello Blaser, Xue-Cheng Tai

Department of Informatics, University of Bergen · Norwegian Research Centre (NORCE)

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

Aug 19, 2026

COSTA: A Cluster-Centric Paradigm for Annotation-Free Open-Set Semantic Segmentation of Aerial Point Clouds with Domain Shifts

Semantic segmentation of aerial point cloud is trapped in a generalization crisis under distinct domain shifts. While test-time adaptation offers a privacy-preserving and computationally efficient way to adapt pre-trained models to unlabeled target-domain data during inference, existing methods, bound to closed-set label assumptions and non-scalable point-wise segmentation pipelines, still struggle with semantic shifts. We ask: can we adapt any given pre-trained aerial point cloud segmentation model to a shifted target domain at the inference phase alone, without additional training, while segmenting target-specific categories beyond the source label space on demand? This paper introduces COSTA, which breaks this limitation by shifting from closed-set point-wise adaptation to cluster-centric open-set semantic propagation. Our core discovery is that, once effectively adapted at test time, the rich feature distribution of aerial point clouds can be distilled into a compact set of well-separated semantic centroids that are transferable across label spaces. COSTA leverages this to reformulate open-set semantic segmentation as a cluster-level propagating process: it first bridges the domain gap through proven test-time adaptation, then groups each batch of target-domain points into a small set of semantic clusters based on the similarity distribution in the adapted feature space, and finally propagates high-confidence pseudo labels obtained from an open-vocabulary vision-language model to all points through cluster-level voting. This cluster-centric paradigm enables test-time adaptation of aerial point clouds under significant domain gaps with mixed semantic shifts. With DALES as the source domain, COSTA enables on-demand segmentation across three aerial point cloud benchmarks with distinct domains and heterogeneous category spaces, achieving up to 70.09% mIoU under this new setting.

Yanghong Lin, Li Fang, Tianyu Li +2

Fujian Institute of Research on the Structure of Matter, Chinese Academy of Sciences, Fuzhou, 350108, Fujian, China. · Spatial Intelligence and Urban Computing, Institute of Urban Environment, Chinese Academy of Sciences, Xiamen, 361021, Fujian, China. · State Key Lab for Ecological Security of Regions and Cities, Institute of Urban Environment, Chinese Academy of Sciences, Xiamen, 361021, Fujian, China. +2

Graph-Based Label Propagation 3D Point Cloud Segmentation Semantic Segmentation 3D Semantic Segmentation Test-Time Adaptation

Aug 2, 2026

SSR: Similarity-Shift Refinement for Training-Free Object-Centric Masks

Object-centric models often produce fragmented masks, boundary leakage, and incorrect region merging. We introduce Similarity-Shift Refinement (SSR), a training-free post-hoc method for improving object-centric masks with a frozen self-supervised Vision Transformer. SSR measures changes in pairwise patch similarity before and after self-attention value aggregation, retains positively strengthened relations, and constructs a sparse affinity graph. This graph propagates the initial soft slot assignments in a single refinement step, without retraining or modifying either model. Across natural-image, synthetic-video, and real-world-video benchmarks, SSR improves all-pixel Adjusted Rand Index in all 24 evaluated model-dataset combinations, with an average gain of 8.5 percentage points. Ablations show that value-space similarity shifts outperform query- and key-space variants as well as static Transformer affinities. However, texture-dense scenes may cause visually similar regions to be over-grouped. Overall, SSR provides a simple and transferable signal for training-free object-centric mask refinement.

Xiaoqian Lu, Guangfu Guo

University of Ottawa · Clemson University

Graph-Based Label Propagation Image Segmentation Object-Centric Representation Learning

Jul 3, 2026

A Near-Linear-Time Solver for Graph $p$ -Laplacian Semi-Supervised Learning via Continuation in $p$

Graph-based semi-supervised learning (SSL) propagates a few labels over a similarity graph by minimizing a Dirichlet-type energy. The standard quadratic (

p=2

) energy reduces to a single graph-Laplacian solve, but it degenerates exactly where SSL is most useful when labels are scarce: gathering more unlabeled data drives the

p=2

estimate to a near-constant function whenever

d\ge2

(Nadler-Srebro-Zhou). Well-posedness requires the nonlinear

p

-Laplacian energy with

p>d

. Existing solvers reduce this to a sequence of weighted Laplacian solves, but their reference implementations use a direct sparse factorization or ichol-preconditioned CG instead. Plugging a near-linear Laplacian solver is not straightforward: at large

p

the conductance weights degenerate near flat-gradient edges, making the system nearly singular and causing stagnation without a damped outer iteration. We close this gap. Recasting

p

-Laplacian SSL as a source-form nonlinear Laplacian flow

Bρ_p(B^\top x)=b

and solving by damped chord-Newton continuation in

p

, every linearized system stays well-conditioned and can be delegated to a near-linear Laplacian engine. On size-scaled graph families the wall-clock is empirically

m^{0.96}

-

m^{1.02}

per family (approximate Cholesky default), and a pooled fit across 228 SuiteSparse graphs gives

m^{1.19}

vs.\

m^{1.45}

for direct factorization; the solver handles a

6.8\times10^7

-edge social network in minutes. Memory is the binding constraint: Cholesky fill reaches

10

-

280\times

the graph nonzeros vs.\ our

O(m)

hierarchy. Against the released FCL solver we are

1.5

-

14\times

faster at matched accuracy. On MNIST

10

-NN,

p=3

scores

64\%

at one label per class vs.\

36\%

for

p=2

. Code: https://github.com/orenlivne/np.

Oren E. Livne

Pine Birch Analytics, Churchville, PA

Graph-Based Semi-Supervised Learning Semi-Supervised Learning Graph-Based Label Propagation

Jul 1, 2026

Multi-Label Node Classification with Label Influence Propagation

Graphs are a complex and versatile data structure used across various domains, with possibly multi-label nodes playing a particularly crucial role. Examples include proteins in PPI networks with multiple functions and users in social or e-commerce networks exhibiting diverse interests. Tackling multi-label node classification (MLNC) on graphs has led to the development of various approaches. Some methods leverage graph neural networks (GNNs) to exploit label co-occurrence correlations, while others incorporate label embeddings to capture label proximity. However, these approaches fail to account for the intricate influences between labels in non-Euclidean graph data. To address this issue, we decompose the message passing process in GNNs into two operations: propagation and transformation. We then conduct a comprehensive analysis and quantification of the influence correlations between labels in each operation. Building on these insights, we propose a novel model, Label Influence Propagation (LIP). Specifically, we construct a label influence graph based on the integrated label correlations. Then, we propagate high-order influences through this graph, dynamically adjusting the learning process by amplifying labels with positive contributions and mitigating those with negative influence. Finally, our framework is evaluated on comprehensive benchmark datasets, consistently outperforming SOTA methods across various settings, demonstrating its effectiveness on MLNC tasks.

Yifei Sun, Zemin Liu, Bryan Hooi +4

Zhejiang University · National University of Singapore · Capital One +1

Graph-Based Label Propagation Multi-Label Classification Graph Neural Networks Node Classification

Jun 12, 2026

MaskedFOP: Polyglot Speaker Identification under Missing Visual Modality via Cascaded Graph Label Propagation

We present MaskedFOP, a system for closed-set polyglot speaker identification under two simultaneous challenges: the face modality is entirely absent at test time, and speech comes from Urdu, a language unseen during face-supervised training. The system integrates three complementary mechanisms. First, a modality-dropout dual-head network built on the Fusion and Orthogonal Projection (FOP) backbone forces the audio branch to develop independent discriminative power via per-sample face masking, ensuring that the audio encoder remains capable when face is absent. Second, two MaskedFOP instances trained on Emphasized Channel Attention, Propagation, and Aggregation in Time Delay Neural Network (ECAPA-TDNN) features with different random seeds produce complementary audio embeddings whose element-wise average yields a more robust 512-dimensional representation than any single model. Third, a two-stage cascaded inference procedure first refines multimodal labels through a fused Graph Label Propagation (GLP) pass (Stage 1), then assigns audio-only labels by cosine nearest-centroid (Stage 2), replacing the 70 sparse training prototypes with ~1,500 in-domain test-set centroids from Stage 1. Submitted to the POLY-SIM 2026 Grand Challenge, the system achieves a mean P-accuracy of 0.9989, placing first among all submissions evaluated on the challenge server. An ablation identifies cascaded seeding as the single largest gain (>8 pp on P4/P6). The code is available at https://github.com/Ayoub-Elkhouzari/POLY-SIM2026.

Ayoub Elkhouzari, Youssef Iraqi, Loubna Mekouar

College of Computing, University Mohammed VI Polytechnic

Missing-Modality Learning Graph-Based Label Propagation Speech Processing

May 1, 2026

Towards Robust and Scalable Density-based Clustering via Graph Propagation

We present CluProp, a novel framework that reimagines varied-density clustering in high-dimensional spaces as a label propagation process over neighborhood graphs. Our approach formally bridges the gap between density-based clustering and graph connectivity, leveraging efficient propagation mechanisms from network science to mitigate the parameter sensitivity inherent in traditional density-based methods. Specifically, we introduce a deterministic density-based propagation strategy to ensure scalable neighborhood identification. The framework is agnostic to the choice of distance metric and exhibits superior performance on large-scale data, processing millions of points in minutes while consistently outperforming existing baselines in accuracy.

Yingtao Zheng, Hugo Phibbs, Ninh Pham

School of Computer Science, University of Auckland, New Zealand. · Department of Mathematics and Computer Science, University of Southern Denmark, Denmark.

Graph-Based Label Propagation Clustering Unsupervised Clustering Density-Based Clustering

Apr 22, 2026

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

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.

Yutong Shen, Ruizhe Xia, Jingyi Liu +1

Beijing University of Technology

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

Apr 16, 2026

MapSR: Prompt-Driven Land Cover Map Super-Resolution via Vision Foundation Models

High-resolution (HR) land-cover mapping is often constrained by the high cost of dense HR annotations. We revisit this problem from the perspective of map super-resolution, which enhances coarse low-resolution (LR) land-cover products into HR maps at the resolution of the input imagery. Existing weakly supervised methods can leverage LR labels, but they typically use them to retrain dense predictors with substantial computational cost. We propose MapSR, a prompt-driven framework that decouples supervision from model training. MapSR uses LR labels once to extract class prompts from frozen vision foundation model features through a lightweight linear probe, after which HR mapping proceeds via training-free metric inference and graph-based prediction refinement. Specifically, class prompts are estimated by aggregating high-confidence HR features identified by the linear probe, and HR predictions are obtained by cosine-similarity matching followed by graph-based propagation for spatial refinement. Experiments on the Chesapeake Bay dataset show that MapSR achieves 59.64% mIoU without any HR labels, remaining competitive with the strongest weakly supervised baseline and surpassing a fully supervised baseline. Notably, MapSR reduces trainable parameters by four orders of magnitude and shortens training time from hours to minutes, enabling scalable HR mapping under limited annotation and compute budgets. The code is available at https://github.com/rikirikirikiriki/MapSR.

Ruiqi Wang, Qi Yu, Jie Ma +1

School of Information Science and Technology, Beijing Foreign Studies University, Beijing 100089, China

Graph-Based Label Propagation Land Cover Classification Remote Sensing Weakly Supervised Learning Image Super-Resolution

Apr 8, 2026

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

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.

S M Shovan, Arindam Khanda, S M Ferdous +2

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

Graph-Based Label Propagation Graph-Based Semi-Supervised Learning

Mar 23, 2026

PEARL: Geometry Aligns Semantics for Training-Free Open-Vocabulary Semantic Segmentation

Training-free open-vocabulary semantic segmentation (OVSS) promises rapid adaptation to new label sets without retraining. Yet, many methods rely on heavy post-processing or handle text and vision in isolation, leaving cross-modal geometry underutilized. Others introduce auxiliary vision backbones or multi-model pipelines, which increase complexity and latency while compromising design simplicity. We present PEARL, Procrustes alignment with text-aware Laplacian propagation, a compact two-step inference that follows an align-then-propagate principle. The Procrustes alignment step performs an orthogonal projection inside the last self-attention block, rotating keys toward the query subspace via a stable polar iteration. The text-aware Laplacian propagation then refines per-pixel logits on a small grid through a confidence-weighted, text-guided graph solve: text provides both a data-trust signal and neighbor gating, while image gradients preserve boundaries. In this work, our method is fully training-free, plug-and-play, and uses only fixed constants, adding minimal latency with a small per-head projection and a few conjugate-gradient steps. Our approach, PEARL, sets a new state-of-the-art in training-free OVSS without extra data or auxiliary backbones across standard benchmarks, achieving superior performance under both with-background and without-background protocols.

Gensheng Pei, Xiruo Jiang, Xinhao Cai +3

Department of Electrical and Computer Engineering, Sungkyunkwan University · School of Computing and Artificial Intelligence, Southwest Jiaotong University · School of Computer Science and Engineering, Nanjing University of Science and Technology

Graph-Based Label Propagation Open-Vocabulary Semantic Segmentation Text-Guided Image Segmentation Vision-Language Alignment

Mar 2, 2026

BAED: a New Paradigm for Few-shot Graph Learning with Explanation in the Loop

The challenges of training and inference in few-shot environments persist in the area of graph representation learning. The quality and quantity of labels are often insufficient due to the extensive expert knowledge required to annotate graph data. In this context, Few-Shot Graph Learning (FSGL) approaches have been developed over the years. Through sophisticated neural architectures and customized training pipelines, these approaches enhance model adaptability to new label distributions. However, compromises in \textcolor{black}{the model's} robustness and interpretability can result in overfitting to noise in labeled data and degraded performance. This paper introduces the first explanation-in-the-loop framework for the FSGL problem, called BAED. We novelly employ the belief propagation algorithm to facilitate label augmentation on graphs. Then, leveraging an auxiliary graph neural network and the gradient backpropagation method, our framework effectively extracts explanatory subgraphs surrounding target nodes. The final predictions are based on these informative subgraphs while mitigating the influence of redundant information from neighboring nodes. Extensive experiments on seven benchmark datasets demonstrate superior prediction accuracy, training efficiency, and explanation quality of BAED. As a pioneer, this work highlights the potential of the explanation-based research paradigm in FSGL.

Chao Chen, Xujia Li, Dongsheng Hong +4

Harbin Institute of Technology (Shenzhen), Guangdong, China · The Hong Kong University of Science and Technology, Hong Kong SAR, China · Fuzhou University, Fujian, China +1

Graph-Based Label Propagation Graph Representation Learning GNN Explainability

Oct 6, 2025

Fractional Heat Kernel for Semi-Supervised Graph Learning with Small Training Sample Size

We develop a source-driven fractional heat-kernel framework for semi-super-vised graph learning that combines nonlocal propagation with sustained label information. A fixed nonzero label source compatible with the Laplacian null space prevents asymptotic collapse into that space, providing a mechanism for mitigating oversmoothing at long diffusion times. The fractional order controls the relative modal attenuation and the spectral weighting of the sustained response, while the diffusion time sets the propagation horizon. We characterize conservation laws and equilibria on normalized and disconnected graphs, develop a null-space deflation, and analyze the approximation of the propagators. On Two-Moon, fractional orders improve source-free propagation, while compatible source-driven diffusion exceeds

96\%

mean accuracy with one training label per class at orders

0.8

and

1

. On Cora and CiteSeer, the source-driven pipeline improves mean accuracy over GAT by

9.2

and

8.0

percentage points at one training label per class, with model selection on

500

labeled validation nodes and closely comparable classical and fractional pipeline configurations; it matches GAT on PubMed and trails it at ten and twenty labels per class on Cora. Within GraphHeat, validation-based exponent selection at a common diffusion time yields a paired gain of

1.45

percentage points at one label per class.

Farid Bozorgnia, Vyacheslav Kungurtsev, Shirali Kadyrov +1

Over-Smoothing in GNNs Graph-Based Semi-Supervised Learning Graph-Based Label Propagation Graph Diffusion Graph Neural Networks

Dec 11, 2024

GLL: A Differentiable Graph Learning Layer for Neural Networks

Standard deep learning architectures used for classification generate label predictions with a projection head and softmax activation function. Although successful, these methods fail to leverage the relational information between samples for generating label predictions. In recent works, graph-based learning techniques, namely Laplace learning, have been heuristically combined with neural networks for both supervised and semi-supervised learning (SSL) tasks. However, prior works approximate the gradient of the loss function with respect to the graph learning algorithm or decouple the processes; end-to-end integration with neural networks is not achieved. In this work, we derive backpropagation equations, via the adjoint method, for inclusion of a general family of graph learning layers into a neural network. The resulting method, distinct from graph neural networks, allows us to precisely integrate similarity graph construction and graph Laplacian-based label propagation into a neural network layer, replacing a projection head and softmax activation function for general classification task. Our experimental results demonstrate smooth label transitions across data, improved generalization and robustness to adversarial attacks, and improved training dynamics compared to a standard softmax-based approach.

Jason Brown, Bohan Chen, Harris Hardiman-Mostow +2

Department of Mathematics University of California, Los Angeles Los Angeles, CA 90095, USA · Computing + Mathematical Sciences (CMS) Department California Institute of Technology Pasadena, CA 91125, USA · School of Mathematics University of Minnesota Minneapolis, MN 55455, USA

Graph-Based Label Propagation Graph-Based Semi-Supervised Learning Graph Structure Learning