# Factor Graphs

A factor graph \(G=((V, F), E)\) is a bipartitie graph where \(V\) are random variable nodes,
\(F\) are factor nodes and edges \(E \subseteq V \times F\). Like directed graphs
and undirected graphs, a given factor graph describes a family
of distributions where each distribution \(p\) in the family can be written as:

\[P(X_V) = \frac{1}{Z} \prod_{i \in F} f_i(X_{V_i})\]
where \(Z = \sum_{X_V} \prod_{i \in F} f_i(X_{V_i})\) is the normalization constant and
\(f_i(\cdot)\) are non-negative functions. Intuitively, what this says is that the probability
density/mass of a realization of the random variables can be expressed as a product of the
variables interacting through their shared factors.

## Converting Undirected Graphs to Factor Graphs

Converting an undirected graph to a factor graph can grow the number of vertices exponentially.
To see why this is, consider the complement of an undirected graph where the nodes are connected
in disjoint triangles; in other words, each node is connected to every other node except for two.

A factor graph is a tree if and only if the undirected graph is chordal and doesn’t contain
$$\tilde{K}_4 i.e. a subgraph that would be chordal but one edge is missing.

## Factor Graph Properties