Belief propagation for finite networks using a symmetry-breaking source node

Seongmin Kim, Alec Kirkley · 2025

Read Belief propagation for finite networks using a symmetry-breaking source node by Seongmin Kim, Alec Kirkley (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-19231.txt.

Introduction

Seongmin Kim and Alec Kirkley improve belief propagation on finite networks. They fix one well-connected source node. That breaks the global symmetry. Belief propagation passes messages to estimate key values. On small, sparse networks its estimates are often poor. Few loops make the problem worse.

Holding one hub node fixed costs nothing extra. Yet accuracy jumps for two test models. Both percolation and Ising models improve. The gain is largest on tree-like networks. Real networks are finite, never infinite. Cheap gains like this are thus worth having in practice.

Catalog record

CREATORSeongmin Kim, Alec Kirkley
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-19231

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Belief propagation for finite networks using a symmetry-breaking source node Seongmin Kim, Alec Kirkley Abstract Belief Propagation (BP) is an efficient message-passing algorithm widely used for inference in graphical models and for solving various problems in statistical physics. However, BP often yields inaccurate estimates of order parameters and their susceptibilities in finite systems, particularly in sparse networks with few loops. Here, we show for both percolation and Ising models that fixing the state of a single well-connected “source” node to break global symmetry substantially improves inference accuracy and captures finite-size effects across a broad range of networks, especially tree-like ones, at no additional computational cost. Message passing enables efficient inference in probabilistic graphical models of complex systems Pearl1988Probabilistic ; Wainwright2007Graphical ; Koller2010Probabilistic . This approach has led to advances across diverse fields, including machine learning Kschischang2001Factor ; Jordan2004Graphical ; Alpaydin2010Introduction , epidemiology Karrer2010Message ; Altarelli2014Bayesian , social network analysis Hastings2006Community ; Decelle2011Inference ; Nguyen2013Budgeted ; Pei2020Influencer , and statistical physics Nishimori2001Statistical ; Zdeborova2016Statistical ; Mezard2009Information . Central to message passing is Belief Propagation (BP), also known as the cavity method, which efficiently computes marginal probabilities by decomposing global inference problems as the exchange of local messages between nodes and their neighbors. BP is exact on acyclic (tree) networks and often provides good approximations on cyclic (loopy) networks that are locally tree-like Murphy1999Loopy ; Mezard2009Information . In statistical physics, the application of BP to phase transition models, such as percolation Karrer2014Percolation ; Allard2019Accuracy ; Cantwell2019Message ; Cantwell2023Heterogeneous ; Mann2023Belief ; Newman2023Message and the Ising model Mooij2005Properties ; Dorogovtsev2008Critical ; Mezard2009Information ; Yoon2011Beliefpropagation ; Kirkley2021Belief ; Newman2023Message , has yielded highly accurate predictions in many large real-world networks. However, this narrative of success holds a profound exception: BP’s ability to describe phase transitions catastrophically breaks down on the very structures where it is theoretically exact—tree networks—creating a paradox Allard2019Accuracy . This failure persists on almost-trees , networks that are only slightly more connected. This paradox arises because the system is symmetric and finite, and thus lacks true spontaneous symmetry breaking (SSB) in theory Dorogovtsev2005Correlations ; Fraser2016Spontaneous . Although finite systems may appear to exhibit SSB and nontrivial order parameters, these are practical measurements rather than quantities defined in the thermodynamic limit. For example, percolation strength refers to the fractional size of the infinite cluster, which exists only in infinitely large systems Stauffer1994Introduction ; similarly, the average magnetization in a finite spin system vanishes if measured over an infinite time as thermal fluctuations restore symmetry Newman1999Monte . Thus, theoretical order parameters are zero in finite systems. BP is indeed exact on trees and correctly predicts the absence of SSB Allard2019Accuracy . However, this theoretical consistency on trees makes BP incompatible with practical metrics used in finite systems, such as the fraction of the largest cluster in percolation or the absolute magnetization in the Ising model. This discrepancy highlights the need for a modified BP approach to accurately infer these practical metrics in finite systems. Ref. Allard2019Accuracy partially addressed this “tree-like network catastrophe” by adding a clique to the tree to induce a nontrivial solution, but the resulting accuracy remains poor. Here, we introduce the Source-Node BP (SNBP) method, a simple modification to the BP framework that explicitly breaks system symmetry by designating a single source node. This enables BP to accurately approximate order parameters and susceptibilities while maintaining computational efficiency. We show that SNBP significantly reduces finite-size errors across various networks, especially tree-like ones, and closely matches ground-truth results from Monte Carlo (MC) simulations. SNBP also outperforms conventional BP and the naive mean-field approximation (MFA) in many real-world networks, offering a practical inference method for finite systems with global symmetries. We demonstrate our framework on two canonical phase transition models, bond percolation and the Ising model, defined on an undirected graph \mathcal{G}=(\mathcal{V},\mathcal{E}) with N nodes and M edges. Bond percolation —Each bond (i,j)\in\mathcal{E} is independently occupied with probability p . In the large- N limit, the model exhibits a phase transition at a critical probability p_{c} : for p<p_{c} , only finite clusters exist, while for p>p_{c} , an infinite cluster spans a nonzero fraction of the network. The theoretical order parameter (percolation strength) is the probability P_{\infty} that a randomly chosen node belongs to the infinite cluster, which is strictly zero in any finite system. In practice, for a finite graph, we measure the practical order parameter as the fractional size of the largest cluster, S_{1}={|\mathcal{C}_{\mathrm{max}}|}/{N} , where |\mathcal{C}_{\mathrm{max}}| is the number of nodes in the largest cluster, \mathcal{C}_{\mathrm{max}} Stauffer1994Introduction . In the large- N limit, S_{1}\to P_{\infty} . The theoretical susceptibility \chi_{\mathrm{true}}=\sum_{|\mathcal{C}|<\infty}|\mathcal{C}|^{2}/N measures the mean finite cluster size, where |\mathcal{C}| is the size of cluster \mathcal{C} . In finite systems, the infinite cluster is absent, and the direct calculation of \chi_{\mathrm{true}} yields no peak. Therefore, the practical susceptibility is defined by excluding the largest cluster, treating it as the infinite cluster: \chi_{\mathrm{practical}}=\sum_{\mathcal{C}\neq\mathcal{C}_{\mathrm{max}}}|\mathcal{C}|^{2}/N Lee1996Universal . Ising model —Each node i\in\mathcal{V} carries a spin \sigma_{i}=\pm 1 . In zero field, the Hamiltonian is \mathcal{H}(\bm{\sigma})=-\sum_{(i,j)\in\mathcal{E}}\sigma_{i}\sigma_{j} . The theoretical order parameter is the average magnetization, m\equiv\sum_{i=1}^{N}\sigma_{i}/N . In the large- N limit, the system exhibits SSB below a critical temperature T_{c} , and the equilibrium magnetization \langle m\rangle becomes nonzero. However, for any finite system, thermal fluctuations cause global spin flips, restoring the symmetry and ensuring \langle m\rangle=0 at all temperatures. Therefore, the absolute magnetization, \langle|m|\rangle , is used as the practical order parameter in finite systems; it is nonvanishing for T<T_{\mathrm{c}} and converges to |\langle m\rangle| as N\to\infty Newman1999Monte . The magnetic susceptibility for each order parameter is given by: \chi_{\mathrm{true}}=\beta N\left(\langle m^{2}\rangle-\langle m\rangle^{2}\right) , and \chi_{\mathrm{practical}}=\beta N\left(\langle m^{2}\rangle-\langle|m|\rangle^{2}\right) , where \beta\equiv 1/T Landau2014Guide . In finite systems, \langle m\rangle=0 , so \chi_{\mathrm{true}} simplifies to \beta N\langle m^{2}\rangle . We introduce the SNBP framework for these two models. SNBP breaks global symmetry by clamping the state of a designated source node x throughout BP iterations, assuming x is always connected to the infinite cluster in percolation or has a fixed spin direction (e.g., positive) in the Ising model. The marginal probability of interest for each system is then the probability that a node is connected to x (percolation) or has a spin aligned with \sigma_{x} (Ising). Consequently, the order parameters become the fraction of nodes in x ’s cluster (percolation) or magnetization aligned with \sigma_{x} (Ising). The source node x can be selected arbitrarily but different choices provide different accuracy improvements. A simple heuristic that works well in practice is to select the highest-degree node as x , since it often belongs to the largest cluster or aligns with the dominant magnetization. This facilitates reliable approximations to practical order parameters in finite systems. Algorithmically, SNBP is distinguished from conventional BP by the inclusion of Kronecker delta terms that enforce a fixed state on the source node. Removing these terms recovers the conventional BP equations (see Supplemental Material for details). Throughout, we denote by \mathcal{N}_{i} the set of neighbors of node i , and by \mathcal{N}_{j}\setminus i the set of neighbors of j excluding i . The cluster containing the source node x is denoted by \mathcal{C}(x) . SNBP for percolation —We derive the SNBP equations by extending conventional BP for percolation Karrer2014Percolation ; Allard2019Accuracy

Read the complete text