# Learning Large-Scale MTP2 Gaussian Graphical Models via Bridge-Block Decomposition

arXiv: https://arxiv.org/abs/2309.13405 · HTML: https://mlsanity.com/paper/2309.13405/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 59 references that are in the map.
- First posted on arXiv 23 Sep 2023.

## Builds on (most cited first, 14 of 14)

- [The UCR Time Series Archive](https://mlsanity.com/paper/1810.07758/) (2018)
- [A Unified Framework for Structured Graph Learning via Spectral Constraints](https://mlsanity.com/paper/1904.09792/) (2019)
- [A Survey of Community Search Over Big Graphs](https://mlsanity.com/paper/1904.12539/) (2019)
- [Structured Graph Learning Via Laplacian Spectral Constraints](https://mlsanity.com/paper/1909.11594/) (2019)
- [Estimation of positive definite M-matrices and structure learning for attractive Gaussian Markov Random fields](https://mlsanity.com/paper/1404.6640/) (2014)
- [Maximum likelihood estimation in Gaussian models under total positivity](https://mlsanity.com/paper/1702.04031/) (2017)
- [Learning Graphs with Monotone Topology Properties and Multiple Connected Components](https://mlsanity.com/paper/1705.10934/) (2017)
- [Graphical Lasso and Thresholding: Equivalence and Closed-form Solutions](https://mlsanity.com/paper/1708.09479/) (2017)
- [Covariance Matrix Estimation under Total Positivity for Portfolio Selection](https://mlsanity.com/paper/1909.04222/) (2019)
- [Fast Projected Newton-like Method for Precision Matrix Estimation under Total Positivity](https://mlsanity.com/paper/2112.01939/) (2021)
- [Total positivity in multivariate extremes](https://mlsanity.com/paper/2112.14727/) (2021)
- [Network Topology Inference with Sparsity and Laplacian Constraints](https://mlsanity.com/paper/2309.00960/) (2023)
- [Refining bridge-block decompositions through two-stage and recursive tree partitioning](https://mlsanity.com/paper/2110.06998/) (2021)
- [Adaptive Estimation of Graphical Models under Total Positivity](https://mlsanity.com/paper/2210.15471/) (2022)

## Built on by (most cited first, 5 of 5)

- [Fair GLASSO: Estimating Fair Graphical Models with Unbiased Statistical Behavior](https://mlsanity.com/paper/2406.09513/) (2024)
- [Fairness-Aware Estimation of Graphical Models](https://mlsanity.com/paper/2408.17396/) (2024)
- [Efficient Sparse PCA via Block-Diagonalization](https://mlsanity.com/paper/2410.14092/) (2024)
- [Leveraging Low-rank Factorizations of Conditional Correlation Matrices in Graph Learning](https://mlsanity.com/paper/2506.10628/) (2025)
- [Learning Gaussian Graphical Models under Total Positivity via Spectral Graph Sparsification](https://mlsanity.com/paper/2605.17154/) (2026)

## Abstract (arXiv)

This paper studies the problem of learning the large-scale Gaussian graphical models that are multivariate totally positive of order two (MTP2). 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.