Capturing Associations in Graphs

CategoryPublications Publications 338

Authors: Wenfei Fan, Ruochun Jin, Muyang Liu, Ping Lu, Chao Tian, Jingren Zhou

Published in: International Conference on Very Large Data Bases (VLDB 2020), Aug 31- Sept 4, 2020, Tokyo, Japan

Date of Publication: Aug 31, 2020


This paper proposes a class of graph association rules, denoted by GARs, to specify regularities between entities in graphs. A GAR is a combination of a graph pattern and a dependency; it may take as predicates ML (machine learning) classifiers for link prediction. We show that GARs help us catch incomplete information in schemaless graphs, predict links in social graphs, identify potential customers in digital marketing, and extend graph functional dependencies (GFDs) to capture both missing links and inconsistencies.

We formalize association deduction with GARs in terms of the chase, and prove its Church-Rosser property. We show that the satisfiability, implication and association deduction problems for GARs are coNP-complete, NP-complete and NP-complete, respectively, retaining the same complexity bounds as their GFD counterparts, despite the increased expressive power of GARs. The incremental deduction problem is DP-complete for GARs versus coNP-complete for GFDs. In addition, we provide parallel algorithms for association deduction and incremental deduction. Using real-life and synthetic graphs, we experimentally verify the effectiveness, scalability and efficiency of the parallel algorithms.

View Full Text

Keywords2020Data qualityExplainable AI by combining statistical and logical methodsVLDBWenfei Fan Previous: Next: