Sparse Quadratic Approximation for Graph Learning
Informazioni aggiuntive
Autori
Pasadakis D.,
Bollhoefer M.,
Schenk O.
Tipo
Articolo pubblicato in rivista scientifica
Anno
2023
Lingua
Inglese
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.
Rivista
IEEE Transactions on Pattern Analysis and Machine Intelligence
Volume
45
Mese
aprile
Pagina inizio
11256
Pagina fine
11269
Parole chiave
1-regularization, Gaussian Markov random fields, M-matrices, partial correlations, precision matrix estimation, sign constraints
