# Matrix factorisation and the interpretation of geodesic distance

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 82 references that are in the map.
- First posted on arXiv 2 Jun 2021.

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

- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [A statistical interpretation of spectral embedding: the generalised random dot product graph](https://mlsanity.com/paper/1709.05506/) (2017)
- [Rates of Convergence of Spectral Methods for Graphon Estimation](https://mlsanity.com/paper/1709.03183/) (2017)
- [On a 'Two Truths' Phenomenon in Spectral Graph Clustering](https://mlsanity.com/paper/1808.07801/) (2018)
- [Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding](https://mlsanity.com/paper/1310.0532/) (2013)
- [Community Detection and Classification in Hierarchical Stochastic Blockmodels](https://mlsanity.com/paper/1503.02115/) (2015)
- [The multilayer random dot product graph](https://mlsanity.com/paper/2007.10455/) (2020)
- [Limit theorems for eigenvectors of the normalized Laplacian for random graphs](https://mlsanity.com/paper/1607.08601/) (2016)
- [Manifold structure in graph embeddings](https://mlsanity.com/paper/2006.05168/) (2020)
- [Network Representation Using Graph Root Distributions](https://mlsanity.com/paper/1802.09684/) (2018)
- [Latent Distance Estimation for Random Geometric Graphs](https://mlsanity.com/paper/1909.06841/) (2019)
- [On estimation and inference in latent structure random graphs](https://mlsanity.com/paper/1806.01401/) (2018)
- [Spectral embedding of weighted graphs](https://mlsanity.com/paper/1910.05534/) (2019)
- [Spectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel](https://mlsanity.com/paper/2011.04558/) (2020)
- [Spectral clustering under degree heterogeneity: a case for the random walk Laplacian](https://mlsanity.com/paper/2105.00987/) (2021)
- [Learning 1-Dimensional Submanifolds for Subsequent Inference on Random Dot Product Graphs](https://mlsanity.com/paper/2004.07348/) (2020)
- [Comparison of brain connectomes using geodesic distance on manifold:a twin study](https://mlsanity.com/paper/1902.01395/) (2019)

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

- [Implications of sparsity and high triangle density for graph representation learning](https://mlsanity.com/paper/2210.15277/) (2022)
- [Spectral embedding and the latent geometry of multipartite networks](https://mlsanity.com/paper/2202.03945/) (2022)
- [How high is `high'? Rethinking the roles of dimensionality in topological data analysis and manifold learning](https://mlsanity.com/paper/2505.16879/) (2025)
- [Uncovering Locally Low-dimensional Structure in Networks by Locally Optimal Spectral Embedding](https://mlsanity.com/paper/2603.11965/) (2026)
- [SalAngaBhava: A Sinhala Market Dataset for Aspect-based Sentiment Analysis](https://mlsanity.com/paper/2607.05259/) (2026)
- [Learning Submanifolds for Subsequent Inference on Random Dot Product Graphs, Part 1: Theory](https://mlsanity.com/paper/2609.19357/) (2026)

## Abstract (arXiv)

Given a graph or similarity matrix, we consider the problem of recovering a notion of true distance between the nodes, and so their true positions. We show that this can be accomplished in two steps: matrix factorisation, followed by nonlinear dimension reduction. This combination is effective because the point cloud obtained in the first step lives close to a manifold in which latent distance is encoded as geodesic distance. Hence, a nonlinear dimension reduction tool, approximating geodesic distance, can recover the latent positions, up to a simple transformation. We give a detailed account of the case where spectral embedding is used, followed by Isomap, and provide encouraging experimental evidence for other combinations of techniques.