Cluster／Clique／Join／Junction Graphs - Graph Decompositions

grahpical model syntax

A graphical model 𝒢 is a tuple 𝒢 = ⟨𝐗, 𝐃, 𝐒, 𝐅, 𝐂⟩ where:

• 𝐗 = {𝑋₁, …, 𝑋_𝑛} set of ordered variables
• 𝐃 = {𝐷₁, …, 𝐷_𝑛} set of corresponding domains of each variable 𝑋_𝑖 (e.g. if 𝑋₁is a boolean variable then 𝐷₁= {true, false}). The size of each 𝐷_𝑖corresponds to the cardinality of variable 𝑋_𝑖
• 𝐒 = {𝑆₁, …, 𝑆_𝑚} set of variable scopes, where each variable scope 𝑆_𝑖is a subset of 𝐗 (i.e. 𝑆_𝑖 ⊆ 𝐗)
• 𝐅 = {𝐹₁, …, 𝐹_𝑚} set of factors/functions, where each factor/function 𝐹_𝑖 is defined over its corresponding variable scope 𝑆_𝑖and maps any assignment over its scope to a real value
  • in context of Bayesian Networks, 𝐅 = set of conditional probability tables
  • in context of Markov Networks, 𝐅 = set of factors
  • global function - is a function whose scope includes all variables (i.e. 𝑆_𝑖 = 𝐗)
  • local functions - is a function whose scope is a proper subset of variables (i.e. 𝑆_𝑖⊂ 𝐗)
• 𝐂 is a set of combination operators which defines how functions are combined. common combination operators are:
  • summation operator (𝛴)
  • multiplication operator (𝛱)
  • AND operator (∧) - for Boolean functions
  • relational join operator (⨝) - when the functions are relation
  • marginalization operator - for reasoning queries
  • max operator - e.g. = argmax_𝑦[ 𝐹_𝑖(𝑥,𝑦) ] = 𝐹_𝑗(𝑥) where 𝐹_𝑗is a new function with scope over variable 𝑥

the set of local functions can be combined in a variety of ways (e.g. combination operators) to generate a new local function or even a global function

Link to original

a cluster graph of a graphical model ⟨𝐗, 𝐃, 𝐒, 𝐅, 𝐂⟩ is an undirected graph where:

• each 𝑐𝑙𝑢𝑠𝑡𝑒𝑟-𝑛𝑜𝑑𝑒 is a subset of 𝐗
• each edge (𝑖,𝑗) connecting 𝑐𝑙𝑢𝑠𝑡𝑒𝑟-𝑛𝑜𝑑𝑒_𝑖 and 𝑐𝑙𝑢𝑠𝑡𝑒𝑟-𝑛𝑜𝑑𝑒_𝑗, is associated with a 𝑠𝑒𝑝𝑠𝑒𝑡 ⊆ {𝑐𝑙𝑢𝑠𝑡𝑒𝑟-𝑛𝑜𝑑𝑒_𝑖 ∩ 𝑐𝑙𝑢𝑠𝑡𝑒𝑟-𝑛𝑜𝑑𝑒_𝑗}
• each factor 𝐹_𝑖 in 𝐅 is assigned to some 𝑐𝑙𝑢𝑠𝑡𝑒𝑟-𝑛𝑜𝑑𝑒 𝑗 such that: 𝑆_𝑖 ⊆ 𝑐𝑙𝑢𝑠𝑡𝑒𝑟-𝑛𝑜𝑑𝑒_𝑗
• existence property & uniqueness property:
  • for each pair of 𝑐𝑙𝑢𝑠𝑡𝑒𝑟-𝑛𝑜𝑑𝑒𝑠 𝑖 & 𝑗:
    • for each variable 𝑋 ∊ {𝑐𝑙𝑢𝑠𝑡𝑒𝑟-𝑛𝑜𝑑𝑒_𝑖 ∩ 𝑐𝑙𝑢𝑠𝑡𝑒𝑟-𝑛𝑜𝑑𝑒_𝑗}
      • there EXITS a UNIQUE path between 𝑖 & 𝑗 for which all 𝑐𝑙𝑢𝑠𝑡𝑒𝑟-𝑛𝑜𝑑𝑒𝑠 and 𝑠𝑒𝑝𝑠𝑒𝑡𝑠 contain 𝑋

Cluster Graph - Examples (Existence-Property & Uniqueness-Property)

Click here to expand...

Illegal Cluster Graphs

violates existence-property

violates uniqueness-property

Good Cluster Graph

Cluster Graph - Construction

Click here to expand...

Bayesian Network → Join Graph

Arc Minimal Join Graph

Minimal Arc-Label Join Graph

Join Graph Decomposition

Tree Decomposition

Join Graphs Comparisons

Cluster Graph - Variants

• Cluster Tree - a cluster graph has no cycles
• Trees - relaxes the existence-property and uniqueness-property