In recent years, graph pattern matching, approximate graph matching and dynamic subgraph indexing have become important graph analysis tools due to the emergence of many new applications such as computational biology and social networks analysis. In this work we investigate these three related problems.
For the first problem, in previous existing models, each edge in the query pattern represents the same relationship, e.g., the two endpoint vertices have to be connected or the distance between them should be within a certain uniform threshold. However, real world applications may require edges representing different relationships or distances. Therefore, we introduce the flexible pattern matching model where a range [mine; maxe] is associated with an edge e in the query pattern, which means that the minimum distance between the matched endpoints of e is in the range of [mine; maxe]. A novel pattern matching algorithm is devised, which consists of several innovations including preprocessing the query pattern, two types of indices, and a top-k matches generation scheme.
For the second problem, we study the problem of finding approximate matches of a query graph in a large database graph with (possible) missing edges. The SAPPER method is proposed, utilizing the hybrid neighborhood unit structures in the index. SAPPER also takes advantage of pre-generated random spanning trees and a carefully designed graph enumeration order.
For the third problem, to the best of our knowledge, most subgraph indexing focuses on the static database graphs. However, in real applications, database graphs may change over time. Thus, we propose an indexing structure, BR-index, for large dynamic graphs. The large database graph is partitioned into a set of overlapping index regions. Features (small subgraphs) are extracted from these regions and used to index them. The updates to G can be localized to a small number of these regions. To further improve the efficiency in updates and query processing, several novel techniques and data structures are invented, which include feature lattice, maximal features, and overlapping regions.
Extensive empirical studies have been conducted to show the effectiveness and efficiency of our indices and methods.