Hypergraphs - Primal Graphs - Dual Graphs - Cluster Graphs - Cluster Trees - Factor Graphs

Hypergraph

any graphical model can be associated with a hypergraph, where X is the set of nodes and H is the scopes of the functions in F, namely H = {}. Therefore, the dual graph of the hypergraph of a graphical model associates a node with each function’s scope and an arc with each 2 nodes corresponding to scopes

Primal Graph

The Primal Graph of a graphical model is an undirected graph that has variables as its vertices and an edge connects any two variables that appear in the scope of the same function

• is an effective way to capture the structure of the knowledge. In particular, graph separation is a sound way to capture conditional independencies relative to probability distributions over directed and undirected graphical models
• in the context of directed acyclic graphs & Bayesian Networks, primal graphs are also called moral graphs
• in the context of probabilistic graphical models, primal graphs are also called i-maps (independence maps)
• in the context of relational databases, primal graphs capture the notion of embedded multi-valued dependencies (EMVDs)

All advanced algorithms for graphical models exploit their graphical structure. Besides the primal graph, other graph depictions include hyper-graphs, dual graphs, and factor graphs

Graph Depictions

the arcs of the primal graph do not provide a one to one correspondence with scopes. Hypergraphs and dual graphs are representations that provide such one-to-one correspondence

Hypergraph

a hypergraph is a pair 𝓗 = {𝐕, 𝐒} where:

• 𝐕 = {𝑣₁, …, 𝑣_n} is a set of nodes
• 𝐒 = {𝑆₁, …, 𝑆_l} is a set of subsets of 𝐕 called hyperedges (e.g. every 𝑆_𝑖⊆𝐕)

a related representation that converts a hypergraph into a regular graph is the dual graph

for example, the figure to the right depicts a hypergraph 𝓗 = {𝐕, 𝐒} where:

• 𝐕 = {A, B, C, D, E, F}
• 𝐒 = {{A,B,C}, {C,D,E}, {E,F,A}, {A,C,E}}

Primal Graph

a hypergraph 𝓗 = {𝐕, 𝐒} can be mapped to a primal graph 𝓗^primal = {𝐕^primal, 𝐄^primal} where:

• 𝐕^primal as its set of nodes
• 𝐄^primal as a set of edges for any two nodes are connected if they appear in the same hyperedge 𝑆₁

for example, the figure to the right depicts a primal graph 𝓗^primal where:

• 𝐕^primal = {A, B, C, D, E, F}
• 𝐄^primal = {{A,B}, {A,C}, {B,C}, {C,D}, {C,E}, {D,E}, {E,F}, {A,E}, {A,F}}

Dual Graph

a hypergraph 𝓗 = {𝐕, 𝐒} can be mapped to a dual graph 𝓗^dual = {𝐕^dual, 𝐄^dual} where:

• 𝐕^dual = 𝐒
  • in other words, the nodes of the dual graph are the hyperedges 𝐒 = {𝑆₁, …, 𝑆_l} in 𝓗
• (𝑆_i, 𝑆_j) ∈ 𝐄^primal iff 𝑆_i ∩ 𝑆_j≠ ∅
  • in other words, there exist an edge between 2 nodes if the intersection between their corresponding hyperedges is not empty

for example, the figure to the right depicts a dual graph 𝓗^dual where:

• 𝐕^dual = {{ABC}, {CDE}, {EFA}, {ACE}}
• 𝐄^dual = {{ABC,CDE}, {ABC,EFA}, {ABC,ACE}, {CDE,EFA}, {CDE,ACE}, {EFA,ACE}}

Dual Graph - Variants

• Cluster Graphs - a relaxed Dual Graph, where nodes can be combined and edges removed as long as it satisfies the cluster graph properties
• Cluster Trees - a cluster graph with no cycles

Factor Graph

a hypergraph 𝓗 = {𝐕, 𝐒} can be mapped to a factor graph 𝓗^factor = {𝐕^variable, 𝐕^function, 𝐄^factor} where:

• 𝐕^variablevariable nodes = 𝐕
• 𝐕^function function nodes = 𝐒
• (𝑣_𝑖, 𝑆_𝑗) ∈ 𝐄^factor iff 𝑣_𝑖∊𝑆_𝑗
  • in other words, each function node is connected to all the variable nodes appearing in the scope