Semi-supervised Eigenvectors for Large-scale Locally-biased Learning

Toke Jansen Hansen, Michael W. Mahoney

Introduction

Spectral methods, such as spectral clustering and Laplacian eigenmaps, are foundational tools in machine learning for uncovering structural features in complex datasets. By analyzing the eigenvectors of a graph Laplacian, these methods identify the "slowest modes of variation" within a dataset. However, a significant limitation persists: eigenvectors are inherently global quantities. In massive datasets—such as social networks with billions of nodes—the local signal of a specific community can be completely overwhelmed by the graph's macro-structure.

This paper introduces semi-supervised eigenvectors, a mathematical framework designed to focus spectral analysis on user-defined local "seed" regions. This approach allows for targeted clustering and classification without losing the desirable mathematical properties—such as orthogonality and variance capture—of traditional spectral methods.

The Generalized LocalSpectral Framework

The authors propose a transition from global spectral analysis to a localized version by introducing specific constraints into the optimization problem. This allows the resulting vectors to inherit the "smoothness" of global eigenvectors while remaining strictly biased toward a target region.

Comparison of Global, Local, and Generalized Local Spectral optimization formulations.

As shown in the figure above, the standard GlobalSpectral problem minimizes the Dirichlet energy ($x^T L_G x$) subject to unit variance and orthogonality to the trivial constant vector. The LocalSpectral formulation introduces a correlation constraint ($x^T D_G s > \sqrt{\kappa}$), where $s$ is a seed vector representing the region of interest. The Generalized LocalSpectral problem further extends this to ensure orthogonality to a set of previously computed vectors ($X$), enabling the extraction of multiple, distinct local features.

Although this optimization problem is non-convex, the authors demonstrate that it can be solved exactly using the S-procedure. By transforming the problem into a sequence of regularized linear equations, they use a binary search to find the optimal regularization parameter ($\gamma$) that perfectly satisfies the correlation constraint.

Scaling to Massive Graphs: The Push-Peeling Heuristic

A primary challenge in spectral learning is scalability. Solving exact linear systems on graphs with billions of edges is computationally prohibitive. To address this, the authors develop the Push-Peeling heuristic.

This method leverages the mathematical relationship between regularized Laplacian systems and localized random walks, such as Personalized PageRank. By employing a "Push" algorithm—a local diffusion process—the computation remains confined to the neighborhood of the seed nodes. To find subsequent orthogonal eigenvectors, the authors "peel off" the components of previously discovered vectors from the random walk. This allows the algorithm's runtime to scale with the size of the local community rather than the entire graph, making it feasible to analyze billion-node networks on standard hardware.

Experimental Results

The effectiveness of semi-supervised eigenvectors was validated across several diverse domains:

  • MNIST Digit Classification: In tasks involving highly similar digits (e.g., 4s and 9s), global eigenvectors often fail to find a clear boundary, resulting in error rates near 36%. By seeding the algorithm with a small number of labeled examples, semi-supervised eigenvectors reduced the error rate to approximately 3%, using only five components.
  • Neuroscience (fMRI): When applied to high-dimensional brain imaging data, seeding the algorithm in the Primary Motor Cortex allowed for the isolation of local signals that predicted motor activity significantly better than global brain-state eigenvectors.
  • Massive Scale Performance: The Push-Peeling heuristic was tested on the LAW/sk-2005 web crawl, containing over 50 million nodes and 3.6 billion edges. While standard exact solvers failed due to memory and time constraints, the localized approach efficiently extracted meaningful structural features by only touching a fraction of the graph.

Conclusion

Semi-supervised eigenvectors provide a powerful "local-to-global" knob for graph-based learning. By adjusting the correlation parameter $\kappa$, users can smoothly interpolate between highly localized views and standard global spectral analysis. This framework not only improves performance on specific sub-tasks but also makes spectral analysis feasible on a scale previously considered unreachable, offering a robust tool for modern large-scale data science.

Summary updated

BibTeX
@article{hansen2014semi,
  author = {Toke Jansen Hansen and Michael W. Mahoney},
  title = {{Semi-supervised Eigenvectors for Large-scale Locally-biased Learning}},
  journal = {J. Mach. Learn. Res.},
  year = {2014},
  url = {https://openreview.net/forum?id=9HduEcjaCg},
}
Figure