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., undirected cycles) into equivalent networks which are singly connected. 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 us ing 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 require ments 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.