Random geometric graphs in high dimension

Abstract

Many machine learning algorithms used for dimensional reduction and manifold learning leverage on the computation of the nearest neighbours to each point of a dataset to perform their tasks. These proximity relations define a so-called geometric graph, where two nodes are linked if they are sufficiently close to each other. Random geometric graphs, where the positions of nodes are randomly generated in a subset of ${\mathbb{R}}^d$, offer a null model to study typical properties of datasets and of machine learning algorithms. Up to now, most of the literature focused on the characterization of low-dimensional random geometric graphs whereas typical datasets of interest in machine learning live in high-dimensional spaces ($d\gg 10^2$). In this work, we consider the infinite dimensions limit of hard and soft random geometric graphs and we show how to compute the average number of subgraphs of given finite size $k$, e.g. the average number of $k$-cliques. This analysis highlights that local observables display different behaviors depending on the chosen ensemble: soft random geometric graphs with continuous activation functions converge to the naive infinite dimensional limit provided by Erdös-Rényi graphs, whereas hard random geometric graphs can show systematic deviations from it. We present numerical evidence that our analytical insights, exact in infinite dimensions, provide a good approximation also for dimension $d\gtrsim 10$.

References in corpus (14)

• Spatial Networks
• Random Geometric Graphs
• Blessing of dimensionality: mathematical foundations of the statistical physics of data
• Connectivity of soft random geometric graphs
• Random Rectangular Graphs
• Intrinsic dimension estimation for locally undersampled data
• Statistical learning theory of structured data
• The shape of shortest paths in random spatial networks
• Counting the learnable functions of structured data
• Beyond the storage capacity: data driven satisfiability transition
• Random spherical graphs
• Statistical mechanics of random geometric graphs: Geometry-induced first order phase transition
• Balancing building and maintenance costs in growing transport networks
• Generalization from correlated sets of patterns in the perceptron

Cited by in corpus (5)

• Statistical learning theory of structured data
• Beyond the storage capacity: data driven satisfiability transition
• Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs
• Isotropic random geometric networks in two dimensions with a penetrable cavity
• Entropy of Random Geometric Graphs in High and Low Dimensions