The Role of Higher-Order Constructs in the Inexact Matching of Semantic Graphs

Michael Wolverton and Jerome Thomere

Inexact pattern matching using semantic graphs has a wideranging use in AI systems, particularly in machine vision, case-based reasoning, and, recently, in intelligence analysis applications. While much previous work in the area has focused on matching simple flat graphs, there is increasing need for and use of complex graphical patterns with higher-order constructs—hierarchical graphs, cardinality constraints, disjunction, and others. This paper reports the results of an experimental analysis of higher-order constructs in graphical patterns and their effect on pattern matching efficiency. The study focuses on two aspects of these constructs—the impact of cardinality constraints on representational power and matching speed, and the benefit of caching hierarchical match results. The analysis shows that both mechanisms provide a significant speedup over conventional flat graph matching.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.