Graph learning improves connectivity from limited data
Graph Learning with Spectral Connectivity Priors for Scarce Data
Machine Learning
Summary
Learning the structure of a network from very little data is hard because you want the network to be both simple and well-connected. The authors propose a method that encourages the network to have strong overall links while remaining sparse locally by using special mathematical clues from graph theory. They develop a way to optimize this idea efficiently and show it gives better results when data is scarce, for example, in cleaning noisy signals connected by the network. This approach helps discover meaningful network patterns when few observations are available.
What this means in practice
- •For data engineers: Construct sparse but globally connected graphs from limited datasets to improve network-based data analysis and predictions.
- •For signal processing teams: Enhance denoising of signals defined over graphs when only small amounts of data are available by using learned graph structures.
Authors
Mingxiao Liu, Bahar Oveisgharan, Bingyan Zou, Gene Cheung, H. Vicky Zhao, Feifei Gao
Abstract
Learning a sparse graph from scarce data is practically important but challenging. Motivated by the desirable combination of local sparsity and strong global connectivity exhibited by expander-like graphs, we propose spectral connectivity-regularized graph learning (SCoGL), a framework that incorporates a family of Laplacian spectral priors to explicitly promote global connectivity. Specifically, SCoGL augments a combinatorial-Laplacian-constrained graphical lasso (GLASSO) objective over a target adjacency matrix $\mathbf{W}$ with a general connectivity prior computed from Laplacian eigenvalues. We derive gradients for several representative connectivity priors and develop a projected gradient descent (PGD) algorithm with Armijo backtracking to efficiently optimize $\mathbf{W}$. Experiments show that the proposed SCoGL variants improve graph recovery and enhance downstream tasks such as graph signal denoising when signal observations are scarce.