# Subspace Projection Methods for Fast Spectral Embeddings of Evolving Graphs

arXiv: https://arxiv.org/abs/2603.19439 · HTML: https://mlsanity.com/paper/2603.19439/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 59 references that are in the map.
- First posted on arXiv 19 Mar 2026.

## Builds on (most cited first, 16 of 16)

- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications](https://mlsanity.com/paper/1709.07604/) (2017)
- [Network Representation Learning: A Survey](https://mlsanity.com/paper/1801.05852/) (2017)
- [Graph Representation Learning: A Survey](https://mlsanity.com/paper/1909.00958/) (2019)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Understanding graph embedding methods and their applications](https://mlsanity.com/paper/2012.08019/) (2020)
- [Dynamic Network Embedding Survey](https://mlsanity.com/paper/2103.15447/) (2021)
- [Graph Signal Processing: History, Development, Impact, and Outlook](https://mlsanity.com/paper/2303.12211/) (2023)
- [Directed Graph Auto-Encoders](https://mlsanity.com/paper/2202.12449/) (2022)
- [TIMERS: Error-Bounded SVD Restart on Dynamic Networks](https://mlsanity.com/paper/1711.09541/) (2017)
- [Online Change Point Detection for Weighted and Directed Random Dot Product Graphs](https://mlsanity.com/paper/2201.11222/) (2022)
- [Efficient Eigen-updating for Spectral Graph Clustering](https://mlsanity.com/paper/1301.1318/) (2013)
- [Gradient-Based Spectral Embeddings of Random Dot Product Graphs](https://mlsanity.com/paper/2307.13818/) (2023)
- [A Perturbation-Based Kernel Approximation Framework](https://mlsanity.com/paper/2009.02955/) (2020)
- [Weighted Random Dot Product Graphs](https://mlsanity.com/paper/2505.03649/) (2025)

## Abstract (arXiv)

Several graph data mining, signal processing, and machine learning downstream tasks rely on information related to the eigenvectors of the associated adjacency or Laplacian matrix. Classical eigendecomposition methods are powerful when the matrix remains static but cannot be applied to problems where the matrix entries are updated or the number of rows and columns increases frequently. Such scenarios occur routinely in graph analytics when the graph is changing dynamically and either edges and/or nodes are being added and removed. This paper puts forth a new algorithmic framework to update the eigenvectors associated with the leading eigenvalues of an initial adjacency or Laplacian matrix as the graph evolves dynamically. The proposed algorithm is based on Rayleigh-Ritz projections, in which the original eigenvalue problem is projected onto a restricted subspace which ideally encapsulates the invariant subspace associated with the sought eigenvectors. Following ideas from eigenvector perturbation analysis, we present a new methodology to build the projection subspace. The proposed framework features lower computational and memory complexity with respect to competitive alternatives while empirical results show strong qualitative performance, both in terms of eigenvector approximation and accuracy of downstream learning tasks of central node identification and node clustering.