Practical Probabilistic Reasoning in Web Knowledge Graphs

• Applicant: Professor Dr. Heiner Stuckenschmidt
• Subject Area: Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: from 2016 to 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 327259924

• Final Report Year: 2020

Final Report Abstract

In this project we tried to develop, implement and evaluate methods that are specifically designed to model uncertain knowledge. Firstly, we studied uncertain reasoning in temporal knowledge graphs by leveraging log-linear models. Secondly, we extended log-linear logics with numerical constraints by using concrete domains (datatypes). Thirdly, we designed approximate inference algorithms that can be parallelized. In probabilistic inference we support two main tasks: (i) MAP inference which is the problem of computing the most probable and consistent knowledge bases, and (ii) marginal inference which is the problem of computing the probability of a given query. Since both of these tasks are intractable. We studied a variant of MAP called MPE (most probable explanation) inference. This task can be solved in polynomial time. However, this result applies only to KBs created using PSL (probabilistic soft logic) in which axioms are annotated with probabilities. In order to tackle the intractability bottleneck in MAP and marginal inference, we designed approximate algorithms that speedup reasoning by several folds. We also investigated two challenging problems that arise in uncertain knowledge bases, namely, debugging and conflict resolution. As highlighted in the motivation of our project proposal, uncertain data are acquired through information extraction and machine learning. These data can be noisy and erroneous. In order to improve the quality of such data, we developed a language that can be used to specify temporal as well as numerical constraints. Hence, it is possible to hand-craft such constraints but also to learn them automatically from data. Temporal as well as numerical constraints together with a KB are fed into our reasoner which performs MAP inference in order to obtain a consistent (possibly coherent) deterministic KB. Additionally, marginal inference can be used to estimate the probability of a query. We developed two probabilistic reasoners, namely, N-RockIt and TeCORE that support reasoning in numerical as well as temporal domains. Moreover, in order to overcome scalability problems in some scenarios, we developed efficient approximate algorithms. We evaluated our approach on knowledge bases that consist of several thousands facts, our encouraging results are published in various venues. An open problem within the scope of the project is how to scale approximate inference while maintaining the margin of error as low as possible. We see two directions towards a solution to this problem: (i) to use subsymbolic approaches by adapting to the problem, and (ii) to perform inference on subgraphs (based on theoretical results on Markov blanket and independence of variables) instead of a full Markov network corresponding to a given KB. The former are easier to scale as well as more robust to noise.

Publications

• Marrying uncertainty and time in knowledge graphs. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA., pages 88–94, 2017
  Melisachew Wudage Chekol, Giuseppe Pirrò, Joerg Schoenfisch, and Heiner Stuckenschmidt
  
• Rule based temporal inference. In Technical Communications of the 33rd International Conference on Logic Programming, ICLP 2017, August 28 to September 1, 2017, Melbourne, Australia, pages 4:1–4:14, 2017
  Melisachew Wudage Chekol and Heiner Stuckenschmidt
  
• Scaling probabilistic temporal query evaluation. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM 2017, Singapore, November 06 - 10, 2017, pages 697–706, 2017
  Melisachew Wudage Chekol
  
• Towards partition-aware lifted inference. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM 2018, Torino, Italy, October 22-26, 2018, pages 1823–1826, 2018
  Melisachew Wudage Chekol and Heiner Stuckenschmidt
  
• Towards probabilistic bitemporal knowledge graphs. In Companion of the The Web Conference 2018 on The Web Conference 2018, WWW 2018, Lyon , France, April 23-27, 2018, pages 1757–1762, 2018
  Melisachew Wudage Chekol and Heiner Stuckenschmidt
  
• Leveraging graph neighborhoods for efficient inference. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM 2019, Beijing, China, November 3-7, 2019, pages 1893–1902, 2019
  Melisachew Wudage Chekol and Heiner Stuckenschmidt
  
• Time-aware probabilistic knowledge graphs. In 26th International Symposium on Temporal Representation and Reasoning, TIME 2019, October 16-19, 2019, Málaga, Spain, pages 8:1–8:17, 2019
  Melisachew Wudage Chekol and Heiner Stuckenschmidt