Proceedings of the VLDB Endowment · 2020 · 37 citations · 55 references
ComputingComputer ScienceData MiningKnowledge RepresentationMachine LearningAutomated ReasoningDirected Acyclic GraphsGraph AlgorithmsGraph AnalyticsGraph MiningGraph TheoryGraph ClassificationGraph Pattern MiningGraph-based Knowledge RepresentationGraph-based Pattern RecognitionGraph-based ReasoningLink Prediction
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.
55
Mining association rules between sets of items in large databases
Rakesh Agrawal, Tomasz Imieliński, Arun Swami · 1993 · 14.8K citations · Full text
Translating embeddings for modeling multi-relational data
Antoine Bordes, Nicolas Usunier, Jason Weston et al. · 2015 · 5.2K citations · Full text
Fabian M. Suchanek, Gjergji Kasneci, Gerhard Weikum · 2007 · 3.9K citations · Full text