Graphical Models Induced by Irreversible Event Accumulation on Trees

Decomposable graphical models are usually adopted for their computational convenience rather than derived from a data-generating mechanism. We show that a special class of them arises naturally from the irreversible accumulation of events along a branching history. Each event is attached to an edge of a latent rooted tree and is inherited by everything below that edge; an observation records which events have occurred at a randomly chosen node, not necessarily a leaf. When the tree is a path, this is the cumulative coding of an ordinal variable, whose indicators form a Markov chain; in the general tree case the Markov chain is replaced by a junction tree. The conditional independence graph of the event indicators is always decomposable and, in fact, is the line graph of the tree (maximal cliques correspond to nodes where two or more edges meet and separators are the single events on the edges joining two such nodes). The graph determines the tree up to the choice of root. A connected graph arises in this way if, and only if, it is chordal, any two of its maximal cliques share at most one vertex, no vertex is in three maximal cliques, and the graph is such that any two maximal cliques share at most one vertex. This provides a simple graphical test for compatibility with the mechanism (necessary but not sufficient, as irreversibility also constrains the distribution's support). The structure breaks down if we look at just the leaves, and measurement error destroys the exact screening and leads to a denser graph rather than simply a weaker dependence. We discuss inference, provide diagnostics for departures such as recurrent events, illustrate them on some simulated data and discuss their application in the context of mutation accumulation and lineage tracing where both ancestral and descendant types are sampled together.