Semantically Ranked Graph Pattern Queries for Link Analysis

Relationship pattern based queries are important components of intelligence link analysis, Typically the analyst gives a prototypical graph pattern which needs to be approximately matched to the data. Performing such inexact graph pattern matching is currently carried out using some variant of graph edit distance measures. This approach suffers from two main shortcomings: (1) it relies on detailed graph edit cost assignment by the analyst, and (2) it cannot efficiently incorporate semantic similarities that can be, in most cases, computed based on appropriate ontologies. In this paper, we propose novel techniques for evaluating graph pattern queries to produce semantically-ranked results. Our approach systematically combines both partial structural matches and semantic similarities in order to relieve the user from specifying edit costs.