# On the Expressibility of the Reconstructional Color Refinement

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 22 references that are in the map.
- First posted on arXiv 13 Jun 2024.

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

- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [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)
- [Using Color Refinement to Boost Enumeration and Counting for Acyclic CQs of Binary Schemas](https://mlsanity.com/paper/2405.12358/) (2024)

## Abstract (arXiv)

One of the most basic facts related to the famous Ulam reconstruction conjecture is that the connectedness of a graph can be determined by the deck of its vertex-deleted subgraphs, which are considered up to isomorphism. We strengthen this result by proving that connectedness can still be determined when the subgraphs in the deck are given up to equivalence under the color refinement isomorphism test. Consequently, this implies that connectedness is recognizable by Reconstruction Graph Neural Networks, a recently introduced GNN architecture inspired by the reconstruction conjecture (Cotta, Morris, Ribeiro 2021).