Manifold structure in graph embeddings

The hypothesis that high-dimensional data tend to live near a manifold of low dimension is an important theme of modern statistics and machine learning, often held to explain why highdimensional learning is realistically possible [61, 5, 15, 13, 18, 44]. The object of this paper is show that, for a theoretically tractable but rich class of random graph models, such a phenomenon occurs in the spectral embedding of a graph. Manifold structure is shown to arise when the graph follows a latent position model [28], wherein connections are posited to occur as a function of the nodes' underlying positions in space. Because of their intuitive appeal, such models have been employed in a great diversity of disciplines, including social science [35, 42, 21], neuroscience [17, 52], statistical mechanics [34], information technology [69], biology [53] and ecology [19]. In many more endeavours latent position models are used -- at least according to Definition 1 (to follow) -- but are known by a different name; examples include the standard [29], mixed [2] and degree-corrected [32] stochastic block models, random geometric graphs [50], and the graphon model [39], which encompasses them.