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: