# On decomposable random graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Oct 2017.

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

- [Benchpress: A Scalable and Versatile Workflow for Benchmarking Structure Learning Algorithms](https://mlsanity.com/paper/2107.03863/) (2021)

## Abstract (arXiv)

Decomposable graphs are known for their tedious and complicated Markov update steps. Instead of modelling them directly, this work introduces a class of tree-dependent bipartite graphs that span the projective space of decomposable graphs. This is achieved through dimensionality expansion that causes the graph nodes to be conditionally independent given a latent tree. The Markov update steps are thus remarkably simplified. Structural modelling with tree-dependent bipartite graphs has additional benefits. For example, certain properties that are hardly attainable in the decomposable form are now easily accessible. Moreover, tree-dependent bipartite graphs can extract and model extra information related to sub-clustering dynamics, while currently known models for decomposable graphs do not. Properties of decomposable graphs are also transferable to the expanded dimension, such as the attractive likelihood factorization property. As a result of using the bipartite representation, tools developed for random graphs can be used. Hence, a framework for random tree-dependent bipartite graphs, thereupon for random decomposable graphs, is proposed.