Beyond Markov Logic: Efficient Mining of Prediction Rules in Large Graphs
This addresses the challenge of efficient rule mining in large knowledge bases for tasks like link prediction, offering a faster alternative to resource-intensive methods.
The paper tackles the problem of mining Horn clauses in large graphs without requiring a schema, introducing HornConcerto which outperforms existing methods in runtime and memory consumption while achieving state-of-the-art results on link prediction benchmarks.
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.