Node Elimination

Elimination order for a graph \(G\) is the total ordering \(\pi\) of nodes of \(G\), where \(\pi(i)\) is the \(i\)th node in the ordering
The result of eliminating node \(X\) from graph \(G\) is another graph obtained from \(G\) by:
- Adding an edge between every pair of non-adjacent neighbors of \(X\)
  - These are called fill-in edges
- Deleting node \(X\)

Graph and Cluster Sequence

Eliminate of nodes from graph \(G\) according to order \(\pi\) induces:
- A graph sequence
- A cluster sequence, where cluster \(C_i\) consists of node \(\pi(i)\) and its neighbors in graph \(G_i\)

A prefix of an elimination order \(\pi\) is a sequence of variables \(\tau\) that occurs in the beginning of \(\pi\)
- Example prefix:

\[ \pi = A,B,C,D,E,\quad\tau = A,B,C\]

We can’t always generate optimal elimination orders but we can generate optimal prefixes
- ‘Not Complete’, aka can’t guarantee a full order
- We can use these rules to eliminate as many nodes as possible before using a heuristic
If graph \(G'\) is the result of applying these rules to \(G\):
- Treewidth(G) = max(treewidth(G’),low)

These rules either update the lower bound on treewidth or are conditioned on it.
Note that a simplicial node is a node that all its neighbors are pairwise adjacent, forming a clique
- An almost simplicial node is a node that all its neighbors but 1 form a clique
There are 4 rules:
- Simplicial rule: Eliminate any simplicial node with degree \(d\), updating low to \(\max(low,d)\)
  - Isler: Eliminate nodes with degree 0
  - Twig: Eliminate nodes with degree 1
- Almost simplicial rule: Eliminate any almost simplicial node with degree \(d\) as long as \(low\geq d\)
  - Series: Eliminate nodes with degree 2 if \(low\geq 2\)
  - Eliminate noes with degree 3 if \(low\geq 3\) and if at least two of the neighbors are connected by an edge
- Buddy rule: If \(low \geq 3\), eliminate any pair of nodes \(X\), \(Y\) that have degree \(3\) each and share the same set of neighbors
- Cube rule: If \(low \geq 3\), eliminate any set of four nodes \(A,B,C,D\) forming the structure below:

Lower bounds are used to empower the pre-processing rule
- Start \(low\) at a larger initial value
Weak lower bounds:
- If graph \(G\) has a clique of size \(n\), then \(treewidth(G)\geq n-1\)
- Degree of the graph (minimum number of neighbors attained by any node)
Strong lower bound:
- Degeneracy of a graph, the maximum degree attained by any of its subgraphs
  - Treewidth of any subgraph cannot be larger than the treewidth of the graph containing it

Searching the entire search space for an optimal elimination order has size \(O(n!)\), but we can limit the search space
- Prune based on query
- Use optimal prefix rules
If we already have an elimination order with width \(w_\pi\)
- If we are currently exploring a prefix with width \(w_\tau\) and a lower bound on graph \(G_\tau\), if \(max(w_\tau,b)\geq w_\pi\) we cannot improve on order \(\pi\) so stop searching this path.

Merging 2 clusters eliminates the seperator between them
- Reduce space requirements for messages in Shenoy
- Increases running time as merging clusters leads to larger cluster size
- Time-space tradeoff

Converting a jointree to elimination order:
- \(O(n^2)\) time
- Elimination order of no greater width than jointree width

Consider the cluster sequence \(C_i,...,C_n\) that results from applying the elim order \(\pi\) to the undirected graph (moral graph of DAG) \(G\).
- Generates clusters of size \(\leq width(\pi,G)+1\) to preserve width and satisfies conditions 1 and 2 of jointree definition
For every \(i<n\) the variables \(C_i\cap(C_{i+1}\cup...\cup C_n)\) are contained in some future cluster \(C_j\) where \(j>i\), the running intersection property.
Non maximal clusters are ones contained in previous clusters of the sequence
- We can remove this from the sequence
- When removed, must reorder sequence to maintain RIP
  - Replace non-maximal cluster with the cluster that contained it
Algorithm:
- \(O(n^2)\) time, \(O(n)\) space

Can also formulate with maximal spanning trees but less efficient in space and time

\[ P(X) = \frac{\prod_{\text{jointree node i}}P(C_i)}{\prod_{\text{jointree edge i-j}}P(C_i\cap C_j)}\]