Manifold structure in graph embeddings
This addresses the challenge of choosing embedding dimensions for graph analysis, offering a theoretical basis for more efficient methods, though it appears incremental as it builds on existing models.
The paper tackles the problem of high-dimensional spectral embeddings in graph analysis by showing that random graph models predict data near a lower-dimensional manifold, enabling methods to circumvent the curse of dimensionality.
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.