2016 · 118 citations · 65 references
ComputingComputer ScienceComputational LinguisticsKnowledge RepresentationNatural Language ProcessingDirected Acyclic GraphsGraph AlgorithmsGraph AnalyticsGraph MiningGraph TheoryKnowledge GraphsDependency GraphsGraph-based Knowledge ModelingGraph-based Knowledge RepresentationKnowledge Graph ReasoningKnowledge Graph ScalabilityScalable Graph AlgorithmsScalable Parallel AlgorithmsTopological Data Structures
We propose a class of functional dependencies for graphs, referred to as GFDs. GFDs capture both attribute-value dependencies and topological structures of entities, and subsume conditional functional dependencies (CFDs) as a special case. We show that the satisfiability and implication problems for GFDs are coNP-complete and NP-complete, respectively, no worse than their CFD counterparts. We also show that the validation problem for GFDs is coNP-complete. Despite the intractability, we develop parallel scalable algorithms for catching violations of GFDs in large-scale graphs. Using real-life and synthetic data, we experimentally verify that GFDs provide an effective approach to detecting inconsistencies in knowledge and social graphs.
65
Mining association rules between sets of items in large databases
Rakesh Agrawal, Tomasz Imieliński, Arun Swami · 1993 · 14.8K citations · Full text
Fabian M. Suchanek, Gjergji Kasneci, Gerhard Weikum · 2007 · 3.9K citations · Full text
Xin Luna Dong, Evgeniy Gabrilovich, Geremy Heitz et al. · 2014 · 1.6K citations
Mining quantitative association rules in large relational tables
Ramakrishnan Srikant, Rakesh Agrawal · 1996 · 1.5K citations · Full text