Partition-aware graph pattern based node matching with updates

Graph Pattern based Node Matching (GPNM) is to find all the matches of the nodes in a data graph GD based on a given pattern graph GP. GPNM has become increasingly important in many applications, e.g., group finding and expert recommendation. In real scenarios, both GP and GD are updated frequently. The existing GPNM methods either need to perform a new GPNM procedure from scratch or incrementally perform the GPNM procedure for each of the updates, leading to low efficiency. Although the elimination relations between updates and partitions of data graphs are considered in the state-of-the-art method, it still suffers from low efficiency as only the labels of nodes are considered in the partitions. Therefore, there is a pressing need for a new method to efficiently deliver the node matching results on the updated graphs. In this paper, we propose a new Partition-aware GPNM algorithm, called P-GPNM, where we propose two new partition methods, i.e., connection-based partition and density-based partition. In these two methods, P-GPNM considers the dense connections between partitions and the inner connections inside a single partition. The experimental results on five social graphs demonstrate that our proposed P-GPNM is much more efficient than the state-of-the-art GPNM methods.