Factor Graph Neural Networks

Zhen Zhang, Fan Wu, Wee Sun Lee

TL;DR

Standard Graph Neural Networks (GNNs) are limited to pairwise connections, but many real-world problems involve complex constraints among groups of variables. This paper introduces the Factor Graph Neural Network (FGNN), which leverages bipartite factor graphs to capture higher-order dependencies. The authors theoretically prove its equivalence to the Max-Product Belief Propagation algorithm and demonstrate state-of-the-art performance on tasks like error-correction decoding and human motion prediction.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) have become the go-to architecture for structured data like molecules and social networks. However, standard GNNs operate on simple graphs where edges connect exactly two nodes. This means they natively capture only pairwise dependencies.

In many real-world scenarios, dependencies are "higher-order." For example, in Low-Density Parity-Check (LDPC) codes used in telecommunications, a specific group of bits must sum to zero. In human motion, the movement of a hand is constrained by the elbow, shoulder, and spine simultaneously. Probabilistic Graphical Models (PGMs) handle this elegantly using "factor graphs"—bipartite graphs containing variable nodes and factor nodes (which represent multi-variable constraints). This paper bridges the gap between PGMs and deep learning by designing a neural network that natively operates on factor graphs, allowing it to learn and reason over higher-order dependencies end-to-end.

Methods

The authors propose the Factor Graph Neural Network (FGNN). Instead of passing messages directly between nodes, the FGNN uses a bipartite structure with two alternating modules:

Variable-to-Factor and Factor-to-Variable Modules
  1. Variable-to-Factor (VF): Passes information from variable nodes to the factor nodes they participate in.
  2. Factor-to-Variable (FV): Passes aggregated constraint information back to the variable nodes.

Both modules are built on the Message Passing Neural Network (MPNN) framework but utilize max-aggregation instead of sum-aggregation.

The core theoretical contribution of the paper is proving that an FGNN can exactly parameterize Max-Product Belief Propagation, a classic approximate inference algorithm used to find the most likely state in a PGM. Because higher-order potentials (the mathematical functions defining the constraints) can grow exponentially, the authors use a tensor decomposition trick. They prove that any potential can be represented as the maximum of a set of rank-1 tensors, which the FGNN can efficiently approximate and learn directly from data.

Datasets

The researchers evaluated the FGNN on three distinct types of datasets:

  • Synthetic PGMs: Four custom datasets consisting of 30-node chains with varying degrees of higher-order "budget" constraints.
  • LDPC Decoding: Simulated 48-bit signals encoded into 96-bit LDPC codes, transmitted through channels corrupted by both standard Gaussian noise and unexpected burst noise.
  • Human3.6M (H3.6M): A standard benchmark dataset for 3D human pose and motion prediction.

Key Insights

  • Theoretical Equivalence: FGNNs aren't just a heuristic architecture; they are theoretically proven to be at least as powerful as Max-Product Belief Propagation. This gives a rigorous mathematical foundation to their representational capacity.
  • Learning Beats Hand-Crafting: In traditional PGMs, inference algorithms like Max-Product often fail or get stuck in poor local minima when graphs have loops. FGNNs, however, jointly learn the latent variables and the inference algorithm tailored to the data distribution, allowing them to succeed where traditional solvers fail.
  • Robustness to the Unknown: In the LDPC decoding task, traditional decoders require the noise parameters to be known. FGNNs can learn a decoding scheme that is highly robust to unexpected, unmodeled burst noise.
  • Higher-Order Priors Matter: The success in human motion prediction proves that treating a skeleton as a set of pairwise bones is suboptimal. Grouping joints into higher-order factors provides a critical structural inductive bias that improves 3D spatial predictions.

Key Results

  • MAP Inference: On complex synthetic PGMs, FGNN achieved 89% to 93% agreement with exact MAP solutions. Standard MPNNs only achieved 71-82%, and traditional Max-Product failed entirely (~50-57%).
  • LDPC Decoding: FGNN outperformed standard MPNNs and traditional Commpy-Sum-Product decoders.
LDPC Decoding Performance

As shown above, the FGNN (red line) is particularly effective in high burst-noise environments (e.g., $\sigma_b = 3$ to $5$), proving its ability to learn robust error-correction strategies.

  • Human Motion Prediction: FGNN achieved state-of-the-art results for 3D joint position prediction. For example, in the "Walking" category at 560 milliseconds, FGNN achieved an error of 44.1mm, significantly beating the standard GNN baseline of 55.0mm.

Limitations and Future Work

The authors acknowledge that the size of a potential grows exponentially with the number of variables it depends on. If a constraint cannot be well-approximated by a moderate number of rank-1 tensors, the required size of the FGNN could explode.

Looking forward, the authors suggest that FGNNs open up new opportunities for injecting structural bias into deep learning. Future directions include applying this architecture to hypergraphs, dynamically assembling factor graphs based on input features, and utilizing typed/conditioned nodes and edges for complex relational reasoning.

Summary updated

Abstract

Most of the successful deep neural network architectures are structured, often consisting of elements like convolutional neural networks and gated recurrent neural networks. Recently, graph neural networks (GNNs) have been successfully applied to graph-structured data such as point cloud and molecular data. These networks often only consider pairwise dependencies, as they operate on a graph structure. We generalize the GNN into a factor graph neural network (FGNN) providing a simple way to incorporate dependencies among multiple variables. We show that FGNN is able to represent Max-Product belief propagation, an approximate inference method on probabilistic graphical models, providing a theoretical understanding on the capabilities of FGNN and related GNNs. Experiments on synthetic and real datasets demonstrate the potential of the proposed architecture.
BibTeX
@inproceedings{zhang2020factor,
  author = {Zhen Zhang and Fan Wu and Wee Sun Lee},
  title = {{Factor Graph Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=VjF2MV5XFW8},
}
Figure