Incrementally Updated Spectral Embeddings

Abstract

Several fundamental tasks in data science rely on computing an extremal eigenspace of size $r\ll n$, where $n$ is the underlying problem dimension. For example, spectral clustering and PCA both require the computation of the leading $r$-dimensional subspace. Often, this process is repeated over time due to the possible temporal nature of the data; e.g., graphs representing relations in a social network may change over time, and feature vectors may be added, removed or updated in a dataset. Therefore, it is important to efficiently carry out the computations involved to keep up with frequent changes in the underlying data and also to dynamically determine a reasonable size for the subspace of interest. We present a complete computational pipeline for efficiently updating spectral embeddings in a variety of contexts. Our basic approach is to "seed" iterative methods for eigenproblems with the most recent subspace estimate to significantly reduce the computations involved, in contrast with a naïve approach which recomputes the subspace of interest from scratch at every step. In this setting, we provide various bounds on the number of iterations common eigensolvers need to perform in order to update the extremal eigenspace to a sufficient tolerance. We also incorporate a criterion for determining the size of the subspace based on successive eigenvalue ratios. We demonstrate the merits of our approach on the tasks of spectral clustering of temporally evolving graphs and PCA of an incrementally updated data matrix.

arXiv comment35 pages, 7 figures

References in corpus (10)

• The Dynamics of Viral Marketing
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
• Spectral centrality measures in complex networks
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Understanding Regularized Spectral Clustering via Graph Conductance
• Bounds on changes in Ritz values for a perturbed invariant subspace of a Hermitian matrix
• Improved Analyses of the Randomized Power Method and Block Lanczos Method
• Robust high dimensional factor models with applications to statistical machine learning
• Uniform bounds for invariant subspace perturbations
• Network interpolation