Learning to Condition: A Neural Heuristic for Scalable MPE Inference
Brij Malhotra, Shivvrat Arya, Tahrima Rahman, Vibhav Giridhar Gogate
Abstract
We introduce learning to condition (L2C), a scalable, data-driven framework for accelerating Most Probable Explanation (MPE) inference in Probabilistic Graphical Models (PGMs)—a fundamentally intractable problem. L2C trains a neural network to score variable-value assignments based on their utility for conditioning, given observed evidence. To facilitate supervised learning, we develop a scalable data generation pipeline that extracts training signals from the search traces of existing MPE solvers. The trained network serves as a heuristic that integrates with search algorithms, acting as a conditioning strategy prior to exact inference or as a branching and node selection policy within branch-and-bound solvers. We evaluate L2C on challenging MPE queries involving high-treewidth PGMs. Experiments show that our learned heuristic significantly reduces the search space while maintaining or improving solution quality over state-of-the-art methods.
BibTeX
@inproceedings{
malhotra2025learning,
title={Learning to Condition: A Neural Heuristic for Scalable {MPE} Inference},
author={Brij Malhotra and Shivvrat Arya and Tahrima Rahman and Vibhav Giridhar Gogate},
booktitle={The Thirty-ninth Annual Conference on Neural Information Processing Systems},
year={2025},
url={https://openreview.net/forum?id=otIdC4tsYf}
}