Structure from Voltage
This provides a more robust method for graph structure analysis, particularly for data sampled from distributions, which is incremental over prior work on ER limitations.
The paper addresses the problem that effective resistance (ER) becomes trivial for distant points in graphs sampled from metric spaces, by showing that scaling resistances by n^2 yields meaningful limits for voltages and ERs, and introducing a 'ground' node to compute distances efficiently.
Effective resistance (ER) is an attractive way to interrogate the structure of graphs. It is an alternative to computing the eigen-vectors of the graph Laplacian. Graph laplacians are used to find low dimensional structures in high dimensional data. Here too, ER based analysis has advantages over eign-vector based methods. Unfortunately Von Luxburg et al. (2010) show that, when vertices correspond to a sample from a distribution over a metric space, the limit of the ER between distant points converges to a trivial quantity that holds no information about the structure of the graph. We show that by using scaling resistances in a graph with $n$ vertices by $n^2$, 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.