Learning Random Geometric Graphs Drawn in Probabilistic Metric Spaces

Dalia Chakrabarty; Kangrui Wang; Chuqiao Zhang; Ye Liu

stat.MLAug 19, 2026

Learning Random Geometric Graphs Drawn in Probabilistic Metric Spaces

Authors: Dalia Chakrabarty, Kangrui Wang, Chuqiao Zhang, Ye Liu

Organizations: Department of Mathematics University of York York YO1 7DD U.K. · Alan Turing Institute London NW1 2DB U.K. · Howbery Park, Wallingford OX10 8BA U.K.

Abstract

We present a new data-driven learning of a Random Geometric Graph (RGG) of a multivariate dataset, where the graph is drawn in a probabilistic metric space. This graph learning works for generic datasets, irrespective of the type of the observables; their probability distributions; or size of the data. We identify a metric of the space that the graph is drawn in, as a probability distribution of a random variable that we introduce, namely, a variable that represents the disparity between the connectedness of two vertices of the graph, and the correlation between the two random variables that are attached to the respective vertex. It is the closed-form {\it{cdf}} of this disparity variable that we advance as the distance function of the host space of the learnt RGG, such that the edge exists between any two nodes, if this inter-nodal distance falls short of a chosen cutoff probability. Drawing the RGG in this probabilistic space leads to the graph being an Soft RGG, such that any edge - if it exists - exists with an identified probability. We forward a simple Rejection Sampling-based technique for learning the probability of any edge. The expected degree distribution of a vertex of this RGG is identified as local, and dependent on the inter-observable correlation matrix. If said correlation matrix is not known, it can be learnt given the data, using its closed-form posterior probability density function, that we forward. We illustrate our graph learning method by learning multiple RGGs of highly multivariate real datasets.

Figures & tables

Fig 1: Flow depicting inference undertaken, when the correlation matrix of the given dataset is known or to-be-learnt.

Fig 2: RGG ${\cal G}_{S,\boldsymbol{\Sigma}_{C}^{(St)}}(\boldsymbol{V},0.1)$ , representing the human disease-phenotype network that we learn using the computed Spearman rank correlation between the rank vectors of a list of phenotypes relevant to a disease, where the phenotype ranking reflects semantic relevance of a phenotype to the disease in question (quantified by HSG as the NPMI parameter in the ${\bf D}_{DPh}$ dataset). In our learnt RGG, $\tau=0.1$ . Here the vertex set $\boldsymbol{V}$ has 8676 elements, but nodes with no edges are discarded from this visualised graph, resulting in 6052 diseases (nodes) and 145210 edges that are shown this figure. Diseases identified by HSG, to belong to one of the 19 given disease class, are presented above in the same colour; the colour key identifying these classes, is attached.

Fig 3: Left: comparison of the relative number of nodes (diseases) that we recover in each of the 19 disease classes (in filled circles joined by solid lines), with the relative class-membership reported by HSG overplotted as open circles threaded by broken lines, Right: our computed ratios of the averaged intra-class to inter-class variance for each of the 19 classes, shown in filled circles; the ROC Area Under Curve values reported by HSG for each class, is overplotted as open circles joined by broken lines. The disease class indices are assigned values 1 to 19; these are the following disease classes respectively: cellular proliferation diseases, integumentary diseases, diseases of the nervous system, genetic diseases, diseases of metabolism, diseases by infectious agents, diseases of mental health, physical disorders, diseases of the reproductive system, of the immune system, of the respiratory system, of the musculoskeletal system, syndromes, gastrointestinal diseases,cardiovascular diseases, urinary diseases, viral infections, thoracic diseases, diseases of the endocrine system.

Panel of Figure 4 — Fig 4: Block of two left-most panels: panel on the bottom left of this block displays the logarithm of the posterior of the RGG variable of dataset ${\bf D}_{loc}$ , learnt at varying values of the cut-off probability. The slope of this graph posterior (with respectto $\tau$ ) is plotted against $\tau$ on the bottom right. The vertical line in black marks the $\tau$ value of 0.2643, at which this slope appears to be minimised. That this $\tau$ value is a minima of the slope, is confirmed by plotting the parametric fit to the numerically-computed first derivative of the slope function with respect to $\tau$ (in the top left), while the fit to the second derivative of the slope function is plotted on the top right of this block. Numerical derivative computation is done via differencing in Python, and fits to the computed data are identified using NumPy’s polynomial fitting, (in Python). The vertical lines in these panels respectively confirm the approximately zero value of the first derivative of the slope, as well as the positivity of the second derivative - at $\tau=0.2643$ . Block of two right-most panels: the same as the two left panels discussed above, except here results relevant to the RGG variable of daatset ${\bf D}_{storm}$ are presented. The optimal $\tau$ value for the RGG of this data is identified as $\tau^{\star}=0.07808$ , at which the slope of the RGG variable with respect to $\tau$ attains a minima (shown by vertical line in the bottom right panel of this block); where first derivative of the slope is approximately 0, (shown in the top left); and its second derivative is positive, as depicted by the vertical line at $\tau\approx 0.07808$ in the top right panel.

Panel of Figure 5 — Fig 5: Left: the learnt RGG ${\cal G}_{S,\boldsymbol{\Sigma}_{loc}}(\boldsymbol{V}_{loc},\tau^{\star})$ , where $\tau^{\star}=0.2643$ . The RGG displays four clusters, where the nodes of each cluster are represented in distinct colours. Right: ${\cal G}_{S,\boldsymbol{\Sigma}_{storm}}(\boldsymbol{V}_{storm},0.07808)$ learnt at the optimal $\tau$ , given dataset ${\bf D}_{storm}$ . Nodes that belong to the distinct clusters of this graph, are presented in distinct colours. Membership in a cluster is identified using the clustering function in the Network package in Python.

Panel of Figure 6 — Fig 6: Top row: RGGs learnt at $\tau$ values of 0.1752, 0.3630, 0.6036, 0.7968, from left to right. Nodes that have a degree of 0, are coloured red in these RGGs. The RGG in the second from left panel, represents the RGG learnt at the optimal $\tau$ , given the dataset ${\bf D}_{user}$ ; nodes in the two modal clusters of this graph are coloured green and blue. Bottom row: figure representing the degree distribution of a learnt RGG, is placed below the panel that presents the learnt RGG.

Graph Structure Learning

Graph structure learning infers or adapts network connections from data for statistical discovery and downstream prediction.

See all 139 papers

Denoising distances beyond the volumetric barrier
Apr 1, 2026Han Huang, Pakawut Jiradilok, Elchanan MosselManifold Learning Latent Space Geometry
Multi-Source Wasserstein Distributionally Robust Graph Learning
Aug 20, 2026Chuansen Peng, Yifan Xia, Jinshan Zhong +1Graph Structure Learning Graph Representation Learning
School of Mathematics, Sichuan University, Chengdu, Sichuan, 610064, China · School of Statistics and Data Science, Southwestern University of Finance and Economics, Chengdu, Sichuan, 611130, China
Reconsidering Dependency Networks from an Information Geometry Perspective
Apr 1, 2026Kazuya Takabatake, Shotaro AkahoGraph Structure Learning Markov Chain Monte Carlo
Independent Researcher, Izumisano, Osaka, Japan · The Institute of Statistical Mathematics, Tachikawa, Tokyo, 190-8565, Japan

Apr 1, 2026J/K move · Enter open · S save

Denoising distances beyond the volumetric barrier

Han Huang, Pakawut Jiradilok, Elchanan Mossel

Manifold Learning Latent Space Geometry

Open paper AskPDF arXiv

We study the problem of reconstructing the latent geometry of a

d

-dimensional Riemannian manifold from a random geometric graph. While recent works have made significant progress in manifold recovery from random geometric graphs, and more generally from noisy distances, the precision of pairwise distance estimation has been fundamentally constrained by the volumetric barrier, namely the natural sample-spacing scale

n^{-1/d}

coming from the fact that a generic point of the manifold typically lies at distance of order

n^{-1/d}

from the nearest sampled point. In this paper, we introduce a novel approach, Orthogonal Ring Distance Estimation Routine (ORDER), which achieves a pointwise distance estimation precision of order

n^{-2/(d+5)}

up to polylogarithmic factors in

n

in polynomial time. This strictly beats the volumetric barrier for dimensions

d > 5

. As a consequence of obtaining pointwise precision better than

n^{-1/d}

, we prove that the Gromov--Wasserstein distance between the reconstructed metric measure space and the true latent manifold is of order

n^{-1/d}

. This matches the Wasserstein convergence rate of empirical measures, demonstrating that our reconstructed graph metric is asymptotically as good as having access to the full pairwise distance matrix of the sampled points. Our results are proven in a very general setting which includes general models of noisy pairwise distances, sparse random geometric graphs, and unknown connection probability functions.

Abstract

Graph Structure Learning

Explore similar work

Denoising distances beyond the volumetric barrier

Multi-Source Wasserstein Distributionally Robust Graph Learning

Reconsidering Dependency Networks from an Information Geometry Perspective