How to Learn a Graph from Smooth Signals

By Vassilis Kalofolias. 2016

594 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

Citations in the corpus

Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs (2019, methodology): “In our experiments, we use a graph regularizer defined as g(w) = λ‖w‖(2) − 1> log(d(w) + δ), which is inspired from (Kalofolias, 2016).”
Graph Learning Based on Total Variation Minimization (2018, background): “In order to avoid that the learned graph is poorly connected, [16, 17] penalizes small weighted node degrees in the objective function.”
Graph Learning From Data Under Laplacian and Structural Constraints (2016, methodology): “Our formulation allows us to improve the accuracy of CGL estimation significantly compared to the approaches in [41]–[43].”
Network Topology Inference from Spectral Templates (2016, background): “The novel idea is to search among all feasible networks for the one that endows the resulting graph-signal transforms with prescribed spectral properties (those guaranteeing graph stationarity [12]), while the inferred graph also exhibits desirable structural characteristics such as sparsity or…”
Connecting the Dots: Identifying Network Structure via Graph Signal Processing (2018, background): “Given these considerations, a general purpose model for learning graphs is advocated in [25], namely”
Graph Learning: A Survey (2021, background): “Kalofolias [56] formulated the objective as a weighted l1 problem and designed a general framework to solve it.”
Learning Graphs From Data: A Signal Representation Perspective (2018, methodology): “Following the same design for F and slightly different designs for K as compared to those in [39] and [40], the authors of [41] have proposed solving a similar objective compared to the graphical Lasso but with the constraints that the solutions correspond to different types of graph Laplacian matri”