Scaling Up Graph-Based Semisupervised Learning via Prototype Vector Machines

Kai Zhang, Liang Lan, James T. Kwok, Slobodan Vučetić, Bahram Parvin

Abstract

Semisupervised learning (SSL) leverages unlabeled data to improve model performance when labeled data is scarce. Graph-based SSL techniques, which enforce smoothness on a data manifold, are state-of-the-art but suffer from high computational costs—typically $O(n^3)$ time and $O(n^2)$ space. This paper introduces Prototype Vector Machines (PVM), which use a sparse set of data prototypes to approximate the graph-based regularizer. This approach reduces complexity to linear time, enabling SSL on massive datasets while maintaining high accuracy and model parsimony.

Introduction

Traditional graph-based SSL methods, such as Laplacian SVMs, require manipulating $n \times n$ matrices for $n$ data points. This quadratic space and cubic time complexity make them impractical for large-scale applications. Furthermore, the resulting models are often "dense," requiring the storage of nearly all training points for inference. PVM addresses these bottlenecks by decoupling the number of model parameters from the number of training samples.

Table comparing the time and space complexity of PVM against traditional and fast SSL methods.

Methodology: Prototype Vector Machines

PVM utilizes a small set of $m$ prototypes ($m \ll n$) to serve two distinct roles:

  1. Manifold Approximation: A low-rank approximation of the graph Laplacian is constructed using these prototypes, similar to Nyström methods, to capture the underlying data structure efficiently.
  2. Model Sparsification: The predictive model is restricted to a linear combination of basis functions centered only at the $m$ prototypes, rather than all $n$ points.

A key contribution is the principled selection of prototypes. The authors demonstrate that for Gaussian kernels, $k$-means clustering centers are mathematically optimal for minimizing the reconstruction error of the data manifold. This allows the model to capture the "shape" of the data with very few points.

Visualization of PVM decision boundaries on the two-moon dataset, showing how prototypes capture the manifold structure.

Key Results

The authors evaluated PVM across 13 diverse datasets, including MNIST, USPS, and biological benchmarks.

  • Efficiency: PVM achieves linear scaling with respect to the number of samples $n$. On datasets where traditional methods failed due to memory limits (e.g., USPS-FULL), PVM completed training in seconds.
  • Accuracy: Despite using fewer than 5% of data points as prototypes, PVM maintained accuracy comparable to full-scale graph methods and frequently outperformed $\ell_1$-regularized sparse models at the same level of sparsity.
  • Versatility: The framework supports multiple loss functions, including PVM(sqr) for least-squares and PVM(hinge) for SVM-like hinge loss.

Conclusion

Prototype Vector Machines provide a scalable framework for graph-based SSL. By using $k$-means centers as structural prototypes, PVM achieves significant speedups and memory savings without sacrificing the benefits of manifold regularization. This makes high-performance semisupervised learning accessible for large-scale, real-world applications.

Reference: Zhang, K., Lan, L., Kwok, J. T., Vucetic, S., & Parvin, B. (2015). Scaling Up Graph-Based Semisupervised Learning via Prototype Vector Machines. IEEE Transactions on Neural Networks and Learning Systems, 26(3), 444-457.

Summary updated

Abstract

When the amount of labeled data are limited, semisupervised learning can improve the learner's performance by also using the often easily available unlabeled data. In particular, a popular approach requires the learned function to be smooth on the underlying data manifold. By approximating this manifold as a weighted graph, such graph-based techniques can often achieve state-of-the-art performance. However, their high time and space complexities make them less attractive on large data sets. In this paper, we propose to scale up graph-based semisupervised learning using a set of sparse prototypes derived from the data. These prototypes serve as a small set of data representatives, which can be used to approximate the graph-based regularizer and to control model complexity. Consequently, both training and testing become much more efficient. Moreover, when the Gaussian kernel is used to define the graph affinity, a simple and principled method to select the prototypes can be obtained. Experiments on a number of real-world data sets demonstrate encouraging performance and scaling properties of the proposed approach. It also compares favorably with models learned via l1 -regularization at the same level of model sparsity. These results demonstrate the efficacy of the proposed approach in producing highly parsimonious and accurate models for semisupervised learning.
BibTeX
@article{zhang2014scaling,
  author = {Kai Zhang and Liang Lan and James T. Kwok and Slobodan Vučetić and Bahram Parvin},
  title = {{Scaling Up Graph-Based Semisupervised Learning via Prototype Vector Machines}},
  journal = {IEEE Transactions on Neural Networks and Learning Systems},
  year = {2014},
  doi = {10.1109/tnnls.2014.2315526},
}
Figure