Tensor Network Message Passing

When studying interacting systems, computing their statistical properties is a fundamental problem in various fields such as physics, applied mathematics, and machine learning. However, this task can be quite challenging due to the exponential growth of the state space as the system size increases. Many standard methods have significant weaknesses. For instance, message-passing algorithms can be inaccurate and even fail to converge due to short loops, while tensor network methods can have exponential computational complexity in large graphs due to long loops. In this Letter, we propose a new method called “tensor network message passing.” This approach allows us to compute local observables like marginal probabilities and correlations by combining the strengths of tensor networks in contracting small subgraphs with many short loops and the strengths of message-passing methods in globally sparse graphs, thus addressing the crucial weaknesses of both approaches. Our algorithm is exact for systems that are globally treelike and locally dense-connected when the dense local graphs have a limited tree width. We have conducted numerical experiments on synthetic and real-world graphs to compute magnetizations of Ising models and spin glasses, and have demonstrated the superiority of our approach over standard belief propagation and the recently proposed loopy message-passing algorithm. In addition, we discuss the potential applications of our method in inference problems in networks, combinatorial optimization problems, and decoding problems in quantum error correction.

Figure 1

Pictorial illustration of BP (a), tensor network contraction (b), and TNMP (c) for computing the marginal probability of node $i$ in an Ising model on a graph. In (b), (c), and (d), circles and squares are tensors converted from the Ising model. The shaded area in each figure denotes the part of the graph that is involved in computing the marginal of $i$. In BP, it is computed using information from its direct neighbors; in exact tensor network contractions, it includes all tensors in the network; and in TNMP, it evolves a predefined neighborhood ${\mathcal{N}}_i$. Panel (d) illustrates the update of $p_{i\to {\mathcal{N}}_l}$ in TNMP by contracting tensors inside ${\mathcal{N}}_i\backslash {\mathcal{N}}_l$ and the cavity tensors (the purple ones).

Figure 2

Top: error of magnetizations $E=(1/n)\sqrt{{\sum }_{i=1}^n(M_i-M_i^{\text{exact}}{)}^2}$, given by various methods for a ferromagnetic Ising model on a synthetic graph (illustrated in the inset) generated using the model of [30]. The graph has $n=1000$ nodes and contains a random graph and cliques on top of it. The random graph has an average degree $d=2$, the cliques have a size ranging from 2 to 9, and the number of them is [36,12,6,3,2,1,1,1], respectively. The temperature of the model is fixed at $T=2.0$ and the external field $h=0.1$. $R$ in the $x$ axis is the minimum distance between all pairs of nodes on the boundary of the neighborhood in our method TNMP (see text) and denotes the maximum length of the path under consideration between the neighbors of a node in Cantwell and Newman’s method [16, 17]. The numbers labeled in the figure indicate maximum neighbor size ${\max }_i|{\mathcal{N}}_i|$ with a given $R$. The error bar of MCMC is 0.0008. Bottom: errors of magnetization obtained by various methods for a random-interaction and random-field spin glass model on the real-world network of bus power system [31] at a fixed temperature $T=2.0$. The coupling $J$ are chosen as $\pm 1$ with equal probability and the external field $h_i$ for node $i$ follows $h_i\sim N[0,(\pi /200)]$. The error bar of MCMC is 0.0022.