# Polynomial-time derivation of optimal k-tree topology from Markov networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 42 references that are in the map.
- First posted on arXiv 9 Apr 2024.

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

- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models](https://mlsanity.com/paper/2106.03969/) (2021)
- [Maximum Likelihood Bounded Tree-Width Markov Networks](https://mlsanity.com/paper/1301.2311/) (2013)
- [If the Current Clique Algorithms are Optimal, so is Valiant's Parser](https://mlsanity.com/paper/1504.01431/) (2015)
- [Finding communities in sparse networks](https://mlsanity.com/paper/1509.06633/) (2015)

## Abstract (arXiv)

Characterization of joint probability distribution for large networks of random variables remains a challenging task in data science. Probabilistic graph approximation with simple topologies has practically been resorted to; typically the tree topology makes joint probability computation much simpler and can be effective for statistical inference on insufficient data. However, to characterize network components where multiple variables cooperate closely to influence others, model topologies beyond a tree are needed, which unfortunately are infeasible to acquire. In particular, our previous work has related optimal approximation of Markov networks of tree-width k >=2 closely to the graph-theoretic problem of finding maximum spanning k-tree (MSkT), which is a provably intractable task. This paper investigates optimal approximation of Markov networks with k-tree topology that retains some designated underlying subgraph. Such a subgraph may encode certain background information that arises in scientific applications, for example, about a known significant pathway in gene networks or the indispensable backbone connectivity in the residue interaction graphs for a biomolecule 3D structure. In particular, it is proved that the β-retaining MSkT problem, for a number of classes β of graphs, admit O(nk+1)-time algorithms for every fixed k>= 1. These β-retaining MSkT algorithms offer efficient solutions for approximation of Markov networks with k-tree topology in the situation where certain persistent information needs to be retained.