Beyond Markov Logic: Efficient Mining of Prediction Rules in Large Graphs
Preprint
Abstract
Graph representations of large knowledge bases may comprise billions of edges. Usually built upon human-generated ontologies, several knowledge bases do not feature declared ontological rules and are far from being complete. Current rule mining approaches rely on schemata or store the graph in-memory, which can be unfeasible for large graphs. In this paper, we introduce HornConcerto, an algorithm to discover Horn clauses in large graphs without the need of a schema. Using a standard fact-based confidence score, we can mine close Horn rules having an arbitrary body size. We show that our method can outperform existing approaches in terms of runtime and memory consumption and mine high-quality rules for the link prediction task, achieving state-of-the-art results on a widely-used benchmark. Moreover, we find that rules alone can perform inference significantly faster than embedding-based methods and achieve accuracies on link prediction comparable to resource-demanding approaches such as Markov Logic Networks.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- UniProt: the universal protein knowledgebaseNucleic Acids Research, 2016
- Fast rule mining in ontological knowledge bases with AMIE $+$ +The VLDB Journal, 2015
- SINA: Semantic interpretation of user queries for question answering on interlinked dataJournal of Web Semantics, 2015
- Inductive Lexical Learning of Class Expressions2014
- RockIt: Exploiting Parallelism and Symmetry for MAP Inference in Statistical Relational ModelsProceedings of the AAAI Conference on Artificial Intelligence, 2013
- DBpedia - A crystallization point for the Web of DataJournal of Web Semantics, 2009
- Semantics and complexity of SPARQLACM Transactions on Database Systems, 2009
- Structure-based inference of xml similarity for fuzzy duplicate detection2007
- Inverse entailment and progolNew Generation Computing, 1995
- Probabilistic knowledge basesIEEE Transactions on Knowledge and Data Engineering, 1995