Manifold structure in graph embeddings
arXiv:2006.05168
Abstract
Statistical analysis of a graph often starts with embedding, the process of representing its nodes as points in space. How to choose the embedding dimension is a nuanced decision in practice, but in theory a notion of true dimension is often available. In spectral embedding, this dimension may be very high. However, this paper shows that existing random graph models, including graphon and other latent position models, predict the data should live near a much lower-dimensional set. One may therefore circumvent the curse of dimensionality by employing methods which exploit hidden manifold structure.
References in corpus (16)
- UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction
- Stochastic blockmodels and community structure in networks
- Hyperbolic Geometry of Complex Networks
- Modeling the Internet's Large-Scale Topology
- Modeling homophily and stochastic equivalence in symmetric relational data
- Rate-optimal graphon estimation
- Sparse graphs using exchangeable random measures
- Nonparametric graphon estimation
- Sparse exchangeable graphs and their limits via graphon processes
- On a 'Two Truths' Phenomenon in Spectral Graph Clustering
- The Class of Random Graphs Arising from Exchangeable Random Measures
- The impossibility of low rank representations for triangle-rich complex networks
- Semiparametric spectral modeling of the Drosophila connectome
- Network Representation Using Graph Root Distributions
- Consistency of adjacency spectral embedding for the mixed membership stochastic blockmodel
- Persistent Homology of Graph Embeddings