Multi-Evidence Lifted Message Passing, with Application to PageRank and the Kalman Filter
Abstract
Lifted message passing algorithms exploit repeated structure within a given graphical model to answer queries ef?ciently. Given evidence, they construct a lifted network of supernodes and superpotentials corresponding to sets of nodes and potentials that are indistinguishable given the evidence. Recently, ef?cient algorithms were presented for updating the structure of an existing lifted network with incremental changes to the evidence. In the inference stage, however, current algorithms need to construct a separate lifted network for each evidence case and run a modi?ed message passing algorithm on each lifted network separately. Consequently, symmetries across the inference tasks are not exploited. In this paper, we present a novel lifted message passing technique that exploits symmetries across multiple evidence cases. The bene?ts of this multi-evidence lifted inference are shown for several important AI tasks such as computing personalized PageRanks and Kalman ?lters via multievidence lifted Gaussian belief propagation.