Compression vs. Accuracy: Compact Models for Efficiency and Interpretation

A tutorial by Malte Luttermann, Jan Speller, Marcel Gehrke, and Tanya Braun at IJCAI-ECAI 2026

• Introduction

  Our surrounding world is inherently uncertain and relational. The field of Statistical Relational AI (StaRAI) has emerged to account for both uncertainty and relational modelling. StaRAI explicitly encodes objects and relations in probabilistic models, which enables algorithms to exploit repeated structures, i.e., subgraphs with matching associated probability functions as well as identical graph structure, e.g., for efficiency gains during inference through compression. To exploit repeated structures, they have to be identified. While such repeated structures frequently occur in many practical applications, they are generally not explicitly represented in a learned model and thus cannot be exploited by inference algorithms. It is therefore crucial to efficiently identify and compress these structures, which results in a significant reduction in storage requirements. In addition, dedicated inference algorithms can use these compressed structures for efficiency gains that can be quantified in a runtime that no longer depends exponentially on the number of overall random variables.

  This tutorial provides a look at recent advances in the field of computing a highly compressed probabilistic relational model from a given probabilistic propositional model. We consider how the compression can efficiently be realised and how the resulting compressed representation is applied to speed up inference. Furthermore, we discuss the approximation of a compressed representation, give error bounds for the induced approximation error as well as investigate how to obtain a compressed model for a given error bound. Additionally, for the trade-off between accuracy and compression, we also discuss a hierarchical clustering approach and provide different points of view on the clustering in preparation for better interpretability.

• Presenters

  A collaborative effort between members of the University of Hamburg and the University of Münster

  • Malte Luttermann
  • Jan Speller
  • Marcel Gehrke
  • Tanya Braun

• Target Audience and Prerequisite Knowledge

  Reasoning under uncertainty is at the core of most AI problems. Even machine learning problems often have a reasoning problem at their heart, which a machine learning algorithm approximates. Unfortunately, reasoning under uncertainty is in general NP-hard. By exploiting reoccurring structures, inference can become tractable, i.e., depend polynomially w.r.t. the number of random variables. The tutorial is therefore potentially interesting for all researchers at the IJCAI conference and in particular those interested in reasoning under uncertainty.

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

• Agenda (including slides when ready)

  1. Introduction and background [Marcel, Tanya]

     • Motivation, use cases

     • Probabilistic (relational) models

     • Lifted probabilistic inference

  2. Compressing models [Malte]

     • The basics of colour passing

     • Recent advances in colour passing

       • Permutations, commutativity, scaling

       • Approximate equivalence

       • Error bounds

  3. Accuracy considerations [Jan]

     • Hierarchical colour passing

       • Hierarchy of error bounds

       • Trade-off of accuracy and compression

     • Geometric interpretation

  4. Summary and future directions [Marcel, Tanya]

• Related Publications

  • Luc De Raedt, Angelika Kimmig, and Hannu Toivonen: ProbLog: A Probabilistic Prolog and its Application in Link Discovery. In IJCAI-07 Proceedings of 20th International Joint Conference on Artificial Intelligence, 2007

  • Norbert Fuhr: Probabilistic Datalog - A Logic for Powerful Retrieval Methods. In: SIGIR-95 Proceedings of the 18th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 1995

  • Marcel Gehrke, Ralf Möller, Tanya Braun: Taming Reasoning in Temporal Probabilistic Relational Models. In ECAI-20 Proceedings of the 24th European Conference on Artificial Intelligence, 2020

  • Manfred Jaeger: Relational Bayesian Networks. In: UAI-97 Proceedings of the 13th Conference on Uncertainty in Artificial Intelligence, 1997

  • Malte Luttermann, Jan Speller, Marcel Gehrke, Tanya Braun, Ralf Möller, and Mattis Hartwig. Approximate Lifted Model Construction. In IJCAI-25 Proc. of the 34th International Conference on Artificial Intelligence, 2025

  • Malte Luttermann, Tanya Braun, Ralf Möller, and Marcel Gehrke. Colour Passing Revisited: Lifted Model Construction with Commutative Factors. In AAAI-24 Proc. of the 38th AAAI Conference on Artificial Intelligence, 2024

  • Malte Luttermann, Johann Machemer, and Marcel Gehrke. Efficient Detection of Commutative Factors in Factor Graphs. In PGM-24 Proc. of the 12th International Conference on Probabilistic Graphical Models, 2024

  • Malte Luttermann, Johann Machemer, and Marcel Gehrke. Efficient Detection of Exchangeable Factors in Factor Graphs. In FLAIRS-24 Proc. of the 37th FLAIRS Conference, 2024

  • David Poole. First-order Probabilistic Inference. In IJCAI-03 Proceedings of the 18th International Joint Conference on Artificial Intelligence, 2003
  • Matthew Richardson and Pedro Domingos. Markov Logic Networks. In Machine Learning, 2006

  • Taisuke Sato: A Statistical Learning Method for Logic Programs with Distribution Semantics. In: Proceedings of the 12th International Conference on Logic Programming, 1995

  • Jan Speller, Malte Luttermann, Marcel Gehrke, and Tanya Braun. Compression versus Accuracy: A Hierarchy of Lifted Models. In ECAI-25 Proc. of the 28th European Conference on Artificial Intelligence, 2025

  • Jan Speller, Malte Luttermann, Marcel Gehrke, and Tanya Braun. Towards Explainability of Approximate Lifted Model Construction: A Geometric Perspective. In FCR-25 11th Workshop on Formal and Cognitive Reasoning, co-located with KI-25, 2025

  • Nima Taghipour, Daan Fierens, Jesse Davis, and Hendrik Blockeel: Lifted Variable Elimination: Decoupling the Operators from the Constraint Language. In: Journal of Artificial Intelligence Research, 47(1), 2013

  • Guy Van den Broeck, Nima Taghipour, Wannes Meert, Jesse Davis, and Luc De Raedt: Lifted Probabilistic Inference by First-order Knowledge Compilation. In: IJCAI-11 Proceedings of the 22nd International Joint Conference on Artificial Intelligence, 2011