Polynomial-Time Derivation of Optimal $k$-Tree Topology from Markov Networks

Abstract

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 the approximation of Markov networks of tree-width $k$ with the minimum information loss (termed optimal approximation) closely to the graph-theoretic problem of finding maximum spanning $k$-tree (MS$k$T), 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 $\beta$-retaining MS$k$T problem, for several classes $\beta$ of graphs (i.e., families of subgraphs that are required to be retained, such as Hamiltonian paths), admits $O(n^{k+1})$-time algorithms for fixed $k\geq 1$. These $\beta$-retaining MS$k$T algorithms offer efficient solutions for approximation of Markov networks with $k$-tree topology in situations where certain persistent structural information needs to be preserved.