Implications of sparsity and high triangle density for graph representation learning
Not on the map. Why?
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.
Key facts. Cited by 1 paper 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
23 of 58 references.
References · 23
- 2016node2vec: Scalable Feature Learning for Networkscited by 1,918
- 2014DeepWalk: Online Learning of Social Representationscited by 1,547
- 2017Community Detection and Stochastic Block Modelscited by 319
- 2017Statistical inference on random dot product graphs: a surveycited by 70
- 2017A statistical interpretation of spectral embedding: the generalised random dot product graphcited by 55
- 2020The impossibility of low rank representations for triangle-rich complex networkscited by 32
- 2014Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatricescited by 29
- 2015Concentration and regularization of random graphscited by 25
- 2018On a 'Two Truths' Phenomenon in Spectral Graph Clusteringcited by 24
- 2020Node Embeddings and Exact Low-Rank Representations of Complex Networkscited by 21
- 2014Sparse graphs using exchangeable random measurescited by 20
- 2016Limit theorems for eigenvectors of the normalized Laplacian for random graphscited by 17
11 more
- 2020Manifold structure in graph embeddingscited by 17
- 2021On the Power of Edge Independent Graph Modelscited by 16
- 2018Network Representation Using Graph Root Distributionscited by 12
- 2018On estimation and inference in latent structure random graphscited by 9
- 2019Efficient Estimation for Random Dot Product Graphs via a One-step Procedurecited by 8
- 2021Matrix factorisation and the interpretation of geodesic distancecited by 6
- 2022Classic Graph Structural Features Outperform Factorization-Based Graph Embedding Methods on Community Labelingcited by 6
- 2019Subsampling Sparse Graphons Under Minimal Assumptionscited by 5
- 2019Change point localization in dependent dynamic nonparametric random dot product graphscited by 5
- 2013The blessing of transitivity in sparse and stochastic networkscited by 4
- 2019Targeted sampling from massive block model graphs with personalized PageRankcited by 2
Built on by
Citing papers per year: 2026: 1.
1 paper.