Capturing More Associations by Referencing External Graphs
Wenfei Fan, Muyang Liu, Shuhao Liu, Chao Tian · Proceedings of the VLDB Endowment · 2024
This paper studies association rule discovery in a graphG1by referencing an external graphG2with overlapping information. The objective is to enrichG1with relevant properties and links fromG2. As a testbed, we consider Graph Association Rules (GARs). We propose a notion of graph joins to enrichG1by aligning entities acrossG1andG2. We also introduce a graph filtering method to support graph joins, by fetching only the data ofG2that pertains to the entities ofG1, to reduce noise and the size of the fused data. Based on these we develop a parallel algorithm to discover GARs acrossG1andG2. Moreover, we provide an incremental GAR discovery algorithm in response to updates toG1andG2. We show that both algorithms guarantee to reduce parallel runtime when given more processors. Better yet, the incremental algorithm is bounded relative to the batch one. Using real-life and synthetic data, we empirically verify that the methods improve the accuracy of association analyses by 30.4% on average, and scale well with large graphs.