# Efficient Estimation for Random Dot Product Graphs via a One-step Procedure

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Oct 2019.

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

- [Hypothesis Testing for Equality of Latent Positions in Random Graphs](https://mlsanity.com/paper/2105.10838/) (2021)
- [Gradient-Based Spectral Embeddings of Random Dot Product Graphs](https://mlsanity.com/paper/2307.13818/) (2023)
- [Identifying Peer Influence in Therapeutic Communities Adjusting for Latent Homophily](https://mlsanity.com/paper/2203.14223/) (2022)
- [Implications of sparsity and high triangle density for graph representation learning](https://mlsanity.com/paper/2210.15277/) (2022)
- [Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/2306.12968/) (2023)
- [LASE: Learned Adjacency Spectral Embeddings](https://mlsanity.com/paper/2412.17734/) (2024)
- [Random Dot Product Graphs as Dynamical Systems: Limitations and Opportunities](https://mlsanity.com/paper/2603.05703/) (2026)
- [Additive Nonparametric Regression with Spatial and Network Objects](https://mlsanity.com/paper/2609.26867/) (2026)

## Abstract (arXiv)

We propose a one-step procedure to estimate the latent positions in random dot product graphs efficiently. Unlike the classical spectral-based methods such as the adjacency and Laplacian spectral embedding, the proposed one-step procedure takes advantage of both the low-rank structure of the expected adjacency matrix and the Bernoulli likelihood information of the sampling model simultaneously. We show that for each vertex, the corresponding row of the one-step estimator converges to a multivariate normal distribution after proper scaling and centering up to an orthogonal transformation, with an efficient covariance matrix. The initial estimator for the one-step procedure needs to satisfy the so-called approximate linearization property. The one-step estimator improves the commonly-adopted spectral embedding methods in the following sense: Globally for all vertices, it yields an asymptotic sum of squares error no greater than those of the spectral methods, and locally for each vertex, the asymptotic covariance matrix of the corresponding row of the one-step estimator dominates those of the spectral embeddings in spectra. The usefulness of the proposed one-step procedure is demonstrated via numerical examples and the analysis of a real-world Wikipedia graph dataset.