Resume
Research
Learning
Blog
Teaching
Jokes
Kernel Papers

# Graph Relations

Let $$I(\cdot)$$ be the set of all conditional independencies consistent with the input graph/input distribution.

Independence Map (I-Map): Graph $$G$$ is an independence map for distribution $$p$$ if $$I(G) \subseteq I(p)$$. Intuitively, that means $$p$$ has at least the conditional independencies implied by the graph.

Perfect Map (P-Map): Graph $$G$$ is a perfect map for distribution $$p$$ if $$I(G) = I(p)$$. For a given undirected graph or a given undirected graph, there always exists some $$p$$ such that $$G$$ is a perfect map for $$p$$.

__Minimal I-Map$$: Graph$$G$$is a minimal I-map for$$p$$if$$G$$is an I-map and removing any edges from the graph causes$$G$$to lose its status as an I-map. To make these terms concrete, consider the following directed graph $$G$$: $X_1 \rightarrow X_3 \leftarrow X_2$ • Suppose $$P(X_1, X_2, X_3) = P(X_1) P(X_2) P(X_3)$$. Then $$G$$ is an I-map. •  Suppose$$P(X_1, X_2, X_3) = P(X_1) P(X_2) P(X_3 X_1, X_2)$$. Then$$G is a P-map.
• Suppose $$P(X_1, X_2, X_3) = P(X_2) P(X_1|X_2) P(X_3|X_1, X_2)$$. Then $$G$$ is neither an I-map nor a P-map.