Our paper “Fast Graph Laplacian Estimation using Effective Resistance” has just been accepted to IEEE Signal Processing Letters. This is work by my PhD student Christoffer Kjellson and in collaboration with Claudio Altafini.
The problem is to infer the structure of a network from noisy observations, in particular when we have fewer observations than nodes. Existing methods for this typically rely on iterative optimization, which can become computationally expensive.
Our key idea is to instead exploit the effective resistance as a distance metric in the graph. We show that a simple nonlinear transformation of these distances can be used to regularize the noisy data, after which the graph Laplacian can be reconstructed directly, without iterative optimization.
Christoffer’s experiments shows that our method achieves comparable graph-recovery performance to existing methods while being substantially faster.
This graph signal processing direction new for my group and I am excited to see where it takes us. Feedback and ideas are welcome!
