In my course on probabilistic graphical models, my professor made a claim which I find a little sus. In discussing the equivalence between Markov Random Fields and Factor Graphs, the following example was given:

An MRF over 3 variables was drawn as a triangle graph (3-cycle). This admits density function like $\psi(x, y, z)$. Naturally, an equivalent factor graph can be drawn by having only one factor connected to all three variables, $p(x,y,z) \propto f(x, y, z)$. However the example where a factor graph with three factors, one along each edge, was also considered, which admits a density like $p(x,y,z) \propto f_1(x,y) \cdot f_2(y,z) \cdot f_3(x,z)$.

The question was posed that all three graphical models are equivalent for the appropriate choice of factors. Formally, the claim is as follows:

For any nonnegative function $f(x,y,z)$, there exists nonnegative functions $u, v, w$ such that $f(x,y,z)=u(x,y)\cdot v(y,z)\cdot w(x,z)$. We can assume that $x,y,z \in \{0,1\}$.

My guess at a counterexample would be a function along the lines of $f(x,y,z) = xy + yz + xz$, but I'm stuck at finding a way to prove that this cannot be written as a product of pairwise factors.

Intuitively, for a binary alphabet, $f(x,y,z)$ can be encoded using 8 values, where each of $u,v,w$ need 4 values, leaving 8 degrees of freedom versus 12. But this intuition seems weak to me.

  • 1
    $\begingroup$ Take $\log$ of every function. Then you are looking for a representation of the form $f(x,y,z)=u(x,y)+v(y,z)+w(x,z)$. This looks like a simple linear algebra problem then. $\endgroup$ Jan 31 at 16:22
  • $\begingroup$ That said, $x,y,z\in \{0,1\}$ is essential because the claim is obviously false for $x,y,z\in \mathbb{R}$. $\endgroup$ Jan 31 at 16:23
  • $\begingroup$ @PeterKravchuk, re, one has to be a little careful with the linear algebra, since the log-ified functions might take the value $-\infty$. $\endgroup$
    – LSpice
    Jan 31 at 16:37
  • $\begingroup$ If I'm not mistaken, then your example $f(x, y, z) = x y + y z + x z$ can be achieved on $\{0, 1\}^3$ with each of $u$, $v$, and $w$ vanishing at $(0, 0)$, $v(1, 1) = 3$, $w(0, 1) = 1/3$, and $u$, $v$, and $w$ being otherwise $1$. $\endgroup$
    – LSpice
    Jan 31 at 16:54
  • $\begingroup$ Not exactly what is asked but somewhat relevant: en.wikipedia.org/wiki/… $\endgroup$ Feb 1 at 5:42

3 Answers 3


Let $f(x,y,z)=x^2+y^2+z^2$ for $(x,y,z) \in \mathbb{R}^3$. The only zero of $f$ is $(0,0,0)$.

If we had three functions $u,v,w$ such that $f(x,y,z)=u(x,y)v(y,z)w(z,x)$ for every $(x,y,z) \in \mathbb{R}^3$, at least one of the functions $u,v,w$ would vanish at $(0,0)$, so $f$ would vanish on a whole line.

This argument also works on $\{0,1\}^3$.

  • $\begingroup$ Thanks! This is a really cute counterexample! $\endgroup$
    – bucket
    Jan 31 at 17:10

This is not true. If $f(x,y,z)$ has such a factorization, then

$$f(a,a,a) f(a,b,b) f(b,a,b) f(b,b,a) = f(b,b,b) f(b,a,a) f(a,b,a) f(a,a,b).$$

A generic three-input function won't obey this.

Your intuition about $8$ versus $12$ parameters is a good place to start. Indeed, if you switch from binary inputs to $n$-ary inputs, then you have $n^3$ versus $3 n^2$, so you have to fail once $n^3 > 3 n^2$, in other words $n>3$.

For $n=2$, looking at dimensions makes it seem likely such a representation exists, but the dimensionality isn't enough to resolve the issue. Switching to $\log$-coordinates, you have a linear map $\mathbb{R}_{\geq 0}^{12} \to \mathbb{R}_{\geq 0}^{8}$ and you want to know if it is surjective. When you write out the actual linear map, it turns out to be only rank $7$; the equation above is the equation of the image (put back in multiplicative coordinates).

  • 4
    $\begingroup$ And more generally, a necessary condition is $$f(a,b,c)f(a,b',c')f(a',b,c')f(a',b',c)=f(a',b,c)f(a,b',c)f(a,b,c')f(a',b',c')$$ for every real numbers $a,b,c,a',b',c'$. $\endgroup$ Jan 31 at 18:41
  • $\begingroup$ Wouldn't multiplicative coördinates give you a map $\mathbb R_{\ge 0}^{12} \to \mathbb R_{\ge 0}^8$, and log coördinates give you a map $(\mathbb R \cup \{-\infty\})^{12} \to (\mathbb R \cup \{-\infty\})^8$ (which restricts to a linear map $\mathbb R^{12} \to \mathbb R^8$)? $\endgroup$
    – LSpice
    Jan 31 at 19:08

A simple counterexample is the function $\exp{xyz}$. This follows from the criterion given below since the appropriate third derivative of its logarithm $xyz$ is $1$.

As noted already, you can use logarithms to reduce to the corresponding problem for sums. But if $f$ has such a representation, then $$\frac{\partial^3 f}{\partial x \partial y \partial z}=0.$$

Per request: the following discrete version is also a necessary condition: $$f(x_0,y_0,z_0)-f(x_1,y_0,z_0)-f(x_0,y_1,z_0)-f(x_0,y_0,z_1)+f(x_0,y_1,z_1)+f(x_1,y_0,z_1)+f(x_1,y_1,z_0)-f(x_1,y_1,z_1)=0$$ for any choices of the variables.

Both of these equations can be transformed into suitable ones for the the original problem by applying them to $\log f$.

In fact, a quick computation suggests that these necessary conditions are also sufficient but this should be regarded as conjectural—I haven't sat down to write out proofs.

  • $\begingroup$ This argument should be discretized (replacing the derivatives with rates of variations) to work with non differentiable functions. $\endgroup$ Jan 31 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.