Approximate Lifted Model Construction

Luttermann, Malte; Speller, Jan; Gehrke, Marcel; Braun, Tanya; Möller, Ralf; Hartwig, Mattis

doi:10.24963/ijcai.2025/1009

Approximate Lifted Model Construction

Malte Luttermann, Jan Speller, Marcel Gehrke, Tanya Braun, Ralf Möller, Mattis Hartwig

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 9077-9085.

https://doi.org/10.24963/ijcai.2025/1009

Keywords

Uncertainty in AI: UAI: Graphical models
Uncertainty in AI: UAI: Statistical relational AI
Uncertainty in AI: UAI: Tractable probabilistic models
Uncertainty in AI: UAI: Uncertainty representations

Abstract

Probabilistic relational models such as parametric factor graphs enable efficient (lifted) inference by exploiting the indistinguishability of objects. In lifted inference, a representative of indistinguishable objects is used for computations. To obtain a relational (i.e., lifted) representation, the Advanced Colour Passing (ACP) algorithm is the state of the art. The ACP algorithm, however, requires underlying distributions, encoded as potential-based factorisations, to exactly match to identify and exploit indistinguishabilities. Hence, ACP is unsuitable for practical applications where potentials learned from data inevitably deviate even if associated objects are indistinguishable. To mitigate this problem, we introduce the ε-Advanced Colour Passing (ε-ACP) algorithm, which allows for a deviation of potentials depending on a hyperparameter ε. ε-ACP efficiently uncovers and exploits indistinguishabilities that are not exact. We prove that the approximation error induced by ε-ACP is strictly bounded and our experiments show that the approximation error is close to zero in practice.

Malte Luttermann, Jan Speller, Marcel Gehrke, Tanya Braun, Ralf Möller, and Mattis Hartwig. 2025. Approximate Lifted Model Construction. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 9077–9085. https://doi.org/10.24963/ijcai.2025/1009

@inproceedings{ijcai2025p1009,
  title     = {Approximate Lifted Model Construction},
  author    = {Luttermann, Malte and Speller, Jan and Gehrke, Marcel and Braun, Tanya and Möller, Ralf and Hartwig, Mattis},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {9077--9085},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/1009},
  url       = {https://doi.org/10.24963/ijcai.2025/1009},
}

TY  - CPAPER
TI  - Approximate Lifted Model Construction
AU  - Luttermann, Malte
AU  - Speller, Jan
AU  - Gehrke, Marcel
AU  - Braun, Tanya
AU  - Möller, Ralf
AU  - Hartwig, Mattis
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 9077
EP  - 9085
DO  - 10.24963/ijcai.2025/1009
UR  - https://doi.org/10.24963/ijcai.2025/1009
ER  -