# Weighted First Order Model Counting with Directed Acyclic Graph Axioms

arXiv: https://arxiv.org/abs/2302.09830 · HTML: https://mlsanity.com/paper/2302.09830/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 30 references that are in the map.
- First posted on arXiv 20 Feb 2023.

## Builds on (most cited first, 10 of 10)

- [Symmetric Weighted First-Order Model Counting](https://mlsanity.com/paper/1412.1505/) (2014)
- [Weighted First-Order Model Counting in the Two-Variable Fragment With Counting Quantifiers](https://mlsanity.com/paper/2007.05619/) (2020)
- [Skolemization for Weighted First-Order Model Counting](https://mlsanity.com/paper/1312.5378/) (2013)
- [New Liftable Classes for First-Order Probabilistic Inference](https://mlsanity.com/paper/1610.08445/) (2016)
- [Weighted model counting beyond two-variable logic](https://mlsanity.com/paper/1804.10185/) (2018)
- [Lifted Inference with Linear Order Axiom](https://mlsanity.com/paper/2211.01164/) (2022)
- [Weighted Model Counting in FO2 with Cardinality Constraints and Counting Quantifiers: A Closed Form Formula](https://mlsanity.com/paper/2110.05992/) (2021)
- [Domain Recursion for Lifted Inference with Existential Quantifiers](https://mlsanity.com/paper/1707.07763/) (2017)
- [On Projectivity in Markov Logic Networks](https://mlsanity.com/paper/2204.04009/) (2022)
- [Transitive Reduction of Citation Networks](https://mlsanity.com/paper/1310.8224/) (2013)

## Built on by (most cited first, 1 of 1)

- [Faster Lifting for Ordered Domains with Predecessor Relations](https://mlsanity.com/paper/2507.19182/) (2025)

## Abstract (arXiv)

Statistical Relational Learning (SRL) integrates First-Order Logic (FOL) and probability theory for learning and inference over relational data. Probabilistic inference and learning in many SRL models can be reduced to Weighted First Order Model Counting (WFOMC). However, WFOMC is known to be intractable (#P1- complete). Hence, logical fragments that admit polynomial time WFOMC are of significant interest. Such fragments are called domain liftable. Recent line of works have shown the two-variable fragment of FOL, extended with counting quantifiers (C2) to be domain-liftable. However, many properties of real-world data can not be modelled in C2. In fact many ubiquitous properties of real-world data are inexressible in FOL. Acyclicity is one such property, found in citation networks, genealogy data, temporal data e.t.c. In this paper we aim to address this problem by investigating the domain liftability of directed acyclicity constraints. We show that the fragment C2 with a Directed Acyclic Graph (DAG) axiom, i.e., a predicate in the language is axiomatized to represent a DAG, is domain-liftable. We present a method based on principle of inclusion-exclusion for WFOMC of C2 formulas extended with DAG axioms.