# Maximum A Posteriori Inference in Sum-Product Networks

arXiv: https://arxiv.org/abs/1708.04846 · HTML: https://mlsanity.com/paper/1708.04846/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Aug 2017.

## Built on by (most cited first, 6 of 6)

- [Tractable Regularization of Probabilistic Circuits](https://mlsanity.com/paper/2106.02264/) (2021)
- [Solving Marginal MAP Exactly by Probabilistic Circuit Transformations](https://mlsanity.com/paper/2111.04833/) (2021)
- [Tractable Representation Learning with Probabilistic Circuits](https://mlsanity.com/paper/2507.04385/) (2025)
- [Neural Network Approximators for Marginal MAP in Probabilistic Circuits](https://mlsanity.com/paper/2402.03621/) (2024)
- [Solving Satisfiability Modulo Counting for Symbolic and Statistical AI Integration With Provable Guarantees](https://mlsanity.com/paper/2309.08883/) (2023)
- [Probably Approximately Correct Maximum A Posteriori Inference](https://mlsanity.com/paper/2601.16083/) (2026)

## Abstract (arXiv)

Sum-product networks (SPNs) are a class of probabilistic graphical models that allow tractable marginal inference. However, the maximum a posteriori (MAP) inference in SPNs is NP-hard. We investigate MAP inference in SPNs from both theoretical and algorithmic perspectives. For the theoretical part, we reduce general MAP inference to its special case without evidence and hidden variables; we also show that it is NP-hard to approximate the MAP problem to 2nε for fixed 0 ≤ ε < 1, where n is the input size. For the algorithmic part, we first present an exact MAP solver that runs reasonably fast and could handle SPNs with up to 1k variables and 150k arcs in our experiments. We then present a new approximate MAP solver with a good balance between speed and accuracy, and our comprehensive experiments on real-world datasets show that it has better overall performance than existing approximate solvers.