Factor Graph

In the propagation of information, we are usually dealing with such relations that some system (factor) $ f$ is related to some inputs (variable) $ x$.

Factor graph builds such networks of relations. In such a graph, we use boxes to represent factors, and circles to represent variables.

Suppose we need to find out the probability of factor $ f_4$, we have to take in the two variables $ X_2$ and $ X_3$.

One important question is that we can actually calculate the probability of a specific configuration of the variables, which is

$$ P \propto f_1(X_1) + f_2(X_1,X_2) + f_3(X_1,X_2) + f_4(X_2,X_3). $$

In general, we can assign weights $ w_i$ to each factors $ f_i$, so that the probability of each set of variables is

$$ P(X_1,X_2,X_3,X_4) \propto w_1 f_1(X_1) + w_2 f_2(X_1,X_2) + w_3 f_3(X_1,X_2) + w_4 f_4(X_2,X_3). $$

The normalization is the partition function, i.e., the summation of all the possible combinations of variables,

$$ Z = \sum_{\{X_1,X_2,X_3,X_4\}} P(X_1,X_2,X_3,X_4). $$

As an example, we consider $ X_i$ is 0 or 1. The combinations are (partially) listed below.

List of Possible Configurations of Variables

$ X_1$	0	1	1	1	…
$ X_2$	0	0	1	1	…
$ X_3$	0	0	0	1	…
$ X_4$	0	0	0	0	…

References and Notes

1. Factor Graph @ Wikipedia
2. DeepDive Docs