Weisfeiler-Leman indistinguishability of graphons

Jan Böker¹

¹RWTH Aachen University

The electronic journal of combinatorics, Tome 30 (2023) no. 4

Résumé

The color refinement algorithm is mainly known as a heuristic method for graph isomorphism testing. It has surprising but natural characterizations in terms of, for example, homomorphism counts from trees and solutions to a system of linear equations. Grebík and Rocha (2022) have recently shown how color refinement and notions that characterize it generalize to graphons, which emerged as limit objects in the theory of dense graph limits. In particular, they show that these characterizations are still equivalent in the graphon case. The $k$-dimensional Weisfeiler-Leman algorithm ($k$-WL) is a more powerful variant of color refinement that colors $k$-tuples instead of single vertices, where the terms $1$-WL and color refinement are often used interchangeably since they compute equivalent colorings. We show how to adapt the result of Grebík and Rocha to $k$-WL or, in other words, how $k$-WL and its characterizations generalize to graphons. In particular, we obtain characterizations in terms of homomorphism densities from multigraphs of bounded treewidth and linear equations. We give a simple example that parallel edges make a difference in the more general case of graphons, which means that, there, the equivalence between $1$-WL and color refinement does not hold anymore. We also show how this equivalence can be recovered by defining a variant of $k$-WL that corresponds to homomorphism densities from simple graphs of bounded treewidth.

Détail

DOI : 10.37236/10973

Classification : 05C80, 05C50, 05C60
Mots-clés : fractional isomorphism, homomorphism densities, Weisfeiler-Leman algorithm