Effective resistance in metric spaces

• URL: http://arxiv.org/abs/2306.15649v1
• Date: Tue, 27 Jun 2023 17:43:18 GMT
• Title: Effective resistance in metric spaces
• Authors: Robi Bhattacharjee, Alexander Cloninger, Yoav Freund, Andreas Oslandsbotn
• Abstract summary: Effective resistance (ER) is an attractive way to interrogate the structure of graphs. We show that the ER between any two points converges to a trivial quantity as the size of the sample increases to infinity. By keeping the regions fixed, we show analytically that the region-based ER converges to a non-trivial limit as the number of points increases to infinity.
• Score: 65.94598202303497
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Effective resistance (ER) is an attractive way to interrogate the structure of graphs. It is an alternative to computing the eigenvectors of the graph Laplacian. One attractive application of ER is to point clouds, i.e. graphs whose vertices correspond to IID samples from a distribution over a metric space. Unfortunately, it was shown that the ER between any two points converges to a trivial quantity that holds no information about the graph's structure as the size of the sample increases to infinity. In this study, we show that this trivial solution can be circumvented by considering a region-based ER between pairs of small regions rather than pairs of points and by scaling the edge weights appropriately with respect to the underlying density in each region. By keeping the regions fixed, we show analytically that the region-based ER converges to a non-trivial limit as the number of points increases to infinity. Namely the ER on a metric space. We support our theoretical findings with numerical experiments.

Related papers

• Shot-noise reduction for lattice Hamiltonians [0.7852714805965528]
  Efficiently estimating energy expectation values of lattice Hamiltonians on quantum computers is a serious challenge. We introduce geometric partitioning as a scalable alternative. We show how the sampling number improvement translates to imperfect eigenstate improvements.
  arXiv  Detail & Related papers  (2024-10-28T17:50:28Z)
• 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)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• 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)
• Bump hunting through density curvature features [0.0]
  We define an abstract bump construct based on curvature functionals of the probability density. We present theoretical results that assure the consistency of bump boundaries in the Hausdorff distance with affordable convergence rates. We conclude that the different curvature instances effectively combine to generate insightful visualizations.
  arXiv  Detail & Related papers  (2022-07-30T10:00:42Z)
• Universality in Anderson localization on random graphs with varying connectivity [0.0]
  We show that there should be a non-ergodic region above a given value of disorder $W_E$. Although no separate $W_E$ exists from $W_C$, the length scale at which fully developed ergodicity is found diverges like $|W-W_C|-1$. The separation of these two scales at the critical point allows for a true non-ergodic, delocalized region.
  arXiv  Detail & Related papers  (2022-05-29T09:47:39Z)
• Structure from Voltage [6.212269948361801]
  Effective resistance (ER) is an attractive way to interrogate the structure of graphs. We show that by using scaling resistances in a graph with $n$ vertices by $n2$, one gets a meaningful limit of the voltages and of effective resistances. We also show that by adding a "ground" node to a metric graph one gets a simple and natural way to compute all of the distances from a chosen point to all other points.
  arXiv  Detail & Related papers  (2022-02-28T20:06:10Z)
• Convergence of Gaussian-smoothed optimal transport distance with sub-gamma distributions and dependent samples [12.77426855794452]
  This paper provides convergence guarantees for estimating the GOT distance under more general settings. A key step in our analysis is to show that the GOT distance is dominated by a family of kernel maximum mean discrepancy distances.
  arXiv  Detail & Related papers  (2021-02-28T04:30:23Z)
• The Convergence Indicator: Improved and completely characterized parameter bounds for actual convergence of Particle Swarm Optimization [68.8204255655161]
  We introduce a new convergence indicator that can be used to calculate whether the particles will finally converge to a single point or diverge. Using this convergence indicator we provide the actual bounds completely characterizing parameter regions that lead to a converging swarm.
  arXiv  Detail & Related papers  (2020-06-06T19:08: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.