Node Aggregation for Distributed Inference in Bayesian Networks

Abstract

This study describes a general framework and several algorithms for reducing Bayesian networks with loops (i.e., undir e cted cycles) into equivalent networks which are singlyconnected. The purpose of this conversion is to take advantage of a distributed inference algorithm [6]. The framework and algorithms center around one basic operation, node aggregation. In this operation, a cluster of nodes in a network is replaced with a single node without changing the underlying joint distribution of the network. The framework for using this operation includes a node aggregation theorem which describes whether a cluster of nodes can be combined, and a complexity analysis which estimates the computational req uirements for the resulting networks. The algorithms described include a heuristic search algorithm which finds the set of node aggregations that makes a network singly connected and allows inference to execute in minimum time, and a "graph-directed" algorithm which is guaranteed to find a feasible but not necessary optimal solution and with less computation than the search algorithm.