Partition-Aware Graph Pattern Based Node Matching With Updates

• Published in: IEEE transactions on knowledge and data engineering 2023-02, Vol.35 (2), p.1922-1937
• Main Authors: Sun, Guohao, Liu, Guanfeng, Wang, Yan, Orgun, Mehmet A., Sheng, Quan Z., Zhou, Xiaofang
• Format: Article
• Language: English
• Subjects: Algorithms; Australia; Data models; elimination relationship; Fans; graph partition; Graph pattern matching; Graphs; Indexes; Matching; Nodes; Partitions (mathematics); Pattern matching; Social networking (online); Sun; updates of graph
• ISSN: 1041-4347; 1558-2191
• DOI: 10.1109/TKDE.2021.3103914

Graph Pattern based Node Matching (GPNM) is to find all the matches of the nodes in a data graph G_D GD based on a given pattern graph G_P GP . GPNM has become increasingly important in many applications, e.g., group finding and expert recommendation. In real scenarios, both G_P GP and G_D GD 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 GP and G_D GD 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, respectively. The experimental results on five real-wo