An Optimal Algorithm for Marginalization in Bayesian Networks

We study the problem of marginalization in Bayesian networks: given a Bayesian network $G=(V, E)$ and nodes $S$ we wish to marginalize, what is the most compact Bayesian network $G'$ over nodes $V \setminus S$ which is faithful to the independencies and ancestral relationships in the original graph. Efficient solutions to this problem are crucial for the problem of abstraction in Bayesian networks. Prior approaches based on Shachter's topological operations are sensitive to user-chosen node removal and edge reversal orders, provide no optimality guarantee, and can be prohibitively slow when searched exhaustively. We present a novel algorithm for marginalization with the first proof of optimality for algorithms of its kind, with an empirical speed up of up to several orders of magnitude over the prior state-of-the-art.