2013/01/10 by Hans L. Bodlaender, Arie M. C. A. Koster, Bodlaender, Hans L. +5 · 1 citation
Computer Science · #Advanced Graph Neural Networks #Bayesian Modeling and Causal Inference #Constraint Satisfaction and Optimization #cs.AI #cs.DS
paper · pdf · doi:10.48550/arxiv.1301.2256
Appears in Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence (UAI2001)
arxiv created 2013/01/10 · arxiv updated 2013/01/14
The currently most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding good triangulations forprobabilistic networks, that is, triangulations with a minimal maximum clique size. We provide a set of rules for stepwise reducing a graph, without losing optimality. This reduction allows us to solve the triangulation problem on a smaller graph. From the smaller graph's triangulation, a triangulation of the original graph is obtained by reversing the reduction steps. Our experimental results show that the graphs of some well-known real-life probabilistic networks can be triangulated optimally just by preprocessing; for other networks, huge reductions in their graph's size are obtained.