Can nonnegative functions $f(x,y,z)$ be written as a product of pairwise functions $u(x,y) v(y,z) w(x, z)$?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.