How to learn a graph from smooth signals
This work addresses the challenge of inferring graph connectivity from data for applications like network analysis, though it appears incremental as it builds on existing graph learning techniques.
The paper tackles the problem of learning graph structures from smooth signals by proposing a framework that formulates it as a weighted ℓ-1 minimization, leading to sparse solutions. It introduces a new model that outperforms state-of-the-art methods in many settings, with efficient primal-dual algorithms validated on artificial and real data.
We propose a framework that learns the graph structure underlying a set of smooth signals. Given $X\in\mathbb{R}^{m\times n}$ whose rows reside on the vertices of an unknown graph, we learn the edge weights $w\in\mathbb{R}_+^{m(m-1)/2}$ under the smoothness assumption that $\text{tr}{X^\top LX}$ is small. We show that the problem is a weighted $\ell$-1 minimization that leads to naturally sparse solutions. We point out how known graph learning or construction techniques fall within our framework and propose a new model that performs better than the state of the art in many settings. We present efficient, scalable primal-dual based algorithms for both our model and the previous state of the art, and evaluate their performance on artificial and real data.