Knowledge Graphs have gained popularity in the last decade, given their ability to represent huge structured knowledge bases. However, they are often incomplete and thus Knowledge Graph Completion (KGC) is currently a hot topic. In this paper we present our idea of performing KGC by learning liftable probabilistic logic programs via regularization, using LIFTCOVER+, with the aim of obtaining more accurate results while learning a smaller set of rules.
CEUR ceur-ws.org
⟨, , ⟩
is ⟨, , ℎ⟩
Even though the term Knowledge Graph (KG) has been used from 1973 [
Data can be naturally and efectively represented with graphs in many real-world domains, such as computer networks, social networks, healthcare (diseases, molecules), transportation, and so on. For this reason, KGs are employed for diferent tasks like query answering, recommender systems, chatbots and voice assistants.
KGs have become popular over the last decade thanks to the introduction of Google’s
Knowledge Graph in 2012 [
born lisa
male gender
ed married lives gender speaks lives netherlands bob dutch speaks lang
Since KGs cannot contain all the possible knowledge in the domain, they are usually
incomplete and sparse, thus it is often necessary to infer missing information (entities or relationships).
This task is referred to as Knowledge Graph Completion (KGC). According to what is missing,
KGC can be divided into specific tasks [
KGC is a very active field of research and many algorithms have been proposed to solve the
problem. They can be divided into traditional and representation learning-based methods [
Our goal is to perform KGC with a Probabilistic Logic Programming (PLP) algorithm [
The triples of a KG can be represented by First-Order Logic (FOL) atoms. For example, the triple ⟨, , ℎ⟩ can be represented by the atom (, ℎ) . Therefore, we (, ℎ) ← (, ℎ ), (ℎ, ℎ ). consider a KG as a set of ground atoms or facts:
= { (, ) | ∈ ℝ, , ∈ ℂ} where ℂ is a set of constants (entities) and ℝ is a set of binary predicates (relations).
Following the approach of AnyBURL [
ℎ( 0, 1) ← 1( 1, 2), … , ( , +1 ).
Here ℎ(…) is the head of the rule, while the (…) form the body. Upper-case letters are variables.
AnyBURL is an anytime algorithm designed to learn rules from knowledge graphs by
following the bottom-up paradigm. With n referring to the number of body atoms and starting from
= 2 , AnyBURL iteratively samples random paths of length n, and learns rules of length − 1 ,
until a certain saturation is reached. For each rule, the confidence is computed as the number
of head and body groundings that are true divided by the number of body groundings that are
true. Considering the KG in Figure 1 from [
Given a ground path rule of the form ℎ( 0, 1) ← 1( 1, 2), … , ( , +1 ), extracted rules can be of one of three types: 1. rules that generalize acyclic ground path rules, i.e., rules where 0 ≠ +1 : 2. rules that generalize cyclic ground path rules, i.e., rules where 0 = +1 : 3. rules that generalize both acyclic and cyclic ground path rules: ℎ( 0, ) ← 1( ,
2), … , ( , +1 ); ℎ( , ) ← 1( ,
2), … , ( , ); ℎ( 0, ) ← 1( , 2), … , ( , +1 ); where , are variables that appear in the head, while can appear only in the body.
A rule is stored only if a certain quality criteria is met (e.g., the confidence above a specified threshold). Then, n is increased by 1 and the loop is repeated. Given a completion task (, ?) , the learnt rules are then used to find an entity c such that (, ) ∉ is true, with ∈ ℝ and , ∈ ℂ . The candidate values for c are ordered according to the maximum confidence of all the rules that generated them. In case of a tie for some candidates, the second rule that generated them is considered, and so on. The following generalized rules can be obtained from the above-mentioned bottom rule: (, ) ← (, where upper-case letters are variables.
In our approach, we learn rules with the AnyBURL algorithm but we attach to each rule a probability instead of a confidence and we tune the probabilities of the set of rules with parameter learning. We use LIFTCOVER+ that uses regularization: we try to bring the parameters close to 0 as much as possible and we remove the rules with a probability below a threshold, because they have a small influence on the final result. By doing so, the ranking should be more accurate and the number of rules learnt smaller. Furthermore, being a rule-based approach, the resulting candidate ranking is explained by the rules, and thus easily understandable.
Aside from AnyBURL [
AMIE [21] and its improved version AMIE++ [22] are top-down rule learning systems tailored to support the Open World Assumption, that is, a scenario in which absent data cannot be used as counterexamples. AMIE++ was developed to work with larger knowledge bases. The authors of [23] proposed a neural model for Existential Positive First-Order logical queries represented via box embeddings. In [24], the authors developed an approach for mining relational nonmonotonic rules from KGs under the Open World Assumption, that combines rule learning and nonmonotonic reasoning. DRUM [25] is an approach used for mining firstorder logical rules from KGs by performing inductive link prediction and thus able to manage previously unseen entities. The authors of [26] proposed a rule learning approach to learn typed rules using type information to guide the rule search.
In this paper, we presented our approach for performing KGC with PLP. The approach is based on the AnyBURL algorithm, however, it difers from it in the ranking method. In fact, we use probabilities instead of confidence values. Furthermore, the algorithm we employ, LIFTCOVER+, uses regularization to prune rules with negligible probabilities. In this way we should be able to obtain a more accurate ranking and a smaller set of learnt rules.
This article was produced while attending the PhD programme in Engineering Science at the University of Ferrara, Cycle XXXVIII, with the support of a scholarship financed by the Ministerial Decree no. 351 of 9th April 2022, based on the NRRP - funded by the European Union - NextGenerationEU - Mission 4 “Education and Research”, Component 1 “Enhancement of the ofer of educational services: from nurseries to universities” - Investment 4.1 “Extension of the number of research doctorates and innovative doctorates for public administration and cultural heritage”. This work has been partially supported by the Spoke 1 “FutureHPC & Big-Data” of the Italian Research Center on High-Performance Computing, Big Data and Quantum Computing (ICSC) funded by MUR Missione 4 - Next Generation EU (NGEU), by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No. 952215, and by the National Group of Computing Science (GNCS-INDAM). on Deep Understanding and Reasoning, URANIA 2016, volume 1802 of CEUR Workshop Proceedings, Sun SITE Central Europe, 2017, pp. 30–37. [15] A. Nguembang Fadja, F. Riguzzi, Probabilistic logic programming in action, in: A. Holzinger, R. Goebel, M. Ferri, V. Palade (Eds.), Towards Integrative Machine Learning and Knowledge Extraction, volume 10344 of Lecture Notes in Computer Science, Springer, 2017, pp. 89–116. doi:10.1007/978-3-319-69775-8\_5. [16] J. Vennekens, S. Verbaeten, M. Bruynooghe, Logic Programs With Annotated Disjunctions, in: 20th International Conference on Logic Programming (ICLP 2004), volume 3132 of Lecture Notes in Computer Science, Springer, 2004, pp. 431–445. [17] A. Nguembang Fadja, F. Riguzzi, Lifted discriminative learning of probabilistic logic programs, Machine Learning 108 (2019) 1111–1135. [18] D. Poole, First-order probabilistic inference, in: G. Gottlob, T. Walsh (Eds.), IJCAI-03, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, Acapulco, Mexico, August 9-15, 2003, Morgan Kaufmann Publishers, 2003, pp. 985–991. [19] E. Gentili, A. Bizzarri, D. Azzolini, R. Zese, F. Riguzzi, Regularization in probabilistic inductive logic programming, in: International Conference on Inductive Logic Programming, 2023. (in press). [20] C. Meilicke, M. W. Chekol, P. Betz, M. Fink, H. Stuckeschmidt, Anytime bottom-up rule learning for large-scale knowledge graph completion, The VLDB Journal (2023) 1–31. [21] L. A. Galárraga, C. Teflioudi, K. Hose, F. Suchanek, Amie: association rule mining under incomplete evidence in ontological knowledge bases, in: Proceedings of the 22nd international conference on World Wide Web, 2013, pp. 413–422. [22] L. Galárraga, C. Teflioudi, K. Hose, F. M. Suchanek, Fast rule mining in ontological knowledge bases with AMIE++, The VLDB Journal 24 (2015) 707–730. [23] H. Ren, W. Hu, J. Leskovec, Query2box: Reasoning over knowledge graphs in vector space using box embeddings, arXiv preprint arXiv:2002.05969 (2020). [24] H. D. Tran, D. Stepanova, M. H. Gad-Elrab, F. A. Lisi, G. Weikum, Towards nonmonotonic relational learning from knowledge graphs, in: Inductive Logic Programming: 26th International Conference, ILP 2016, London, UK, September 4-6, 2016, Revised Selected Papers 26, Springer, 2017, pp. 94–107. [25] A. Sadeghian, M. Armandpour, P. Ding, D. Z. Wang, Drum: End-to-end diferentiable rule mining on knowledge graphs, Advances in Neural Information Processing Systems 32 (2019). [26] H. Wu, Z. Wang, K. Wang, Y.-D. Shen, Learning typed rules over knowledge graphs, in: Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 19, 2022, pp. 494–503.