# Fast Graph Laplacian Estimation using Effective Resistance

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 25 references that are in the map.
- First posted on arXiv 20 Sep 2026.

## Builds on (most cited first, 8 of 8)

- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Connecting the Dots: Identifying Network Structure via Graph Signal Processing](https://mlsanity.com/paper/1810.13066/) (2018)
- [A Unified Framework for Structured Graph Learning via Spectral Constraints](https://mlsanity.com/paper/1904.09792/) (2019)
- [Model Selection Techniques -- An Overview](https://mlsanity.com/paper/1810.09583/) (2018)
- [An efficient algorithm for graph Laplacian optimization based on effective resistances](https://mlsanity.com/paper/2004.08451/) (2020)
- [Efficient Graph Laplacian Estimation by Proximal Newton](https://mlsanity.com/paper/2302.06434/) (2023)
- [Graph Inference with Effective Resistance Queries](https://mlsanity.com/paper/2502.18350/) (2025)

## Abstract (arXiv)

Inferring network topology from noisy node observations is a central problem in graph signal processing. In this paper, we consider Laplacian-constrained graph estimation for Gaussian Markov random fields, focusing on the underdetermined regime in which the number of samples is smaller than the number of graph nodes. Existing approaches often formulate the problem as a sparsity-regularized maximum-likelihood estimation problem. While effective, such methods typically require iterative optimization and are often computationally demanding, particularly under Laplacian constraints. Instead, we propose a non-iterative estimator of graph Laplacians that uses effective resistance for regularization, and evaluate the method using a simple sparsification procedure. Experiments show that with some trade-off in edge and weight recovery on the considered dataset, computational cost for moderately sized graphs can be substantially reduced.