Reconstructing TensorLog for Scalable End-to-End Rule Learning

Logical rules play a crucial role in knowledge graph (KG) reasoning. They underpin various database applications and serve as pivotal components for enhancing large language models (LLMs) with KGs. In recent years, end-to-end rule learning has emerged as a promising paradigm to learn logical rules. The key insight of end-to-end rule learning is to transform the rule learning problem in a discrete space into the parameter learning problem in a continuous space, by employing TensorLog operators to simulate the inference of logical rules. However, these TensorLog-based methods struggle with limited scalability in learning rules from large-scale KGs. To improve the efficiency and scalability of end-to-end rule learning, we propose an efficient framework named FastLog which reconstructs TensorLog by reducing vector-matrix multiplications to vector computations. We theoretically show that FastLog has a lower time complexity than TensorLog. Furthermore, we propose a dynamic pruning strategy in FastLog to further improve efficiency. Thanks to this strategy, the time complexity of FastLog can be further reduced to a constant. Extensive experimental results on a variety of benchmark KGs demonstrate that FastLog improves the efficiency of end-to-end methods by a significant margin without efficacy degradation in link prediction. Notably, with our reconstruction of TensorLog, existing TensorLog-based methods are enabled to learn logical rules on two large-scale datasets with up to three hundred million triples, while achieving a high efficacy comparable with the most advanced rule learner.