CS Paper Radar

Learning Random Geometric Graphs Drawn in Probabilistic Metric Spaces

Dalia Chakrabarty, Kangrui Wang, Chuqiao Zhang, Ye Liu

cs.LG stat.MLstat.AP ·submitted 2026-08-19 16:31 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Detecting Random Geometric Graphs with General Kernel

cs.IT math.STmath.PR ·2026-10-08 ·Dong Huang, Shuangping Li
similarity 0.63
Abstract

We study testing a random geometric graph with a fixed kernel against an Erdős-Rényi graph with the same edge density. Under the null hypothesis, the graph has $n$ vertices and independent edges with probability $p$. Under the alternative hypothesis, latent points $X_1,\ldots,X_n$ are independent and uniform on $\mathbb{S}^{d-1}$, and edges are conditionally independent with probabilities $K(\langle X_i,X_j\rangle)$, where $p=\mathbb{E}[K(\langle X_1,X_2\rangle)]$. The goal is to determine a critical dimension $d_\star = d_\star(n,K)$: the total variation distance between the two graph laws tends to one for $d\ll d_\star$ and to zero for $d\gg d_\star$. For dense graphs, [BDER16] established $d_\star\asymp n^3$ for hard threshold kernels, whereas [MWX26] proved $d_\star\asymp n^{3/4}$ for smooth kernels with $K'(0)\ne0$. We connect these results by characterizing the detection thresholds for kernels that need not be differentiable at zero. We also determine the thresholds for smooth kernels whose first nonzero derivative at zero has finite order greater than one. Throughout these classes, signed triangle or quadrilateral counts attain the optimal detection threshold. For certain nondifferentiable kernels, quadrilateral counts are optimal while triangle counts are suboptimal.

0.30

From topology learning to graph generation: A unifying perspective

cs.LG stat.MLeess.SP ·2026-09-02 ·Xiaowen Dong, Hoi-To Wai, Siheng Chen, Laura Toni, Dorina Thanou
similarity 0.62
Abstract

Learning graph structures from data is a fundamental problem that spans a wide range of signal processing and machine learning tasks. While significant effort has been made to tackle the problem, existing research has largely evolved along two parallel directions. The first seeks to infer the topology of an individual graph from observations supported on it, whereas the second seeks to learn a generative distribution from observed graph instances, enabling the sampling of new graphs. This review presents a unified framework that connects these formulations by viewing them as inverse problems of a common generation process for graph data. We review the major methodologies within this framework, highlight their relationships, strengths, and limitations, and identify opportunities for integrating ideas across paradigms. By bridging graph topology learning and graph generation, this review provides a broader cross-disciplinary perspective on the field and outlines promising directions for future research.

0.27

Correlation Clustering with Random Partial Information

cs.DS cs.LG ·2026-08-17 ·Rajath Rao K. N., Jens Schlöter, Sami Davies, Amira Ouchene, Yasamin Nazari
theory similarity 0.62
Abstract · 17 pages, 5 figures, 6 tables

Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, yet on general (non-complete) graphs, the best guarantees blow up to $O(\log n)$ and $O(\sqrt{n})$. This gap between the two regimes motivates the following question: are there classes of incomplete graphs that circumvent the lower bounds on general graphs and admit approximation guarantees approaching those attainable on complete graphs? We study a natural class of graphs obtained by randomly subsampling a complete signed graph $G$, where each edge is independently deleted with probability $q$. For such graph instances both for the min-max and the min-disagreement objectives, we prove approximation guarantees (depending on $q$) that are substantially better than the bounds achievable for general graphs. We supplement our theoretical results with experiments that also suggest that the approximation ratios of our algorithm are close to those of the complete graph and better than the worst-case bounds for general (non-complete) graphs.

0.26

Learning Submanifolds for Subsequent Inference on Random Dot Product Graphs, Part 1: Theory

cs.LG stat.ML ·2026-09-16 ·Michael W. Trosset, Carey E. Priebe
similarity 0.61
Abstract · 23 pages

We propose a framework for restricted inference on random dot product graphs whose latent positions lie on an unknown low-dimensional support manifold. For general decision problems, we propose semisupervised decision rules that use auxiliary data to learn the support manifold. Specifically, our rules use the Isomap manifold learning procedure to construct a low-dimensional Euclidean representation of the observed graph, in which space an isometrically invariant function maps configurations of points to actions. We study the behavior of the proposed rules as the quantity of auxiliary data sampled from the unknown support manifold increases. We show that, as the auxiliary sample size increases, the risk of the semisupervised rule converges to the risk of an oracle rule that relies on the maximal amount of low-dimensional Euclidean structure that can be extracted from the support manifold. Examples, applications, and simulation studies are deferred to a sequel.

0.38

A Probabilistic Interpretation of the Ball Mapper Graph

cs.CG math.AT ·2026-08-11 ·John Rick Manzanares, Jay-Anne Bulauan
theory similarity 0.60
Abstract

We introduce Probabilistic Ball Mapper, a formulation of Ball Mapper in which each data point is assigned a probability distribution supported only on the metric balls that contain it. This assignment defines both a partition subordinate to the Ball Mapper cover and a Markov kernel from the finite data space to the cover. We study two assignment schemes: a uniform-on-support rule and a localized radial-basis rule that incorporates distance to landmarks while preserving the underlying cover. Pushing the empirical data distribution through the kernel produces a probability distribution over vertices. Drawing twice, conditionally and independently, from each pointwise distribution produces a soft-overlap matrix. This matrix is symmetric, nonnegative, positive semidefinite, and has the vertex distribution as both marginals. It therefore provides a mass-normalized refinement of classical Ball Mapper overlap rather than another unnormalized edge count. For graphs constructed on a common cover, the vertex and overlap distributions can be compared directly. For independently fitted covers, we formulate Wasserstein and fused Gromov--Wasserstein-type discrepancies that account for vertex mass, landmark geometry when a common ambient metric is available, and intrinsic graph relations. For a fixed cover, we derive explicit perturbation bounds controlled by the sensitivity of the assignment rule, the magnitude of the data perturbation, and the data mass near cover boundaries. When the cover is recomputed, landmark motion creates an additional source of variation, for which we state a transport-based stability principle rather than an unconditional theorem. The resulting framework turns Ball Mapper into a probability-valued representation suitable for quantitative comparison while retaining its geometric interpretability and computational simplicity.

0.04

Graph Matching in Random Geometric Graphs I: Efficient Algorithms

cs.DS math.PRmath.ST ·2026-10-12 ·Dong Huang, Ankang Jiao, Shuangping Li, Zhangsong Li
hot direction similarity 0.60
Abstract · 62 pages, 4 figures

We study the recovery of the hidden vertex correspondence between two correlated dense random geometric graphs. Each graph is generated from $n$ latent unit vectors in $\mathbb R^d$; the vectors $u_i^A$ and $u_i^B$ of corresponding vertices satisfy $\langle u_i^A,u_i^B\rangle=ρ$, and the vertex labels of the second graph are permuted by an unknown permutation $π$. For every fixed correlation $ρ\in(0,1]$ and every edge density bounded away from zero and one, we give a randomized polynomial time algorithm that recovers $π$ exactly with probability tending to one whenever $d\ge(\log n)^L$, where $L$ depends only on the correlation and the density bounds. The algorithm assigns to each vertex a signature formed by counting decorated paths with a constant number of seeds. The number of such seeded templates grows exponentially with the path length, with an arbitrarily large constant base, so the resulting statistics amplify an arbitrarily small constant correlation. We control the dependencies created by the latent geometry in two ways: when $d$ is larger than $n/(\log n)^{L_0}$ for a suitable constant $L_0$, by comparing local moments with those of correlated Erdős--Rényi graphs; for smaller $d$, by spectral estimation of the latent geometry combined with a harmonic correction. We also provide low-degree evidence for a tradeoff between the correlation and the computational cost.

0.36

Topology-induced Operators Reveal Complementary Graph Representations without Training

cs.LG cs.SI ·2026-09-08 ·Meng Qin, Jinqiang Cui, Hongwei Zheng, Weihua Li, Sen Pei
similarity 0.59
Abstract

Graph representation learning has largely focused on designing increasingly sophisticated models to transform graph topology into vector representations, or embeddings. However, the extent to which embedding quality depends on model learning, rather than on the underlying topological transformations, remains unclear. Here, we show that informative embeddings can be derived without complicated model design and gradient-based training. Propagating random features through implicit hierarchical structures induced by random walks and anonymous walks yields embeddings that capture node proximity and structural role, respectively. These two training-free embeddings preserve complementary aspects of graph organization and perform competitively with classic and recent methods across various node-, edge-, and graph-level tasks. They often require substantially less computation, resulting in a favorable quality-efficiency trade-off. Combining the two types of embeddings further improves inference quality of some tasks compared with using either embedding type alone. Our results suggest that informative graph embeddings can arise from carefully chosen topological transformations before any learning operation is applied.

0.04

Multi-Source Wasserstein Distributionally Robust Graph Learning

cs.LG ·2026-08-20 ·Chuansen Peng, Yifan Xia, Jinshan Zhong, Xiaojing Shen
theory similarity 0.59
Abstract

Reconstructing complex network topologies from data is a fundamental challenge in cybernetics and graph signal processing, with applications in neuroscience, sensor, and social networks. In practice, target-domain samples are scarce while heterogeneous source-domain data are abundant. Fusing these sources is challenging: Euclidean averaging works for homogeneous sources but degrades sharply as inter-source divergence grows, collapsing distinct geometries into an inflated, biased consensus. We exploit the Wasserstein metric's distribution-preserving properties to counter heterogeneity while preserving each source's intrinsic geometry. We propose MS-WDRO, a multi-source Wasserstein distributionally robust graph learning framework that fuses heterogeneous sources via their weighted Wasserstein barycenter, a geometrically principled nominal distribution, then builds an ambiguity ball around it to hedge residual uncertainty. Minimizing worst-case risk yields a tractable regularized Laplacian estimator solved efficiently via a provably convergent ADMM scheme. We establish non-asymptotic guarantees: a finite-sample concentration bound for the empirical barycenter, a pooling bias lower bound proving naive aggregation is suboptimal, and an out-of-sample excess risk bound decaying at a parametric rate with only logarithmic dependence on source count. To calibrate hyperparameters governing robustness, sparsity, and source fusion, we unroll the solver into a differentiable architecture trained end-to-end, achieving data-adaptive calibration beyond cross-validation while retaining interpretability. Experiments on synthetic benchmarks and the multi-site ABIDE~I neuroimaging dataset show MS-WDRO consistently outperforms seven baselines in graph recovery, sample efficiency, and downstream diagnostic utility, with the largest gains in the sample-scarce regime.

0.11