How to learn a graph from smooth signals

Abstract

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.

8 pages + supplementary material. Accepted in AISTATS 2016, Cadiz, Spain

References in corpus (1)

• Matrix Completion on Graphs

Cited by in corpus (8)

• Large Scale Graph Learning from Smooth Signals
• Bias-Variance Tradeoff of Graph Laplacian Regularizer
• Source Localization on Graphs via l1 Recovery and Spectral Graph Theory
• Evaluating Graph Signal Processing for Neuroimaging Through Classification and Dimensionality Reduction
• Convolutional neural networks on irregular domains based on approximate vertex-domain translations
• Learning Product Graphs Underlying Smooth Graph Signals
• Learning Networks from Random Walk-Based Node Similarities
• A Time-Vertex Signal Processing Framework