Fusion of a set of attributed graphs for event reconstruction

Conflicting and incomplete information of uncertain reliability is endemic to analytic communities supporting military, national, and homeland security operations. The prevalence of human-source information necessitates approaches for integrating diverse and sometimes inconsistent second hand observations. Given a set of attributed graphs representing a number of independent, potentially noisy observations of the same object, attributed graph association can be used to recover the true attributes of the object. Reconstructing an event based on given conflicting observations (to arrive at an accurate consensus report) is one of the tasks that can be handled by graph association. This paper presents an approach to treating graph association problems by employing a probabilistic graphical model (PGM) with latent (hidden) matching variables. Its key idea is to avoid explicit graph matching, the step inherent to all conventional error-tolerant graph matching algorithms. Given a set of attributed graphs, the PGM is parameterized using the Expectation-Maximization technique, with Markov Chain Monte Carlo sampling employed for treating the latent matching variables. In order to assess the feasibility of the presented approach, we test it on a set of synthetically generated, deterministic problem instances. It is observed that the algorithm consistently converges to correct solutions in the time linear in dataset size.