Resume
Research
Learning
Blog
Teaching
Jokes
Kernel Papers

# 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.