Sparse Quadratic Approximation for Graph Learning.

Area of Science:

• Machine Learning
• Graph Theory
• Optimization

Background:

• Learning graphs via M-matrices using l1-regularized Gaussian maximum-likelihood is computationally challenging for large datasets.
• Recent methods frame this as a constrained optimization problem within precision matrix estimation.

Purpose of the Study:

• To develop efficient algorithms for learning M-matrices, applicable to graph Laplacian estimation.
• To address the computational bottlenecks in large-scale graph learning.

Main Methods:

• Developed an unconstrained post-processing method for M-matrix learning.
• Implemented a constrained approach using sequential quadratic programming.
• Built upon state-of-the-art sparse precision matrix estimation techniques.

Main Results:

• Proposed algorithms accelerate graph learning by up to three orders of magnitude.
• Achieved accurate retrieval of latent graphical structures.
• Demonstrated effectiveness, accuracy, and performance compared to existing methods.

Conclusions:

• The novel algorithms offer a significant speedup for graph learning tasks.
• The methods accurately recover graph structures and are applicable to real-world problems like COVID-19 case clustering and image classification.