# An efficient algorithm for graph Laplacian optimization based on effective resistances

arXiv: https://arxiv.org/abs/2004.08451 · HTML: https://mlsanity.com/paper/2004.08451/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Apr 2020.

## Built on by (most cited first, 4 of 4)

- [Laplacian Constrained Precision Matrix Estimation: Existence and High Dimensional Consistency](https://mlsanity.com/paper/2111.00590/) (2021)
- [Towards joint graph learning and sampling set selection from data](https://mlsanity.com/paper/2412.09753/) (2024)
- [Joint Graph and Vertex Importance Learning](https://mlsanity.com/paper/2303.08552/) (2023)
- [Fast Graph Laplacian Estimation using Effective Resistance](https://mlsanity.com/paper/2609.23668/) (2026)

## Abstract (arXiv)

In graph signal processing, data samples are associated to vertices on a graph, while edge weights represent similarities between those samples. We propose a convex optimization problem to learn sparse well connected graphs from data. We prove that each edge weight in our solution is upper bounded by the inverse of the distance between data features of the corresponding nodes. We also show that the effective resistance distance between nodes is upper bounded by the distance between nodal data features. Thus, our proposed method learns a sparse well connected graph that encodes geometric properties of the data. We also propose a coordinate minimization algorithm that, at each iteration, updates an edge weight using exact minimization. The algorithm has a simple and low complexity implementation based on closed form expressions.