Learning Large-Scale MTP₂ Gaussian Graphical Models via Bridge-Block Decomposition

2023/09/23 by Xiwen Wang, Wang, Xiwen, Jiaxi Ying +3 · 1 citation
Computer Science · #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #FOS: Electrical engineering #Machine Learning (cs.LG) #Signal Processing (eess.SP) #electronic engineering #information engineering

paper · pdf · doi:10.48550/arxiv.2309.13405

openalex publication_date 2023/09/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper studies the problem of learning the large-scale Gaussian graphical models that are multivariate totally positive of order two (MTP₂). By introducing the concept of bridge, which commonly exists in large-scale sparse graphs, we show that the entire problem can be equivalently optimized through (1) several smaller-scaled sub-problems induced by a bridge-block decomposition on the thresholded sample covariance graph and (2) a set of explicit solutions on entries corresponding to bridges. From practical aspect, this simple and provable discipline can be applied to break down a large problem into small tractable ones, leading to enormous reduction on the computational complexity and substantial improvements for all existing algorithms. The synthetic and real-world experiments demonstrate that our proposed method presents a significant speed-up compared to the state-of-the-art benchmarks.

Cited by

• Leveraging Low-rank Factorizations of Conditional Correlation Matrices in Graph Learning

Related

• Learning Graphical Models Using Multiplicative Weights
• Learning Gaussian Graphical Models via Multiplicative Weights
• Learning Some Popular Gaussian Graphical Models without Condition Number Bounds
• High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion
• Learning Gaussian Graphical Models with Observed or Latent FVSs