On the Expressibility of the Reconstructional Color Refinement
This is an incremental theoretical result that strengthens a known fact in graph theory and connects it to graph neural networks, potentially aiding researchers in graph algorithms and machine learning.
The paper proves that graph connectedness can be determined from vertex-deleted subgraphs even when they are considered only up to color refinement equivalence, rather than full isomorphism, strengthening a known result related to the Ulam reconstruction conjecture. This implies that connectedness is recognizable by Reconstruction Graph Neural Networks, a specific GNN architecture.
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).