Graph Learning From Data Under Laplacian and Structural Constraints

By Hilmi E. Egilmez, Eduardo Pavez, Antonio Ortega. IEEE Journal on Selected Topics in Signal Processing, 2016

367 citations recorded by the source corpus.

Graphs are fundamental mathematical structures used in various fields to represent data, signals, and processes. In this paper, we propose a novel framework for learning/estimating graphs from data. The proposed framework includes (i) formulation of various graph learning problems, (ii) their probabilistic interpretations, and (iii) associated algorithms. Specifically, graph learning problems are posed as the estimation of graph Laplacian matrices from some observed data under given structural constraints (e.g., graph connectivity and sparsity level). From a probabilistic perspective, the problems of interest correspond to maximum a posteriori parameter estimation of Gaussian–Markov random field models, whose precision (inverse covariance) is a graph Laplacian matrix. For the proposed graph learning problems, specialized algorithms are developed by incorporating the graph Laplacian and structural constraints. The experimental results demonstrate that the proposed algorithms outperform the current state-of-the-art methods in terms of accuracy and computational efficiency.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/fffcdd2541018f8dfe806d7db653e36c88d8fcd9

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 Statistical and Nonlinear Physics

Citations in the corpus

Graph Signal Processing: Overview, Challenges, and Applications (2017, methodology): “Recent work on learning graph from data [43], [44], which makes use of Markov random field models to define optimality criteria for the learned graphs, connects graphical”
Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings (2020, background): “In the field of graph signal processing, researchers have explored various ways of learning graphs from data [10, 12, 50, 25, 3, 1], with certain structural constraints (e.”
Graph Learning: A Survey (2021, methodology): “The problem of learning graph from a dataset is stated as estimating graph Laplacian, or graph topology [54].”
Connecting the Dots: Identifying Network Structure via Graph Signal Processing (2018, methodology): “To this end, it suffices to notice that smooth signals have a higher likelihood under GMRF models with a Laplacian-constrained precision matrix.”