# Robust Estimation of Tree Structured Ising Models

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2020.

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

- [Outlier-Robust Learning of Ising Models Under Dobrushin's Condition](https://mlsanity.com/paper/2102.02171/) (2021)
- [Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models](https://mlsanity.com/paper/2106.03969/) (2021)
- [SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples](https://mlsanity.com/paper/2101.08917/) (2021)
- [Robust estimation of tree structured models](https://mlsanity.com/paper/2102.05472/) (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)
- [Robust Model Selection of Gaussian Graphical Models](https://mlsanity.com/paper/2211.05690/) (2022)

## Abstract (arXiv)

We consider the task of learning Ising models when the signs of different random variables are flipped independently with possibly unequal, unknown probabilities. In this paper, we focus on the problem of robust estimation of tree-structured Ising models. Without any additional assumption of side information, this is an open problem. We first prove that this problem is unidentifiable, however, this unidentifiability is limited to a small equivalence class of trees formed by leaf nodes exchanging positions with their neighbors. Next, we propose an algorithm to solve the above problem with logarithmic sample complexity in the number of nodes and polynomial run-time complexity. Lastly, we empirically demonstrate that, as expected, existing algorithms are not inherently robust in the proposed setting whereas our algorithm correctly recovers the underlying equivalence class.