# Implications of sparsity and high triangle density for graph representation learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 58 references that are in the map.
- First posted on arXiv 27 Oct 2022.

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

- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [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)
- [The impossibility of low rank representations for triangle-rich complex networks](https://mlsanity.com/paper/2003.12635/) (2020)
- [Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices](https://mlsanity.com/paper/1402.1267/) (2014)
- [Concentration and regularization of random graphs](https://mlsanity.com/paper/1506.00669/) (2015)
- [On a 'Two Truths' Phenomenon in Spectral Graph Clustering](https://mlsanity.com/paper/1808.07801/) (2018)
- [Node Embeddings and Exact Low-Rank Representations of Complex Networks](https://mlsanity.com/paper/2006.05592/) (2020)
- [Sparse graphs using exchangeable random measures](https://mlsanity.com/paper/1401.1137/) (2014)
- [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)
- [On the Power of Edge Independent Graph Models](https://mlsanity.com/paper/2111.00048/) (2021)
- [Network Representation Using Graph Root Distributions](https://mlsanity.com/paper/1802.09684/) (2018)
- [On estimation and inference in latent structure random graphs](https://mlsanity.com/paper/1806.01401/) (2018)
- [Efficient Estimation for Random Dot Product Graphs via a One-step Procedure](https://mlsanity.com/paper/1910.04333/) (2019)
- [Matrix factorisation and the interpretation of geodesic distance](https://mlsanity.com/paper/2106.01260/) (2021)
- [Classic Graph Structural Features Outperform Factorization-Based Graph Embedding Methods on Community Labeling](https://mlsanity.com/paper/2201.08481/) (2022)
- [Subsampling Sparse Graphons Under Minimal Assumptions](https://mlsanity.com/paper/1907.12528/) (2019)
- [Change point localization in dependent dynamic nonparametric random dot product graphs](https://mlsanity.com/paper/1911.07494/) (2019)
- [The blessing of transitivity in sparse and stochastic networks](https://mlsanity.com/paper/1307.2302/) (2013)
- [Targeted sampling from massive block model graphs with personalized PageRank](https://mlsanity.com/paper/1910.12937/) (2019)

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

- [Uncovering Locally Low-dimensional Structure in Networks by Locally Optimal Spectral Embedding](https://mlsanity.com/paper/2603.11965/) (2026)

## Abstract (arXiv)

Recent work has shown that sparse graphs containing many triangles cannot be reproduced using a finite-dimensional representation of the nodes, in which link probabilities are inner products. Here, we show that such graphs can be reproduced using an infinite-dimensional inner product model, where the node representations lie on a low-dimensional manifold. Recovering a global representation of the manifold is impossible in a sparse regime. However, we can zoom in on local neighbourhoods, where a lower-dimensional representation is possible. As our constructions allow the points to be uniformly distributed on the manifold, we find evidence against the common perception that triangles imply community structure.