Graph Laplacian for Semi-supervised Learning

Or Streicher, Guy Gilboa

Abstract

Semi-supervised learning (SSL) leverages the underlying structure of unlabeled data to augment small sets of labeled examples. Traditional graph-based SSL methods often rely on the Graph Laplacian to smooth predictions across the data manifold. However, in "low-label" regimes where labels are extremely scarce, standard approaches frequently suffer from discontinuous solutions or poor spectral embeddings. This paper introduces a novel Semi-Supervised Laplacian ($L_{SSL}$) that integrates label information directly into the graph operator. By incorporating contrastive and density-based constraints into the affinity matrix, the proposed method enables a smooth transition between unsupervised clustering and supervised classification, significantly outperforming traditional methods on both synthetic and real-world benchmarks.

Introduction

In modern machine learning, the acquisition of high-quality labels remains a significant bottleneck. Semi-supervised learning (SSL) addresses this by utilizing the geometric structure of a large unlabeled dataset to propagate information from a few "golden" labeled points. A central tool in this domain is the Graph Laplacian, which is typically used to solve a Dirichlet problem: fixing known labels and allowing values to "flow" across the graph to predict unknown points.

Despite its utility, the standard Graph Laplacian faces limitations when the number of labels is very small. In these scenarios, the resulting solution often becomes "spiky" or discontinuous at labeled nodes, failing to generalize to the broader cluster. Furthermore, standard spectral clustering—which identifies clusters via the eigenvectors of the Laplacian—often fails to incorporate label information effectively during the embedding process.

The Semi-Supervised Laplacian ($L_{SSL}$)

The core innovation presented by Streicher and Gilboa is the Semi-Supervised Affinity Matrix ($W_{SSL}$). Rather than relying solely on a standard Gaussian kernel to determine similarity between nodes, the authors inject label information directly into the graph's weights through three primary mechanisms:

  1. Same-Cluster Attraction: If two labeled points are known to belong to the same class, they are assigned the maximum possible similarity weight, forcing the model to treat them as tightly connected.
  2. Different-Cluster Repulsion: If two labeled points belong to different classes, their connection is effectively severed or penalized. This creates a sharp contrast between different classes within the operator itself.
  3. Density Reinforcement: The connections between labeled and unlabeled points are boosted to ensure that the influence of the labels propagates effectively into the surrounding unlabeled regions.

By constructing the Laplacian operator as $L_{SSL} = D_{SSL} - W_{SSL}$, the authors create a framework where spectral clustering "knows" about the labels from the outset, rather than attempting to map labels onto an unsupervised embedding post-hoc.

Experimental Framework

The effectiveness of the $L_{SSL}$ was validated using a combination of synthetic datasets and high-dimensional benchmarks:

  • Synthetic Manifolds (2-Moons & 3-Moons): These datasets feature intertwined shapes that test an algorithm's ability to capture non-linear structures and separate clusters with minimal supervision.
  • MNIST and Fashion-MNIST (F-MNIST): These classic benchmarks, consisting of 70,000 images of handwritten digits and clothing items respectively, were used to test the method's performance on high-dimensional, real-world data.

Key Insights

Contrast over Density

A significant finding of this research is that for spectral clustering, contrastive information (knowing which points do not belong together) is more critical than density information (simply increasing the weight of labeled points). The inclusion of repulsive forces between different classes prevents the "bleeding" of labels across cluster boundaries.

Spectral Embedding Clarity

In experiments with the 3-Moons dataset, the authors observed that while standard Laplacians produce overlapping and ambiguous spectral embeddings, the $L_{SSL}$ produces distinct, elongated "prongs" in the embedding space. This structural clarity makes the subsequent clustering step significantly more robust.

Smooth Interpolation

The $L_{SSL}$ operator allows for a mathematical "sliding scale." As the number of labels increases, the operator smoothly transitions from an unsupervised clusterer to a supervised classifier, providing a unified framework for varying levels of data supervision.

Results and Performance

The $L_{SSL}$ demonstrated superior performance across all tested datasets, particularly in the low-label regime:

  • Accuracy and NMI: On the 2-Moons dataset under high noise conditions, $L_{SSL}$ maintained high Normalized Mutual Information (NMI) and Accuracy (ACC) scores, while standard Laplacians and Weighted Nonlocal Laplacians (WNLL) saw performance degradation.
  • Benchmark Scaling: On MNIST and Fashion-MNIST subsets of 10,000 samples, $L_{SSL}$ consistently outperformed standard Dirichlet and spectral methods. Notably, on MNIST, the spectral $L_{SSL}$ achieved significantly higher NMI with as few as 20–40 labels compared to its unsupervised counterparts.
  • Robustness: The method proved resilient to "noisy" data points—those located far from their true cluster centers—which often confuse traditional graph-based approaches.

Conclusion and Future Work

The Semi-Supervised Laplacian provides a powerful modification to traditional graph-based SSL by weaving label information into the very fabric of the graph operator. While this study focuses on the linear case (quadratic energy), the authors suggest that the logic of incorporating contrastive and density measures could be extended to non-linear p-Laplacians, which may offer even better performance in high-dimensional tasks.

Future research will also need to address the computational challenges of scaling these methods. While $L_{SSL}$ is highly effective for datasets in the range of 10,000 to 70,000 points, calculating eigenvectors for matrices representing millions of points remains a significant hurdle in the field of graph-based machine learning.

Summary updated

BibTeX
@inproceedings{streicher2023graph,
  author = {Or Streicher and Guy Gilboa},
  title = {{Graph Laplacian for Semi-supervised Learning}},
  booktitle = {SSVM},
  year = {2023},
  doi = {10.1007/978-3-031-31975-4\_19},
}
Figure