Comparison of heuristics for inexact graph matching with application to soft data fusion.

摘要

Many modern-day defense intelligence problems involve extensive amounts of human reporting that results in large quantities of digital textual data that can be parsed into graphical structures, forming a "data graph" of the cumulative human observations of a complex environment. The problem domains, involving complicated and dynamic behaviors of many individuals in dynamically interacting social networks are very difficult to model (and so deductive knowledge of the problem environments is typically unavailable), but analysts can often specify a priori or learned sets of conditions of interest in the problem space in linguistic form (queries in effect), that can also be represented as sets of graphs of interest or what we have called "target graphs". Finding or testing for the existence of these conditions of interest or queried-conditions in the data graph can be done by inexact graph matching techniques; we have implemented one design using a truncated branch and bound algorithm. This technology thus supports a dynamic discovery process for the human analyst, allowing him to initiate and evolve queries as he dynamically discovers patterns of interest in the data. As our applications are focused on real-time streaming data, the trade off between computational efficiency and accuracy is of critical concern. This study compares two heuristic algorithms- Modified Neighborhood Search Algorithm and Genetic Algorithm to our "baseline" approach to provide a quantitative evaluation of trade space results. We analyze these three algorithms with respect to computation time and quality of the solution.