Graph Neural Network Decoder

The GNN decoder directly maps the parity-check matrix of a linear block code onto a bipartite graph structure. Variable nodes represent transmitted bits, while check nodes represent parity constraints. This graph becomes the neural network's compute graph, where each node maintains a hidden state vector that is iteratively updated through learned message passing. Unlike standard belief propagation, which uses fixed statistical formulas, the GNN learns optimal update functions from data, allowing it to overcome short cycles and trapping sets that degrade traditional decoders.

In each decoding iteration, messages flow from variable nodes to check nodes and back, but the aggregation and transformation functions are parameterized by multi-layer perceptrons (MLPs) or gated recurrent units (GRUs). The neural message function learns to weigh incoming information based on reliability, effectively suppressing misleading messages from short cycles. Key operations include:

• Message computation: Neural network transforms concatenated node and edge features
• Aggregation: Learned weighted sum or attention-based pooling of incoming messages
• Node update: GRU or residual update to the hidden state This learned schedule converges in fewer iterations than standard belief propagation.

A critical architectural property of GNN decoders is permutation equivariance—the output ordering respects any permutation of the input variable nodes. This is enforced by sharing the same neural network weights across all nodes of the same type (variable or check), making the decoder inherently symmetric with respect to the transmitted codeword. This weight sharing dramatically reduces the parameter count and ensures the decoder generalizes across all bit positions without memorizing specific code indices. The property is mathematically guaranteed by the graph convolution operation, which treats nodes identically based on their structural role.

GNN decoders are trained end-to-end using a syndrome-based loss function that measures how well the decoded codeword satisfies the parity-check equations. The loss combines:

• Binary cross-entropy between transmitted and decoded bits
• Syndrome loss penalizing non-zero parity checks
• Regularization on the message magnitudes to prevent overconfidence Training uses teacher forcing where the true transmitted codeword is known, and gradients flow through all message-passing iterations via backpropagation through time (BPTT). The model learns to correct error patterns specific to the target channel, such as burst errors or correlated noise.

A hypernetwork architecture enables a single GNN decoder to adapt to multiple different linear block codes without retraining. The hypernetwork takes the parity-check matrix as input and generates the weights for the main GNN decoder's message functions. This allows the decoder to dynamically switch between codes—such as different LDPC code rates or block lengths—based on channel conditions. The hypernetwork learns a mapping from the code structure to optimal decoding parameters, effectively encoding the relationship between the parity-check matrix sparsity pattern and the required message-passing behavior.

For short block codes where maximum likelihood decoding is computationally feasible, GNN decoders can be trained using active learning to focus on the most challenging error patterns. The training process alternates between:

• Decoding batches of noisy codewords
• Identifying codewords where the GNN fails but ML decoding succeeds
• Augmenting the training set with these hard negative examples This curriculum learning approach ensures the GNN learns to resolve error floors and near-codeword confusions that plague traditional iterative decoders, achieving near-ML performance with significantly lower computational complexity than exhaustive search.

The foundational bipartite graph structure that a GNN decoder operates on. Variable nodes represent transmitted bits, while check nodes represent parity constraints. Edges connect a variable node to a check node if that bit participates in the corresponding parity equation. This sparse graphical model encodes the entire algebraic structure of a linear block code, such as LDPC or polar codes, and serves as the input topology for message-passing neural networks.

A learned generalization of the classical belief propagation (BP) algorithm where graph neural networks replace hand-crafted message update functions. Instead of fixed sum-product or min-sum rules, neural message functions are parameterized by multilayer perceptrons or gated recurrent units that learn optimal message transformations from data. This overcomes BP's well-known shortcomings on graphs with short cycles by learning to compensate for loopy message correlations.

An extension of GNN decoding that models higher-order parity-check constraints as hyperedges connecting more than two nodes. Rather than decomposing a degree-d check into pairwise factor nodes, hypergraph networks process all incident variable nodes jointly using permutation-invariant aggregation functions. This preserves the natural symmetry of the parity constraint and often yields faster convergence with fewer message-passing iterations.

A sequential decoding architecture where the GNN predicts one bit at a time, conditioning each prediction on previously decoded bits. After each bit decision, the graph structure is updated to reflect the reduced uncertainty, and the node embeddings are recomputed. This progressive codeword reconstruction approach allows the decoder to exploit structured dependencies and is particularly effective for short block codes where maximum-likelihood decoding is computationally prohibitive.

A technique where the GNN learns to assign attention weights or scalar multipliers to each edge in the Tanner graph, effectively learning which message pathways are most reliable. In classical BP, all edges are treated uniformly, but real-world channels introduce asymmetric reliabilities. Learned edge weights allow the decoder to attenuate messages from unreliable variable nodes and amplify those from high-confidence regions, significantly improving decoding performance on fading channels.

A family of codes where the parity-check matrix itself is co-designed with the GNN decoder through differentiable code search. The binary or real-valued parity-check matrix is treated as a trainable parameter, optimized end-to-end with the decoder to minimize bit error rate. This produces codes that are structurally tailored to the inductive biases of graph neural networks, often outperforming human-designed codes of equivalent rate and length.