# Recoverability Landscape of Tree Structured Markov Random Fields under Symmetric Noise

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 38 references that are in the map.
- First posted on arXiv 17 Feb 2021.

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

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Learning Graphical Models Using Multiplicative Weights](https://mlsanity.com/paper/1706.06274/) (2017)
- [Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications](https://mlsanity.com/paper/1705.11107/) (2017)
- [Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu](https://mlsanity.com/paper/2011.04144/) (2020)
- [Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models](https://mlsanity.com/paper/1810.11905/) (2018)
- [Learning a Tree-Structured Ising Model in Order to Make Predictions](https://mlsanity.com/paper/1604.06749/) (2016)
- [Structure learning of antiferromagnetic Ising models](https://mlsanity.com/paper/1412.1443/) (2014)
- [Learning Ising Models with Independent Failures](https://mlsanity.com/paper/1902.04728/) (2019)
- [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)
- [Sample-Optimal and Efficient Learning of Tree Ising models](https://mlsanity.com/paper/2010.14864/) (2020)
- [Hardness of parameter estimation in graphical models](https://mlsanity.com/paper/1409.3836/) (2014)
- [SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples](https://mlsanity.com/paper/2101.08917/) (2021)
- [Exact Asymptotics for Learning Tree-Structured Graphical Models with Side Information: Noiseless and Noisy Samples](https://mlsanity.com/paper/2005.04354/) (2020)
- [Robust estimation of tree structured models](https://mlsanity.com/paper/2102.05472/) (2021)

## Abstract (arXiv)

We study the problem of learning tree-structured Markov random fields (MRF) on discrete random variables with common support when the observations are corrupted by a k-ary symmetric noise channel with unknown probability of error. For Ising models (support size = 2), past work has shown that graph structure can only be recovered up to the leaf clusters (a leaf node, its parent, and its siblings form a leaf cluster) and exact recovery is impossible. No prior work has addressed the setting of support size of 3 or more, and indeed this setting is far richer. As we show, when the support size is 3 or more, the structure of the leaf clusters may be partially or fully identifiable. We provide a precise characterization of this phenomenon and show that the extent of recoverability is dictated by the joint PMF of the random variables. In particular, we provide necessary and sufficient conditions for exact recoverability. Furthermore, we present a polynomial time, sample efficient algorithm that recovers the exact tree when this is possible, or up to the unidentifiability as promised by our characterization, when full recoverability is impossible. Finally, we demonstrate the efficacy of our algorithm experimentally.