Partition-Aware Graph Pattern based Node Matching with Updates
Guohao Sun, Guanfeng Liu, Yan Wang, Mehmet Ali Orgun, Quan Z. Sheng, Xiaofang Zhou · IEEE Transactions on Knowledge and Data Engineering · 2021
Graph Pattern based Node Matching(GPNM) is to find all the matches of the nodes in a data graph$G_D$based on a given pattern graph$G_P$. GPNM has become increasingly important in many applications, e.g., group finding and expert recommendation. In real scenarios, both$G_P$and$G_D$are updated frequently. However, the existing GPNM methods either need to perform a new GPNM procedure from scratch to deliver the node matching results based on the updated$G_P$and$G_D$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 partitionanddensity-based partition. In these two methods, P-GPNM considers the dense connections between partitions and the inner connections inside a single partition, respectively. The experimental results on five real-world social graphs demonstrate that our proposed P-GPNM is much more efficient than the state-of-the-art GPNM methods.