🤖 machine learning

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

The paper proposes SLeDGe, a semi-supervised learning method for data streams that jointly learns a predictive model and an adaptive graph structure under strict memory and label constraints, effectively capturing evolving sample relationships and outperforming state-of-the-art competitors across 12 datasets.

Original authors: Heechan Moon, Kijung Shin

Published 2026-06-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Heechan Moon, Kijung Shin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a bustling newsroom where information (data) arrives non-stop, like a firehose of breaking news. Your job is to sort this news into categories (like "Sports," "Politics," or "Entertainment"). However, you have two major problems:

You have very little time and space: You can't keep every single article that ever came in; your filing cabinet is tiny.
You have very few experts: Only a tiny fraction of the articles come with a label saying what category they belong to. Most are just blank sheets of paper.

This is the challenge of Semi-Supervised Learning on Data Streams. The paper introduces a new method called SLeDGe to solve this.

Here is how SLeDGe works, explained through simple analogies:

1. The Two Special Filing Cabinets (Memory)

Most old methods try to keep a static list of "similar" items or treat every new article as a stranger. SLeDGe is smarter. It maintains two small, special filing cabinets in its memory:

The "Expert" Cabinet (Labeled Memory): This holds a few articles that do have labels. SLeDGe treats these like expert prototypes. If a new article looks very similar to an existing expert, it updates that expert's file to reflect the new information quickly. It's like a teacher updating their lesson plan based on a new, clear example.
The "Student" Cabinet (Unlabeled Memory): This holds articles without labels. SLeDGe is more cautious here. It updates these files slowly, blending new information with what was already there. It's like a student taking notes; they don't erase their whole notebook just because they heard one new fact; they gradually add to their understanding.

Why this matters: This balance allows the system to learn new things fast (plasticity) without forgetting old, reliable patterns (stability).

2. The Dynamic Map (Graph Structure Learning)

Traditional methods use a fixed map to connect similar items. Imagine a map where "Apples" are always connected to "Oranges" because they are both fruit, even if the context changes. This is rigid and often wrong.

SLeDGe draws a live, breathing map.

As new data arrives, SLeDGe constantly redraws the lines connecting the articles in its cabinets.
It asks: "Who is actually related to whom right now?"
It only keeps the strongest, most important connections and cuts out the weak, noisy ones (like removing a shaky bridge).

This is called Graph Structure Learning. Instead of guessing relationships, it learns them as the data flows in.

3. The Label Relay Race (Propagation)

Once the map is drawn, SLeDGe uses it to pass the "label" baton.

Imagine you have one article labeled "Sports."
Because SLeDGe's live map shows that this "Sports" article is strongly connected to a nearby unlabeled article, it confidently guesses that the unlabeled one is also "Sports."
It then uses that guess to help label other articles connected to it.
This creates a chain reaction, allowing the system to learn from thousands of unlabeled articles using only a handful of labeled ones.

4. The Lightweight Version (SLeDGe-L)

The main SLeDGe method is powerful but can get heavy if the filing cabinets get too full (because drawing a map for everyone takes time).

The authors created a SLeDGe-L (Light) version.
Think of this as a "speed run" mode. Instead of checking connections between everyone, it only checks connections between the "Experts" (labeled items) and the rest.
This makes it much faster and scalable, like a delivery driver who only stops at the main hubs rather than every single house, while still getting the job done.

The Results: Why It Wins

The authors tested SLeDGe on 12 different datasets (ranging from web pages to images and sensor data).

The Score: When they only had 0.1% of the data labeled (basically one label for every 1,000 items), SLeDGe was 31.7% more accurate than the best existing methods.
With slightly more labels (1%): It was still 14.8% better than the competition.

In a Nutshell

SLeDGe is like a highly efficient newsroom manager who:

Keeps a tiny, curated list of "Experts" and "Students."
Constantly redraws a map of who knows whom based on current events.
Uses that map to spread knowledge from the few labeled experts to the many unlabeled students.
Does all this without running out of memory or time, even when the news never stops.

The paper claims this approach is significantly better at handling the chaos of continuous data streams with very few labels than previous methods.

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

1. Problem Definition

The paper addresses the challenge of Semi-Supervised Learning (SSL) on data streams. In this setting, data arrives sequentially ( $D = \{x_t\}_{t=1}^T$ ) in high volume, and the learner must operate under two strict constraints:

Memory Constraints: The system has a fixed, limited memory capacity ( $M$ ) and cannot store the entire history of the stream.
Label Scarcity: Only a tiny fraction of incoming samples have observed labels ( $y_t$ ), making traditional supervised learning infeasible.

Existing SSL methods for streams often fail because they either treat samples independently, rely on fixed similarity heuristics (which cannot capture evolving relationships), or assume static offline datasets. The core problem is how to effectively propagate limited label supervision to unlabeled samples while adapting to the continuous evolution of data distributions and relationships over time.

2. Methodology: SLeDGe

The authors propose SLeDGe (Semi-supervised Learning on Data Stream with Graph structure learning), a framework that jointly learns a predictive model and an adaptive graph structure. The method operates in three continuous stages for every incoming sample $x_t$ :

A. Dual-Memory Update Mechanism

To balance the need for rapid adaptation (plasticity) with the retention of historical consistency (stability), SLeDGe maintains two distinct compact memory buffers:

Labeled Memory ( $M_L$ ): Optimized for plasticity. It stores prototypes for each class. When a new labeled sample arrives, it either fills an empty slot or updates the most similar existing prototype via a weighted combination. The update weight $\alpha$ is dynamic, favoring the new input to facilitate rapid integration of novel features.
Unlabeled Memory ( $M_U$ ): Optimized for stability. It stores representative unlabeled prototypes. Updates here use a weight $\beta$ that favors the existing prototype, reflecting the uncertainty of unlabeled data and ensuring gradual information accumulation.

B. Dynamic Graph Structure Learning (GSL)

Instead of using a fixed graph or static similarity metrics, SLeDGe constructs a graph dynamically at each time step over the combined memory ( $M_L \cup M_U$ ) and the current sample $x_t$ .

Embedding ( $f_E$ ): A Multi-Layer Perceptron (MLP) maps input features to a latent space.
Scoring ( $f_S$ ): A scoring function (cosine similarity) computes pairwise relational weights between all nodes in the memory and the current sample, generating a dense adjacency matrix.
Pruning ( $f_P$ ): To ensure efficiency, the dense matrix is pruned to retain only the top- $k$ connections per node, resulting in a sparse adjacency matrix $A_t$ .
Classification ( $f_B$ ): A Graph Convolutional Network (GCN)-style backbone propagates supervision through the learned graph structure $A_t$ to generate predictions.

C. Model Optimization

The model is updated using a composite loss function:

Supervised Loss ( $L_L$ ): Cross-entropy loss computed on the labeled memory, weighted by a temporal decay factor to prioritize recent samples.
Structural Regularization ( $L_{reg}$ ): A term that encourages consistency between pairwise similarities in the input space and the latent space. This stabilizes the dynamic graph inference, preventing the graph structure from becoming erratic.

D. Lightweight Variant: SLeDGe-L

To address the quadratic time complexity ( $O(M^2)$ ) of the full graph construction when memory size $M$ is large, the authors propose SLeDGe-L. This variant restricts graph scoring to a class-centric approach, computing similarities only between labeled prototypes and all memory samples. This reduces the complexity to linear in $M$ ( $O(c \cdot M)$ ), where $c$ is the number of classes.

3. Key Contributions

Adaptive Graph Structure: Unlike prior stream SSL methods that rely on fixed graphs, SLeDGe learns a dynamic graph topology that evolves with the data stream, capturing time-varying inter-sample dependencies.
Dual-Strategy Memory Management: The introduction of distinct update strategies for labeled (plasticity-focused) and unlabeled (stability-focused) memories allows the model to balance adaptation to new features with the preservation of historical knowledge.
Efficiency under Constraints: The framework is designed to operate under strict memory budgets and extreme label scarcity (as low as 0.1% labels) while maintaining computational efficiency through sparse graph pruning and a lightweight variant (SLeDGe-L).
Structural Regularization: The inclusion of a consistency regularization term ensures that the learned graph structure remains stable and meaningful during the streaming process.

4. Experimental Results

The authors evaluated SLeDGe on 12 datasets spanning web, image, and tabular domains.

Performance: SLeDGe outperformed state-of-the-art competitors (TLP, ReSSL, HDSSL) across all datasets.
- With 0.1% labels, it achieved an average relative accuracy gain of 31.7% over the strongest baseline.
- With 1.0% labels, it achieved an average relative accuracy gain of 14.8%.
Ablation Studies: Experiments confirmed that both the memory module and the dynamic graph structure are critical. Removing the dynamic graph (reverting to a static k-NN graph) resulted in significantly lower performance, validating the necessity of learning evolving relationships.
Scalability: The method demonstrates linear scaling with respect to the data stream size (constant time per sample). SLeDGe-L showed superior scalability with respect to memory buffer size compared to the full version, confirming the theoretical complexity analysis.
Speed: Despite being a deep learning model, SLeDGe was competitive in running time against cluster-based methods, particularly on high-dimensional data where it leveraged embedding-level computations.

5. Significance and Claims

The paper claims that SLeDGe fills a critical gap in the literature by enabling Graph Structure Learning (GSL) in streaming settings where memory and labels are severely constrained. The authors argue that existing methods fail because they cannot model how relationships between samples evolve over time. By jointly learning the predictive model and the graph structure, SLeDGe effectively propagates limited supervision to unlabeled data, achieving substantial accuracy improvements without requiring the storage of the entire data history. The work emphasizes that dynamic graph inference is superior to static similarity measures in non-stationary data stream environments.