Weisfeiler-Leman Algorithm

The -dimensional Weisfeiler-Leman algorithm is an iterative graph coloring algorithm that assigns colors to k-tuples of vertices of a finite graph. For , the initial color of such a k-tuple records the equality and adjacency relations among its coordinates. At each subsequent round, the new color records the old color together with the multiset, over all vertices , of the ordered k-tuples of colors obtained by replacing each coordinate in turn by . The process stops when no color class splits (Immerman and Sengupta 2019). The resulting stable coloring is unchanged by another refinement round. The one-dimensional Weisfeiler-Leman algorithm is commonly known as color refinement.

To compare graphs and , the algorithm is applied to their graph disjoint union. It distinguishes the graphs if the multisets of stable colors on the -tuples from and are different. Since the coloring is invariant under graph isomorphism, graphs distinguished by the algorithm cannot be isomorphic. The least for which the algorithm distinguishes from every graph not isomorphic to is the Weisfeiler-Leman dimension of (Grohe 2017).

The algorithm is named for Boris Weisfeiler and Andrei Leman (1968), who introduced the original method while reducing a finite multigraph to canonical form. Their procedure repeatedly refines colors on ordered pairs of vertices by counting two-step walks with specified color sequences. This pair refinement is the classical two-dimensional Weisfeiler-Leman algorithm. The modern -dimensional algorithm extends it from ordered pairs to k-tuples (Grohe 2017). Upon reaching the stable coloring, the adjacency matrices of its color classes span an associative algebra . This is the "algebra which appears therein" in the paper's title. Its relation to the automorphism group of was central to the authors' study.

The stable coloring produced by the two-dimensional algorithm determines a coherent configuration.