Entropic Optimal Transport in Random Graphs
- URL: http://arxiv.org/abs/2201.03949v1
- Date: Tue, 11 Jan 2022 13:52:34 GMT
- Title: Entropic Optimal Transport in Random Graphs
- Authors: Nicolas Keriven
- Abstract summary: 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.
- Score: 8.7314407902481
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In graph analysis, a classic task consists in computing similarity measures
between (groups of) nodes. In latent space random graphs, nodes are associated
to unknown latent variables. One may then seek to compute distances directly in
the latent space, using only the graph structure. In this paper, we show that
it is possible to consistently estimate entropic-regularized Optimal Transport
(OT) distances between groups of nodes in the latent space. We provide a
general stability result for entropic OT with respect to perturbations of the
cost matrix. We then apply it to several examples of random graphs, such as
graphons or $\epsilon$-graphs on manifolds. Along the way, we prove new
concentration results for the so-called Universal Singular Value Thresholding
estimator, and for the estimation of geodesic distances on a manifold.
Related papers
- Node Regression on Latent Position Random Graphs via Local Averaging [10.962094053749093]
We study the performance of various estimators for node regression.
An alternative consists in first estimating the true distances between the latent positions, then injecting these estimated distances into a classical Nadaraya Watson estimator.
We show that this method can achieve standard nonparametric rates in certain instances even when the graph neighborhood is too large or too small.
arXiv Detail & Related papers (2024-10-29T12:17:06Z) - Generalization of Geometric Graph Neural Networks [84.01980526069075]
We study the generalization capabilities of geometric graph neural networks (GNNs)
We prove a generalization gap between the optimal empirical risk and the optimal statistical risk of this GNN.
The most important observation is that the generalization capability can be realized with one large graph instead of being limited to the size of the graph as in previous results.
arXiv Detail & Related papers (2024-09-08T18:55:57Z) - An Ad-hoc graph node vector embedding algorithm for general knowledge graphs using Kinetica-Graph [0.0]
This paper discusses how to generate general graph node embeddings from knowledge graph representations.
The embedded space is composed of a number of sub-features to mimic both local affinity and remote structural relevance.
arXiv Detail & Related papers (2024-07-22T14:43:10Z) - Reconstructing the Geometry of Random Geometric Graphs [9.004991291124096]
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.
arXiv Detail & Related papers (2024-02-14T21:34:44Z) - 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) - Graph Fourier MMD for Signals on Graphs [67.68356461123219]
We propose a novel distance between distributions and signals on graphs.
GFMMD is defined via an optimal witness function that is both smooth on the graph and maximizes difference in expectation.
We showcase it on graph benchmark datasets as well as on single cell RNA-sequencing data analysis.
arXiv Detail & Related papers (2023-06-05T00:01:17Z) - 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) - Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF)
We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF)
We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
arXiv Detail & Related papers (2022-05-28T15:37:03Z) - A metric on directed graphs and Markov chains based on hitting
probabilities [0.0]
We introduce a metric on the state space of any ergodic, finite-state, time-homogeneous Markov chain.
Our construction is based on hitting probabilities, with nearness in the metric space related to the transfer of random walkers from one node to another at stationarity.
Notably, our metric is insensitive to shortest and average walk distances, thus giving new information compared to existing metrics.
arXiv Detail & Related papers (2020-06-25T15:25:05Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs.
We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions.
Our methods are scalable to sparse graphs consisting of millions of nodes.
arXiv Detail & Related papers (2020-02-14T11:42:16Z)
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.