CS Paper Radar

A Probabilistic Interpretation of the Ball Mapper Graph

John Rick Manzanares, Jay-Anne Bulauan

cs.CG math.AT ·submitted 2026-08-11 20:03 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Learning Random Geometric Graphs Drawn in Probabilistic Metric Spaces

cs.LG stat.MLstat.AP ·2026-08-19 ·Dalia Chakrabarty, Kangrui Wang, Chuqiao Zhang, Ye Liu
similarity 0.60
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.

0.27

FréchetFlow: Flow Matching for Non-Euclidean Data

cs.AI stat.ME ·2026-11-11 ·Yidong Zhou, Muqing Cui, Hans-Georg Müller
similarity 0.59
Abstract · 53 pages, 7 figures

Scientific observations such as probability distributions, trees and covariance matrices call for generative models that respect their non-Euclidean geometry. While flow matching has been extended to manifolds by utilizing geodesics and velocities, such manifold structures are not available in a general metric space. We introduce FréchetFlow, a generative modeling framework for metric space-valued data that requires neither linear operations nor a smooth manifold structure. A key feature of the proposed approach is that we utilize well-established Euclidean flows to learn the joint distribution of distances to a set of landmarks, whereupon new objects are reconstructed from generated landmark representations. The reconstruction step utilizes weighted Fréchet means of reference objects, drawing on Fréchet regression. We establish Wasserstein error bounds that connect accuracy of the generated object distributions to the placement of landmarks, flow approximation and reconstruction error and prove consistency under finite second moments. This leads to convergence rates that depend on the metric complexity of the target objects, tail moments and fitting accuracy. Experiments show competitive accuracy with established flow matching methods in Euclidean simulations and lower Wasserstein errors than specifically tailored methods for several scientific datasets. Across simulation settings, we find that generation error decreases as sample size increases.

0.09

Joint Independence Testing for Latent Position Random Graphs

cs.LG stat.MLcs.SI ·2026-10-25 ·Xiaoyi Wen, Zoltan Szabo
theory similarity 0.57
Abstract

Kernel techniques are among the most powerful methods in data science and statistics. One of the key properties of kernels contributing to their numerous successful applications is that the associated reproducing kernel Hilbert space is expressive enough to encode probability distributions without loss of information or to capture the joint independence of $M\ge 2$ random variables, under mild conditions. Computationally, these measures (i) rely on the so-called Gram matrix which contains the pairwise similarity of sample points, and (ii) converge at a rate $O \left(n^{-\frac{1}{2}}\right)$, where $n$ denotes the sample size. We focus on measuring the independence of latent position random graphs (LPRGs), a model widely-applied for instance in neuroscience, sociology, and epidemiology. In LPRGs a latent representation is associated to each node. The similarity of these representations (meant via a kernel) determines whether two nodes are connected, making the Gram matrices only implicitly observable and the estimation challenging. Despite the fundamental importance of quantifying the independence of $M$ LPRGs, very little is known about the solution of this problem; existing techniques are restricted to $M=2$ components and only guarantee consistency without rates. In this work, (i) we define an independence measure called graph Hilbert-Schmidt independence criterion (GHSIC) for $M\ge 2$ LPRGs, (ii) we prove that it can be estimated at a rate $\tilde{O}\left(n^{-\frac{1}{3}}\right)$ relying on spectral decomposition of adjacency matrices, (iii) without the need to choose kernels and their hyperparameters. Numerical experiments demonstrate the effectiveness of the proposed GHSIC estimator both on synthetic examples and in the analysis of brain functional connectivity subnetworks in natural language perception.

0.19

Probabilistic Scene Graphs: Hierarchical Representation and Real-time System

cs.RO ·2026-09-19 ·Waqas Ali, Michele Antonazzi, Timon Homberger, Thien-Minh Nguyen, Lukas Rosenberger Schmid +2 more
similarity 0.55
Abstract

3D scene graphs provide semantically rich and hierarchical representations for robot perception. However, existing systems do not maintain uncertainty as an explicit belief or propagate it through the operations that construct and refine the graph. We introduce Probabilistic Scene Graph (PSG), a generalization of the conventional scene graph that represents a posterior over possible graphs, factorized into a discrete graph structure of entities, relations, and semantic attributes, and continuous states that ground them spatially, with uncertainty maintained over both components. Geometry is carried directly by the nodes rather than selected from a separately constructed metric map, so a metric map, where needed, follows from the graph rather than preceding it. We instantiate PSG's probabilistic spatial grounding with hierarchical graphs of Gaussians (HGG): each object primitive is represented by a full-covariance Gaussian under a Normal-Inverse-Wishart belief, and the same parametrization applied recursively within a node yields a geometry graph that resolves its surface at finer resolution. We then build a mapping pipeline that preserves these beliefs throughout graph construction and refinement: a purely graph-based coarse-to-fine alignment registers observations by comparing node beliefs, while a nested Expectation-Maximization and factor-graph optimization jointly refines poses, object parameters, and internal geometry. Across six datasets spanning indoor RGB-D, outdoor LiDAR, and cross-modality deployment, HGG operates at sensor rate with near-constant memory and achieves state-of-the-art object accuracy and zero-shot graph alignment.

0.16

A General Kernel Framework for Non-CND Distance Measures Using |D|-Dimensional Sparse Landmark Embeddings

cs.LG stat.MLmath.PR ·2026-09-16 ·Marcus M. Noack, Maher B. Alghalayini, Mark D. Risser
similarity 0.55
Abstract

Kernel methods, and Gaussian Processes (GPs) in particular, require a Hilbertian distance measure---one whose square is conditionally negative definite (CND)---to guarantee positive semi-definiteness (PSD) of the kernel matrix; a condition that fails for many natural input spaces, including smooth manifolds and spaces of probability distributions. We propose the Sparse Landmark Embedding (SLE) kernel, which eliminates this requirement entirely. Each input is embedded into a sparse feature vector via compactly supported bump functions centered at all |D| training points; applying any standard PSD kernel in this embedding space yields a kernel that is provably PSD for arbitrary distance measures. The compact support automatically controls embedding sparsity, keeping kernel matrices well-conditioned and computationally tractable despite the high ambient dimension. We provide theoretical guarantees on PSD, sparsity, stability, and universal approximation, and show that the SLE kernel matches or substantially exceeds domain-specific baselines in both predictive accuracy and uncertainty quantification using geodesic and Wasserstein distances.

0.18

Constant-Curvature Sliced Gromov-Wasserstein for Heterogeneous Cross-Curvature Alignment

cs.LG ·2026-10-05 ·Shanglin Li, Wenjing Lu, Muyang Li, Nicu Sebe, Ziheng Chen
similarity 0.55
Abstract

Recent advances in representation learning have highlighted the utility of constant-curvature models, such as hyperbolic and spherical spaces, for modeling complex data. Mixed-curvature models further enhance this by integrating multiple constant-curvature components. However, these models typically learn each component space independently because spaces with different curvatures are inherently heterogeneous and lack a unified metric. Consequently, they lack explicit mechanisms to enforce geometric consistency across various spaces. Moreover, the problem of comparing probability distributions across mixed-curvature spaces remains unexplored. To compare distributions on heterogeneous spaces, Gromov-Wasserstein (GW) distances provide a principled framework by aligning their intra-space geometries. Building on this, we propose constant-curvature sliced Gromov-Wasserstein (CCSGW), a novel divergence for aligning distributions supported on heterogeneous constant-curvature spaces. We first introduce the missing geodesic-based one-dimensional projections for spherical spaces, and then extend sliced GW to constant-curvature spaces, enabling efficient and principled comparison across manifolds with different curvatures. This formulation preserves intrinsic geometric relationships while avoiding the high computational cost. We provide theoretical analysis showing that CCSGW controls intrinsic geometric discrepancy across heterogeneous spaces, promoting distribution-level geometric consistency. By integrating CCSGW into existing mixed-curvature learning tasks, including graph anomaly detection, graph node classification, and multimodal learning, we observe consistent performance gains across diverse settings.

0.06

Detecting Random Geometric Graphs with General Kernel

cs.IT math.STmath.PR ·2026-10-08 ·Dong Huang, Shuangping Li
similarity 0.55
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

Sliced Wasserstein Sketches with Error Certificates

cs.LG ·2026-10-14 ·Elaheh Akbari, James Liu, Keaton Hamm, Soheil Kolouri
similarity 0.54
Abstract

Compact representations that support geometrically meaningful comparisons are valuable for learning from probability distributions. We study optimal, free-weight $M$-atom quantization of one-dimensional probability measures in quadratic Wasserstein distance and extend it to higher dimensions via slicing. Using $L$ shared projections yields a sketch with $O(LM)$ comparison time. Our main result is an exact decomposition of squared distance error into residual and partition-mismatch terms, yielding computable certificates for arbitrary centroid sketches. For optimal sketches, a finite $(2+δ)$ moment for some $δ>0$ guarantees $O(M^{-1})$ error in the finite-direction sliced distance, while equal-mass sketches can converge more slowly. Each slice preserves its mean, while storing residual energies enables covariance recovery from sufficiently many generic directions. Experiments on document, point-cloud, and flow-cytometry benchmarks show that optimal sketches substantially reduce storage while preserving the classification performance of uncompressed sliced distances. They also improve generalization from few labelled subjects and support end-to-end learning as compact pooling layers.

0.23