Belief propagation for networks with loops: The neighborhoods-intersections-based method

• URL: http://arxiv.org/abs/2506.13791v1
• Date: Wed, 11 Jun 2025 13:01:29 GMT
• Title: Belief propagation for networks with loops: The neighborhoods-intersections-based method
• Authors: Pedro Hack,
• Abstract summary: We introduce a new generalized BP scheme, the NIB-method, which only spends computational resources provided they are needed to account for correlations in the network.<n>We show that, given a network with only short loops, the NIB-method is exact and optimal, and we characterize its time complexity reduction with respect to the KCN-method.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In order to diminish the damaging effect of loops on belief propagation (BP), the first explicit version of generalized BP for networks, the KCN-method, was recently introduced. Despite its success, the KCN-method spends computational resources inefficiently. Such inefficiencies can quickly turn the exact application of the method unfeasible, since its time complexity increases exponentially with them. This affects for instance tree networks, for which, despite not offering any accuracy advantage with respect to BP, the time complexity of the KCN-method grows exponentially with the nodes' degree. To avoid these issues, we introduce here a new generalized BP scheme, the NIB-method, which only spends computational resources provided they are needed in order to account for correlations in the network. In fact, we show that, given a network with only short loops, the NIB-method is exact and optimal, and we characterize its time complexity reduction with respect to the KCN-method. If long loops are also present, both methods become approximate. In this scenario, we discuss the relation between the methods and we show how to interpolate between them, obtaining a richer family of generalized BP algorithms that trade accuracy for complexity. Lastly, we find a good agreement between the (approximate) KCN and NIB methods when computing the partition function for two artificial networks.

Related papers

• Gradient-Free Training of Recurrent Neural Networks using Random Perturbations [1.1742364055094265]
  Recurrent neural networks (RNNs) hold immense potential for computations due to their Turing completeness and sequential processing capabilities. Backpropagation through time (BPTT), the prevailing method, extends the backpropagation algorithm by unrolling the RNN over time. BPTT suffers from significant drawbacks, including the need to interleave forward and backward phases and store exact gradient information. We present a new approach to perturbation-based learning in RNNs whose performance is competitive with BPTT.
  arXiv  Detail & Related papers  (2024-05-14T21:15:29Z)
• The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
  We propose a new learning framework for neural networks, namely Cascaded Forward (CaFo) algorithm, which does not rely on BP optimization as that in FF. Unlike FF, our framework directly outputs label distributions at each cascaded block, which does not require generation of additional negative samples. In our framework each block can be trained independently, so it can be easily deployed into parallel acceleration systems.
  arXiv  Detail & Related papers  (2023-03-17T02:01:11Z)
• A Taxonomy of Recurrent Learning Rules [1.4186974630564675]
  Backpropagation through time (BPTT) is the de facto standard for training recurrent neural networks (RNNs) E-prop was proposed as a causal, local, and efficient practical alternative to these algorithms. We derive RTRL from BPTT using a detailed notation bringing intuition and clarification to how they are connected.
  arXiv  Detail & Related papers  (2022-07-23T07:03:42Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  The critical node problem (CNP) aims to find a set of critical nodes from a network whose deletion maximally degrades the pairwise connectivity of the residual network. This work proposes a feature importance-aware graph attention network for node representation. It combines it with dueling double deep Q-network to create an end-to-end algorithm to solve CNP for the first time.
  arXiv  Detail & Related papers  (2021-12-03T14:23:05Z)
• Manifold Regularized Dynamic Network Pruning [102.24146031250034]
  This paper proposes a new paradigm that dynamically removes redundant filters by embedding the manifold information of all instances into the space of pruned networks. The effectiveness of the proposed method is verified on several benchmarks, which shows better performance in terms of both accuracy and computational cost.
  arXiv  Detail & Related papers  (2021-03-10T03:59:03Z)
• Predictive Coding Can Do Exact Backpropagation on Convolutional and Recurrent Neural Networks [40.51949948934705]
  Predictive coding networks (PCNs) are an influential model for information processing in the brain. BP is commonly regarded to be the most successful learning method in modern machine learning. We show that a biologically plausible algorithm is able to exactly replicate the accuracy of BP on complex architectures.
  arXiv  Detail & Related papers  (2021-03-05T14:57:01Z)
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks [56.084798078072396]
  We take a step towards closing the gap between theory and practice by significantly improving the known theoretical bounds on both the network width and the convergence time. We show that convergence to a global minimum is guaranteed for networks with quadratic widths in the sample size and linear in their depth at a time logarithmic in both. Our analysis and convergence bounds are derived via the construction of a surrogate network with fixed activation patterns that can be transformed at any time to an equivalent ReLU network of a reasonable size.
  arXiv  Detail & Related papers  (2021-01-12T00:40:45Z)
• Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers [112.23981192818721]
  We propose to use backward mode linear relaxation based analysis (LiRPA) to replace Linear Programming (LP) during the BaB process. Unlike LP, LiRPA when applied naively can produce much weaker bounds and even cannot check certain conflicts of sub-domains during splitting. We demonstrate an order of magnitude speedup compared to existing LP-based approaches.
  arXiv  Detail & Related papers  (2020-11-27T16:42:12Z)
• Learning Sparse Filters in Deep Convolutional Neural Networks with a l1/l2 Pseudo-Norm [5.3791844634527495]
  Deep neural networks (DNNs) have proven to be efficient for numerous tasks, but come at a high memory and computation cost. Recent research has shown that their structure can be more compact without compromising their performance. We present a sparsity-inducing regularization term based on the ratio l1/l2 pseudo-norm defined on the filter coefficients.
  arXiv  Detail & Related papers  (2020-07-20T11:56:12Z)
• Belief Propagation Neural Networks [103.97004780313105]
  We introduce belief propagation neural networks (BPNNs) BPNNs operate on factor graphs and generalize Belief propagation (BP) We show that BPNNs converges 1.7x faster on Ising models while providing tighter bounds. On challenging model counting problems, BPNNs compute estimates 100's of times faster than state-of-the-art handcrafted methods.
  arXiv  Detail & Related papers  (2020-07-01T07:39:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.