Sparse Quadratic Approximation for Graph Learning
Additional information
Authors
Bollhoefer M.,
Schenk O.
Type
Journal Article
Year
2022
Language
English
Abstract
Learning graphs represented by M -matrices via an ` 1 -regularized Gaussian maximum-likelihood method is a popular approach, but also one that poses computational challenges for large scale datasets. Recently proposed methods cast this problem as a constrained optimization variant of precision matrix estimation. In this paper, we build on a state-of-the-art sparse precision matrix estimation method and introduce two algorithms that learn M -matrices, that can be subsequently used for the estimation of graph Laplacian matrices. In the first one, we propose an unconstrained method that follows a post processing approach in order to learn an
M -matrix, and in the second one, we implement a constrained approach based on sequential quadratic programming. We also demonstrate the effectiveness, accuracy, and performance of both algorithms. Our numerical examples and comparative results with modern open-source packages reveal that the proposed methods can accelerate the learning of graphs by up to 3 orders of magnitude, while accurately retrieving the latent graphical structure of the data. Furthermore, we conduct large scale case studies for the clustering of COVID-19 daily cases and the classification of image datasets to highlight the applicability in real-world scenarios.
Journal
Technology Research
Start page number
1
End page number
12
Keywords
L1-regularization, Gaussian Markov Random Fields, M-matrices, partial correlations, precision matrix estimation, sign constraints
