Affinity graphs from effective conductances

Several algorithms for real-world problems encode data and their relationships as graphs. In particular, the so-called 'affinity' graphs are very useful in the context of computer vision where they're used among else in image segmentation. It is well known that the quality of affinity graphs affects directly the segmentation quality. As a result, research on affinity schemes is central in computer vision.  In this work we propose a method that views the affinity graph as an electrical network and iteratively updates the weights of an initial `naive' affinity graph with their effective conductances, i.e. an electrical measure of connectivity. 

Finding the effective conductances takes O(n^2.5) time with standard algorithms, where n is the number of pixels in the image. In our work we take  advantage of very recent breakthroughs in algorithms, and in particular fast linear system solvers as well as the Johnson-Lindenstrauss theorem to reduce the computational time of finding the effective resistances to O(n lg²n). 

We evaluate the algorithm on several images, with an emphasis on neural images, with the purpose of advancing the state of the art in the acquisition of connectomes, i.e. maps of neurons and and their connections.