Resume
Research
Learning
Blog
Teaching
Jokes
Kernel Papers

# Directed vs Undirected Graphs

Directed and undirected graphs can represent different distributions.

• Ex: $$1 \rightarrow 2 \rightarrow 3 \Rightarrow 1 - 2 - 3$$. However, so too does $$1 \leftarrow 2 \leftarrow 3 \Rightarrow 1 - 2 - 3$$ as does $$1 \leftarrow 2 \rightarrow 3 \Rightarrow 1 - 2 - 3$$. So 3 directed graphs can be represented by one undirected graph.

• Ex: $$1 \rightarrow 2 \leftarrow 3$$ has no equivalent undirected graph with these and only these conditional independencies.

• Ex: $$1 - 2 - 3 - 4 - 1$$ has no equivalent directed graph. Because the undirected graph has a loop, at some point, 2 edges will collide. Suppose the collision happens at $$3 \rightarrow 4 \leftarrow 1$$. In the undirected graph, we have $$1 \perp 3 \lvert 2, 4$$. But in the directed graph, we have $$1 \not\perp \lvert 2, 4$$.

Efficient Representation: Suppose $$G_1, G_2$$ are two graphs with corresponding families $$P(G_1), P(G_2)$$ and with sets of CIs given by $$I(G_1), I(G_2)$$. If a distribution $$p$$ is representable by both graphs i.e. $$p \in P(G_1), p \in P(G_2)$$, we say $$G_1$$ is a more efficient representation of $$p$$ if $$I(G_1) \subset I(G_2)$$.

Independence Map: A DAG or UG is called an independence map (or I-map) for distribution $$p$$ if set of CIs expressed by graph $$I(G) \subset I(p)$$, where $$I(p)$$ is the set of CIs expressed by the distribution.

The implication of being an I-map is that $$p$$ is one of the distributions in the set of families represented by the graph.

Perfect Map: A graph $$G$$ is a perfect map for distribution $$p$$ if $$I(G) = I(p)$$.

Minimal I-Map: A graph $$G$$ is a minimal I-map if removing any edge would cause it to no longer be an I-map for distribution $$p$$.

Note: A minimal I-map for a distribution $$p$$ may not be unique. It depends on the choice of topological ordering and which CIes (if any) are dropped.

Moralization: An undirected graph $$G' = (V, E')$$ is a moralization of a DAG $$G=(V, E)$$ if $$(i, j) \in E \Rightarrow (i, j) \in E'$$ and if $$i \rightarrow k \leftarrow j$$, we connect $$i$$ to $$j$$ (either direction fine). This connection is called a “moralization” after “marrying” two unmarried nodes.

Claim: DAG $$G$$ has undirected perfect map $$\Leftrightarrow$$ moralization of G does not add any edges.

Chordal: An undirected graph (UG) is chordal if every loop of size $$\geq 4$$ has a chord (an edge connecting 2 non-consecutive nodes in loop)

Claim: Undirected graph G has a directed P-map $$\Leftrightarrow$$ G is chordal