# Sparse Graph Learning from Sparse Data via Fiedler Number Maximization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 20 references that are in the map.
- First posted on arXiv 28 Apr 2026.

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

- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Graph Learning: A Survey](https://mlsanity.com/paper/2105.00696/) (2021)
- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [Graph Spectral Image Processing](https://mlsanity.com/paper/1801.04749/) (2018)
- [Structured Graph Learning Via Laplacian Spectral Constraints](https://mlsanity.com/paper/1909.11594/) (2019)
- [Fiedler Regularization: Learning Neural Networks with Graph Sparsity](https://mlsanity.com/paper/2003.00992/) (2020)
- [Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection](https://mlsanity.com/paper/2010.13179/) (2020)
- [Graph Sparsification for GCN Towards Optimal Crop Yield Predictions](https://mlsanity.com/paper/2306.01725/) (2023)
- [Signal Processing in the Retina: Interpretable Graph Classifier to Predict Ganglion Cell Responses](https://mlsanity.com/paper/2401.01813/) (2024)

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

- [Graph Learning with Spectral Connectivity Priors for Scarce Data](https://mlsanity.com/paper/2609.27278/) (2026)

## Abstract (arXiv)

We aim to learn a sparse and connected graph from sparse data, where the number of observations K can be substantially smaller than the signal dimension N for signals x in R^N, and the underlying distribution is unknown. In this severely ill-posed setting, we incorporate Fiedler number (the second eigenvalue of the graph Laplacian matrix that quantifies connectedness) as a robust regularization term in the sparse graph learning objective. We first develop a greedy algorithm that iteratively selects one edge globally for weakening/removal to reduce the objective, leveraging eigenvalue perturbation theorems that bound the adverse effect of an edge change to the Fiedler number. Next, we design a parallel variant, based on the Cheeger's inequality, that recursively partitions an input graph into two sub-graphs using an approximate Cheeger cut to distributedly find an optimal edge. Simulation experiments show that Fiedler number maximization robustifies sparse graph estimates, outperforming previous sparse graph learning algorithms.