On a Class of Tensor Markov Fields

Abstract

Here, we introduce a class of Tensor Markov Fields intended as probabilistic graphical models from random variables spanned over multiplexed contexts. These fields are an extension of Markov Random Fields for tensor-valued random variables. By extending the results of Dobruschin, Hammersley and Clifford to such tensor valued fields, we proved that tensor Markov fields are indeed Gibbs fields, whenever strictly positive probability measures are considered. Hence, there is a direct relationship with many results from theoretical statistical mechanics. We showed how this class of Markov fields it can be built based on a statistical dependency structures inferred on information theoretical grounds over empirical data. Thus, aside from purely theoretical interest, the Tensor Markov Fields described here may be useful for mathematical modeling and data analysis due to their intrinsic simplicity and generality.

1. General Definitions

Here, we introduce Tensor Markov Fields, i.e., Markov random fields [1,2] over tensor spaces. Tensor Markov Fields (TMFs) represent the joint probability distribution for a set of tensor-valued random variables.

Let $X=X_{\alpha }^{\beta }$ be one of such tensor-valued random variables. Here $X_i^j\in X$ may represent either a variable $i\in \alpha$, that may exist in a given context or layer $j\in \beta$ (giving rise to a class of so-called multilayer graphical models or multilayer networks) or a single tensor-valued quantity $X_i^j$. A TMF will be an undirected multilayer graph representing the statistical dependency structure of X as given by the joint probability distribution $\mathbb{P}\left(X\right)$.

As an extension of the case of Markov random fields, a TMF is a multilayer graph $\widehat{G}=(V,E)$ formed by a set V of vertices or nodes (the $X_i^j$’s) and a set $E\subseteq V\times V$ of edges connecting the nodes, either on the same layer or through different layers (Figure 1). The set of edges represents a neighborhood law N stating which vertex is connected (dependent) to which other vertex in the multilayer graph. With this in mind, a TMF can be also represented (slightly abusing notation) as $\widehat{G}=(V,N)$. The set of neighbors of a given point $X_i^j$ will be denoted $N_{X_i^j}$.

1.1. Configuration

It is possible to assign to each point in the multilayer graph, one of a finite set S of labels. Such assignment will be called a configuration. We will assign probability measures to the set $\mathrm{\Omega }$ of all possible configurations $\omega$. Hence, ${\omega }_A$ represents the configuration $\omega$ restricted to the subset A of V. It is possible to think of ${\omega }_A$ as a configuration on the smaller multilayer graph ${\widehat{G}}_A$ restricting V to points of A (Figure 2).

1.2. Local Characteristics

It is also possible to extend the notion of local characteristics from MRFs. The local characteristics of a probability measure $\mathbb{P}$ defined on $\mathrm{\Omega }$ are the conditional probabilities of the form:

$$\mathbb{P}\left({\omega }_t\right|{\omega }_{T\backslash t})=\mathbb{P}\left({\omega }_t\right|{\omega }_{N_t})$$

(1)

i.e., the probability that the point t is assigned the value ${\omega }_t$, given the values at all other points of the multilayer graph. In order to make explicit the tensorial nature of the multilayer graph $\widehat{G}$, let us re-write Equation (1). Let us also recall the fact that the probability measure will define a tensor Markov random field (a TMF) if the local characteristics depend only of the knowledge of the outcomes at neighboring points, i.e., if for every $\omega$

$$\mathbb{P}\left({\omega }_{X_i^j}\right|{\omega }_{\widehat{G}\backslash X_i^j})=\mathbb{P}\left({\omega }_{X_i^j}\right|{\omega }_{N_{X_i^j}})$$

(2)

1.3. Cliques

Given an arbitrary graph (or in the present case a multilayer graph), we shall say that a set of points C is a clique if every pair of points in C are neighbors (see Figure 3). This definition includes the empty set as a clique. A clique is thus a set whose induced subgraph is complete, for this reason cliques are also called complete induced subgraphs or maximal subgraphs (although these latter term may be ambiguous).

1.4. Configuration Potentials

A potential $\eta$ is a way to assign a number ${\eta }_A\left(\omega \right)$ to every subconfiguration ${\omega }_A$ of a configuration $\omega$ in the multilayer graph $\widehat{G}$. Given a potential, we shall say that it defines (or better, induces) a dimensionless energy $U\left(\omega \right)$ on the set of all configurations $\omega$ by

$$U\left(\omega \right)=\sum _A{\eta }_A\left(\omega \right)$$

(3)

In the preceeding expression, for fixed $\omega$, the sum is taken over all subsets $A\subseteq V$ including the empty set. We can define a probability measure, called the Gibbs measure induced by U as

$$\mathbb{P}\left(\omega \right)=\frac{e^{-U\left(\omega \right)}}{Z}$$

(4)

with Z a normalization constant called the partition function.

$$Z=\sum _{\omega }{e}^{-U\left(\omega \right)}$$

(5)

In physics, the term potential is often used in connection with the so-called potential energies. Physicists often call ${\eta }_A$ a dimensionless potential energy, and they call ${\varphi }_A=e^{-{\eta }_A}$ a potential.

Equations (4) and (5) can be thus rewritten as:

$$\mathbb{P}\left(\omega \right)=\frac{{\prod }_A{\varphi }_A\left(\omega \right)}{Z}$$

(6)

$$Z=\sum _{\omega }\prod _A{\varphi }_A\left(\omega \right)$$

(7)

Since this latter use is more common in probability and graph theory, we will refer to Equations (6) and (7) as the definitions of Gibbs measure and partition function (respectively) unless otherwise stated.

1.5. Gibbs Fields

A potential is called a nearest neighbor Gibbs potential if ${\varphi }_A\left(\omega \right)=1$ whenever A is not a clique. It is customary to refer as a Gibbs measure to a measure induced by a nearest neighbor Gibbs potential. However, it is possible to define more general Gibbs measures by considering other types of potentials.

The inclusion of all cliques in the calculation of the Gibbs measure is necessary to establish the equivalence between Gibbs random fields and Markov random fields. Let us see how a nearest neighbor Gibbs measure on a multilayer graph determines a TMF.

Let $\mathbb{P}\left(\omega \right)$ be a probability measure determined on $\mathrm{\Omega }$ by a nearest neighbor Gibbs potential $\varphi$:

$$\mathbb{P}\left(\omega \right)=\frac{{\prod }_C{\varphi }_C\left(\omega \right)}{Z}$$

(8)

With the product taken over all cliques C on the multilayer graph $\widehat{G}$. Then,

$$\mathbb{P}\left({\omega }_{X_i^j}\right|{\omega }_{\widehat{G}\backslash X_i^j})=\frac{\mathbb{P}\left(\omega \right)}{{\sum }_{{\omega }^{\prime }}\mathbb{P}\left({\omega }^{\prime }\right)}$$

(9)

Here ${\omega }^{\prime }$ is any configuration which agrees with $\omega$ at all points except $X_i^j$.

$$\mathbb{P}\left({\omega }_{X_i^j}\right|{\omega }_{\widehat{G}\backslash X_i^j})=\frac{{\prod }_C{\varphi }_C\left(\omega \right)}{{\sum }_{{\omega }^{\prime }}{\prod }_C{\varphi }_C\left({\omega }^{\prime }\right)}$$

(10)

For any clique C that does not contain $X_i^j$, ${\varphi }_C\left(\omega \right)={\varphi }_C\left({\omega }^{\prime }\right)$, So that all the terms that correspond to cliques that do not contain the point $X_i^j$ cancel both from the numerator and the denominator in Equation (10), therefore this probability depends only on the values $x_i^j$ at $X_i^j$ and its neighbors. $\mathbb{P}$ defines thus a TMF.

A more general proof of this equivalence is given by Hammersley-Clifford theorem that will be presented in the following section.

2. Extended Hammersley Clifford Theorem

Here we will outline a proof for an extension of Hammersley-Clifford theorem for Tensor Markov Fields (i.e., we will show that a Tensor Markov Field is equivalent to a Tensor Gibbs Field).

Let $\widehat{G}=(V,N)$ be a multilayer graph representing a TMF as defined in the previous section. With $V=X_{\alpha }^{\beta }=\left\{X_i^j\right\}$, a set of vertices over a tensor field and N a neighborhood law that connects vertices over this tensor field. The field $\widehat{G}$ obeys the following neighborhood law given its Markov property (see Equation (2))

$$\mathbb{P}\left(X_i^j\right|X_{\widehat{G}\backslash X_i^j})=\mathbb{P}\left(X_i^j\right|X_{N_i^j})$$

(11)

Here $X_{N_i^j}$ is any neighbor of $X_i^j$. The Hammersley-Clifford theorem states that a MRF is also a local Gibbs field. In the case of a TMF we have the following expression:

$$\mathbb{P}\left(X\right)=\frac{1}{Z}\prod _{c\in C_{\widehat{G}}}{\varphi }_c\left(X_c\right)$$

(12)

In order to prove the equivalence of Equations (11) and (12), we will first bult a deductive (backward direction) part of the proof to be complemented with a constructive (forward direction) part as presented in the following subsections.

2.1. Backward Direction

Let us consider Equation (11) at the light of Bayes’ theorem:

$$\mathbb{P}\left(X_i^j\right|X_{\widehat{G}\backslash X_i^j})=\frac{\mathbb{P}(X_i^j,X_{N_i^j})}{\mathbb{P}\left(X_{N_i^j}\right)}$$

(13)

Using a clique-approach to calculate the joint and marginal probabilities (see next subsection to support the following statement):

$$\mathbb{P}\left(X_i^j\right|X_{\widehat{G}\backslash X_i^j})=\frac{{\sum }_{\widehat{G}\backslash D_i^j}{\prod }_{c\in C_{\widehat{G}}}{\varphi }_c\left(X_c\right)}{{\sum }_{X_i^j}{\sum }_{\widehat{G}\backslash D_i^j}{\prod }_{c\in C_{\widehat{G}}}{\varphi }_c\left(X_c\right)}$$

(14)

Let us split the product ${\prod }_{c\in C_{\widehat{G}}}{\varphi }_c\left(X_c\right)$ into two products, one over the set of cliques that contain $X_i^j$ (let us call it $C_i^j$) and another set formed by cliques not containing $X_i^j$ (let us call it $R_i^j$):

$$\mathbb{P}\left(X_i^j\right|X_{\widehat{G}\backslash X_i^j})=\frac{{\sum }_{\widehat{G}\backslash D_i^j}{\prod }_{c\in C_i^j}{\varphi }_c\left(X_c\right){\prod }_{c\in R_i^j}{\varphi }_c\left(X_c\right)}{{\sum }_{X_i^j}{\sum }_{\widehat{G}\backslash D_i^j}{\prod }_{c\in C_i^j}{\varphi }_c\left(X_c\right){\prod }_{c\in R_i^j}{\varphi }_c\left(X_c\right)}$$

(15)

Factoring out the terms depending on $X_i^j$ (that do not contribute to cliques in the domain $\widehat{G}\backslash X_i^j$):

$$\mathbb{P}\left(X_i^j\right|X_{\widehat{G}\backslash X_i^j})=\frac{{\prod }_{c\in C_i^j}{\varphi }_c\left(X_c\right){\sum }_{\widehat{G}\backslash D_i^j}{\prod }_{c\in R_i^j}{\varphi }_c\left(X_c\right)}{{\sum }_{X_i^j}{\prod }_{c\in C_i^j}{\varphi }_c\left(X_c\right){\sum }_{\widehat{G}\backslash D_i^j}{\prod }_{c\in R_i^j}{\varphi }_c\left(X_c\right)}$$

(16)

The term ${\sum }_{\widehat{G}\backslash D_i^j}{\prod }_{c\in R_i^j}{\varphi }_c\left(X_c\right)$ does not involve $X_i^j$ (by construction) so, it can be factored out from the summation over $X_i^j$ in the denominator.

$$\mathbb{P}\left(X_i^j\right|X_{\widehat{G}\backslash X_i^j})=\frac{{\prod }_{c\in C_i^j}{\varphi }_c\left(X_c\right){\sum }_{\widehat{G}\backslash D_i^j}{\prod }_{c\in R_i^j}{\varphi }_c\left(X_c\right)}{{\sum }_{\widehat{G}\backslash D_i^j}{\prod }_{c\in R_i^j}{\varphi }_c\left(X_c\right){\sum }_{X_i^j}{\prod }_{c\in C_i^j}{\varphi }_c\left(X_c\right)}$$

(17)

We can cancel the term in the numerator and denominator:

$$\mathbb{P}\left(X_i^j\right|X_{\widehat{G}\backslash X_i^j})=\frac{{\prod }_{c\in C_i^j}{\varphi }_c\left(X_c\right)}{{\sum }_{X_i^j}{\prod }_{c\in C_i^j}{\varphi }_c\left(X_c\right)}$$

(18)

Then we multiply by $\frac{{\prod }_{c\in R_i^j}{\varphi }_c\left(X_c\right)}{{\prod }_{c\in R_i^j}{\varphi }_c\left(X_c\right)}$

$$\mathbb{P}\left(X_i^j\right|X_{\widehat{G}\backslash X_i^j})=\frac{{\prod }_{c\in C_i^j}{\varphi }_c\left(X_c\right){\prod }_{c\in R_i^j}{\varphi }_c\left(X_c\right)}{{\sum }_{X_i^j}{\prod }_{c\in C_i^j}{\varphi }_c\left(X_c\right){\prod }_{c\in R_i^j}{\varphi }_c\left(X_c\right)}$$

(19)

Remembering that $C_i^j\bigcup R_i^j=C_{\widehat{G}}$,

$$\mathbb{P}\left(X_i^j\right|X_{\widehat{G}\backslash X_i^j})=\frac{{\prod }_{c\in \widehat{G}}{\varphi }_c\left(X_c\right)}{{\sum }_{X_i^j}{\prod }_{c\in \widehat{G}}{\varphi }_c\left(X_c\right)}$$

(20)

Equation (20) is nothing but the definition of a local Gibbs Tensor Field (Equation (12)).

2.2. Forward Direction

In this subsection we will show how to express the clique potential functions ${\varphi }_c\left(X_c\right)$, given the joint probability distribution over the tensor field and the Markov property.

Consider any subset $\sigma \subset \widehat{G}$ of the multilayer graph $\widehat{G}$. We define a candidate potential function (following Möbius inversion lemma) [3] as follows:

$$f_{\sigma }(X_{\sigma }=x_{\sigma })=\prod _{\zeta \subset \sigma }\mathbb{P}{(X_{\zeta }=x_{\zeta },X_{\widehat{G}\backslash \zeta }=0)}^{-1^{\left|\sigma \right|-\left|\zeta \right|}}$$

(21)

In order for $f_{\sigma }$ to be a proper clique potential, it must satisfy the following two conditions:

(i)

${\prod }_{\sigma \subset \widehat{G}}{f}_{\sigma }\left(X_{\sigma }\right)=\mathbb{P}\left(X\right)$

(ii)

$f_{\sigma }\left(X_{\sigma }\right)=1$ whenever $\sigma$ is not a clique

To prove (i), we need to show that all factors in $f_{\sigma }(X_{\sigma }=x_{\sigma })$ cancel out, except for $\mathbb{P}\left(X\right)$.

To do this, it will be useful to consider the following combinatorial expansion of zero:

$$0={(1-1)}^K=C_0^K-C_1^K+C_2^K+\cdots +{(-1)}^K{C}_K^K$$

(22)

Here, of course $C_B^A$ is the number of combinations of B elements from an A-element set.

Let us consider any subset $\zeta$ of $\widehat{G}$. Let us consider a factor $\Delta =\mathbb{P}(X_{\zeta }=x_{\zeta },X_{\widehat{G}\backslash \zeta }=0)$. For the case of $f\zeta \left(X_{\zeta }\right)$ it occurs as ${\Delta }^{-1^0}=\Delta$. Such factor also occurs in subsets containg $\zeta$ and other additional elements. If it includes $\zeta$ and one additional element, there are $C_1^{|\widehat{G}|-|\zeta |}$ such functions. The additional element creates an inverse factor ${\Delta }^{-1^1}={\Delta }^{-1}$. The functions over subsets containg $\zeta$ and two additional elements contributes with a factor ${\Delta }^{-1^2}={\Delta }^1=\Delta$. If we continue this process and consider Equation (22), it is evident that all odd cardinality difference terms cancel out with all even cardinality difference terms so that the only remaining factor corresponds to $\zeta =\widehat{G}$ equal to $\mathbb{P}\left(X\right)$ thus fulfilling condition (i).

In order to show how condition (ii) is fulfilled, we will need to use the Markov property of TMFs. Let us consider $\sigma *\subset \widehat{G}$ that is not a clique. Then it will be possible to find two nodes $X_i^h$ and $X_j^k$ in $\sigma *$ that are not connected to each other. Let us recall Equation (21):

$$f_{\sigma }(X_{\sigma }*=x_{\sigma }*)=\prod _{\zeta \subset \sigma *}\mathbb{P}{(X_{\zeta }=x_{\zeta },X_{\widehat{G}\backslash \zeta }=0)}^{-1^{|\sigma *|-\left|\zeta \right|}}$$

(23)

An arbitrary subset $\zeta$ may belong to any of the following classes: (i) $\zeta =\omega$ a generic subset of $\sigma$; (ii) $\zeta =\omega \cup \left\{X_i^h\right\}$; (iii) $\zeta =\omega \cup \left\{X_j^k\right\}$ or (iv) $\zeta =\omega \cup \{X_i^h,X_j^k\}$. If we write down Equation (23) factored down to these contributions we get:

$$f_{\sigma }(X_{\sigma }*=x_{\sigma }*)=\prod _{\omega \subset \sigma *\backslash \{X_i^h,X_j^k\}}{\left[\frac{\mathbb{P}(X_{\omega },X_{\widehat{G}\backslash \omega }=0)\mathbb{P}(X_{\omega \cup \{X_i^h,X_j^k\}},X_{\widehat{G}\backslash \omega \cup \{X_i^h,X_j^k\}}=0)}{\mathbb{P}(X_{\omega \cup \left\{X_i^h\right\}},X_{\widehat{G}\backslash \omega \cup \left\{X_i^h\right\}}=0)\mathbb{P}(X_{\omega \cup \left\{X_j^k\right\}},X_{\widehat{G}\backslash \omega \cup \left\{X_j^k\right\}}=0)}\right]}^{-1^{|\sigma *|-\left|\zeta \right|}}$$

(24)

Let us consider two of the factors in Equation (24) at the light of Bayes’ theorem:

$$\frac{\mathbb{P}(X_{\omega },X_{\widehat{G}\backslash \omega }=0)}{\mathbb{P}(X_{\omega \cup \left\{X_i^h\right\}},X_{\widehat{G}\backslash \omega \cup \left\{X_i^h\right\}}=0)}=\frac{\mathbb{P}(X_{\left\{X_i^h\right\}}=0|X_{\left\{X_j^k\right\}}=0,X_{\omega },X_{\widehat{G}\backslash \omega \cup \{X_i^h,X_j^k\}}=0)\mathbb{P}(X_{\left\{X_j^k\right\}}=0,X_{\omega },X_{\widehat{G}\backslash \omega \cup \{X_i^h,X_j^k\}}=0)}{\mathbb{P}(X_{\left\{X_i^h\right\}}|X_{\left\{X_j^k\right\}}=0,X_{\omega },X_{\widehat{G}\backslash \omega \cup \{X_i^h,X_j^k\}}=0)\mathbb{P}(X_{\left\{X_j^k\right\}}=0,X_{\omega },X_{\widehat{G}\backslash \omega \cup \{X_i^h,X_j^k\}}=0)}$$

(25)

We can notice that the priors in the numerator and denominator of Equation (25) are the same. We can then cancell them out. Since by definition $X_i^h$ and $X_j^k$ are conditionally independent given the rest of the multilayer graph, we can also replace the default value $X_j^k=0$ for $X_j^k$ instead.

$$\frac{\mathbb{P}(X_{\omega },X_{\widehat{G}\backslash \omega }=0)}{\mathbb{P}(X_{\omega \cup \left\{X_i^h\right\}},X_{\widehat{G}\backslash \omega \cup \left\{X_i^h\right\}}=0)}=\frac{\mathbb{P}(X_{\left\{X_i^h\right\}}=0|X_{\left\{X_j^k\right\}},X_{\omega },X_{\widehat{G}\backslash \omega \cup \{X_i^h,X_j^k\}}=0)\mathbb{P}(X_{\left\{X_j^k\right\}},X_{\omega },X_{\widehat{G}\backslash \omega \cup \{X_i^h,X_j^k\}}=0)}{\mathbb{P}(X_{\left\{X_i^h\right\}}|X_{\left\{X_j^k\right\}},X_{\omega },X_{\widehat{G}\backslash \omega \cup \{X_i^h,X_j^k\}}=0)\mathbb{P}(X_{\left\{X_j^k\right\}},X_{\omega },X_{\widehat{G}\backslash \omega \cup \{X_i^h,X_j^k\}}=0)}$$

(26)

Since $X_i^h$ and $X_j^k$ are conditionally independent given the rest of the multilayer graph, we can also replace the condition for $X_j^k$ with any other, without affecting $X_i^h$. By adjusting this prior conveniently, we can write out:

$$\frac{\mathbb{P}(X_{\omega },X_{\widehat{G}\backslash \omega }=0)}{\mathbb{P}(X_{\omega \cup \left\{X_i^h\right\}},X_{\widehat{G}\backslash \omega \cup \left\{X_i^h\right\}}=0)}=\frac{\mathbb{P}(X_{\omega \cup \left\{X_j^k\right\}},X_{\widehat{G}\backslash \omega \cup \left\{X_j^k\right\}}=0)}{\mathbb{P}(X_{\omega \cup \{X_i^h,X_j^k\}},X_{\widehat{G}\backslash \omega \cup \{X_i^h,X_j^k\}}=0)}$$

(27)

By substituting Equation (27) into Equation (24) we get (condition (ii)):

$$f_{\sigma }\ast (X_{\sigma }\ast )=1$$

(28)

3. An Information-Theoretical Class of Tensor Markov Fields

Let us consider again the set of tensor-valued random variables $X=X_{\alpha }^{\beta }$. It is possible to calculate, for every duplex in X, the mutual information function $I(·,·)$ [4]:

$$I(X_i^h,X_j^k)=\sum _{\mathrm{\Omega }}\sum _{{\mathrm{\Omega }}^{\prime }}p(X_i^h,X_j^k)log\frac{p(X_i^h,X_j^k)}{p\left(X_i^h\right)p\left(X_j^k\right)}$$

(29)

Let us consider a multilayer graph scenario. From now on, the indices $i,j$ will refer to the random variables, whereas $h,k$ will be indices for the layers. $\mathrm{\Omega }$ and ${\mathrm{\Omega }}^{\prime }$ are the respective sampling spaces (that may, of course, be equal). In order to discard self-information, let us define the off-diagonal mutual information as follows:

$$I^{†}(X_i^h,X_j^k)=I(X_i^h,X_j^k)\times \left(1-{\delta }_{X_i^h{X}_j^k}\right)$$

(30)

With the bi-delta function ${\delta }_{X_i^h{X}_j^k}$ defined as:

$${\delta }_{X_i^h{X}_j^k}=\left\{\begin{array}{cc}1,\hfill & \mathrm{if}i=j\mathrm{and}h=k\hfill \\ 0,\hfill & \mathrm{otherwise}\hfill \end{array}\right.$$

(31)

By having the complete set of off-diagonal mutual information functions for all the random variables and layers, it is possible to define the following hyper-matrix elements:

$$A_{ij}^{hk}=\mathrm{\Theta }\left[I^{†}(X_i^h,X_j^k)-I_0\right]$$

(32)

as well as:

$$W_{ij}^{hk}=A_{ij}^{hk}\circ I^{†}(X_i^h,X_j^k)$$

(33)

Here $\mathrm{\Theta }[·]$ is Heavyside’s function and $I_0$ is a lower bound for mutual information (a threshold) to be considered significant.

We call $A_{ij}^{hk}$ and $W_{ij}^{hk}$ the adjacency hypermatrix and the strength hypermatrix respectively (notice that ∘ in Equation (33) represents the product of a scalar times a hypermatrix). The adjacency hyper-matrix and the strength hyper-matrix define the (unweighted and weighted, respectively) neighborhood law of the associated TMF, hence the statistical dependency structure for the set of random variables and contexts (layers).

Although the adjacency and strength hypermatrices are indeed, proper representations of the undirected (unweighted and weighted) dependency structure of $\mathbb{P}\left(X\right)$, it has been considered advantageous to embed them into a tensor linear structure, in order to be able to work out some of the mathematical properties of such fields relying on the methods of tensor algebra. One relevant proposal in this regard, has been advanced by De Domenico and collaborators, in the context of multilayer networks.

Following the ideas of De Domenico and co-workers [5], we introduce the unweighted and weighted adjacency 4-tensors (respectively) as follows:

$$\mathbb{A}=\sum _{h,k=1}^L\sum _{i,j=1}^N{A}_{ij}^{hk}\otimes {\xi }_{\beta \delta }^{\alpha \gamma }$$

(34)

$$\mathbb{W}=\sum _{h,k=1}^L\sum _{i,j=1}^N{W}_{ij}^{hk}\otimes {\xi }_{\beta \delta }^{\alpha \gamma }$$

(35)

Here, ${\xi }_{\beta \delta }^{\alpha \gamma }={\xi }_{\beta \delta }^{\alpha \gamma }\left[ijhk\right]$ is a unit four-tensor whose role is to provide the hypermatrices with the desired linear properties (projections, contractions, etc.). Square brackets indicate that the indices $i,j,h$ and k belong to the $\alpha ,\beta ,\gamma$ and $\delta$ dimensions and ⊗ represents a form of a tensor matricization product (i.e., the one producing a 4-tensor out of a 4-index hypermatrix times a unitary 4-tensor).

3.1. Conditional Independence in Tensor Markov Fields

In order to discuss the conditional independence structure induced by the present class of TMFs, let us analyze Equation (32). As already mentioned, the hyper-adjacency matrix $A_{ij}^{hk}$ represents the neigborhood law (as given by the Markov property) on the multilayer graph $\widehat{G}$ (i.e., the TMF). Every non-zero entry on this hypermatrix represents a statistical dependence relation between two elements on X. The conditional dependence structure on TMFs inferred from mutual information measures via Equation (32) are related not only to the statistical independence conditions (as given by a zero mutual information measure between two elements), but also to the lower bound $I_0$ and in general to the dependency structure of the whole multilayer graph.

The definition of conditional independence (CI) for tensor random variables is as follows:

$$(X_i^h\perp \perp X_j^k)|X_l^m\iff {\mathbb{F}}_{X_i^h,X_j^k|X_l^m=X_l^m*}(X_i^h*,X_j^k*)={\mathbb{F}}_{X_i^h|X_l^m=X_l^m*}(X_i^h*)·{\mathbb{F}}_{X_j^k|X_l^m=X_l^m*}(X_j^k*)$$

(36)

$\forall X_i^h,X_j^k,X_l^m\in X$.

Here $\perp \perp$ represents conditional independence between two random variables, were ${\mathbb{F}}_{X_i^h,X_j^k|X_l^m=X_l^m\ast }(X_i^h\ast ,X_j^k\ast )=Pr(X_i^h\le X_i^h\ast ,X_j^k\le X_j^k\ast |X_l^m=X_l^m\ast )$ is the joint conditional cumulative distribution of $X_i^h$ and $X_j^k$ given $X_l^m$ and $X_i^h\ast$, $X_j^k\ast$ and $X_l^m\ast$ are realization events of the corresponding random variables.

In the case of MRFs (and by extension TMFs), CI is defined by means of (multi)graph separation: in this sense we say that $X_i^h\perp {\perp }_{\widehat{G}}{X}_j^k|X_l^m$ iff $X_l^m$ separates $X_i^h$ from $X_j^k$ in the multilayer graph $\widehat{G}$. This means that if we remove node $X_l^m$ there are no undirected paths from $X_i^h$ to $X_j^k$ in $\widehat{G}$.

Conditional independence in random fields is often considered in terms of subsets of V. Let A, B and C be three subsets of V. The statement $X_A\perp {\perp }_{\widehat{G}}{X}_B|X_C$, which holds only iff C separates A from B in the multilayer graph $\widehat{G}$, meaning that if we remove all vertices in C there will be no paths connecting any vertex in A to any vertex in B is called the global Markov property of TMFs.

The smallest set of vertices that renders a vertex $X_i^h$ conditionally independent of all other vertices in the multilayer graph is called its Markov blanket, denoted $mb\left(X_i^h\right)$. If we define the closure of a node $X_i^h$ as $\mathcal{C}\left(X_i^h\right)$ then $X_i^h\perp \perp \widehat{G}\backslash \mathcal{C}\left(X_i^h\right)|mb\left(X_i^h\right)$.

It is possible to show that in a TMF, the Markov blanket of a vertex is its set of first neighbors. This is called the undirected local Markov property. Starting from the local Markov property it is possible to show that two vertices $X_i^h$ and $X_j^k$ are conditionally independent given the rest if there is no direct edge between them. This has been called the pairwise Markov property.

If we denote by ${\widehat{G}}_{X_i^h\to X_j^k}$ the set of undirected paths in the multilayer graph $\widehat{G}$ connecting vertices $X_i^h$ and $X_j^k$, then the pairwise Markov property of a TMF can be stated as:

$$X_i^h\perp \perp X_j^k|\widehat{G}\backslash \{X_i^h,X_j^k\}\iff {\widehat{G}}_{X_i^h\to X_j^k}=\varnothing$$

(37)

It is clear that the global Markov property implies the local Markov property which in turn implies the pairwise Markov property. For systems with positive definity probability densities, it has been probed (in the case of MRFs) that pairwise Markov actually implied global Markov (See [6] p. 119 for a proof). For the present extension this is important since it is easier to assess pairwise conditional independence statements.

3.2. Indepence Maps

Let $I_{\widehat{G}}$ denote the set of all conditional independence relations encoded by the multilayer graph $\widehat{G}$ (i.e., those CI relations given by the Global Markov property). Let $I_{\mathbb{P}}$ be the set of all CI relations implied by the probability distribution $\mathbb{P}\left(X_i^j\right)$. A multilayer graph $\widehat{G}$ will be called an independence map (I-map) for a probability distribution $\mathbb{P}\left(X_i^j\right)$, if all CI relations implied by $\widehat{G}$ hold for $\mathbb{P}\left(X_i^j\right)$, i.e., $I_{\widehat{G}}\subseteq I_{\mathbb{P}}$ [6].

The converse statement is not necessarily true, i.e., there may be some CI relations implied by $\mathbb{P}\left(X_i^j\right)$ that are not encoded in the multilayer graph $\widehat{G}$. We may be usually interested in minimal I-maps, i.e., I-maps from which none of the edges could be removed without destroying its CI properties.

Every distribution has a unique minimal I-map (and a given graph representation). Let $\mathbb{P}\left(X_i^j\right)>0$. Let ${\widehat{G}}^{†}$ be the multilayer graph obtained by introducing edges between all pairs of vertices $X_i^h$, $X_j^k$ such that $X_i^h\perp \perp X_j^k|X\backslash \{X_i^h,X_j^k\}$, then ${\widehat{G}}^{†}$ is the unique minimal I-map. We call $\widehat{G}$ a perfect map of $\mathbb{P}$ when there is no dependencies $\widehat{G}$ which are not indicated by $\mathbb{P}$, i.e., $I_{\widehat{G}}=I_{\mathbb{P}}$ [6].

3.3. Conditional Independence Tests

Conditional independence tests are useful to evaluate whether CI conditions apply either exactly or in the case of applications under a certain bounded error. In order to be able to write down expressions for C.I. tests let us introduce the following conditional kernels [7]:

$${\mathbb{C}}_A\left(B\right)=\mathbb{P}\left(B\right|A)=\frac{\mathbb{P}\left(AB\right)}{\mathbb{P}\left(A\right)}$$

(38)

as well as their generalized recursive relations:

$${\mathbb{C}}_{ABC}\left(D\right)={\mathbb{C}}_{AB}\left(D\right|C)=\frac{{\mathbb{C}}_{AB}\left(CD\right)}{{\mathbb{C}}_{AB}\left(C\right)}$$

(39)

The conditional probability of $X_h^k$ given $X_i^j$ can be thus written as:

$${\mathbb{C}}_{X_i^j}\left(X_h^k\right)=\mathbb{P}\left(X_h^k\right|X_i^j)=\frac{\mathbb{P}(X_h^k,X_i^j)}{\mathbb{P}\left(X_i^j\right)}$$

(40)

We can then write down expressions for Markov conditional independence as follows:

$$X_i^j\perp \perp X_h^k|X_l^m\Rightarrow \mathbb{P}(X_i^j,X_h^k|X_l^m)=\mathbb{P}\left(X_i^j\right|X_l^m)\times \mathbb{P}\left(X_h^k\right|X_l^m)$$

(41)

Following Bayes’ theorem, CI conditions –in this case– will be of the form:

$$\mathbb{P}(X_i^j,X_h^k|X_l^m)=\frac{\mathbb{P}(X_i^j,X_l^m)}{\mathbb{P}\left(X_l^m\right)}\times \frac{\mathbb{P}(X_h^k,X_l^m)}{\mathbb{P}\left(X_l^m\right)}=\frac{\mathbb{P}(X_i^j,X_l^m)\times \mathbb{P}(X_h^k,X_l^m)}{{\mathbb{P}\left(X_l^m\right)}^2}$$

(42)

Equation (42) is useful since in large scale data applications is computationally cheaper to work with joint and marginal probabilities rather than conditionals.

Now let us consider the case of conditional independence given several conditional variables. The case for CI given two variables could be written—using conditional kernels—as follows:

$$X_i^j\perp \perp X_h^k|X_l^m,X_n^o\Rightarrow \mathbb{P}(X_i^j,X_h^k|X_l^m,X_n^o)=\mathbb{P}\left(X_i^j\right|X_l^m,X_n^o)\times \mathbb{P}\left(X_h^k\right|X_l^m,X_n^o)$$

(43)

Hence,

$$\mathbb{P}(X_i^j,X_h^k|X_l^m,X_n^o)={\mathbb{C}}_{X_l^m,X_n^o}\left(X_i^j\right)\times {\mathbb{C}}_{X_l^m,X_n^o}\left(X_h^k\right)$$

(44)

Using Bayes’ theorem,

$$\mathbb{P}(X_i^j,X_h^k|X_l^m,X_n^o)=\frac{\mathbb{P}(X_i^j,X_l^m,X_n^o)}{\mathbb{P}(X_l^m,X_n^o)}\times \frac{\mathbb{P}(X_h^k,X_l^m,X_n^o)}{\mathbb{P}(X_l^m,X_n^o)}$$

(45)

$$\mathbb{P}(X_i^j,X_h^k|X_l^m,X_n^o)=\frac{\mathbb{P}(X_i^j,X_l^m,X_n^o)\times \mathbb{P}(X_h^k,X_l^m,X_n^o)}{{\mathbb{P}(X_l^m,X_n^o)}^2}$$

(46)

In order to generalize the previous results to CI relations given an arbitrary set of conditionals, let us consider the following sigma-algebraic approach:

Let ${\Sigma }_{ih}^{jk}$ be the $\sigma$-algebra of all subsets of X that do not contain $X_i^j$ or $X_h^k$. If we consider the contravariant index $i\in \alpha$ with $i=1,2,\dots ,N$ and the covariant index $j\in \beta$ with $j=1,2,\dots ,L$, then there are $\mathcal{M}=\frac{NL}{2}$ such $\sigma$-algebras in X (let us recall that TMFs are undirected graphical models).

A relevant problem for network reconstruction is that of establishing the more general Markov pairwise CI conditions, i.e., the CI relations for every edge not drawn in the graph. Two arbitrary nodes $X_i^j$ and $X_h^k$ are conditionally independent given the rest of the graph iff:

$$X_i^j\perp \perp X_h^k|{\Sigma }_{ih}^{jk}\Rightarrow \mathbb{P}(X_i^j,X_h^k|{\Sigma }_{ih}^{jk})=\mathbb{P}\left(X_i^j\right|{\Sigma }_{ih}^{jk})\times \mathbb{P}\left(X_h^k\right|{\Sigma }_{ih}^{jk})$$

(47)

By using conditional kernels, the recursive relations and Bayes’ theorem it is possible to write down $\mathcal{M}$ expressions of the form:

$$\mathbb{P}(X_i^j,X_h^k|{\Sigma }_{ih}^{jk})=\frac{\mathbb{P}(X_i^j,{\Sigma }_{ih}^{jk})\times \mathbb{P}(X_h^k,{\Sigma }_{ih}^{jk})}{{\mathbb{P}\left({\Sigma }_{ih}^{jk}\right)}^2}$$

(48)

The family of Equations (48) represent the CI relations for all the non-existing edges in the hypergraph $\widehat{G}$, i.e., every pair of nodes $X_i^j$ and $X_h^k$ not-connected in $\widehat{G}$ must be conditionally independent given the rest of the nodes in the graph. These expression may serve to implement exact tests or optimization strategies for graph reconstruction and/or graph sparsification in applications considering a mutual information threshold $I_0$ as in Equation (32).

In brief, for every node pair with a mutual information value lesser than $I_0$, the presented graph reconstruction approach will not draw an edge, hence implying CI between the two nodes given the rest. Such CI condition may be tested on the data to see whether it holds or the threshold itself can be determined by resorting to optimization schemes (e.g., error bounds) in Equation (48).

4. Graph Theoretical Features and Multilinear Structure

Once the probabilistic properties of TMFs have been set, it may be fit to briefly present some of their graph theoretical features, as well as some preliminaries as to the reasons to embed hyperadjecency matrices into multilayer adjacency tensors. Given that TMFs are indeed PGMs, some of their graph characteristics will result relevant here.

Since the work by De Domenico and coworkers [5] covers in great detail how the multilinear structure of the multilayer adjacency tensor allows the calculation of these quantities—usually as projection operations—we will only mention connectivity degree vectors since these are related with the size of the TMF dependency neighborhoods.

Let us recall multilayer adjacency tensors, as defined in Equations (34) and (35). To ease presentation, we will work with the unweighted tensor ${\mathbb{A}}_{\beta \delta }^{\alpha \gamma }$ (Equation (34)). The multidegree centrality vector $K^{\alpha }$ which contains the connectivity degrees of the nodes spanning different layers can be written as follows:

$$K^{\alpha }={\mathbb{A}}_{\beta \delta }^{\alpha \gamma }{U}_{\gamma }^{\delta }{u}^{\beta }$$

(49)

Here $U_{\gamma }^{\delta }$ is a rank 2 tensor that contains a 1 in every component and $u^{\beta }$ is a rank 1 tensor that contains a 1 in every component—these quantities are called 1—tensors by De Domenico and coworkers [5]. It can be shown that $K^{\alpha }$ is indeed given by the sums of the connectivity degree vectors $k^{\alpha }$ corresponding to all different layers:

$$K^{\alpha }=\sum _{h=1}^L\sum _{k=1}^L{k}^{\alpha }\left(hk\right)$$

(50)

$k^{\alpha }\left(hk\right)$ is the vector of connections that nodes in the set $\alpha =1,2,\dots ,N$ in layer h have to any other nodes in layer k. Whereas $K^{\alpha }$ is the vector with connections in all the layers. Appropriate projections will yield measures such as the size of the neighborhood to a given vertex $|N_{X_i^j}|$, the size of its Markov blanquet $\left|mb\right(X_i^h\left)\right|$, or other similar quantities.

5. Specific Applications

After having considered some of the properties of this class of Tensor Markov Fields, it may become evident that aside from purely theoretical importance, there is a number of important applications that may arise as probabilistic graphical models in tensor valued problems, among the ones that are somewhat evident are the following:

• The analysis of multidimensional biomolecular networks such as the ones arising from multi-omic experiments (For a real-life example, see Figure 4) [8,9,10];
• Probabilistic graphical models in computer vision (especially 3D reconstructions and 4D [3D+time] rendering) [11];
• The study of fracture mechanics in continuous deformable media [12];
• Probabilistic network models for seismic dynamics [13];
• Boolean networks in control theory [14].

Some of these problems are being treated indeed as multiple instances of Markov fields or as multipartite graphs or hypergraphs. However, it may become evident that when random variables across layers are interdependent (which is often the case), the definitions of potentials, cliques and partition functions, as well as the conditional statistical independence features become manageable (and in some cases even meaninful) under the presented formalism of Tensor Markov Fields.

6. Conclusions

Here we have presented the definitions and fundamental properties of Tensor Markov Fields, i.e., random Markov fields over tensor spaces. We have proved –by extending the results of Dobruschin, Hammersley and Clifford to such tensor valued fields– that tensor Markov fields are indeed Gibbs fields whenever strictly positive probability measures are considered. We also introduced a class of tensor Markov fields obtained by using information theoretical statistical dependence measures inducing local and global Markov properties, and show how these can be used as probabilistic graphical models in multi-context environments much in the spirit of the so-called multilayer network approach. Finally, we discuss the convenience of embedding tensor Markov fields in the multilinear tensor representation of multilayer networks.