Abstract
Our paper builds on the recent trend of using neural networks trained with self-supervised or supervised learning to solve the Most Probable Explanation (MPE) task in discrete graphical models. At inference time, these networks take an evidence assignment as input and generate the most likely assignment for the remaining variables via a single forward pass. We address two key limitations of existing approaches: (1) the inability to fully exploit the graphical model's structure and parameters, and (2) the suboptimal discretization of continuous neural network outputs. Our approach embeds model structure and parameters into a more expressive feature representation, significantly improving performance. Existing methods rely on standard thresholding, which often yields suboptimal results due to the non-convexity of the loss function. We introduce two methods to overcome discretization challenges: (1) an external oracle-based approach that infers uncertain variables using additional evidence from confidently predicted ones, and (2) a technique that identifies and selects the highest-scoring discrete solutions near the continuous output. Experimental results on various probabilistic models demonstrate the effectiveness and scalability of our approach, highlighting its practical impact.
Introduction
Probabilistic Graphical Models (PGMs), such as Bayesian and Markov Networks, are essential for structured machine learning tasks ranging from medical diagnosis to computer vision. A fundamental challenge in PGMs is the "Most Probable Explanation" (MPE) query—identifying the most likely state of the world given observed evidence. As an NP-hard problem, traditional approximate solvers like Belief Propagation often face trade-offs between accuracy and speed, especially in complex, high-treewidth models.
Recent "neural solvers" attempt to bypass these bottlenecks by training neural networks to predict MPE assignments in a single forward pass. However, these early attempts suffered from structural blindness—failing to leverage the PGM's internal parameters—and the "rounding problem," where simple thresholding of continuous outputs misses optimal discrete solutions. SINE (Scalable MPE Inference) addresses these flaws through hypergraph-based encoding and uncertainty-aware discretization.
Methodology
1. Hypergraph-Based Encoding
SINE moves beyond flat input vectors by representing the PGM as a hypergraph. In this representation, variables are nodes, and the probabilistic factors or cliques are hyperedges connecting groups of nodes. By employing a Hypergraph Neural Network (HGNN) with attention mechanisms, SINE allows the network to learn the specific dependencies and parameters of the PGM, creating a significantly richer internal representation.
2. Advanced Discretization Techniques
To bridge the gap between "fuzzy" neural outputs and discrete 0/1 assignments, SINE introduces two strategies:
- Oracle-Assisted Uncertainty-Aware Inference (OAUAI): The model identifies variables where the network is "unsure" (outputs near 0.5). It fixes the confident variables and delegates the small subset of uncertain ones to a traditional exact solver (the "Oracle").
- Fast Heuristic Search (k-Nearest): Instead of simple rounding, SINE performs a rapid search in the neighborhood of the continuous output to identify the top-$k$ closest binary assignments, selecting the one that maximizes the PGM's probability.
Evaluation and Results
The researchers evaluated SINE on 30 high-treewidth binary models from UAI inference competitions, including 25 higher-order models (up to 1,444 variables) and 5 pairwise networks (up to 1,600 variables).
Key results include:
- Superior Accuracy: The HGNN + OAUAI combination outperformed the traditional Max-Product Belief Propagation baseline in over 80% of higher-order model experiments.
- Scalability: As query complexity increased (predicting 90% of variables), SINE’s advantage grew, showing up to a 40% improvement in log-likelihood scores.
- Embedding Quality: HGNN-based embeddings outperformed simpler query-based embeddings in 78% of cases, validating the importance of structural awareness.
Conclusion and Future Work
SINE demonstrates that combining neural speed with structural awareness and targeted exact inference provides a powerful framework for MPE tasks. While currently limited to binary variables, future research will focus on extending SINE to multi-valued categorical variables and developing joint training schemes to optimize the discretization process alongside the neural network.
Summary updated