# Symmetric Weighted First-Order Model Counting

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Dec 2014.

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

- [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)
- [Lifted Algorithms for Symmetric Weighted First-Order Model Sampling](https://mlsanity.com/paper/2308.08828/) (2023)
- [On Projectivity in Markov Logic Networks](https://mlsanity.com/paper/2204.04009/) (2022)
- [Lifted Inference beyond First-Order Logic](https://mlsanity.com/paper/2308.11738/) (2023)
- [Bridging Weighted First Order Model Counting and Graph Polynomials](https://mlsanity.com/paper/2407.11877/) (2024)
- [On Exact Sampling in the Two-Variable Fragment of First-Order Logic](https://mlsanity.com/paper/2302.02730/) (2023)
- [Projectivity revisited](https://mlsanity.com/paper/2207.00625/) (2022)
- [Faster Lifting for Ordered Domains with Predecessor Relations](https://mlsanity.com/paper/2507.19182/) (2025)
- [Weighted First Order Model Counting with Directed Acyclic Graph Axioms](https://mlsanity.com/paper/2302.09830/) (2023)
- [Synthesising Recursive Functions for First-Order Model Counting: Challenges, Progress, and Conjectures](https://mlsanity.com/paper/2306.04189/) (2023)
- [Towards Practical First-Order Model Counting](https://mlsanity.com/paper/2502.12278/) (2025)
- [Polynomial-Time Relational Probabilistic Inference in Open Universes](https://mlsanity.com/paper/2505.04115/) (2025)
- [Model Enumeration of Two-Variable Logic with Quadratic Delay Complexity](https://mlsanity.com/paper/2505.19648/) (2025)
- [Swift Markov Logic for Probabilistic Reasoning on Knowledge Graphs](https://mlsanity.com/paper/2210.00283/) (2022)
- [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)
- [Parallel Noising in Neural Markov Logic Networks](https://mlsanity.com/paper/2607.19126/) (2026)

## Abstract (arXiv)

The FO Model Counting problem (FOMC) is the following: given a sentence Phi in FO and a number n, compute the number of models of Phi over a domain of size n; the Weighted variant (WFOMC) generalizes the problem by associating a weight to each tuple and defining the weight of a model to be the product of weights of its tuples. In this paper we study the complexity of the symmetric WFOMC, where all tuples of a given relation have the same weight. Our motivation comes from an important application, inference in Knowledge Bases with soft constraints, like Markov Logic Networks, but the problem is also of independent theoretical interest. We study both the data complexity, and the combined complexity of FOMC and WFOMC. For the data complexity we prove the existence of an FO3 formula for which FOMC is #P1-complete, and the existence of a Conjunctive Query for which WFOMC is #P1-complete. We also prove that all γ-acyclic queries have polynomial time data complexity. For the combined complexity, we prove that, for every fragment FOk, k≥ 2, the combined complexity of FOMC (or WFOMC) is #P-complete.