# Lifted Inference beyond First-Order Logic

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 50 references that are in the map.
- First posted on arXiv 22 Aug 2023.

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

- [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)
- [On Discovering Interesting Combinatorial Integer Sequences](https://mlsanity.com/paper/2302.04606/) (2023)
- [Transitive Reduction of Citation Networks](https://mlsanity.com/paper/1310.8224/) (2013)

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

- [Bridging Weighted First Order Model Counting and Graph Polynomials](https://mlsanity.com/paper/2407.11877/) (2024)
- [Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations](https://mlsanity.com/paper/2508.11515/) (2025)
- [Tractable Weighted First-Order Model Counting with Bounded Treewidth Binary Evidence](https://mlsanity.com/paper/2511.09174/) (2025)
- [A Fast Model Counting Algorithm for Two-Variable Logic with Counting and Modulo Counting Quantifiers](https://mlsanity.com/paper/2605.03391/) (2026)
- [Solving Combinatorial Counting Problems with Weighted First-Order Model Counting](https://mlsanity.com/paper/2605.24845/) (2026)

## Abstract (arXiv)

Weighted First Order Model Counting (WFOMC) is fundamental to probabilistic inference in statistical relational learning models. As WFOMC is known to be intractable in general (#P-complete), logical fragments that admit polynomial time WFOMC are of significant interest. Such fragments are called domain liftable. Recent works have shown that the two-variable fragment of first order logic extended with counting quantifiers (C2) is domain-liftable. However, many properties of real-world data, like acyclicity in citation networks and connectivity in social networks, cannot be modeled in C2, or first order logic in general. In this work, we expand the domain liftability of C2 with multiple such properties. We show that any C2 sentence remains domain liftable when one of its relations is restricted to represent a directed acyclic graph, a connected graph, a tree (resp. a directed tree) or a forest (resp. a directed forest). All our results rely on a novel and general methodology of "counting by splitting". Besides their application to probabilistic inference, our results provide a general framework for counting combinatorial structures. We expand a vast array of previous results in discrete mathematics literature on directed acyclic graphs, phylogenetic networks, etc.