Stability of Entropic Wasserstein Barycenters and application to random geometric graphs

• URL: http://arxiv.org/abs/2210.10535v2
• Date: Mon, 27 Mar 2023 10:01:30 GMT
• Title: Stability of Entropic Wasserstein Barycenters and application to random geometric graphs
• Authors: Marc Theveneau, Nicolas Keriven
• Abstract summary: Wasserstein barycenters (WB) are a notion of barycenters derived from the theory of Optimal Transport. We show how WBs on discretized meshes relate to the geometry of the underlying manifold.
• Score: 8.7314407902481
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: As interest in graph data has grown in recent years, the computation of various geometric tools has become essential. In some area such as mesh processing, they often rely on the computation of geodesics and shortest paths in discretized manifolds. A recent example of such a tool is the computation of Wasserstein barycenters (WB), a very general notion of barycenters derived from the theory of Optimal Transport, and their entropic-regularized variant. In this paper, we examine how WBs on discretized meshes relate to the geometry of the underlying manifold. We first provide a generic stability result with respect to the input cost matrices. We then apply this result to random geometric graphs on manifolds, whose shortest paths converge to geodesics, hence proving the consistency of WBs computed on discretized shapes.

Related papers

• Ironing the Graphs: Toward a Correct Geometric Analysis of Large-Scale Graphs [2.2557806157585834]
  We argue that the classical embedding techniques cannot lead to correct geometric interpretation as they miss the curvature at each point, of manifold. We present an embedding approach, the discrete Ricci flow graph embedding (dRfge) based on the discrete Ricci flow. A major contribution of this paper is that for the first time, we prove the convergence of discrete Ricci flow to a constant curvature and stable distance metrics over the edges.
  arXiv  Detail & Related papers  (2024-07-31T13:47:53Z)
• Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
  We study a random graph model for small-world networks which are ubiquitous in social and biological sciences. For both detection and recovery of the planted dense cycle, we characterize the information-theoretic thresholds in terms of $n$, $tau$, and an edge-wise signal-to-noise ratio $lambda$.
  arXiv  Detail & Related papers  (2024-02-01T03:39:01Z)
• Towards Efficient Time Stepping for Numerical Shape Correspondence [55.2480439325792]
  Methods based on partial differential equations (PDEs) have been established, encompassing e.g. the classic heat kernel signature. We consider here several time stepping schemes. The goal of this investigation is to assess, if one may identify a useful property of methods for time integration for the shape analysis context.
  arXiv  Detail & Related papers  (2023-12-21T13:40:03Z)
• The Fisher-Rao geometry of CES distributions [50.50897590847961]
  The Fisher-Rao information geometry allows for leveraging tools from differential geometry. We will present some practical uses of these geometric tools in the framework of elliptical distributions.
  arXiv  Detail & Related papers  (2023-10-02T09:23:32Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Geometric Scattering on Measure Spaces [12.0756034112778]
  We introduce a general, unified model for geometric scattering on measure spaces. We consider finite measure spaces that are obtained from randomly sampling an unknown manifold. We propose two methods for constructing a data-driven graph on which the associated graph scattering transform approximates the scattering transform on the underlying manifold.
  arXiv  Detail & Related papers  (2022-08-17T22:40:09Z)
• 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)
• q-Paths: Generalizing the Geometric Annealing Path using Power Means [51.73925445218366]
  We introduce $q$-paths, a family of paths which includes the geometric and arithmetic mixtures as special cases. We show that small deviations away from the geometric path yield empirical gains for Bayesian inference.
  arXiv  Detail & Related papers  (2021-07-01T21:09:06Z)
• On Riemannian Optimization over Positive Definite Matrices with the Bures-Wasserstein Geometry [45.1944007785671]
  We comparatively analyze the Bures-Wasserstein (BW) geometry with the popular Affine-Invariant (AI) geometry. We build on an observation that the BW metric has a linear dependence on SPD matrices in contrast to the quadratic dependence of the AI metric. We show that the BW geometry has a non-negative curvature, which further improves convergence rates of algorithms over the non-positively curved AI geometry.
  arXiv  Detail & Related papers  (2021-06-01T07:39:19Z)
• Bayesian Quadrature on Riemannian Data Manifolds [79.71142807798284]
  A principled way to model nonlinear geometric structure inherent in data is provided. However, these operations are typically computationally demanding. In particular, we focus on Bayesian quadrature (BQ) to numerically compute integrals over normal laws. We show that by leveraging both prior knowledge and an active exploration scheme, BQ significantly reduces the number of required evaluations.
  arXiv  Detail & Related papers  (2021-02-12T17:38:04Z)
• Computationally Tractable Riemannian Manifolds for Graph Embeddings [10.420394952839242]
  We show how to learn and optimize graph embeddings in certain curved Riemannian spaces. Our results serve as new evidence for the benefits of non-Euclidean embeddings in machine learning pipelines.
  arXiv  Detail & Related papers  (2020-02-20T10:55:47Z)

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.