**Part Of**: [Advanced Inference In Graphical Models] sequence

**Followup To**: [An Inference Trail To Chordal Graphs]

Table Of Contents

- Context
- Parallels Between Trees and Chordal Graphs
- Parameterizing Simpliciality
- Definition By Construction
- K-trees
- Takeaways

Parallels Between Trees And Chordal Graphs

In Murderous Messages, we defined perfect elimination orderings as follows:

Let

perfect elimination ordering(PEO) refer to exact inference algorithms that do not at any step introduce fill-in edges; F = {}. In order to accomplish such an ordering, we should eliminate nodes that match either one of two elimination principles:

- have only zero or one neighbor (
leaf nodes)- have neighbors that are already fully connected. (
simplicial nodes)

In our inference trails towards both trees and chordal graphs, we came upon the following similar-looking properties:

- Every tree with size > 1 has two leaf nodes (nodes in a tree with only one neighbor).
- A chordal graph is either a clique, or at least two non-adjacent nodes are simplicial. [Lemma 30]

Note the implication that you’ll never run out of leaf/simplicial nodes to eliminate: every time you remove a leaf/simplicial node, the resultant tree/graph still retains this two-target characteristic. Since you are assured leaves/simplicials “all the way down”, this guarantees that both trees and chordal graphs may sustain perfect elimination orders. And that is nice.

We proceeded to author construction-based definitions of these data structures. Note again how frustratingly similar they are, despite their independent derivations!

- T is a tree if it is generated via the following process: Start with a node v. Repeatedly choose a next vertex, and connect it with an edge to exactly one previously chosen vertex.
- G is a chordal graph if generated via the following process: Start with a clique. All chordal graphs can be generated by connecting the next node to some set of previously-chosen nodes that are a clique. [Corollary 36]

Parameterizing Simpliciality

Let’s transcend an appeal to coincidence: why have two things when we can have one? 😛

Time to consolidate. Recall our definition of simplicial node?

Simplicial node: a node whose neighbors form a clique.

Let’s make this definition more granular, and define a concept that hinges on the size of this neighbor-clique.

k-simplicial node: a node whose neighbors form a clique of size k.

Here’s how this looks “in action”:

A few notes about the boundaries of this distribution:

- What is the maximum size of an k-simplicial node? When the entire graph is a clique, when k = N (the number of all nodes). k spans [1..N].
- Does a 1-simplicial node remind you of anything? It should.
*Creating a**1-simplicial node is equivalent to appending a leaf node.*

Definition By Construction

With this definition of k-simplicials in hand, let’s return to our twin construction properties mentioned above.

- T is a tree if generated via the following process: Start with a node v. Repeatedly choose a next vertex, and connect it with an edge to exactly one previously chosen vertex.
- G is a chordal graph if generated via the following process: Start with a clique. All chordal graphs can be generated by connecting the next node to some set of previously-chosen nodes that are a clique. [Corollary 36]

Now, we can represent this graphically by realizing that the former process is about consistently appending 1-simplicials, and the latter process fueled by k-simplicials. The distinction, then, looks like this:

k-Trees

In our visualization of tree construction, did you notice how the color of tree construction doesn’t change? Let’s generalize this property beyond orange (1-simplicials).

Let **k-tree** represent a tree whose construction process is fueled by k-simplicials. I illustrate four of these tree abstractions here:

Are there k-trees that are not chordal graphs? How do k-trees generally relate to our previous concepts of trees and chordal graphs? Another illustration should clarify these inter-relationships:

A tree is a subset of a k-tree which is a subset of chordal graphs. We know this because:

- A chordal graph is constructed by (any chain of) simplicials
- A k-tree is constructed by (one consistent chain of) simplicials.
- A tree is constructed by (one particular consistent chain of) simplicials.

Takeaways

- A leaf node is synonymous with a simplicial node of size 1.
- A k-tree is a tree constructed with simplicial nodes of size k (a 1-tree is synonymous with a tree, per the above identity).
- A tree is a kind of k-tree which is a kind of chordal graph: these three data structures are strict subsets of one another.

Here’s a consolidation of the above images, for convenience: