PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Enhanced Belief Propagation on Factor Graphs

Victor Garcia Satorras, Max Welling

arXiv:2003.01998v5cs.LGstat.ML

TL;DR

BP can produce suboptimal estimates when the graphical model is misspecified or loopy. The paper extends GNNs to factor graphs and uses them to refine BP messages; on LDPC decoding, the hybrid matches LDPC closely on Gaussian channels and outperforms it on bursty channels.

  • Problem

    BP may give suboptimal estimates when the data-generating process is only approximated or the factor graph contains loops.

    Source: §1 · p. 1

  • Method

    The paper extends GNNs to factor graphs and combines an FG-GNN with BP, using the GNN to refine BP messages during inference.

    Source: §4.1 · p. 4, §4.2 · p. 5

  • Results

    The hybrid method closely matches LDPC performance on Gaussian channels and outperforms it when noise is bursty.

    Source: §1 · p. 2

  • Takeaways & Limitations

    For LDPC decoding, the hybrid combines BP's prior structure with learned adaptation and is more robust than LDPC when bursty interference is present.

    Source: §5.1 · p. 8

    LDPC training uses transmitted ground-truth bits, which are assumed known to the receiver during training.

    Source: §4.3 · p. 5

Abstract

from arXiv · show

A graphical model is a structured representation of locally dependent random variables. A traditional method to reason over these random variables is to perform inference using belief propagation. When provided with the true data generating process, belief propagation can infer the optimal posterior probability estimates in tree structured factor graphs. However, in many cases we may only have access to a poor approximation of the data generating process, or we may face loops in the factor graph, leading to suboptimal estimates. In this work we first extend graph neural networks to factor graphs (FG-GNN). We then propose a new hybrid model that runs conjointly a FG-GNN with belief propagation. The FG-GNN receives as input messages from belief propagation at every inference iteration and outputs a corrected version of them. As a result, we obtain a more accurate algorithm that combines the benefits of both belief propagation and graph neural networks. We apply our ideas to error correction decoding tasks, and we show that our algorithm can outperform belief propagation for LDPC codes on bursty channels.

1 Introduction

Belief propagation can be suboptimal when the graphical model is approximate or loopy. The paper combines BP with a factor-graph GNN and reports stronger decoding performance than LDPC on bursty noise.

1 Introduction

  • BP is optimal on non-loopy graphs when the true data-generating process is known, but model mismatch and loops can yield suboptimal estimates or non-convergence.The paper identifies these as limitations motivating its hybrid method.Source: §1 · p. 1
  • The hybrid model feeds BP messages to a GNN at every inference iteration, which returns refined messages to BP.With labeled data, it outperforms BP or GNNs alone when BP is not guaranteed to obtain optimal marginals.Source: §1 · p. 1
  • LDPC is a successful error-correction application of BP on a sparse, loopy bipartite graph, and performs near the Shannon limit on Gaussian channels.LDPC is used in Wi-Fi and has been adopted for 5G.Source: §1 · pp. 1–2
  • For LDPC decoding, the hybrid method matches LDPC closely on Gaussian channels and outperforms it on bursty noise channels.The paper frames bursty noise as a deviation from the Gaussian-channel assumption.Source: §1 · p. 2
  • The paper extends GNN equations to factor graphs, introduces Neural Enhanced Belief Propagation, and reports improved Bit Error Rate on a non-Gaussian bursty channel.NEBP refines BP messages using the factor-graph GNN.Source: §1 · p. 2

2 Background

The background introduces factor graphs as a representation of graphical models, BP as message passing over them, and LDPC decoding as a BP inference task on a code-specific factor graph.

2.1 Factor Graphs

  • A factor graph is a bipartite representation linking factors to variables, with the joint distribution expressed as a normalized product of factors.The normalization constant is Z.Source: §2.1 · p. 2

2.2 Belief Propagation

  • BP passes real-valued messages along factor-graph edges to infer marginals by locally marginalizing variables.Variable-to-factor messages combine incoming messages from other neighboring factors; factor-to-variable messages combine a factor with incoming messages and marginalize other variables.Source: §2.2 · p. 2
  • BP initializes messages uniformly, recursively applies both message updates until convergence, and estimates marginals by multiplying incoming factor messages.The paper illustrates these messages on a factor graph, with squares for factors and circles for variables.Source: §2.2 · p. 2

2.3 LDPC codes

  • An LDPC code uses a sparse parity-check matrix H to constrain codewords by Hx = 0, with rows representing factors and columns representing transmitted-bit variables.For a linear code (n, k), the graph has n variables and n − k factors.Source: §2.3 · p. 2
  • LDPC decoding represents the codeword prior and received-signal likelihood as factors, then runs loopy BP on their associated factor graph to infer the transmitted codeword.The received codeword is modeled with independent noise across bits.Source: §2.3 · p. 3

3 Related Work

Related work spans neural methods for graphical inference and GNNs on factor graphs. This paper distinguishes its approach as a hybrid that refines BP messages with a GNN.

3 Related Work

  • Unlike prior GNN inference work limited to pairwise factor graphs and Kalman filtering, this work applies a GNN to arbitrary factor graphs and hybridizes it with BP.The paper contrasts this hybrid with fully learned inference methods, including Recurrent Inference Machines and Iterative Amortized Inference.Source: §3 · p. 3
  • The paper connects its method to meta-learning because it learns a more flexible algorithm on top of an existing one.It also relates the sparse factor graph to prior knowledge encoded for the task.Source: §3 · p. 3
  • Prior approaches include trainable graphical-model factors, BP on learned graphical representations, and CNN–CRF combinations; this work adapts GNN equations to factor graphs as a building block for NEBP.The paper notes that factors with more than two variables make direct treatment as GNN edges less straightforward.Source: §3 · p. 3
  • Unlike methods estimating marginals with GNNs or learning edge weights for high-density parity-check codes, this work combines GNNs and BP for low-density parity-check decoding.Its learned messages refine BP messages without being constrained to BP's message-passing scheme.Source: §3 · p. 3

4 Method

The method extends GNN message passing to factor graphs of arbitrary factor arity, then couples this FG-GNN with BP so learned refinements update BP messages at each inference iteration.

4.1 Graph Neural Network for Factor Graphs

  • FG-GNN supports factors with arbitrary numbers of variables by representing factor and variable nodes separately, using typed edge and node updates, and treating singleton factors as variable attributes.The bipartite representation makes interactions pairwise between factor-nodes and variable-nodes.Source: §4.1 · pp. 4–5

4.2 Neural Enhanced Belief Propagation

  • NEBP alternates BP with two FG-GNN iterations that refine BP messages, then estimates marginals from the refined messages after N iterations.The FG-GNN receives BP messages as attributes; the final marginal estimate uses the product of incoming factor-to-variable messages.Source: §4.2 · p. 5

4.3 Training and Loss

  • Training back-propagates through the multi-layer estimation model to update FG-GNN weights, using binary cross entropy on estimated marginals and known ground truths.The number of training iterations is chosen by cross-validation.Source: §4.3 · p. 5
  • The regularization term is the mean of fu outputs and encourages NEBP to behave more like BP; setting fu outputs to zero makes the hybrid equivalent to BP.The scalar fs output only changes message norms, which BP normalizes at every iteration.Source: §4.3 · p. 5

5 Experiments

The experiments evaluate BP, FG-GNN, and NEBP on LDPC decoding with bursty noise and inference in a mismatched Ising model. NEBP is robust to bursty-channel deviations, while the Ising results show that the best method depends on the degree of mismatch.

5 Experiments

  • Across both tasks, FG-GNN and NEBP use learned message-passing components, with NEBP combining BP and FG-GNN messages.The experiments use two-layer MLPs for edge operations and two-layer MLPs followed by a GRU for node updates.Source: §5 · p. 6

5.1 Low Density Parity Check codes

  • The LDPC experiment transmits 96-bit codewords through a bursty channel, with burst noise added at probability ρ=0.05 and SNR supplied for each frame.The dataset uses SNR values 0–4 and samples σ_b uniformly from [0, 5]; LDPC-bursty is included as a baseline that accounts for burst-noise variance.Source: §5.1 · pp. 6–7
  • NEBP achieves the best performance across burst-noise values, stays competitive with LDPC for AWGN, and is more robust as burst variance increases.At fixed SNR=3, its performance decreases less than LDPC and LDPC-bursty as σ_b grows.Source: §5.1 · pp. 7–8

5.2 Ising model

  • The Ising experiment uses a 16-variable squared lattice with hidden soft interactions, and compares methods including damped BP to reduce cyclic information.Damping improved BP in this experiment, unlike the LDPC experiment, whose sparse graphs minimize cyclic information.Source: §5.2 · p. 8
  • For the Ising model, damped BP performs best at u=0, but FG-GNN performs best at u=0.8, where BP messages are no longer beneficial; NEBP remains close.NEBP has a significant margin over BP and FG-GNN at u=0.Source: §5.2 · p. 8

6 Conclusions

The paper presents a hybrid inference method that combines belief propagation with a graph neural network designed for factor graphs. On LDPC decoding with bursty noise, the neural enhancement improves performance relative to both LDPC and FG-GNN as burst variance grows.

6 Conclusions

  • The proposed hybrid inference method runs BP jointly with a factor-graph GNN, combining graphical-model prior knowledge with parameters learned from labeled data.The FG-GNN is trained on a representative distribution of channels rather than a single channel, which the authors describe as meta-learning.Source: §6 · p. 9
  • On realistic bursty-noise LDPC decoding, neural enhancement improves performance relative to both LDPC and FG-GNN as burst variance increases.Source: §6 · p. 9
  • The method is intended for cases where the data-generating process is not fully known, allowing BP's graphical-model prior to be combined with learned parameters.Source: §6 · p. 9

Related papers

Loading 2003.01998v5…