Two Classes of Optimal Multi-Input Structures for Node Computations in Message Passing Algorithms

A graph, denoted as $G\triangleq G_{v}\cup G_{e}$, consists of a node set $G_{v}$ and an edge set $G_{e}$. Any element in $G_{e}$ is called a directed (resp. undirected) edge which is denoted by an ordered (resp. unordered) pair $(a,b)\in G_{v}\times G_{v}$. The term “ordered” (resp. “unordered”) implies that $(a,b)\neq(b,a)$ (resp. $(a,b)=(b,a)$). A graph $G$ is a directed (undirected) graph if and only if (iff) each element in $G_{e}$ is a directed (undirected) edge. When graphically represented, directed edges are depicted using arrows, whereas undirected edges are depicted using lines. A graph $G^{\prime}$ is called a subgraph of $G$ if $G^{\prime}\subseteq G$.

In a directed graph $G$, an edge $(a,b)$ is referred to as a leaving or outgoing edge of node $a$, and an entering or incoming edge of node $b$. In contrast, for an undirected graph $G$, the edge $(a,b)$ is simply described as an edge of $a$ and $b$. To describe the operations of removing or adding a node $a$ or an edge $(a,b)$ from/to a graph $G$, we utilize the notation of subtraction/addition (represented by $-/+$). Specifically, $G-a\triangleq G\setminus(\{a\}\cup\{(a_{1},a_{2})\in G:a_{1}=a~{}\text{or}~{}a_{2}=a\})$, $G+a\triangleq G\cup\{a\}$, $G-(a,b)\triangleq G\setminus\{(a,b)\}$, and $G+(a,b)\triangleq G\cup\{a,b\}\cup\{(a,b)\}$.

For any graph $G$ and node $a\in G$, define $d(a,G)$ as the degree of $a$ in $G$. If $G$ is an undirected graph, $d(a,G)$ is the number of edges connecting with $a$. If $G$ is a directed graph, $d(a,G)$ is the number of incoming edges of $a$. For any graph $G$ and $i\in\mathbb{Z}_{+}$, define $d_{i}(G)$ as the number of degree-$i$ nodes in $G$. For any graph $G$, define $\mathbf{q}\triangleq(q_{1},q_{2},...,q_{m-1})\in\mathbb{Z}_{+}^{m-1}$ as the degree vector of $G$, where for each $i\in[m-1]$, $q_{i}=d_{i+2}(G)$ if $G$ is undirected and $q_{i}=d_{i+1}(G)$ if $G$ is directed.

We call node sequence $P=(v_{0},v_{1},\ldots,v_{k})$ a path in $G$ iff $(v_{i-1},v_{i})\in G,\forall i\in[k]$, where $k$ is called the length of $P$. Moreover, $P$ is called a simple path iff $v_{i}\neq v_{j},\forall~{}0\leq i<j\leq k$. For any $a,b\in G$, we say that $a$ is reachable from $b$ if there exists a path from $b$ to $a$. The distance from $a$ to $b$ is defined as the length of the shortest path from $a$ to $b$. If no such path exists, the distance is regarded as $\infty$. We further call $P$ a cycle if $k\geq 2$, $v_{0}=v_{k}$, $(v_{0},v_{1})\neq(v_{1},v_{2})$, and $(v_{1},v_{2},\ldots,v_{k})$ is a simple path.

For any directed graph $G$, we call $G$ a directed acyclic graph (DAG) iff there exists no cycle in $G$. For any DAG $G$ and $a\in G$, define $E(a,G)\triangleq(\{b\in G:\text{$a$ is reachable from $b$}\},\{(b^{\prime},b^{\prime\prime})\in G:\text{$a$ is reachable from $b^{\prime\prime}$}\})$ as a subgraph of $G$. Moreover, we define $E(G)\triangleq\{E(a,G):a\in G\}$. An undirected graph is connected if every node is reachable from all other nodes.

A tree is defined as a connected, acyclic, undirected graph. Given any tree $T$ and any node $a\in T$, we call $a$ a leaf of $T$ if its degree $d(a,T)=1$. Otherwise, we call $a$ an internal node.

A rooted tree is a tree in which there is a unique node called the root of the tree. We consider a rooted tree $T$, with its root denoted by $r(T)$. The depth of any node $a\in T$ is defined as the distance between $a$ and $r(T)$. Additionally, for a non-negative integer $i$, denote the $i$-th level as the set of all the nodes with the depth $i$. The height of $T$ is determined by the greatest depth among all its nodes. For any edge $(a,b)\in T$, if the depth of $a$ is greater than the depth of $b$, then $b$ is designated as the parent of $a$, and conversely, $a$ is the child of $b$.

The directed variant of a rooted tree $T$, say $T^{\prime}$, is created by converting each undirected edge $(a,b)\in T$, where $a$ is a child of $b$, into a directed edge from $a$ to $b$ in $T^{\prime}$. We refer to $T^{\prime}$ as a directed rooted tree (DRT), with $T$ being its undirected counterpart. For any node $a\in T^{\prime}$, $E(a,T^{\prime})$ is called the subtree of $T^{\prime}$ rooted at $a$. For any $(a,b)\in T$, let $D(a,b,T)\triangleq E(a,T_{b})$, where $T_{b}$ is the result (a DRT) by making $T$ as a DRT with root $b$. Let $D(T)\triangleq\{D(a,b,T):(a,b)\in T\}$.

For any graph $G$, we call $G$ a labelled graph iff every node in $G$ is given a unique label (as a result, each edge is also given a unique label). Conversely, if not all nodes in $G$ are uniquely labelled, $G$ is termed a partially unlabelled graph.

Two labelled graphs $G$ and $G^{\prime}$ are considered identical, i.e., $G=G^{\prime}$, iff $G$ and $G^{\prime}$ have same labelled nodes and edges (and root for rooted trees). Meanwhile, two partially unlabelled graphs, $G$ and $G^{\prime}$, are deemed identical if there exists a labelling scheme for the unlabelled nodes in both $G$ and $G^{\prime}$ that renders them labelled and identical.

Two partially unlabelled graphs $G$ and $G^{\prime}$ are the same iff there exists a way to label all unlabelled nodes in $G$ and $G^{\prime}$ such that $G$ and $G^{\prime}$ become labelled and the identical. Graphs $G$ and $G^{\prime}$ are isomorphic if there is a way to reassign labels to all nodes in both graphs, resulting in identically labelled $G$ and $G^{\prime}$.

In this subsection, we propose a class of trees, called star trees, in Definition 5. Next, Construction 1 and Lemma 1 illustrate that, based on any star tree $T$, we can obtain a low complexity structure, denoted as $h(T)$, which is called a star-tree-based structure.

Denote $\mathcal{T}_{n}$ as the set of all $n$-input star trees. For example, Fig. 5 shows the only star tree in $\mathcal{T}_{3}$, and Fig. 6(a) shows a star tree in $\mathcal{T}_{7}$. In fact, we can obtain a structure based on any star tree. For instance, consider the star tree in Fig. 6(a). First, making $x_{1}$ as the root and changing undirected edges to directed ones can lead to the DRT in Fig. 6(b). Second, removing $x_{1}$ and labelling the new root as $y_{1}$ can result in the DRT in Fig. 6(c) which could be used for computing $y_{1}$ from $X\setminus\{x_{1}\}$. Third, proceed the above steps by replacing $x_{1}$ and $y_{1}$ with $x_{j}$ and $y_{j},\forall j\in[2,7]$, respectively, leading to the seven DRTs in Fig. 7. Finally, these DRTs can be united (under the union operation $\vee$) to the structure in Fig. 8. We formally describe the construction from star trees to structures in Construction 1, and use Lemma 1 to state the correctness of the construction.

All the structures derived from star trees via Construction 1 are called star-tree-based structures. For example, considering $n=7$ and the star tree in Fig. 6(a), the DRTs $D(a,x_{j},T),\forall j\in[n]$ correspond to the seven DRTs in Fig. 7, and the star-tree-based structure $h(T)$ corresponds to the structure in Fig. 8.

According to Lemma 1, Construction 1 is a one-to-one mapping from star trees to star-tree-based structures. As shown in Fig. 8, each computation node is either reachable to $y_{j}$ or reachable from $x_{j}$, for any $j\in[7]$. Noting that in any structure, a node reachable from $x_{j}$ can never be contained in the DRT rooted at $y_{j}$, the computation nodes in Fig. 8 have been contained in as many DRTs in Fig. 7 as possible, indicating that they are fully reused. In particular, it was proved in [18] that for $m=2$, the star-tree-based structures have the lowest complexity among all the binary-input structures. This implies that for $m>2$, star-tree-based structures are likely to have the near-lowest (and sometimes the lowest) complexity among all structures. We thus focus on star-tree-based structures in this section.

In this subsection, first, Lemma 2 illustrates that the complexity of a star-tree-based structure is totally determined by the degree vector of the corresponding star tree. Next, Lemma 3 establishes a necessary and sufficient condition between degree vectors and the existence of a star trees. Based on these preparations, we finally formulate Problem 1 and then solve it in Theorem 1, aiming to obtain complexity-optimal star-tree-based structures via optimizing degree vectors.

Recall that the degree vector of $T$ is $\mathbf{q}=(d_{3}(T),d_{4}(T),\ldots,d_{m+1}(T))$. Therefore, Lemma 2 indicates that $c(h(T))$ is fully determined by $\mathbf{q}$. We are interested in optimizing degree vectors to generate complexity-optimal star-tree-based structures. Since Construction 1 establishes a one-to-one mapping between star trees and star-tree-based structures, the remaining question is that what degree vectors can result in valid $n$-input star trees. The following lemma answers this question.

For any $n\geq 3$, there exists at least one degree vector $\mathbf{q}=(q_{1},q_{2},\ldots,q_{m-1})$ satisfying (2) and to generate star tree via Construction 2. Note that it may result in multiple star trees, since there are multiple feasible choices of $q_{i}$ $(1\leq i<m)$ from $\mathbf{q}$ in Steps 1 and 2. Combining with Lemma 1, $\mathbf{q}$ corresponds to multiple star-tree-based structures. Denote $\mathcal{S}^{\mathrm{star}}(\mathbf{q})$ as the set of all the star-tree-based structures derived from $\mathbf{q}$. Since the complexity of any structure in $\mathcal{S}^{\mathrm{star}}(\mathbf{q})$ is the same by Lemma 2, it suffices to optimize degree vectors to generate complexity-optimal star-tree-based structures. Specifically, define $C_{\min}^{\mathrm{star}}(n)\triangleq\min_{T\in\mathcal{T}_{n}}c(h(T))$ as the minimum complexity of star-tree-based structures with input size $n$. Computing $C_{\min}^{\mathrm{star}}(n)$ is equivalent to solving the following optimization problem.

The left problem is to solve Problem 1, which can be done in Algorithm 1. The following theorem illustrates the correctness and time complexity of Algorithm 1.

By Algorithm 1, we are able to determine the lowest complexity $C_{\min}^{\mathrm{star}}(n)$ of star-tree-based structures with input size $n$. Further by backtracking, we can obtain an (or all if needed) optimal degree vector $\mathbf{q}$ which leads to complexity-optimal star-tree-based structures $\mathcal{S}^{\mathrm{star}}(\mathbf{q})$. However, the structures in $\mathcal{S}^{\mathrm{star}}(\mathbf{q})$ may have different latency. We are interested in further obtaining the latency-optimal structures in $\mathcal{S}^{\mathrm{star}}(\mathbf{q})$ in the following subsection.

In this subsection, first, Lemma 4 defines the latency of star trees and shows that it can fully characterize the latency of the corresponding star-tree-based structures. Then, Lemma 5 illustrates how to compute the latency of star trees. Based on these preparations, we finally formulate Problem 2 and then solve it in Theorem 2, aiming to obtain the latency-optimal structures in $\mathcal{S}^{\mathrm{star}}(\mathbf{q})$ via minimizing the latency of star trees corresponding to a given degree vector $\mathbf{q}$.

As shown in Lemma 4, minimizing the latency of structures derived from the star trees with a given degree vector is equivalent to minimizing the latency of the star trees. The following lemma shows how to compute the latency of a star tree.

Lemma 5 indicates that, the minimum latency of star trees with degree vector $\mathbf{q}$ is equal to the minimum value of $l(D_{1})+l(D_{2})$, where $D_{1}$ and $D_{2}$ are two DRTs (respectively corresponding to $D(a,b,T)$ and $D(b,a,T)$ in Lemma 5) satisfy the following three conditions: (i) $l(D_{1})-l_{d(r(D_{1}),D_{1})}\leq l(D_{2})$, (ii) $l(D_{1})>l(D_{2})$, and (iii) $d_{i+1}(D_{1})+d_{i+1}(D_{2})=q_{i},\forall i\in[m-1]$, i.e., the summation of $D_{1}$ and $D_{2}$’s degree vectors equals $\mathbf{q}$. As a result, computing $L_{\min}^{\mathrm{star}}(\mathbf{q})\triangleq\min_{S\in\mathcal{S}^{\mathrm{star}}(\mathbf{q})}l(S)$, the minimum latency of the star-tree-based structures derived from degree vector $\mathbf{q}$, is equivalent to solving the following optimizing problem.

To this end, for any degree vector $\mathbf{u}$ and positive integer $t$, define $\tau(\mathbf{u},t)=\min_{D^{\prime}_{1},...,D^{\prime}_{t}}$ $\max\{l(D^{\prime}_{1}),...,l(D^{\prime}_{t})\}$, where $D^{\prime}_{1},...,D^{\prime}_{t}$ are DRTs and the summation of their degree vectors equals $\mathbf{u}$. Here, $\tau(\mathbf{u},t)$ returns the lowest latency of the substructures that have the degree vector $\mathbf{u}$ and consist of $t$ disjoint DRTs. It will be computed later in Algorithm 3. For any two degree vectors $\mathbf{u}$, $\mathbf{u}^{\prime}\in\mathbb{Z}_{+}^{m-1}$, we say $\mathbf{u}\preceq\mathbf{u}^{\prime}$ iff for each $i\in[m-1]$, $u_{i}\leq u_{i}^{\prime}$. Then, we can solve Problem 2 by Algorithm 2.