Extending Association Rules with Graph Patterns

Abstract We propose a general class of graph-pattern association rules ( GPARs ) for social network analysis. Extending association rules for itemsets, GPARs can help us discover associations among entities in social networks and identify potential customers. Despite the benefits, GPARs bring us challenges: the problem of GPARs discovery is already intractable, not to mention mining over large social networks. Nonetheless, we show that it is still feasible to discover GPARs from large social networks. We first formalize the GPARs mining problem and decompose it into two subproblems: frequent pattern mining and rule generation. To address two subproblems, we develop a parallel algorithm along with an optimization strategy to construct DFS code graphs, whose nodes correspond to frequent patterns. We also provide efficient algorithms to generate (resp. representative) GPARs by using (resp. maximal) frequent patterns. Using real-life and synthetic graphs, we experimentally verify that our algorithms not only scale well but can also identify interesting GPARs with high quality among social entities.