Label Propagation for Graph Based Semi Supervised Learning

This direction is merged into another direction: graph-based label propagation (graph-based semi-supervised learning). Its last version stays readable and citable here.

Version 1 of 152 papers54 conceptsfrozen 2026-10-04

In most machine learning tasks, the bottleneck is not the lack of data, but the lack of labeled data. While we have oceans of raw text, images, and sensor logs, manually annotating them is expensive and slow. Graph-based semi-supervised learning (GBSSL) offers a way to bridge this gap by treating data points as nodes in a network and "flowing" labels from a small set of seeds to the rest of the dataset.

The Intuition: Data as a Fluid Network

The core idea, championed by researchers like Zhengyu Niu, Donghong Ji, and Chew Lim Tan, is to represent both labeled and unlabeled instances as vertices in a graph. Edges between these vertices are weighted based on similarity: the more similar two data points are, the stronger the "pipe" connecting them.

In this framework, labels are treated like a fluid. You "pour" labels into the few nodes you have already categorized (the seeds) and let that information diffuse through the edges. As Raif M. Rustamov and colleagues describe in Interpretable Graph-Based Semi-Supervised Learning via Flows, this can be mathematically modeled as a network flow problem where labeled points act as sources and unlabeled points act as sinks.

This process relies on the cluster assumption: that data points in high-density regions of the feature space should share the same label. By leveraging "global consistency," the algorithm ensures that the final labeling is smooth across the entire graph structure, rather than just making local decisions.

From Seeds to Pseudo-Labels

One of the most powerful applications of this idea is using label propagation as a "pre-processing" step to generate training data for other models. This is often called pseudo-labeling.

Instead of using the graph model as the final classifier, researchers like Aaron Li-Feng Han and Lidia S. Chao use it to automatically label a massive raw dataset, which is then used to train a standard supervised model like a Conditional Random Field (CRF). This "two-step" pipeline is surprisingly effective. In fact, Hande Dong and Xiangnan He demonstrated in On the Equivalence of Decoupled Graph Convolution Network and Label Propagation that many modern "decoupled" Graph Convolutional Networks are mathematically equivalent to this two-step process of propagation followed by training.

Constructing the "Right" Graph

The "secret sauce" of these systems isn't just the propagation algorithm—it's how the graph is built. As Rada Mihalcea and Dragomir Radev argue in their foundational work on Networks and Natural Language Processing, the nodes and edges must be carefully defined to capture the nuances of the domain.

  • In NLP: Nodes might be words or sentences, with edges representing co-occurrence or semantic similarity.
  • In Computer Vision: Chenglong Li uses image patches as nodes to track objects, propagating "foreground" labels to distinguish targets from background noise.
  • In Biology: Hansheng Xue and Yu Lin use biological constraints (must-link/cannot-link) to anchor the propagation process for metagenomic binning.

Modern Frontiers: GCNs and LLMs

The rise of deep learning has not replaced label propagation; it has supercharged it.

Modern frameworks like the GraphNet Zoo, developed by Marianne de Vriendt, combine deep neural networks (for feature extraction) with graph-based energy models (for label diffusion). Similarly, Afshin Rahimi 0001 and Trevor Cohn use Graph Convolutional Networks (GCNs) to propagate location labels across social media networks where only 1% of users are geotagged.

Most recently, Large Language Models (LLMs) have entered the loop. In Large Language Models as Topological Structure Enhancers for Text-Attributed Graphs, Shengyin Sun and colleagues show how LLMs can be used to prune "noisy" edges in a graph, ensuring that the labels propagate only through the most reliable connections. This synergy allows researchers to achieve "Oracle-level" performance with a fraction of the manual effort or expensive API calls.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_label_propagation_for_graph_based_semi_s_41195745,
  title = {Label Propagation for Graph Based Semi Supervised Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/label-propagation-for-graph-based-semi-supervised-learning/rdr_411957456e5c44f084827f195fa0dc60},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_label_propagation_for_graph_based_semi_s_41195745_v1,
  title = {Label Propagation for Graph Based Semi Supervised Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/label-propagation-for-graph-based-semi-supervised-learning/rdr_411957456e5c44f084827f195fa0dc60/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}