# Graphs Identified by Logics with Counting

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Mar 2015.

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

- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Reconstruction for Powerful Graph Representations](https://mlsanity.com/paper/2110.00577/) (2021)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks](https://mlsanity.com/paper/2203.13913/) (2022)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [Weisfeiler and Leman Go Relational](https://mlsanity.com/paper/2211.17113/) (2022)
- [Fine-grained Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2306.03698/) (2023)
- [The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs](https://mlsanity.com/paper/2105.05911/) (2021)
- [Bridging Weighted First Order Model Counting and Graph Polynomials](https://mlsanity.com/paper/2407.11877/) (2024)
- [Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limit](https://mlsanity.com/paper/2505.00291/) (2025)
- [Local Fragments, Global Gains: Subgraph Counting using Graph Neural Networks](https://mlsanity.com/paper/2305.19659/) (2023)

## Abstract (arXiv)

We classify graphs and, more generally, finite relational structures that are identified by C2, that is, two-variable first-order logic with counting. Using this classification, we show that it can be decided in almost linear time whether a structure is identified by C2. Our classification implies that for every graph identified by this logic, all vertex-colored versions of it are also identified. A similar statement is true for finite relational structures. We provide constructions that solve the inversion problem for finite structures in linear time. This problem has previously been shown to be polynomial time solvable by Martin Otto. For graphs, we conclude that every C2-equivalence class contains a graph whose orbits are exactly the classes of the C2-partition of its vertex set and which has a single automorphism witnessing this fact. For general k, we show that such statements are not true by providing examples of graphs of size linear in k which are identified by C3 but for which the orbit partition is strictly finer than the Ck-partition. We also provide identified graphs which have vertex-colored versions that are not identified by Ck.