Factor Graph Grammars (FGGs) introduce a novel formalism enabling researchers to define probability models with dynamic, repeating, or even infinite structures—such as those frequently encountered in natural language processing (NLP). By applying graph grammar theory to factor graphs, this framework allows for exact and tractable inference on complex models without the need to manually "unroll" them into massive, fixed structures.
The Problem with Static Graphs
In probabilistic modeling, factor graphs are a standard tool for representing variable interactions. However, traditional factor graphs are inherently static: variables and their connections are defined once and remain fixed.
This static nature poses a significant challenge for fields like NLP. For instance, in a Hidden Markov Model (HMM) representing a sentence, the number of variables depends on the sentence length, which varies. While tools like "plate notation" (for repetition) or Sum-Product Networks (for alternatives) exist, they are often restricted to specific structures or fixed-length inputs. Conversely, highly expressive solutions like probabilistic programming languages often render exact inference impossible.
The core question the authors address is: Can we create a framework expressive enough to handle dynamic structures but constrained enough to keep inference tractable?
Methods: Factor Graph Grammars
To solve this, the authors introduce Factor Graph Grammars (FGGs), building on the theory of Hyperedge Replacement Grammars (HRGs).
- The Grammar Approach: Instead of defining a single, monolithic graph, an FGG defines a set of "production rules." These rules dictate how to replace a placeholder (a "nonterminal" edge) with a specific fragment of a factor graph. By recursively applying these rules, the grammar can generate an infinite set of potential factor graphs (e.g., all possible HMMs for any sentence length).
- Conjunction Operation: The framework includes a modular way to "multiply" two FGGs. One FGG can define the general model (like an HMM), while another defines a specific query (e.g., "the sentence has 5 words and the 3rd word is 'apple'").
- Generalized Variable Elimination: For models with finite variable domains (like a fixed set of part-of-speech tags), inference doesn't require generating the full graphs. Instead, it can be performed by solving a system of polynomial equations derived directly from the grammar rules.
(Note: As a theoretical paper focused on formalisms and algorithms, the authors demonstrate their concepts using toy examples of HMMs and Probabilistic Context-Free Grammars rather than empirical datasets.)
Key Insights and Results
- Grammars as Logic Templates: The core insight is treating a grammar not just as a string generator, but as a template for generating logic. An FGG acts as a recipe for building a factor graph of any arbitrary size.
- Inference via Equations: For recursive grammars (like PCFGs), inference transforms into finding the "least fixed point" of a system of equations. This generalizes the "inside-outside" algorithms used in NLP to arbitrary graph structures.
- Complexity Bounds and Treewidth: The complexity of inference is tied to the "treewidth" of the graph fragments in the rules. If the rules are simple, inference remains efficient even for infinitely large generated graphs. Specifically:
- Nonrecursive FGGs (finite sets of graphs) yield linear inference time relative to grammar size.
- Linearly recursive FGGs (like HMMs) require matrix inversion but remain tractable.
- Nonlinearly recursive FGGs (like PCFGs) require iterative approximation.
- Expressivity and Conversion: FGGs can simulate plated factor graphs, dynamic graphical models, and Sum-Product Networks. Furthermore, any nonrecursive FGG can be converted into a single standard factor graph, enabling the use of off-the-shelf inference tools.
- The Decidability Wall: The authors identify a hard mathematical limit: calculating the sum-product becomes undecidable (equivalent to the Halting Problem) if a model features both an infinite set of possible graphs and variables with infinite continuous domains (like real numbers).
Limitations and Future Work
While converting an FGG to a single factor graph is possible, it can cause a "treewidth explosion," potentially slowing down standard inference algorithms significantly. Additionally, the most complex (nonlinearly recursive) grammars currently rely on iterative approximation rather than closed-form solutions.
Because this paper is primarily mathematical, the authors note that future work will focus on implementing these algorithms as differentiable operations in deep learning frameworks and developing approximate inference techniques for scenarios where exact calculations are too slow.
Summary updated