Effective resistance in metric spaces
This work addresses a limitation in graph analysis for point cloud data, offering a method to extract meaningful structural information from large samples, though it appears incremental as it builds on existing ER theory.
The authors tackled the problem of effective resistance (ER) becoming trivial for large point clouds by proposing a region-based ER between small regions with density-scaled edge weights, and they proved that this approach converges to a non-trivial limit as point count increases, supported by numerical experiments.
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.