Spectral methods are highly effective tools in machine learning. By mapping data into a lower-dimensional subspace spanned by the eigenvectors of a similarity matrix or a graph Laplacian, they reveal complex, non-linear structures that confound traditional algorithms like $K$-means. As shown in the foundational work On Spectral Clustering: Analysis and an algorithm by Andrew Y. Ng et al., this approach provides a mathematically grounded framework for finding natural clusters.
However, this mathematical elegance comes at a steep price: computing the full eigendecomposition of an $n \times n$ affinity matrix scales cubically ($O(n^3)$) with the number of data points. When datasets grow into millions of samples, this computational bottleneck renders standard spectral methods completely impractical. To make these methods scalable, researchers have developed several distinct strategies to bypass or approximate the expensive eigendecomposition step.
The Ubiquity of the Eigendecomposition Bottleneck
The $O(n^3)$ computational barrier is not unique to clustering; it plagues any machine learning task that relies on spectral geometry. For instance, Charilaos I. Kanatsoulis et al. note in Learning Efficient Positional Encodings with Graph Neural Networks that computing spectral positional encodings via Laplacian eigenvectors creates a severe scalability bottleneck for large graph datasets.
Similarly, evaluating data diversity or representation uncertainty using kernel matrices scales cubically, as highlighted by Dan Friedman et al. in The Vendi Score: A Diversity Evaluation Metric for Machine Learning and by Farzan Farnia et al. in The Maximum von Neumann Entropy Principle: Theory and Applications in Machine Learning. Whether performing manifold alignment (Jihun Hamm et al. in Semisupervised alignment of manifolds) or estimating gradients for implicit distributions (Jiaxin Shi et al. in A Spectral Approach to Gradient Estimation for Implicit Distributions), researchers face the same fundamental challenge: how to extract the geometric insights of spectral representations without paying the cubic computational toll.
Landmark and Anchor-Based Graph Approximations
One intuitive way to bypass the $O(n^3)$ bottleneck is to avoid constructing the full $n \times n$ pairwise affinity matrix entirely. Instead of measuring the similarity between every single pair of points, we can select a small set of $m$ representative "anchors" or "landmarks" (where $m \ll n$). By constructing a bipartite graph that only models the relationships between the $n$ data points and the $m$ anchors, the size of the matrix under consideration drops dramatically.
For example, Yeqing Li et al. leverage this structure in Large-Scale Multi-View Spectral Clustering via Bipartite Graph, achieving massive speedups by computing eigenvectors on a much smaller cross-affinity matrix. Similarly, Xiaojun Chen et al. combine an anchor-based data representation with a discrete label alignment step in Scalable Normalized Cut with Improved Spectral Rotation. By reducing the problem to an $n \times m$ matrix, the subsequent decomposition scales linearly with $n$, effectively breaking the cubic bottleneck.
Stochastic Optimization on Manifolds
Another powerful paradigm shifts the problem from linear algebra to continuous optimization. Finding the top $k$ eigenvectors of a matrix can be framed as maximizing a quadratic form subject to orthogonality constraints—an optimization problem over the Stiefel manifold. Instead of computing the exact global solution in one shot, we can approximate it iteratively using stochastic gradient descent (SGD) on mini-batches.
Yufei Han introduces this perspective in Mini-Batch Spectral Clustering, demonstrating that framing spectral clustering as a stochastic optimization problem yields an $O(n)$ per-iteration complexity while guaranteeing convergence to the exact solution in the limit.
To avoid the expensive orthogonalization steps typically required to keep updates on the manifold, Ziyu Chen et al. propose SpecNet2: Orthogonalization-free Spectral Embedding by Neural Networks. By using an unconstrained optimization objective and tracking graph neighbors during mini-batch training, their framework achieves the accuracy of global spectral methods with the scalability of deep learning.
Deep Learning Surrogates and Functional Embeddings
Rather than approximating the eigenvectors of a specific, static dataset, what if we learn a parameterized function (like a neural network) that maps data points directly to their spectral embeddings? This strategy solves two problems at once: it avoids the $O(n^3)$ matrix decomposition during training, and it naturally solves the "out-of-sample" problem, allowing the model to instantly embed new data points without recomputing the entire system.
This functional approach was explored by Jason Weston et al. in Large-Scale Clustering through Functional Embedding, where they trained a neural network using SGD to minimize a spectral clustering objective directly, scaling the method to millions of points. In the context of graph data, Fei Tian et al. introduce Learning Deep Representations for Graph Clustering, which replaces traditional spectral decomposition with Stacked Sparse Autoencoders. By leveraging the theoretical link between matrix reconstruction and spectral clustering, they generate highly scalable, non-linear graph embeddings.
Iterative Solvers and Alternative Operators
Finally, scalability can be achieved by replacing full eigendecomposition with lighter numerical approximations or alternative geometric operators. If the goal is simply to approximate the cluster structure or the overall distribution of eigenvalues, we do not need the exact precision of standard eigensolvers.
Wengang Guo et al. demonstrate this in Deep Spectral Clustering via Joint Spectral Embedding and Kmeans by replacing the traditional, computationally heavy eigendecomposition step with a lightweight power iteration module.
For geometric shape analysis, Maxime Kirgo avoids computing the full eigen-decomposition of the Laplace-Beltrami Operator on dense meshes in Wavelet-based Heat Kernel Derivatives: Towards Informative Localized Shape Analysis. Instead, the author approximates the time derivative of the heat kernel using wavelets, creating a localized functional dictionary that is significantly faster to compute while remaining highly effective for high-frequency signal reconstruction.