Tree, Generalized

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”:

EE512 Generalizing Trees- N-simplicials

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:

 

EE512 Generalizing Trees- Tree Construction Basics (1)

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:

EE512 Generalizing Trees- k-Trees

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:

EE512 Generalizing Trees- Tree Hierarchy

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:

EE512 Generalized Trees- Summary Infographic (1)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s