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.