Capturing More Associations by Referencing External Graphs

Download PDF

Abstract

This paper studies association rule discovery in a graph G1 by referencing an external graph G2 with overlapping information. The objective is to enrich G1 with relevant properties and links from G2. As a testbed, we consider Graph Association Rules (GARs). We propose a notion of graph joins to enrich G1 by aligning entities across G1 and G2. We also introduce a graph filtering method to support graph joins, by fetching only the data of G2 that pertains to the entities of G1, to reduce noise and the size of the fused data. Based on these we develop a parallel algorithm to discover GARs across G1 and G2. Moreover, we provide an incremental GAR discovery algorithm in response to updates to G1 and G2. 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.