# SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 39 references that are in the map.
- First posted on arXiv 22 Jan 2021.

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

- [Learning a Tree-Structured Ising Model in Order to Make Predictions](https://mlsanity.com/paper/1604.06749/) (2016)
- [Robust Learning of Fixed-Structure Bayesian Networks](https://mlsanity.com/paper/1606.07384/) (2016)
- [Predictive Learning on Hidden Tree-Structured Ising Models](https://mlsanity.com/paper/1812.04700/) (2018)
- [Robust estimation of tree structured Gaussian Graphical Model](https://mlsanity.com/paper/1901.08770/) (2019)
- [Robust Estimation of Tree Structured Ising Models](https://mlsanity.com/paper/2006.05601/) (2020)
- [On the Information Theoretic Limits of Learning Ising Models](https://mlsanity.com/paper/1411.1434/) (2014)
- [Spectral neighbor joining for reconstruction of latent tree models](https://mlsanity.com/paper/2002.12547/) (2020)
- [Exact Asymptotics for Learning Tree-Structured Graphical Models with Side Information: Noiseless and Noisy Samples](https://mlsanity.com/paper/2005.04354/) (2020)
- [On the Difficulty of Selecting Ising Models with Approximate Recovery](https://mlsanity.com/paper/1602.03647/) (2016)
- [Optimal Rates for Learning Hidden Tree Structures](https://mlsanity.com/paper/1909.09596/) (2019)

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

- [Robustifying Algorithms of Learning Latent Trees with Vector Variables](https://mlsanity.com/paper/2106.00885/) (2021)
- [Recoverability Landscape of Tree Structured Markov Random Fields under Symmetric Noise](https://mlsanity.com/paper/2102.08554/) (2021)
- [Decentralized Learning of Tree-Structured Gaussian Graphical Models from Noisy Data](https://mlsanity.com/paper/2109.10642/) (2021)
- [Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees](https://mlsanity.com/paper/2110.14341/) (2021)
- [Robust Model Selection of Gaussian Graphical Models](https://mlsanity.com/paper/2211.05690/) (2022)

## Abstract (arXiv)

We consider learning Ising tree models when the observations from the nodes are corrupted by independent but non-identically distributed noise with unknown statistics. Katiyar et al. (2020) showed that although the exact tree structure cannot be recovered, one can recover a partial tree structure; that is, a structure belonging to the equivalence class containing the true tree. This paper presents a systematic improvement of Katiyar et al. (2020). First, we present a novel impossibility result by deriving a bound on the necessary number of samples for partial recovery. Second, we derive a significantly improved sample complexity result in which the dependence on the minimum correlation ρmin is ρmin-8 instead of ρmin-24. Finally, we propose Symmetrized Geometric Averaging (SGA), a more statistically robust algorithm for partial tree recovery. We provide error exponent analyses and extensive numerical results on a variety of trees to show that the sample complexity of SGA is significantly better than the algorithm of Katiyar et al. (2020). SGA can be readily extended to Gaussian models and is shown via numerical experiments to be similarly superior.