# Graded modal logic and counting bisimulation

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2019.

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

- [The Logic of Graph Neural Networks](https://mlsanity.com/paper/2104.14624/) (2021)
- [Expressiveness and Approximation Properties of Graph Neural Networks](https://mlsanity.com/paper/2204.04661/) (2022)
- [A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs](https://mlsanity.com/paper/2302.02209/) (2023)
- [Link Prediction with Relational Hypergraphs](https://mlsanity.com/paper/2402.04062/) (2024)
- [Understanding Expressivity of GNN in Rule Learning](https://mlsanity.com/paper/2303.12306/) (2023)
- [The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic](https://mlsanity.com/paper/2505.08021/) (2025)
- [Logical Characterizations of GNNs with Mean Aggregation](https://mlsanity.com/paper/2507.18145/) (2025)
- [Halting Recurrent GNNs and the Graded μ-Calculus](https://mlsanity.com/paper/2505.11050/) (2025)
- [Are Targeted Messages More Effective?](https://mlsanity.com/paper/2403.06817/) (2024)
- [Unifying approach to uniform expressivity of graph neural networks](https://mlsanity.com/paper/2602.18409/) (2026)
- [Graph Learning via Logic-Based Weisfeiler-Leman Variants and Tabularization](https://mlsanity.com/paper/2508.10651/) (2025)
- [Enhancing Logical Expressiveness in Graph Neural Networks via Path-Neighbor Aggregation](https://mlsanity.com/paper/2511.07994/) (2025)
- [Structural Preservation and the Logical Expressiveness of Graph Neural Networks](https://mlsanity.com/paper/2606.17882/) (2026)

## Abstract (arXiv)

This note sketches the extension of the basic characterisation theorems as the bisimulation-invariant fragment of first-order logic to modal logic with graded modalities and matching adaptation of bisimulation. We focus on showing expressive completeness of graded multi-modal logic for those first-order properties of pointed Kripke structures that are preserved under counting bisimulation equivalence among all or among just all finite pointed Kripke structures.