Semi-Supervised Learning with Adaptive Spectral Transform

Hanxiao Liu, Yiming YangAISTATS 2016 · OpenReview

Abstract

This paper proposes a novel nonparametric framework for semi-supervised learning and for optimizing the Laplacian spectrum of the data manifold simultaneously. Our formulation leads to a convex optimization problem that automatically adapts to the specific structure of a dataset, outperforming traditional fixed-kernel methods and two-step alignment approaches.

Introduction

In graph-based semi-supervised learning (SSL), the core assumption is that connected data points likely share the same label. This is typically modeled using the graph Laplacian, which governs the diffusion of label information across the network. However, standard Laplacians are often too rigid to capture the nuances of complex data manifolds.

Researchers frequently employ Spectral Transformations (ST)—such as heat diffusion or random walks—to warp the Laplacian's eigenvalues. The primary challenge lies in determining the optimal transformation. Existing approaches are often heuristic (manually selecting a function) or involve a sub-optimal two-step process: estimating a transformation based on labels and then performing SSL. This paper introduces Adaptive Spectral Transform (AST) to unify label prediction and spectrum optimization into a single, principled framework.

Methods

The Adaptive Spectral Transform (AST) framework utilizes a joint optimization objective that minimizes label prediction error while simultaneously searching for the optimal nonparametric spectral transformation.

Key Components

  • Nonparametric Learning: Unlike parametric methods that assume a specific functional form (e.g., exponential), AST learns weights for each eigenvalue directly from the data.
  • Convex Reformulation: The authors demonstrate that this joint task can be reformulated as a convex optimization problem via Lagrangian duality, ensuring a global optimum.
  • Optimization via Bundle Method: The problem is solved using a variant of the bundle method (BMRM), which iteratively constructs a piecewise-linear lower bound of the objective function.
  • Sparsity and Scalability: To maintain computational efficiency, an $\ell_1$-norm penalty is applied to the transformed spectrum, and the method focuses on the top-$k$ eigenvectors.
Comparison of spectral transformations learned by different methods. AST adapts its spectrum nonparametrically to the data structure.

Experimental Evaluation

AST was evaluated against several baselines, including standard SSL, Diffusion kernels, and Nonparametric Kernel Target Alignment (NKTA), across three benchmark datasets: 20NewsGroup (text), Isolet (audio), and MNIST (images).

Performance and Efficiency

AST consistently outperformed all baselines in terms of classification accuracy. Notably, on the MNIST dataset with 128 labeled samples, AST achieved an accuracy of 94.5%, surpassing standard SSL (92.8%) and Diffusion kernels (93.1%). Furthermore, AST exhibited significantly lower variance than NKTA, indicating greater robustness to the specific choice of labeled samples.

Experimental results across 20NewsGroup, Isolet, and MNIST datasets for varying training sizes.

In terms of computational efficiency, while AST is more complex than simple parametric methods, it proved to be nearly 10x faster than the previous state-of-the-art nonparametric method, NKTA, on the MNIST dataset (2.5 seconds vs. 24.1 seconds).

Conclusion

AST represents a significant advancement in graph-based SSL by treating graph structure learning and label prediction as mutually reinforcing tasks. By tying the spectral transformation directly to the SSL objective, the model achieves superior accuracy and stability. Future work may address the dependency on initial graph construction and the computational costs associated with eigendecomposition for massive-scale graphs.

Summary updated

Abstract

This paper proposes a novel nonparametric framework for semi-supervised learning and for optimizing the Laplacian spectrum of the data manifold simultaneously. Our formulation leads to a convex opt...
BibTeX
@inproceedings{liu2016semi,
  author = {Hanxiao Liu and Yiming Yang},
  title = {{Semi-Supervised Learning with Adaptive Spectral Transform}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
  url = {https://openreview.net/forum?id=OQvl4zBjR1U},
}
Figure