Highlights

Product of Tensors and Description of Networks

Luca Chiantini, Giuseppe Alessio D’Inverno, Sara Marziali

• Study of the characterization of the signal distribution in a network under the lens of tensor algebra

• Formal proof of equality between the total tensor of the network and the Bhattacharya-Mesner Product on the set of the activation tensors

Product of Tensors and Description of Networks

Luca Chiantini^{a}, Giuseppe Alessio D’Inverno^{b}, Sara Marziali^{a}

aDepartment of Information Engineering and Mathematics, University of Siena, Via

Roma 56, Siena, 58100, Italy

bInternational School for Advanced Studies, Via Bonomea 265, Trieste, 34136, Italy

Abstract

We study the characterization of the signal distribution in a network under the lens of tensor algebra. More specifically, we describe every activation function as tensor distributions with respect to the nodes, called activation tensors. The distribution of the signal is encoded in the total tensor of the network. We formally prove that the total tensor can be obtained by computing the Bhattacharya-Mesner Product, an n-ary operation for tensors of order n, on the set of activation tensors properly ordered and processed via two basic operations, that we call blow and forget. Our theoretical framework can be validated through the related code developed in Python.

Keywords: Networks, Tensor algebra, Bhattacharya-Mesner Product 2020 MSC: 15A69

The last shall be the first. Matthew, 16:20

Introduction

In this work, we introduce a description of network behavior based on the Bhattacharya-Mesner Product (BMP) of tensors. The BMP is an n-ary operation on tensors of order n that generalizes the binary matrix multiplication. It was introduced in [10] (see also [11] and [1]) and has been used to describe algebraic and geometric properties of tensors in [4–6,12].

Email addresses: luca.chiantini@unisi.it (Luca Chiantini), gdinvern@sissa.it (Giuseppe Alessio D’Inverno), sara.marziali@student.unisi.it (Sara Marziali)

In our setting, a Signal Propagation Network (see Definition 2) is determined by an underlying directed graph, describing the flow of a signal through the set of nodes, and by a list of activation tensors, one for each node. We focus on directed acyclic graphs (DAGs), that is, graphs with no oriented cycles, in order to exclude circular signal transmission. The absence of cycles guarantees the existence of total orderings of the nodes compatible with the partial order induced by the graph. We regard such a total ordering as a constituting aspect of the network. Each activation tensor is responsible for the reaction of the node to the state of its parents.

The dimension of the activation tensor is equal to the number of incoming arrows (in-degree) of the node plus one. The size of the activation tensor, in turn, depends on the number of states of each node, which we assume to be constant through the network. More precisely, for a node a whose parents are the nodes (b_{j_{1}}, …, b_{j_{d}}) (in the fixed total order), the entry A_{i_{1},...,i_{d},i_{d+1}} of the activation tensor A represents the probability that a takes the state i_{d+1} when the node b_{j_{k}} is in state i_{k}, for k = 1, …, d.

In our analysis, we transform the collection of activation tensors {A_{i}} into tensors {T_{a_{i}}} of dimension n, where n is the number of nodes of the graph, by means of a procedure based on two operations on the indices called blow (or inflation, following the terminology of [4]) and forget (or copy), described in Section 3, Procedure 22.

We observe that these operations are well defined independently of the number of nodes and of the choice of activation tensors, which may be arbitrary and may vary from node to node. Examples of reasonable activation tensors, in the spirit of [2], are given throughout the paper. To better align the model with a statistical interpretation of the network, one could impose stochastic constraints on the activation tensors, for instance, requiring their entries to be positive real numbers in the interval [0, 1] and to sum to 1 over the output state. We do not impose such restrictions here, since they are not needed for our computations.

It turns out that, for a fixed network in which all nodes are observable, the set of total tensors describing the final states of the network forms a toric variety. Since all nodes are observable, the total tensor of the network depends on parameters and fills a toric subvariety of the (projective) space of tensors. The main geometric aspects of this variety are therefore strictly related to the algebraic structure of the BMP, and we will explore the connection, as well as extensions to networks with hidden nodes, via marginalization of the BMP in future investigations.

Our main result (Theorem 23) shows that the final state of the network can be determined by computing the BMP, for a given ordering, of the activation tensors associated with the nodes suitably modified by the blow and forget operations introduced above.

The paper is organized as follows. In Section 1, we introduce SPNs and present the notation and basic concepts on tensors, with particular emphasis on activation tensors. In Section 2, we define the BMP of tensors and discuss its algebraic properties. Finally, in Section 3, we show how a network can be characterized in terms of the BMP.

1. Basic notation and concepts

1.1. Basic notation on tensors

In this section, we introduce the main notation for tensors and networks. Standard references for tensor theory are [7,8].

Definition 1. Let V_{1}, …, V_{d} be complex vector spaces of dimensions v_{1}, …, v_{d}, respectively. A function

f: V_{1} × ⋯ × V_{d} → ℂ

is multilinear if it is linear in each factor V_{l}, l = 1, …, d. The space of such multilinear functions is denoted by V_{1}^{∗} ⊗ V_{2}^{∗} ⊗ ⋯ ⊗ V_{d}^{∗} and it is referred to as tensor product of V_{1}^{∗}, …, V_{d}^{∗}. Elements

T ∈ V_{1}^{∗} ⊗ V_{2}^{∗} ⊗ ⋯ ⊗ V_{d}^{∗}

are called tensors. The integer d is sometimes named the dimension of T, while the expression v_{1} × ⋯ × v_{d} is the size of T. We say a tensor is cubical of size n if v_{1} = ⋯ = v_{d} = n.

Our labeling convention for a tensor T ∈ ℂ^{2}⊗ℂ^{2}⊗ℂ^{2} is shown in Figure 1.

1.2. Networks

A basic reference for networks and activation tensors is [9]. Following the notation proposed in [3], let G be a directed acyclic graph (DAG) with V (G) the set of nodes, or vertices, and E(G) the set of edges. We call arrows the oriented edges of G. For any node a ∈ V (G), we say that a node b ∈ V (G) is a parent of a if there is an arrow b → a in the graph, that is, if b → a ∈ E(G). We denote by parents(a) = { b ∈ V (G) : b is a parent of a } the set of parents of a. The in-degree of a, in-deg(a), is the cardinality of parents(a). We write |V (G)| for the cardinality of G.

\begin{matrix}T_{1,0,0} \\ T_{1,1,0} \\ T_{1,0,1} \\ T_{1,1,1} \\ T_{0,0,0} \\ T_{0,1,0} \\ T_{0,0,1} \\ T_{0,1,1} \end{matrix}

Figure 1: Labeling convention. The convention used to label the entries of a tensor T ∈ ℂ^{2} ⊗ ℂ^{2} ⊗ ℂ^{2}.

Definition 2. In our setting, a Signal Propagation Network (SPN) is a pair

N = N (G, A),

consisting of the following data:

(i) a directed graph G = (V (G), E(G)) without (oriented) cycles, whose nodes represent the discrete variables of the network; we say that the SPN is n-ary if every node can take n states;

(ii) a set A of activation tensors A_{i}, one for each node a_{i} ∈ V (G), which determines the state of the node based on the states of its parents. More precisely, let a_{i} be a node of an n-ary SPN N (G), with d = in-deg(a_{i}). The activation tensor A_{i} ∈ A associated to a_{i} is any tensor of dimension d + 1 such that

A_{i} ∈ \underbrace{(ℂ^{n}) ⊗ ⋯ ⊗ (ℂ^{n});}_{d+1 times}

(iii) an ordering of the nodes compatible with the partial ordering given by the graph (topological sort).

Note that the absence of cycles (as in Definition 2(i)) in the graph implies that some topological ordering always exists (see Definition 2(iii)). This can be easily seen by induction.

Unless otherwise stated, we work with n-ary SPNs in which each node can take the same n states, numbered from 0 to n − 1. In particular, in the next sections we will mainly consider the binary case n = 2, interpreting state 0 as inactive and state 1 as active.

By Definition 2, the SPN N (G) is defined by its underlying DAG together with the activation tensors associated with its nodes. In particular, if d = 0, then an activation tensor associated with a node a_{i} is simply a vector of ℂ^{n}. If d = 1, then an activation tensor at a_{i} is an n × n matrix of complex numbers.

1.3. Tensors of networks We now explain the role of the activation tensors of the network. Consider an n-ary signal transmitted by the nodes of an SPN N, following

the pattern prescribed by the arrows of the underlying DAG. Let d be the indegree of a node a and {b_{1}, …, b_{d}} be the set of its parents, ordered according to the total ordering of the network. Then, node a decides its state depending on the states of its parents.

Consequently, the entry A_{i_{1},...,i_{d},i_{d+1}} of the activation tensor represents the frequency with which the node a takes the state i_{d+1} when its parent b_{1} is in the state i_{1}, its parent b_{2} is in the state i_{2}, …, its parent b_{d} is in the state i_{d}.

Remark 3. One could adopt a stochastic point of view by requiring

∑_{l=0}^{n−1} A_{i_{1},...,i_{d},l} = 1,

so that A_{i_{1},...,i_{d},i_{d+1}} represents the probability that the node a takes the state i_{d+1} when b_{1} takes the state i_{1}, …, and b_{d} takes the state i_{d}. We do not impose this assumption, since it is not necessary for our analysis.

Example 4. Some examples of activation tensors, for different values of d, are listed in the following.

• When d = 0, the activation tensor A = (a_{0}, …, a_{n−1}) is defined such that node a takes the state i with frequency a_{i}.

• When d = 1, well-known examples of activation tensors are the Jukes-Cantor matrices, in which all the entries in the diagonal are equal to a parameter α and all the off-diagonal entries are equal to a parameter β. For instance, in the binary case,

A = (\begin{matrix}α & β \\ β & α \end{matrix}) ,

with α, β ∈ ℂ.

0 0 1 1 1 0 0 1

Figure 2: Activation tensor with threshold of value one. Example of a threshold of value one activation tensor for a node in a binary SPN, with d = 2.

\begin{matrix}β \\ β \\ α \\ α \\ α \\ β \\ β \\ α \end{matrix}

Figure 3: Activation tensor with quantum-threshold of value one. Example of a quantum-threshold activation tensor for a node in a binary SPN with parameters α, β ∈ ℂ.

• For d ≥ 1, a relevant case of activation tensor for binary SPNs is the threshold of value one, namely the tensor associated to the Boolean logical operator ∃. The node a takes the state 1 if at least one of its parents is in the state 1, while a takes the state 0 otherwise. Hence A_{i_{1},...,i_{d},i_{d+1}} is 0 if i_{1} = ⋯ = i_{d} = 0 and i_{d+1} = 1, or when at least one of i_{1}, …, i_{d} is equal to 1 and i_{d+1} = 0. In all remaining cases, the corresponding entry of A is equal to 1.

An example, for d = 2, is shown in Figure 2.

• The activation tensor above can be modified by replacing the values 0 and 1 with two parameters α, β ∈ ℂ, yielding the quantum-threshold of value one. Specifically, the node a will take the state α if it obeys the rule, and the state β otherwise.

For d = 2 the tensor in Figure 3 is obtained by modifying the 0’s in Figure 2 with β’s and the 1’s with α’s.

Definition 5. Let N (G, A) be an n-ary SPN, with |V (G)| = q, and nodes a_{1}, …, a_{q}. The total tensor associated with the network is the dimension-q tensor N of size \underbrace{n × ⋯ × n}_{q times} whose entry N_{i_{1},...,i_{q}}, where i_{h} = 0, …, n − 1, for h = 1, …, q, is defined as follows. For each node a_{j}, j = 1, …, q, let d_{j} = in-deg(a_{j}) < q, let A_{j} be its activation tensor, and let P_{j} be the d_{j}- tuple of indices in {i_{1}, …, i_{q}} corresponding to the parents of a_{j}, namely P_{j} = (i_{k} : b_{k} ∈ parents(a_{j})) (where the tuple is ordered according to the chosen topological ordering of the SPN). Then

N_{i_{1},...,i_{q}} = Π_{j=1}^{q}(A_{j})_{concat[P_{j},i_{j}]}.  (1)

Here, concat[x, y] denotes the concatenation of tuples x and y.

The following examples, in the binary case, illustrate the meaning of the total tensor.

Example 6. Consider the SPN characterized by the underlying graph in Figure 4 with three nodes (a_{1}, a_{2}, a_{3}) (in the unique possible ordering) and the following activation tensors: the vector A_{1} = (α, β) for the source

node a_{1}, the Jukes-Cantor matrix A_{2} = (\begin{matrix}α & β \\ β & α \end{matrix}) for a_{2} and set A_{3} = A_{2}

for a_{3}. This can be considered as a Signal Propagation Network analogue of a short Markov chain

\begin{matrix}a_{1} \\ a_{2} \\ a_{3} \end{matrix}

Figure 4: SPN analogue of a Markov chain with three nodes. Underlying graph of an SPN with three nodes a_{1}, a_{2}, a_{3}. The state of a_{2} depends on a_{1} and the state of a_{3} depends on a_{2}.

To compute the total tensor, we determine the indices of the parents of each node. For node a_{1}, which is the source, we have in-deg(a_{1}) = 0 and P_{1} = (). For node a_{2}, we have in-deg(a_{2}) = 1, parents(a_{2}) = {a_{1}} and P_{2} = (i_{1}). Finally, for node a_{3}, we have in-deg(a_{3}) = 1, parents(a_{3}) = {a_{2}} and P_{3} = (i_{2}).

Hence, by Definition 5,

N_{i_{1},i_{2},i_{3}} = (A_{1})_{i_{1}}(A_{2})_{i_{1},i_{2}}(A_{3})_{i_{2},i_{3}},

and the corresponding tensor is represented in Figure 5.

\begin{matrix}αβ^{2} \\ αβ^{2} \\ β^{3} \\ α^{2}β \\ α^{3} \\ αβ^{2} \\ α^{2}β \\ α^{2}β \end{matrix}

Figure 5: Total tensor of the SPN in Example 6. Representation of the total tensor of the SPN in Example 6 with parameters α, β ∈ ℂ. A possible reading of the values of the total tensor is the following: N_{0,0,0} means that a_{1} takes state 0 (α), then a_{2} obeys and takes state 0 (α again), and a_{3} obeys and takes state 0 (another α), so N_{0,0,0} = α^{3}; N_{0,1,1} means that a_{1} takes state 0 (α), then a_{2} disobeys and takes state 1 (β), while a_{3} obeys and takes state 1 (another α), so N_{0,1,1} = α^{2}β; and so on.

Example 7. Consider the SPN associated with the graph in Figure 6, with three nodes (a_{1}, a_{2}, a_{3}) in the unique possible ordering and, as activation tensors, the vector A_{1} = (α, β) for the source node a_{1}, the Jukes-Cantor

matrix A_{2} = (\begin{matrix}α & β \\ β & α \end{matrix}) for a_{2}, and the quantum-threshold of value one tensor

A_{3} of Example 4 for a_{3}.

\begin{matrix}a_{1} \\ a_{2} \\ a_{3} \end{matrix}

Figure 6: Acyclic triangle with three nodes. Underlying graph of an SPN with three nodes a_{1}, a_{2}, a_{3}. The state of the node a_{2} depends on the state of the node a_{1}, and the state of the node a_{3} depends on both the states of a_{1} and a_{2}.

For node a_{1}, which is the source, we have A_{1} = (α, β), in-deg(a_{1}) = 0, and P_{1} = (). For node a_{2}, we have in-deg(a_{2}) = 1 and P_{2} = (i_{1}). For node a_{3}, we have in-deg(a_{3}) = 2 and P_{3} = (i_{1}, i_{2}).

Then, the total tensor N of the SPN, according to Equation (1), can be computed as

N_{i_{1},i_{2},i_{3}} = (A_{1})_{i_{1}}(A_{2})_{i_{1},i_{2}}(A_{3})_{i_{1},i_{2},i_{3}},

and its representation is shown in Figure 7.

\begin{matrix}β^{3} \\ αβ^{2} \\ αβ^{2} \\ α^{2}β \\ α^{3} \\ αβ^{2} \\ α^{2}β \\ α^{2}β \end{matrix}

Figure 7: Total tensor of the acyclic triangle. Representation of the total tensor of a binary acyclic triangle with nodes a_{1}, a_{2}, a_{3} and parameters α, β ∈ ℂ.

2. The Bhattacharya-Mesner Product

2.1. Bhattacharya-Mesner Product

The Bhattacharya-Mesner Product of tensors is a d-ary operation in the space of d-dimensional cubical tensors which generalizes the row-by-column product of matrices. It is defined for tensors with coefficients in any field 𝕂 (and even when 𝕂 is just a ring), although we will apply it mainly to complex tensors.

Definition 8. Let T_{1} = (t_{i_{1},...,i_{d}}^{(1)}), T_{2} = (t_{i_{1},...,i_{d}}^{(2)}), …, T_{d} = (t_{i_{1},...,i_{d}}^{(d)}) be dimensiond tensors of sizes l × n_{2} × ⋯ × n_{d}, n_{1} × l × n_{3} × ⋯ × n_{d}, ⋯, n_{1} × ⋯ × l, respectively. The generalized Bhattacharya-Mesner Product ( shortly BMP), denoted by ∘(T_{1}, T_{2}, …, T_{d}), is a d-ary operation whose result is a tensor T = (t_{i_{1},...,i_{d}})_{i_{1},...,i_{d}} of size n_{1} × n_{2} × ⋯ × n_{d} defined by:

(T)_{i_{1},...,i_{d}} = ∑_{h=0}^{l−1}(T_{1})_{h,i_{2},...,i_{d}} ⋯ (T_{d})_{i_{1},i_{2},...,h},

that is,

t_{i_{1},...,i_{d}} = ∑_{h=0}^{l−1} t_{h,i_{2},...,i_{d}}^{(1)} ⋯ t_{i_{1},i_{2},...,h}^{(d)}.

Remark 9. The BMP generalizes the classical matrix multiplication when d = 2. Indeed, if we consider two matrices T_{1} ∈ ℂ^{n_{1}×l} and T_{2} ∈ ℂ^{l×n_{2}}, their product is defined as

(T_{1} · T_{2})_{i,j} = ∑_{h=0}^{l−1}(T_{1})_{i,h} · (T_{2})_{h,j} = ∑_{h=0}^{l−1}(T_{2})_{h,j}(T_{1})_{i,h} = ∘(T_{2}, T_{1}).

Hence, ∘(A_{2}, A_{1}) coincides with the usual matrix multiplication A_{1} · A_{2}, where the order of the factors is reversed.

Example 10. Let us give an example of the product of three 2×2×2 tensors T_{1} = (t_{i_{1},i_{2}}^{(1)}), T_{2} = (t_{i_{1},i_{2}}^{(2)}), T_{3} = (t_{i_{1},i_{2}}^{(3)}). The BMP

T = (t_{i_{1},i_{2}}) = ∘(T_{1}, T_{2}, T_{3})

can be computed as follows:

t_{i_{1},i_{2}} = ∑_{h=0}^{1} t_{h,i_{2},i_{3}}^{(1)} · t_{i_{1},h,i_{3}}^{(2)} · t_{i_{1},i_{2},h}^{(3)} = t_{0,i_{2},i_{3}}^{(1)} · t_{i_{1},0,i_{3}}^{(2)} · t_{i_{1},i_{2},0}^{(3)} + t_{1,i_{2},i_{3}}^{(1)} · t_{i_{1},1,i_{3}}^{(2)} · t_{i_{1},i_{2},1}^{(3)}.

For example,

\begin{matrix}∘ \\ ( \\ 5 \\ 6 \\ 7 \\ 8 \\ 1 \\ 2 \\ 3 \\ 4 \\ , \\ 13 \\ 14 \\ 15 \\ 16 \\ 9 \\ 10 \\ 11 \\ 12 \\ , \\ 21 \\ 22 \\ 23 \\ 24 \\ 17 \\ 18 \\ 19 \\ 20 \\ ) \\ = \\ 1883 \\ 2588 \\ 3521 \\ 4392 \\ 1103 \\ 1524 \\ 2157 \\ 2712 \end{matrix} .

2.2. Some algebraic properties of BMP

It is almost immediate to observe that the BMP is non-commutative. The BMP is also non-associative, in the sense that, for general dimension-3 tensors A, B, C, D, E,

∘(∘(A, B, C), D, E) ≠ ∘(A, B, ∘(C, D, E)).

Nevertheless, the BMP is multilinear and satisfies some interesting properties.

Multiple identities.

We continue the comparison with matrices (that is, dimension-2 tensors) in order to show how their behavior is generalized in case of dimension-d tensors. When d = 2, for any matrix A of size m × n, there exist identity matrices I_{m} and I_{n} of size m × m and n × n, respectively, such that AI_{n} = A and I_{m}A = A. The role of the identity matrix can be generalized for dimension-n tensors by introducing identitary tensors.

Definition 11. Let n, d ∈ ℕ. For all j, k = 1, …, d with j < k, define the dimension-d identitary tensors I^{j,k} of size n × ⋯ × n by

(I^{j,k})_{i_{1},...,i_{d}} = \begin{cases}1 & if i_{j} = i_{k}; \\ 0 & else. \end{cases}

Notice that when d = 2 there is only one such tensor, namely I^{1,2}, which coincides with the identity matrix.

Example 12. In the case of 2 × 2 × 2 tensors, the dimension-3 identitary tensors are the following:

I^{1,2} = 01011010, I^{1,3} = 00111100, I^{2,3} = 10011001 .

The role of identitary tensors is clarified by the following proposition.

Proposition 13. Let A be a cubical dimension-d tensor. Then,

∘(A, I^{1,2}, …, I^{1,d}) = A, ∘(I^{1,d}, …, I^{d−1,d}, A) = A,

and, for any j = 2, …, d − 1,

∘(I^{1,j}, …, I^{j−1,j}, A, I^{j,j+1}, …, I^{j,d}) = A.

Proof. Let us prove the case where j = 2, …, d − 1. The proofs for the first two equalities are similar. Let T = ∘(I^{1,j}, …, I^{j−1,j}, A, I^{j,j+1}, …, I^{j,d}). By Definition 8,

T_{i_{1},...,i_{d}} = ∑_{h=0}^{l−1}(I^{1,j})_{h,i_{2},...,i_{d}} ⋯ (I^{j−1,j})_{i_{1},...,i_{j−2},h,i_{j},...,i_{d}}·
· A_{i_{1},...i_{j−1},h,i_{j+1},...,i_{d}} · (I^{j,j+1})_{i_{1},...,i_{j},h,i_{j+2},...,i_{d}} ⋯ (I^{j,d})_{i_{1},...i_{d−1},h}.

For j = 2, …, d − 1, the first term I^{1,j} appearing in each addend of the summation ensures that only the addend in which h = i_{j} is different from 0.

Therefore

(I^{1,j})_{i_{j},i_{2},...,i_{d}} = (I^{j,j+1})_{i_{j},...,i_{j−1},i_{j},i_{j},i_{j+2},...,i_{d}} = ⋯ = (I^{j,d})_{i_{1},...,i_{d−1},i_{j}} = 1,

and, hence, T_{i_{1},...,i_{d}} = A_{i_{1},...,i_{d}}.

In particular, from Proposition 13, one obtains that the dimension-3 identitary tensors of Example 12 satisfy

∘(A, I^{1,2}, I^{1,3}) = A

for every 2 × 2 × 2 tensor A.

Transposition.

In the case of dimension-2 tensors, the transpose of the product of two matrices is equal to the product of the transpose of the second matrix and the transpose of the first matrix, namely, for matrices A, B properly sized, we have (AB)^{T} = B^{T} A^{T}. Again, this behavior can be generalized for dimensiond tensors.

Definition 14. Let 𝔖_{d} denote the symmetric group on d elements, and A be a dimension-d tensor. For any σ ∈ 𝔖_{d}, the σ-transpose of A is the dimension-d tensor A^{σ} obtained by permuting the d indices of A according to σ.

In the case of matrices, there are 2 indices and hence only 2 permutations, yielding the identity and the usual transpose. For dimension-d tensors, there are d! such permutations, obtaining (d! − 1) σ-transposes of an dimensiond tensor. From the definition of the BMP, it is immediate to prove the following.

Proposition 15. Let A_{1}, …, A_{d} be properly sized tensors of dimension d and, given σ ∈ 𝔖_{d} a permutation of d indices, call A_{1}^{σ}, …, A_{d}^{σ} their σtransposes. Then

(∘(A_{1}, …, A_{d}))^{σ} = ∘(A_{σ(1)}^{σ}, …, A_{σ(d)}^{σ}).

Proof. We report the computation for d = 3. Let A_{1}, A_{2}, A_{3} be 3-tensors of sizes l × n_{2} × n_{3}, n_{1} × l × n_{3}, n_{1} × n_{2} × l, respectively, and consider the permutation σ ∈ 𝔖_{3} defined as

σ(1) = 1,  σ(2) = 3,  σ(3) = 2.

We define T := ∘(A_{1}, A_{2}, A_{3}) = ∑_{h=0}^{l−1}(A_{1})_{h,j,k} · (A_{2})_{i,h,k}(A_{3})_{i,j,k}, and, by Defini-

tion 14,

(T^{σ})_{i,j,k} = ( ∑_{h=0}^{l−1}(A_{1})_{h,j,k} · (A_{2})_{i,h,k} · (A_{3})_{i,j,h})^{σ} =

= ∑_{h=0}^{l−1}(A_{1})_{h,k,j} · (A_{2})_{i,h,j} · (A_{3})_{i,k,h} = T_{i,k,j}.

On the other hand, we denote T′ = ∘(A_{σ(1)}^{σ}, A_{σ(2)}^{σ}, A_{σ(3)}^{σ}), that is

T′_{i,j,k} = ∘(A_{1}^{σ}, A_{3}^{σ}, A_{2}^{σ})_{i,j,k}.

Since

(A_{1}^{σ})_{i,j,k} = (A_{1})_{i,k,j}, (A_{2}^{σ})_{i,j,k} = (A_{2})_{i,k,j}, (A_{3}^{σ})_{i,j,k} = (A_{3})_{i,k,j}, T′ can be computed as

T′_{ijk} = ∘(A_{1}^{σ}, A_{3}^{σ}, A_{2}^{σ})_{i,j,k} = ∑_{h=0}^{l−1}(A_{1})_{h,j,k}^{σ} · (A_{3})_{i,h,k}^{σ} · (A_{2})_{i,j,h}^{σ} =

= ∑_{h=0}^{l−1}(A_{1})_{h,k,j} · (A_{3})_{i,k,h} · (A_{2})_{i,h,j}.

Finally,

(∘(A_{1}, A_{2}, A_{3})^{σ})_{ijk} = T_{i,k,j} = ∑_{h=0}^{l−1}(A_{1})_{h,k,j} · (A_{2})_{i,h,j} · (A_{3})_{i,k,h} =

= ∑_{h=0}^{l−1}(A_{1})_{h,k,j} · (A_{3})_{i,k,h} · (A_{2})_{i,h,j} = T′_{i,j,k} =

= ∘(A_{1}^{σ}, A_{3}^{σ}, A_{2}^{σ})_{i,j,k}.

3. Network characterization in terms of BMP

3.1. Expansion of tensors

The following operations are fundamental in transforming the activation tensor of each node into a tensor which, through the BMP, yields the total tensor of the SPN.

We call these operations blow and forget. The former increases the dimension of a tensor from d to d + 1, while the latter increases the dimension of a tensor from d to an arbitrary dimension d′ > d.

The blow operation.

Definition 16. Let T ∈ V^{⊗d}. The blow, or inflation, of T is the tensor b(T) of dimension d + 1 defined by

(b(T))_{i_{1},...,i_{d+1}} = \{ \begin{matrix}T_{i_{1},...,i_{d}} & if i_{1} = i_{d+1}; \\ 0 & else. \end{matrix}  (2)

We observe that this definition of inflation (or blow) extends the notion introduced in [4, Section 2.4].

Example 17. The blow b(M) of the matrix M = (\begin{matrix}a & b \\ c & d \end{matrix}) is the following

dimension-3 tensor:

\begin{matrix}b(M) = \\ 0 \\ 0 \\ c \\ d \\ a \\ b \\ 0 \\ 0 \end{matrix}

Notice that the blow is defined only in coordinates.

Remark 18. If T = v_{1} ⊗ ⋯ ⊗ v_{d} is a tensor of rank 1, then in general its blow is no longer of rank 1. Indeed, if {e_{1}, …, e_{n}} is a basis of V and

v_{1} = a_{1}e_{1} + ⋯ + a_{n}e_{n},

then

b(T) = ∑_{i=1}^{n} a_{i}e_{i} ⊗ v_{2} ⊗ ⋯ ⊗ v_{d} ⊗ e_{i}.

The forget operation.

Definition 19. Let T ∈ V^{⊗d}. For d′ > d, let J ⊂ {1, …, d′} be such that |J| = d′ − d. The J-th forget, or J-th copy, of T is the tensor f_{J}(T) of dimension d′ defined by

(f_{J}(T))_{i_{1},...,i_{d′}} = T_{j_{1},...,j_{d}},  (3)

where (j_{1}, …, j_{d}) is the list obtained from (i_{1}, …, i_{d′}) by deleting the entries i_{k} for all k ∈ J.

For instance, the forget operation f_{{k}}(T) creates a tensor whose entry with indices i_{1}, …, i_{d+1} corresponds to the entry of T where i_{h} = j_{h} for h = 1, …, k − 1, and i_{h} = j_{h−1} for h = k + 1, …, d + 1.

Example 20. The forget f_{\{2\}}(M) of the matrix M = (\begin{matrix}a & b \\ c & d \end{matrix}) is the following

dimension-3 tensor:

\begin{matrix}f_{\{2\}}(M) = \\ c \\ c \\ d \\ d \\ a \\ a \\ b \\ b \end{matrix}

In this example, (f_{{2}}(M))_{i_{1},i_{3}} = M_{j_{1},j_{2}} where i_{1} = j_{1}, i_{3} = j_{2}. Indeed, (f_{{2}}(M))_{0,0,0} = (f_{{2}}(M))_{0,1,0} = M_{0,0} = a.

Remark 21. If T = v_{1} ⊗ ⋯ ⊗ v_{d} is a tensor of rank 1, then its J-th forget tensor f_{J}(T) is again a tensor of rank 1. Indeed, if {e_{1}, …, e_{n}} is a basis of V for which v_{1} = a_{1}e_{1} + ⋯ + a_{n}e_{n}, then

f_{{k}}(T) = w_{1} ⊗ ⋯ ⊗ w_{d′},

where w_{i} = v_{i} if i ∉ J, while w_{i} = e_{1} + ⋯ + e_{n} if i ∈ J.

Notice that when J = ∅, one has f_{J}(T) = T.

3.2. The Theorem

We are now ready to explain how the total tensor of an SPN can be obtained as the BMP of tensors constructed from the activation tensors of the network.

Let N (G, A) be an SPN with |V (G)| = q nodes and total ordering (a_{1}, a_{2}, …, a_{q}). We call a_{1} the source and a_{q} the sink of the network.

For each node a_{i} ∈ V (G), we define P_{i} as the set of indices corresponding to the parents of a_{i} (see Definition 5), so that P_{i} ⊂ {1, …, i − 1}. Let p_{i} be the cardinality of P_{i} (p_{i} = |P_{i}|) and let T_{a_{i}} be the activation tensor of the node a_{i}. According to Definition 2(ii), tensor A_{i} has dimension p_{i} + 1.

Procedure 22. For each node a_{i} ∈ V (G), we define the associated dimensionq tensor T_{a_{i}} by the following procedure.

Step 1. Start with the activation tensor A_{i}.

Step 2. If i > 1, compute the dimension-i forget tensor A′_{i} = f_{J}(A_{i}), where J = {1, …, i − 1} \ P_{i}.

Step 3. If i ≠ q, compute the blow tensor A′′_{i} = b(A′_{i}). Thus A′′_{i} has dimension i + 1.

Step 4. Define T_{a_{i}} as the dimension-q forget tensor T_{a_{i}} = f_{H}(A′′_{i}), where H = {i + 2, …, q}.

This construction, based on Equation (2) and Equation (3), ensures that each activation tensor is expanded to a dimension-q tensor. More precisely:

• the initial dimension of A_{i} is p_{i} + 1 ≤ i;

• since |J| = i − 1 − p_{i}, after Step 2 the tensor has dimension i;

• if i < q, after Step 3 the tensor has dimension i + 1;

• if i+1 < q, Step 4 adds the remaining indices and yields a dimension-q tensor.

Theorem 23. Let N (G, A) be an SPN with |V (G)| = q nodes and total ordering (a_{1}, a_{2}, …, a_{q}), such that a_{1} is the source and a_{2} is the sink. Moreover, assume that T_{a_{1}}, …, T_{a_{q}} are the dimension-q tensors obtained from the activation tensors A_{1}, …, A_{q} by applying Procedure 22. Then the BMP

∘(T_{a_{q}}, T_{a_{1}}, …, T_{a_{q−1}})  (4)

computes the total tensor N of the network.

We stress that the tensor T_{a_{q}} associated with the sink node must appear in the first position of the BMP in Equation (4).

Before proving the main theorem, let us illustrate the procedure with some examples.

Example 24. Consider the basic case of an SPN in which there are only two nodes, a_{1} the source and a_{2} the sink. The activation tensor of a_{1} is a vector A_{1}. The activation tensor of a_{2} depends on whether the arrow a_{1} → a_{2} is present.

Assume that the arrow a_{1} → a_{2} exists. Then, the activation tensor A_{2} = (a_{ij}) of a_{2} is a matrix describing the reaction of a_{2} to the state of a_{1}. Applying Procedure 22 to A_{1}, we obtain T_{a_{1}} = b(A_{1}), since here J = H = ∅. By Definition 16, T_{a_{1}} is the diagonal matrix with the vector A_{1} in the diagonal. If we apply Procedure 22 to A_{2}, since J = H = ∅, we simply obtain the matrix

T_{a_{2}} = A_{2}.

Hence, the BMP ∘(T_{a_{2}}, T_{a_{1}}), which in this case is just the usual matrix multiplication T_{a_{1}} · T_{a_{2}}, gives the matrix N with entries

N_{ij} = (A_{1})_{i}(A_{2})_{i,j},

that is the total tensor of the network.

Assume now that the arrow a_{1} → a_{2} does not exist. Then, the activation tensor of a_{2} is a vector A_{2}. As above, applying Procedure 22 to A_{1}, we obtain T_{a_{1}} = b(A_{1}), that is the diagonal matrix with the vector A_{1} in the diagonal. If we apply Procedure 22 to A_{2}, we get the forget tensor T_{a_{2}} = f_{{1}}(A_{2}), which is the n × n matrix whose rows are all equal to A_{2}. Then, the BMP N = ∘(T_{a_{2}}, T_{a_{1}}), which corresponds to the matrix multiplication T_{a_{1}} · T_{a_{2}}, has entries

N_{ij} = (A_{1})_{i}(A_{2})_{j},

expressing the independence of the two nodes. Again, N is the tensor of the network.

Example 25. Consider the SPN of Example 6 with activation tensor A_{1} of the source node a_{1} equal to (α, β) and let the activation tensors A_{2} and A_{3}

of nodes a_{2} and a_{3} be both equal to the Jukes-Cantor matrix A = (\begin{matrix}α & β \\ β & α \end{matrix})

of Example 4.

The total tensor of the network is thus given by the BMP of the tensors T_{a_{3}}, T_{a_{1}}, T_{a_{2}}, where

T_{a_{1}} = f_{{3}}(b(A_{1})),  T_{a_{2}} = b(A_{2}),  T_{a_{3}} = f_{{1}}(A_{3}).

One computes

\begin{matrix}T_{a_{1}} = \\ 0 \\ β \\ 0 \\ β \\ α \\ 0 \\ α \\ 0 \\ , T_{a_{2}} = \\ 0 \\ 0 \\ β \\ α \\ α \\ β \\ 0 \\ 0 \\ , T_{a_{3}} = \\ α \\ β \\ β \\ α \\ α \\ β \\ β \\ α \end{matrix} ,

and the product ∘(T_{a_{3}}, T_{a_{1}}, T_{a_{2}}) gives

N = αβ^{2} αβ^{2} β^{3} α^{2}β α^{3} αβ^{2} α^{2}β α^{2}β ,

which parameterizes a twisted cubic curve in the projective space of tensors of size 2 × 2 × 2, lying in the linear subspace of equations

N_{0,1,0} = N_{1,0,0} = N_{1,1,0}, N_{0,0,1} = N_{0,1,1} = N_{1,1,1}.

Note that both the left and right faces of the tensor have rank 1, corresponding to the fact that a_{3} is independent of a_{1} given a_{2}.

If we remove from the network the arrow that joins a_{2} and a_{3}, and we consider as activation tensors A_{1} and A_{2} as above, and A_{3} = (α, β), we obtain a new SPN whose graph is represented in Figure 8.

The transformed tensors are

T_{a_{1}} = f_{{3}}(b(A_{1})),  T_{a_{2}} = b(A_{2}),  T_{a_{3}} = f_{{1,2}}(A_{3}),

that is

\begin{matrix}a_{1} \\ a_{2} \\ a_{3} \end{matrix}

Figure 8: SPN with three nodes, two of which are sources. Underlying graph of an SPN with three nodes a_{1}, a_{2}, a_{3}. The state of node a_{2} depends on a_{1}, nodes a_{1} and a_{3} are sources.

\begin{matrix}T_{a_{1}} = \\ 0 \\ β \\ 0 \\ β \\ α \\ 0 \\ α \\ 0 \\ , T_{a_{2}} = \\ 0 \\ 0 \\ β \\ α \\ α \\ β \\ 0 \\ 0 \\ , T_{a_{3}} = \\ α \\ α \\ β \\ β \\ α \\ α \\ β \\ β \end{matrix} .

We get that the total tensor of the SPN is the BMP ∘(T_{a_{3}}, T_{a_{1}}, T_{a_{2}}), corresponding to the tensor

N = αβ^{2} α^{2}β β^{3} αβ^{2} α^{3} α^{2}β α^{2}β αβ^{2} ,

which parameterizes a different twisted cubic curve.

Note that not only both the left and right faces of the tensor have rank 1, that is a_{2} is independent of a_{1} given a_{3}, but also the upper and lower faces have rank 1, since a_{2} and a_{3} are independent.

Example 26. It is obvious that in a network without arrows all the activation tensors of the nodes are vectors, and the tensor product of these vectors defines a rank one tensor N which is the total tensor of the network.

More explicitly, let an n-ary SPN with no arrows have q nodes a_{1}, …, a_{q}, with total ordering (a_{1}, …, a_{q}), and let w_{i} ∈ ℂ^{n} be the activation vector of node a_{i}, i = 1, …, q. Then, Theorem 23 implies that the BMP of the associated dimension-q tensors {T_{a_{i}}}_{i=1}^{q}, obtained from {w_{i}}_{i=1}^{q} by applying Procedure 22, is equal to

w_{1} ⊗ ⋯ ⊗ w_{q}.

This can also be verified directly. Namely, we have: T_{a_{1}} = f_{{3,...,q}}(b(w_{1})), T_{a_{j}} = f_{{j+2,...,q}}(b(f_{{1,...j−1}}(w_{j}))) for j = 2, …, q − 2; and

T_{a_{q−1}} = b(f_{{1,...,q−2}}(w_{q−1})), T_{a_{q}} = f_{{1,...,q−1}}(w_{q}).

Thus, assuming w_{i} = (w_{i1}, …, w_{in}) for all i = 1, …, q, the computation of the product N = ∘(T_{a_{q}}, T_{a_{1}}, …, T_{a_{q−1}}) goes as follows:

N_{i_{1},...,i_{q}} = ∑_{h=0}^{n−1} (T_{a_{q}})_{h,i_{2},...,i_{q}} · (T_{a_{1}})_{i_{1},h,i_{3},...,q} ⋯ (T_{a_{q−1}})_{i_{1},...,i_{q−1},h}.

Since the last operation used to obtain T_{a_{q−1}} is a blow, the only surviving summand is the one with h = i_{1}. Hence

N_{i_{1},...,i_{q}} = (T_{a_{q}})_{i_{1},i_{2},...,i_{q}} · (T_{a_{1}})_{i_{1},i_{1},i_{3},...,i_{q}} ⋯ (T_{a_{q−1}})_{i_{1},...,i_{q−1},i_{1}}.

By construction, one gets

(T_{a_{q}})_{i_{1},i_{2},...,i_{q}} = (f_{{1,...,q−1}}(w_{q}))_{i_{1},i_{2},...,i_{q}} = w_{qi_{q}}.

Analogously, for j = 2, …, q − 2,

(T_{a_{j}})_{i_{1},i_{2},...,i_{q}} = (f_{{j+2,...,q}}(b(f_{{1,...,j−1}}(w_{j}))))_{i_{1},i_{2},...,i_{j−1},i_{1},i_{j+1},...,i_{q}}, where the index i_{1} in the middle appears in position j. Thus, (f_{{j+2,...,q}}(b(f_{{1,...,j−1}}(w_{j}))))_{i_{1},i_{2},...,i_{j−1},i_{1},i_{j+1}...,i_{q}} = (b(f_{{1,...,j−1}}(w_{j})))_{i_{1},i_{2},...,i_{j−1},i_{1}}, and

(f_{{1,...,j−1}}(w_{j}))_{i_{1},i_{2},...,i_{j−1}} = w_{ji_{j}}.

With the same argument, one proves that

(T_{a_{1}})_{i_{1},i_{1},i_{3},...,i_{q}} = w_{1i_{1}}, and (T_{a_{q−1}})_{i_{1},i_{2},...,i_{q−1},i_{1}} = w_{q−1 i_{q−1}}.

Then

N_{i_{1},...,i_{q}} = w_{1i_{1}} ⋯ w_{qi_{q}},

that is,

N = w_{1} ⊗ ⋯ ⊗ w_{q}.

Proof of Theorem 23. We work by induction on the number of nodes, the case q = 1 being trivial. We could also use Example 24 as a basis for the induction, starting with q = 2.

Assume the statement holds for every SPN with at most q − 1 nodes, and pick an SPN N (G, A) with |V (G)| = q and total ordering (a_{1}, …, a_{q}).

If we exclude the sink a_{q}, then we obtain an SPN N′(G′, A′) for which the theorem holds, by induction. Use on the nodes of G′ the ordering defined for the nodes of G.

Let N be the total tensor of N, and let N′ be the total tensor of N′. Then, the relation between N and N′ can be described as follows. Call P = P_{q} the set of indices corresponding to the parents of a_{q}, sorted by the ordering defined for G. If A_{q} is the activation tensor of a_{q}, then

N_{i_{1},...,i_{q}} = N′_{i_{1},...,i_{q−1}}(A_{q})_{P (i_{1},...,i_{q})}  (5)

where P (i_{1}, …, i_{q}) denotes the tuple obtained by selecting from (i_{1}, …, i_{q}) the indices corresponding to the elements of P , and then appending i_{q}.

After applying Procedure 22, let T′_{a_{i}} be the tensor associated with a_{i} for the SPN N′, and let T_{a_{i}} be the tensor associated with the same node for the SPN N, with i = 1, … q − 1. Then, T′_{a_{i}} and T_{a_{i}} are linked by the following relations:

\begin{cases}T_{a_{i}} & = f_{\{q\}}(T′_{a_{i}}) if i = 1, …, q − 2; \\ T_{a_{q−1}} & = b(T′_{a_{q−1}}). \end{cases}

Moreover, applying Procedure 22 to the activation tensor A_{q}, we obtain the tensor T_{a_{q}} associated with node a_{q}:

T_{a_{q}} = f_{J}(A_{q}) where J = {1 …, q − 1} \ P.  (6)

Now, we only need to perform the required calculations. The entries of the tensor M = ∘(T_{a_{q}}, T_{a_{1}}, …, T_{a_{q−1}}) have the following structure:

M_{i_{1},...,i_{q}} = ∑_{h=0}^{n−1}(T_{a_{q}})_{h,i_{2},...,i_{q}} · (T_{a_{1}})_{i_{1},h,i_{3},...,i_{q}} ⋯ (T_{a_{q−1}})_{i_{1},...,i_{q−1},h}.

Since T_{a_{q−1}} is constructed according to Equation (2), the only nonzero summand is the one with h = i_{1}. Therefore,

M_{i_{1},...,i_{q}} = (T_{a_{q}})_{i_{1},i_{2},...,i_{q}} · (T_{a_{1}})_{i_{1},i_{1},i_{3},...,i_{q}} ⋯ (T_{a_{q−1}})_{i_{1},...,i_{q−1},i_{1}}.

By Equation (6),

(T_{a_{q}})_{i_{1},i_{2},...,i_{q}} = (f_{J}(A_{q}))_{i_{1},i_{2},...,i_{q}} = (A_{q})_{P (i_{1},...,i_{q})}.

Moreover, for j = 1, …, q − 2,

(T_{a_{j}})_{i_{1},...,i_{j−1},i_{1},i_{j+1},...,i_{q}} = (T′_{a_{j}})_{i_{1},...,i_{j−1},i_{1},i_{j+1},...,i_{q−1}},  (7)

and

(T_{a_{q−1}})_{i_{1},...,i_{q−1},i_{1}} = (T′_{a_{q−1}})_{i_{1},...,i_{q−1}}  (8)

for the last factor in the product.

By the inductive hypothesis, N′ can be computed as ∘(T′_{q−1}, T′_{1}, …, T′_{q−2}), thus

N′_{i_{1},...,i_{q}} = ∑_{h=0}^{n−1}(T′_{a_{q−1}})_{h,i_{2},...,i_{q−1}} · (T′_{1})_{i_{1},h,i_{3},...,i_{q−1}} ⋯ (T_{a_{q−2}})_{i_{1},...,i_{q−2},h}.

With the same blow argument already introduced in Example 26, the unique surviving summand has h = i_{1}, so

N′_{i_{1},...,i_{q}} = (T′_{a_{q−1}})_{i_{1},...,i_{q−1}}(T′_{a_{1}})_{i_{1},i_{1},i_{3},...,i_{q−1}} ⋯ (T′_{a_{q−2}})_{i_{1},...,i_{q−2},i_{1}}.

Comparing with Equation (7) and Equation (8), we obtain

N′_{i_{1},...,i_{q}} = (T_{a_{q−1}})_{i_{1},...,i_{q−1},i_{1}} · (T_{a_{1}})_{i_{1},i_{1},i_{3},...,i_{q}} ⋯ (T_{a_{q−2}})_{i_{1},...,i_{q−1},i_{1}}.  (9)

Finally, from Equation (5) and Equation (9), we get

N_{i_{1},...,i_{q}} = N′_{i_{1},...,i_{d−1}}(A_{q})_{P (i_{1},...,i_{q})} =

= (T_{a_{q−1}})_{i_{1},...,i_{q−1},i_{1}} · (T_{a_{1}})_{i_{1},i_{1},i_{3},...,i_{q}} ⋯ (T_{a_{q−2}})_{i_{1},...,i_{q−1},i_{1}} · (T_{q})_{i_{1},i_{2},...,i_{q}} = M_{i_{1},...,i_{q}}.

The claim follows.

Example 27. Consider the binary SPN, whose graph is displayed in Figure 9, with the (unique) ordering (a_{1}, a_{2}, a_{3}, a_{4}, a_{5}). The activation tensors A_{1} at node a_{1}, A_{2} at node a_{2}, and so on, which depend on two parameters, are defined as follows:

A_{1} = (α, β),  A_{2} = A_{4} = (\begin{matrix}α & β \\ β & α \end{matrix}) ,  \begin{matrix}A_{3} = A_{5} = \\ β \\ β \\ α \\ α \\ α \\ β \\ β \\ α \end{matrix} .

\begin{matrix}a_{1} \\ a_{2} \\ a_{3} \\ a_{4} \\ a_{5} \end{matrix}

Figure 9: SPN with five nodes. Underlying graph of an SPN with nodes a_{1}, a_{2}, a_{3}, a_{4}, a_{5}. The source is a_{1} and the sink is a_{5}.

Then, the total tensor N is given by the BMP

N = ∘(T_{a_{5}}, T_{a_{1}}, T_{a_{2}}, T_{a_{3}}, T_{a_{4}}),

where T_{a_{1}}, T_{a_{2}}, T_{a_{3}}, T_{a_{4}}, T_{a_{5}} are the dimension-5 tensors constructed according to Procedure 22. One computes:

T_{a_{1}} = f_{{3,4,5}}(b(A_{1})) T_{a_{2}} = f_{{4,5}}(b(A_{2})), T_{a_{3}} = f_{{5}}(b(A_{3})),

T_{a_{4}} = b(f_{{1,2}}(A_{4})), T_{a_{5}} = f_{{1,3}}(A_{5}).

It follows that T_{a_{1}}, T_{a_{2}}, T_{a_{3}}, T_{a_{4}}, T_{a_{5}} are given by

\begin{matrix}(T_{a_{1}})_{0,0,0,0,0} = α, & (T_{a_{1}})_{0,0,0,0,1} = α, & (T_{a_{1}})_{0,0,0,1,0} = α, & (T_{a_{1}})_{0,0,0,1,1} = α, \\ (T_{a_{1}})_{0,0,1,0,0} = α, & (T_{a_{1}})_{0,0,1,0,1} = α, & (T_{a_{1}})_{0,0,1,1,0} = α, & (T_{a_{1}})_{0,0,1,1,1} = α, \\ T_{a_{1}})_{0,1,0,0,0} = 0, & (T_{a_{1}})_{0,1,0,0,1} = 0, & (T_{a_{1}})_{0,1,0,1,0} = 0, & (T_{a_{1}})_{0,1,0,1,1} = 0, \\ (T_{a_{1}})_{0,1,1,0,0} = 0, & (T_{a_{1}})_{0,1,1,0,1} = 0, & (T_{a_{1}})_{0,1,1,1,0} = 0, & (T_{a_{1}})_{0,1,1,1,1} = 0, \\ (T_{a_{1}})_{1,0,0,0,0} = 0, & (T_{a_{1}})_{1,0,0,0,1} = 0, & (T_{a_{1}})_{1,0,0,1,0} = 0, & (T_{a_{1}})_{1,0,0,1,1} = 0, \\ (T_{a_{1}})_{1,0,1,0,0} = 0, & (T_{a_{1}})_{1,0,1,0,1} = 0, & (T_{a_{1}})_{1,0,1,1,0} = 0, & (T_{a_{1}})_{1,0,1,1,1} = 0, \\ (T_{a_{1}})_{1,1,0,0,0} = β, & (T_{a_{1}})_{1,1,0,0,1} = β, & (T_{a_{1}})_{1,1,0,1,0} = β, & (T_{a_{1}})_{1,1,0,1,1} = β, \\ (T_{a_{1}})_{1,1,1,0,0} = β, & (T_{a_{1}})_{1,1,1,0,1} = β, & (T_{a_{1}})_{1,1,1,1,0} = β, & (T_{a_{1}})_{1,1,1,1,1} = β; \end{matrix}

\begin{matrix}(T_{a_{2}})_{0,0,0,0,0} = α, & (T_{a_{2}})_{0,0,0,0,1} = α, & (T_{a_{2}})_{0,0,0,1,0} = α, & (T_{a_{2}})_{0,0,0,1,1} = α, \\ (T_{a_{2}})_{0,0,1,0,0} = 0, & (T_{a_{2}})_{0,0,1,0,1} = 0, & (T_{a_{2}})_{0,0,1,1,0} = 0, & (T_{a_{2}})_{0,0,1,1,1} = 0, \\ (T_{a_{2}})_{0,1,0,0,0} = β, & (T_{a_{2}})_{0,1,0,0,1} = β, & (T_{a_{2}})_{0,1,0,1,0} = β, & (T_{a_{2}})_{0,1,0,1,1} = β, \\ (T_{a_{2}})_{0,1,1,0,0} = 0, & (T_{a_{2}})_{0,1,1,0,1} = 0, & (T_{a_{2}})_{0,1,1,1,0} = 0, & (T_{a_{2}})_{0,1,1,1,1} = 0, \\ (T_{a_{2}})_{1,0,0,0,0} = 0, & (T_{a_{2}})_{1,0,0,0,1} = 0, & (T_{a_{2}})_{1,0,0,1,0} = 0, & (T_{a_{2}})_{1,0,0,1,1} = 0, \\ (T_{a_{2}})_{1,0,1,0,0} = β, & (T_{a_{2}})_{1,0,1,0,1} = β, & (T_{a_{2}})_{1,0,1,1,0} = β, & (T_{a_{2}})_{1,0,1,1,1} = β, \\ (T_{a_{2}})_{1,1,0,0,0} = 0, & (T_{a_{2}})_{1,1,0,0,1} = 0, & (T_{a_{2}})_{1,1,0,1,0} = 0, & (T_{a_{2}})_{1,1,0,1,1} = 0, \\ (T_{a_{2}})_{1,1,1,0,0} = α, & (T_{a_{2}})_{1,1,1,0,1} = α, & (T_{a_{2}})_{1,1,1,1,0} = α, & (T_{a_{2}})_{1,1,1,1,1} = α; \end{matrix}

\begin{matrix}(T_{a_{3}})_{0,0,0,0,0} = α, & (T_{a_{3}})_{0,0,0,0,1} = α, & (T_{a_{3}})_{0,0,0,1,0} = 0, & (T_{a_{3}})_{0,0,0,1,1} = 0, \\ (T_{a_{3}})_{0,0,1,0,0} = β, & (T_{a_{3}})_{0,0,1,0,1} = β, & (T_{a_{3}})_{0,0,1,1,0} = 0, & (T_{a_{3}})_{0,0,1,1,1} = 0, \\ (T_{a_{3}})_{0,1,0,0,0} = β, & (T_{a_{3}})_{0,1,0,0,1} = β, & (T_{a_{3}})_{0,1,0,1,0} = 0, & (T_{a_{3}})_{0,1,0,1,1} = 0, \\ (T_{a_{3}})_{0,1,1,0,0} = α, & (T_{a_{3}})_{0,1,1,0,1} = α, & (T_{a_{3}})_{0,1,1,1,0} = 0, & (T_{a_{3}})_{0,1,1,1,1} = 0, \\ (T_{a_{3}})_{1,0,0,0,0} = 0, & (T_{a_{3}})_{1,0,0,0,1} = 0, & (T_{a_{3}})_{1,0,0,1,0} = β, & (T_{a_{3}})_{1,0,0,1,1} = β, \\ (T_{a_{3}})_{1,0,1,0,0} = 0, & (T_{a_{3}})_{1,0,1,0,1} = 0, & (T_{a_{3}})_{1,0,1,1,0} = α, & (T_{a_{3}})_{1,0,1,1,1} = α, \\ (T_{a_{3}})_{1,1,0,0,0} = 0, & (T_{a_{3}})_{1,1,0,0,1} = 0, & (T_{a_{3}})_{1,1,0,1,0} = β, & (T_{a_{3}})_{1,1,0,1,1} = β, \\ (T_{a_{3}})_{1,1,1,0,0} = 0, & (T_{a_{3}})_{1,1,1,0,1} = 0, & (T_{a_{3}})_{1,1,1,1,0} = α, & (T_{a_{3}})_{1,1,1,1,1} = α; \end{matrix}

\begin{matrix}(T_{a_{4}})_{0,0,0,0,0} = α, & (T_{a_{4}})_{0,0,0,0,1} = 0, & (T_{a_{4}})_{0,0,0,1,0} = β, & (T_{a_{4}})_{0,0,0,1,1} = 0, \\ (T_{a_{4}})_{0,0,1,0,0} = β, & (T_{a_{4}})_{0,0,1,0,1} = 0, & (T_{a_{4}})_{0,0,1,1,0} = α, & (T_{a_{4}})_{0,0,1,1,1} = 0, \\ (T_{a_{4}})_{0,1,0,0,0} = α, & (T_{a_{4}})_{0,1,0,0,1} = 0, & (T_{a_{4}})_{0,1,0,1,0} = β, & (T_{a_{4}})_{0,1,0,1,1} = 0, \\ (T_{a_{4}})_{0,1,1,0,0} = β, & (T_{a_{4}})_{0,1,1,0,1} = 0, & (T_{a_{4}})_{0,1,1,1,0} = α, & (T_{a_{4}})_{0,1,1,1,1} = 0, \\ (T_{a_{4}})_{1,0,0,0,0} = 0, & (T_{a_{4}})_{1,0,0,0,1} = α, & (T_{a_{4}})_{1,0,0,1,0} = 0, & (T_{a_{4}})_{1,0,0,1,1} = β, \\ (T_{a_{4}})_{1,0,1,0,0} = 0, & (T_{a_{4}})_{1,0,1,0,1} = β, & (T_{a_{4}})_{1,0,1,1,0} = 0, & (T_{a_{4}})_{1,0,1,1,1} = α, \\ (T_{a_{4}})_{1,1,0,0,0} = 0, & (T_{a_{4}})_{1,1,0,0,1} = α, & (T_{a_{4}})_{1,1,0,1,0} = 0, & (T_{a_{4}})_{1,1,0,1,1} = β, \\ (T_{a_{4}})_{1,1,1,0,0} = 0, & (T_{a_{4}})_{1,1,1,0,1} = β, & (T_{a_{4}})_{1,1,1,1,0} = 0, & (T_{a_{4}})_{1,1,1,1,1} = α; \end{matrix}

\begin{matrix}(T_{a_{5}})_{0,0,0,0,0} = α, & (T_{a_{5}})_{0,0,0,0,1} = β, & (T_{a_{5}})_{0,0,0,1,0} = β, & (T_{a_{5}})_{0,0,0,1,1} = α, \\ (T_{a_{5}})_{0,0,1,0,0} = α, & (T_{a_{5}})_{0,0,1,0,1} = β, & (T_{a_{5}})_{0,0,1,1,0} = β, & (T_{a_{5}})_{0,0,1,1,1} = α, \\ (T_{a_{5}})_{0,1,0,0,0} = β, & (T_{a_{5}})_{0,1,0,0,1} = α, & (T_{a_{5}})_{0,1,0,1,0} = β, & (T_{a_{5}})_{0,1,0,1,1} = α, \\ (T_{a_{5}})_{0,1,1,0,0} = β, & (T_{a_{5}})_{0,1,1,0,1} = α, & (T_{a_{5}})_{0,1,1,1,0} = β, & (T_{a_{5}})_{0,1,1,1,1} = α, \\ (T_{a_{5}})_{1,0,0,0,0} = α, & (T_{a_{5}})_{1,0,0,0,1} = β, & (T_{a_{5}})_{1,0,0,1,0} = β, & (T_{a_{5}})_{1,0,0,1,1} = α, \\ (T_{a_{5}})_{1,0,1,0,0} = α, & (T_{a_{5}})_{1,0,1,0,1} = β, & (T_{a_{5}})_{1,0,1,1,0} = β, & (T_{a_{5}})_{1,0,1,1,1} = α, \\ (T_{a_{5}})_{1,1,0,0,0} = β, & (T_{a_{5}})_{1,1,0,0,1} = α, & (T_{a_{5}})_{1,1,0,1,0} = β, & (T_{a_{5}})_{1,1,0,1,1} = α, \\ (T_{a_{5}})_{1,1,1,0,0} = β, & (T_{a_{5}})_{1,1,1,0,1} = α, & (T_{a_{5}})_{1,1,1,1,0} = β, & (T_{a_{5}})_{1,1,1,1,1} = α; \end{matrix}

and, by computing the BMP ∘(T_{a_{5}}, T_{a_{1}}, T_{a_{2}}, T_{a_{3}}, T_{a_{4}}), we obtain the correct evaluation of N, whose entries are

\begin{matrix}N_{0,0,0,0,0} = α^{5} & N_{0,0,0,0,1} = α^{4}β & N_{0,0,0,1,0} = α^{3}β^{2} & N_{0,0,0,1,1} = α^{4}β \\ N_{0,0,1,0,0} = α^{3}β^{2} & N_{0,0,1,0,1} = α^{2}β^{3} & N_{0,0,1,1,0} = α^{3}β^{2} & N_{0,0,1,1,1} = α^{4}β \\ N_{0,1,0,0,0} = α^{2}β^{3} & N_{0,1,0,0,1} = α^{3}β^{2} & N_{0,1,0,1,0} = αβ^{4} & N_{0,1,0,1,1} = α^{2}β^{3} \\ N_{0,1,1,0,0} = α^{2}β^{3} & N_{0,1,1,0,1} = α^{3}β^{2} & N_{0,1,1,1,0} = α^{3}β^{2} & N_{0,1,1,1,1} = α^{4}β \\ N_{1,0,0,0,0} = α^{2}β^{3} & N_{1,0,0,0,1} = αβ^{4} & N_{1,0,0,1,0} = β^{5} & N_{1,0,0,1,1} = αβ^{4} \\ N_{1,0,1,0,0} = α^{2}β^{3} & N_{1,0,1,0,1} = αβ^{4} & N_{1,0,1,1,0} = α^{2}β^{3} & N_{1,0,1,1,1} = α^{3}β^{2} \\ N_{1,1,0,0,0} = α^{2}β^{3} & N_{1,1,0,0,1} = α^{3}β^{2} & N_{1,1,0,1,0} = αβ^{4} & N_{1,1,0,1,1} = α^{2}β^{3} \\ N_{1,1,1,0,0} = α^{2}β^{3} & N_{1,1,1,0,1} = α^{3}β^{2} & N_{1,1,1,1,0} = α^{3}β^{2} & N_{1,1,1,1,1} = α^{4}β. \end{matrix}

Observe that, in the projective space of tensors of type 2 × 2 × 2 × 2 × 2, the tensors defined by N, when α, β vary, describe a rational normal curve of degree 5 (highly degenerate).

3.3. Software

A Python software has been implemented for computing the BMP of tensors of arbitrary dimension d, as in Definition 8, and for performing the procedure described in Procedure 22. Given an SPN, the software performs the blow and forget operations for the tensor of each node, computing the transformed tensors T_{a_{i}}. By Theorem 23, the BMP of these tensors yields the total tensor of the network. The only data required to run the code are the adjacency matrix of a DAG with a source and a sink, and the list of activation tensors assigned to the nodes (compatible with their number of parents); alternatively, random tensors can be generated according to the adjacency matrix of the DAG, for any number of nodes. All the Examples presented in this paper and BPMs for random networks up to 12 nodes can be computed in less than 1 second on a Macbook Pro with M1 Pro processor.

The software is open-source and freely available at: https://github.com/MarzialiS/BMP-Network, along with a notebook to run all the Examples presented in this work.

Acknowledgements

The authors want to warmly thank Luke Oeding, who introduced them to the early works of Bhattacharya and Mesner, Fulvio Gesmundo, and Edinah Gnang, for useful discussions on the subject of the paper. G.A.D. acknowledges the support provided by the European Union - NextGenerationEU, in the framework of the iNEST - Interconnected Nord-Est Innovation Ecosystem (iNEST ECS00000043 – CUP G93C22000610007) project and its CC5 Young Researchers initiative. The views and opinions expressed are solely those of the author and do not necessarily reflect those of the European Union, nor can the European Union be held responsible for him. In addition, G.A.D. would like to acknowledge INdAM–GNCS. L.C. is member of INdAM-GNSAGA.

References

[1] Prabir Bhattacharya, A new 3-D transform using a ternary product, IEEE transactions on signal processing 43 (1995), no. 12, 3081–3084.

[2] Cristiano Bocci, Luca Chiantini, et al., An introduction to algebraic statistics with tensors, Vol. 1, Springer, 2019.

[3] Reinhard Diestel, Graph theory, Springer (print edition); Reinhard Diestel (eBooks), 2024.

[4] Edinah K Gnang, A combinatorial approach to hypermatrix algebra, arXiv preprint arXiv:1403.3134 (2014).

[5] Edinah K Gnang and Yuval Filmus, On the spectra of hypermatrix direct sum and Kronecker products constructions, Linear Algebra and its Applications 519 (2017), 238–277.

[6] , On the Bhattacharya-Mesner rank of third order hypermatrices, Linear Algebra and its Applications 588 (2020), 391–418.

[7] Leslie Hogben, Handbook of linear algebra, CRC press, 2006.

[8] Joseph M Landsberg, Tensors: geometry and applications: geometry and applications, Vol. 128, American Mathematical Soc., 2011.

[9] Sara Marziali, Boolean operators and neural networks, ANNALI DELL’UNIVERSITA’ DI FERRARA 70 (2024/10/01), no. 4, 1767–1783.

[10] Dale M Mesner and Prabir Bhattacharya, Association schemes on triples and a ternary algebra, Journal of Combinatorial Theory, Series A 55 (1990), no. 2, 204– 234.

[11] , A ternary algebra arising from association schemes on triples, Journal of algebra 164 (1994), no. 3, 595–613.

[12] Fan Tian, Misha E Kilmer, Eric Miller, and Abani Patra, Tensor BM-Decomposition for Compression and Analysis of Spatio-Temporal Third-order Data, arXiv preprint arXiv:2306.09201 (2023).