StaRAI - Semantics and Symmetries in Exact Lifted Inference

A tutorial on Statistical Relational AI (StaRAI) at the ECAI 2020

24th European Conference on Artificial Intelligence, August 29th - September 2nd 2020, Santiago de Compostela, Spain


Symmetries in a probabilistic graphical model with a known number of constants allow for lifted inference to perform tractable problem solving given a liftable model and a liftable query. In this tutorial, we show how to retain properties of lifted inference even with an unknown set of constants as well as how to retain a liftable model by approximating symmetries while performing inference.


Relational modelling allows for representing knowledge and reasoning under uncertainty (KRR and UAI), which are main topics of the ECAI 2020 call for papers. The goal of this tutorial is two-fold:

  1. to provide an overview about recent developments in probabilistic relational mod- elling and reasoning with a focus on obtaining/restoring a lifted model and their semantics and
  2. to discuss new directions for investigation.

Therefore, this tutorial on the one hand provides an introduction to novices to a major topic within AI as well as discusses a topic of emerging importance for AI.

The tutorial will be mostly self-contained. While we assume familiarity with probabilistic graphical models, like Bayesian networks, we will revisit all necessary definitions.


  1. Probabilistic relational modelling
    • Probabilistic relational models (PRMs)
    • Inference tasks
    • Algorithms
  2. Exact symmetries and changing domains in static PRMs
    • Complexity, completeness, and tractability
    • From propositional to lifted models
    • Lifted Evidence and lifted queries
    • Changing domains
    • Unknown domains
  3. Stable Inference over Time in dynamic PRMs
    • Reasoning over time
    • Keeping reasoning polynomial
  4. Summary

Selected References and Further Reading

  • David Poole: First-order Probabilistic Inference, IJCAI-03.
  • Mathias Niepert and Guy Van den Broeck: Tractability through Exchangeability: A New Perspective on Efficient Probabilistic Inference, AAAI-14
  • Guy Van den Broeck and Mathias Niepert: Lifted Probabilistic Inference for Asymmetric Graphical Models, AAAI-15.
  • Mathias Niepert: Symmetry-aware Marginal Density Estimation, AAAI-13.
  • Parag Singla and Pedro Domingos: Markov Logic in Infinite Domains, UAI-07.
  • Babak Ahmadi, Kristian Kersting, Martin Mladenov, and Sriraam Natarajan: Exploiting Symmetries for Scaling Loopy Belief Propagation and Relational Training, Machine Learning 92(1).
  • Tanya Braun and Ralf Möller: Exploring Unknown Universes in Probabilistic Relational Models, AI-19.
  • Marcel Gehrke, Tanya Braun, and Ralf Möller: Taming Reasoning in Temporal Probabilistic Relational Models, ECAI-20.

Download Presentations

  • Probabilistic Relational Models (PRMs): pdf
  • Exact Symmetries and Changing Domains in Static PRMs: pdf
  • Stable Inference over Time in Dynamic PRMs: pdf
  • Summary: pdf

Video Recording

The tutorial was recorded and is made available by


(Registration might be necessary.)