Reconstructing the Geometry of Random Geometric Graphs
- URL: http://arxiv.org/abs/2402.09591v2
- Date: Tue, 11 Jun 2024 01:50:34 GMT
- Title: Reconstructing the Geometry of Random Geometric Graphs
- Authors: Han Huang, Pakawut Jiradilok, Elchanan Mossel,
- Abstract summary: Random geometric graphs are random graph models defined on metric spaces.
We show how to efficiently reconstruct the geometry of the underlying space from the sampled graph.
- Score: 9.004991291124096
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Random geometric graphs are random graph models defined on metric spaces. Such a model is defined by first sampling points from a metric space and then connecting each pair of sampled points with probability that depends on their distance, independently among pairs. In this work, we show how to efficiently reconstruct the geometry of the underlying space from the sampled graph under the manifold assumption, i.e., assuming that the underlying space is a low dimensional manifold and that the connection probability is a strictly decreasing function of the Euclidean distance between the points in a given embedding of the manifold in $\mathbb{R}^N$. Our work complements a large body of work on manifold learning, where the goal is to recover a manifold from sampled points sampled in the manifold along with their (approximate) distances.
Related papers
- Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
Learning disentangled representations from unlabelled data is a fundamental challenge in machine learning.
We introduce a novel approach to disentangled representation learning based on quadratic optimal transport.
We demonstrate the effectiveness of our approach for quantifying disentanglement across four standard benchmarks.
arXiv Detail & Related papers (2024-07-10T16:51:32Z) - Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure.
We introduce a new class of manifold, named soft manifold, that can solve this situation.
Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
arXiv Detail & Related papers (2023-11-29T12:48:33Z) - Neural Latent Geometry Search: Product Manifold Inference via
Gromov-Hausdorff-Informed Bayesian Optimization [21.97865037637575]
We mathematically define this novel formulation and coin it as neural latent geometry search (NLGS)
We propose a novel notion of distance between candidate latent geometries based on the Gromov-Hausdorff distance from metric geometry.
We then design a graph search space based on the notion of smoothness between latent geometries and employ the calculated as an additional inductive bias.
arXiv Detail & Related papers (2023-09-09T14:29:22Z) - Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
We consider graphs as geometric graphs: nodes are randomly sampled from an underlying metric space, and any pair of nodes is connected if their distance is less than a specified neighborhood radius.
In a social network communities can be modeled as densely sampled areas, and hubs as nodes with larger neighborhood radius.
We develop methods to estimate the unknown sampling density in a self-supervised fashion.
arXiv Detail & Related papers (2022-10-15T08:01:08Z) - Shape And Structure Preserving Differential Privacy [70.08490462870144]
We show how the gradient of the squared distance function offers better control over sensitivity than the Laplace mechanism.
We also show how using the gradient of the squared distance function offers better control over sensitivity than the Laplace mechanism.
arXiv Detail & Related papers (2022-09-21T18:14:38Z) - Entropic Optimal Transport in Random Graphs [8.7314407902481]
In graph analysis, a classic task consists in computing similarity measures between (groups of) nodes.
We show that it is possible to consistently estimate distances between groups of nodes in the latent space.
arXiv Detail & Related papers (2022-01-11T13:52:34Z) - Identifying the latent space geometry of network models through analysis
of curvature [7.644165047073435]
We present a method to consistently estimate the manifold type, dimension, and curvature from an empirically relevant class of latent spaces.
Our core insight comes by representing the graph as a noisy distance matrix based on the ties between cliques.
arXiv Detail & Related papers (2020-12-19T00:35:29Z) - Ultrahyperbolic Representation Learning [13.828165530602224]
In machine learning, data is usually represented in a (flat) Euclidean space where distances between points are along straight lines.
We propose a representation living on a pseudo-Riemannian manifold of constant nonzero curvature.
We provide the necessary learning tools in this geometry and extend gradient-based optimization techniques.
arXiv Detail & Related papers (2020-07-01T03:49:24Z) - Disentangling by Subspace Diffusion [72.1895236605335]
We show that fully unsupervised factorization of a data manifold is possible if the true metric of the manifold is known.
Our work reduces the question of whether unsupervised metric learning is possible, providing a unifying insight into the geometric nature of representation learning.
arXiv Detail & Related papers (2020-06-23T13:33:19Z) - Geometry of Similarity Comparisons [51.552779977889045]
We show that the ordinal capacity of a space form is related to its dimension and the sign of its curvature.
More importantly, we show that the statistical behavior of the ordinal spread random variables defined on a similarity graph can be used to identify its underlying space form.
arXiv Detail & Related papers (2020-06-17T13:37:42Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.