Efficient Constrained Subgraph Extraction for Exploratory Discovery in Large Knowledge Graphs

Knowledge graphs which often integrate heterogeneous data can be exploited for serendipitous knowledge discovery using appropriate integration paradigms. We posit that a semi-structured querying model which blends the benefits of structured and unstructured querying could offer a sweetspot. However, there is a need for effective algorithmic techniques for such query processing.In this paper, we propose a class of constrained subgraph connection structure discovery queries whose specification is only partially structured. Graph theoretically, these amount subgraph homeomorphism problems that tolerate flexibility in graph structure matching. Central to achieving the goals of performance and scale of query evaluation is the use of a path algebraic framework rather than a graph theoretic framework. The path algebraic framework is coupled with some efficient data encoding, representation and indexing. Together, these allow more effective querying than using the traditional graph traversal style algorithms, demonstrated by a comparative evaluation.