# Gradient-Based Spectral Embeddings of Random Dot Product Graphs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 48 references that are in the map.
- First posted on arXiv 25 Jul 2023.

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

- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Machine Learning on Graphs: A Model and Comprehensive Taxonomy](https://mlsanity.com/paper/2005.03675/) (2020)
- [Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiation](https://mlsanity.com/paper/1603.03236/) (2016)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [Global rates of convergence for nonconvex optimization on manifolds](https://mlsanity.com/paper/1605.08101/) (2016)
- [Dropping Convexity for Faster Semi-definite Optimization](https://mlsanity.com/paper/1509.03917/) (2015)
- [Community Detection and Classification in Hierarchical Stochastic Blockmodels](https://mlsanity.com/paper/1503.02115/) (2015)
- [TIMERS: Error-Bounded SVD Restart on Dynamic Networks](https://mlsanity.com/paper/1711.09541/) (2017)
- [The multilayer random dot product graph](https://mlsanity.com/paper/2007.10455/) (2020)
- [GraSPy: Graph Statistics in Python](https://mlsanity.com/paper/1904.05329/) (2019)
- [Spectral embedding for dynamic networks with stability guarantees](https://mlsanity.com/paper/2106.01282/) (2021)
- [Sequential change-point detection based on nearest neighbors](https://mlsanity.com/paper/1604.03611/) (2016)
- [Out-of-sample extension of graph adjacency spectral embedding](https://mlsanity.com/paper/1802.06307/) (2018)
- [Efficient Estimation for Random Dot Product Graphs via a One-step Procedure](https://mlsanity.com/paper/1910.04333/) (2019)
- [Online Change Point Detection for Weighted and Directed Random Dot Product Graphs](https://mlsanity.com/paper/2201.11222/) (2022)
- [Robust Estimation from Multiple Graphs under Gross Error Contamination](https://mlsanity.com/paper/1707.03487/) (2017)
- [Optimal network online change point localisation](https://mlsanity.com/paper/2101.05477/) (2021)
- [Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descent](https://mlsanity.com/paper/2102.02396/) (2021)

## Built on by (most cited first, 3 of 3)

- [Rank Is Not Capacity: Spectral Occupancy for Latent Graph Models](https://mlsanity.com/paper/2605.11142/) (2026)
- [LASE: Learned Adjacency Spectral Embeddings](https://mlsanity.com/paper/2412.17734/) (2024)
- [Subspace Projection Methods for Fast Spectral Embeddings of Evolving Graphs](https://mlsanity.com/paper/2603.19439/) (2026)

## Abstract (arXiv)

The Random Dot Product Graph (RDPG) is a generative model for relational data, where nodes are represented via latent vectors in low-dimensional Euclidean space. RDPGs crucially postulate that edge formation probabilities are given by the dot product of the corresponding latent positions. Accordingly, the embedding task of estimating these vectors from an observed graph is typically posed as a low-rank matrix factorization problem. The workhorse Adjacency Spectral Embedding (ASE) enjoys solid statistical properties, but it is formally solving a surrogate problem and can be computationally intensive. In this paper, we bring to bear recent advances in non-convex optimization and demonstrate their impact to RDPG inference. We advocate first-order gradient descent methods to better solve the embedding problem, and to organically accommodate broader network embedding applications of practical relevance. Notably, we argue that RDPG embeddings of directed graphs loose interpretability unless the factor matrices are constrained to have orthogonal columns. We thus develop a novel feasible optimization method in the resulting manifold. The effectiveness of the graph representation learning framework is demonstrated on reproducible experiments with both synthetic and real network data. Our open-source algorithm implementations are scalable, and unlike the ASE they are robust to missing edge data and can track slowly-varying latent positions from streaming graphs.