The Weisfeiler-Leman Algorithm and Recognition of Graph Properties

Abstract

The k-dimensional Weisfeiler-Leman algorithm ($k\text {-}\mathrm {WL}$) is a very useful combinatorial tool in graph isomorphism testing. We address the applicability of $k\text {-}\mathrm {WL}$ to recognition of graph properties. Let G be an input graph with n vertices. We show that, if n is prime, then vertex-transitivity of G can be seen in a straightforward way from the output of $2\text {-}\mathrm {WL}$ on G and on the vertex-individualized copies of G. This is perhaps the first non-trivial example of using the Weisfeiler-Leman algorithm for recognition of a natural graph property rather than for isomorphism testing. On the other hand, we show that, if n is divisible by 16, then $k\text {-}\mathrm {WL}$ is unable to distinguish between vertex-transitive and non-vertex-transitive graphs with n vertices unless $k=\varOmega (\sqrt{n})$.

O. Verbitsky was supported by DFG grant KO 1053/8-1. He is on leave from the IAPMM, Lviv, Ukraine.

1 Introduction

The k-dimensional Weisfeiler-Leman algorithm ($k\text {-}\mathrm {WL}$), whose original, 2-dimensional version [20] appeared in 1968, has played a prominent role in isomorphism testing already for a half century. Given a graph G with vertex set V, $k\text {-}\mathrm {WL}$ computes a canonical coloring $\mathrm {WL}_k(G)$ of the Cartesian power $V^k$. Let $\widehat{\mathrm {WL}}_{k}(G)$ denote the multiset of colors appearing in $\mathrm {WL}_k(G)$. The algorithm decides that two graphs G and H are isomorphic if $\widehat{\mathrm {WL}}_{k}(G)=\widehat{\mathrm {WL}}_{k}(H)$, and that they are non-isomorphic otherwise. While a negative decision is always correct, Cai, Fürer, and Immerman [5] constructed examples of non-isomorphic graphs G and H with n vertices such that $\widehat{\mathrm {WL}}_{k}(G)=\widehat{\mathrm {WL}}_{k}(H)$ unless $k=\varOmega (n)$. Nevertheless, a constant dimension k suffices to correctly decide isomorphism for many special classes of graphs (when G is in the class under consideration and H is arbitrary). For example, $k=2$ is enough if G is an interval graph [10], $k=3$ is enough for planar graphs [15], and there is a constant $k=k(M)$ sufficient for all graphs not containing a given graph M as a minor [13]. Last but not least, $k\text {-}\mathrm {WL}$ is an important component in Babai’s quasipolynomial-time algorithm [3] for general graph isomorphism.

In the present paper, we initiate a discussion of the applicability of $k\text {-}\mathrm {WL}$ to recognition of graph properties rather than to testing isomorphism. That is, given a single graph G as input, we are interested in knowing which properties of G can be easily detected by looking at $\mathrm {WL}_k(G)$ or, in other words, for which decision problems the execution of $k\text {-}\mathrm {WL}$ on an input graph is a reasonable preprocessing step. Of course, some regularity properties are recognized in a trivial way. For example, G is strongly regular if and only if $2\text {-}\mathrm {WL}$ splits $V^2$ just in the diagonal $\{(u,u)\,:\,u\in V\}$, the adjacency relation of G, and the complement.

For a graph property $\mathcal {P}$, we use the same character $\mathcal {P}$ to denote also the class of all graphs possessing this property. While the multiset of canonical colors $\widehat{\mathrm {WL}}_{k}(G)$ retains the isomorphism type of the original graph G only if k is sufficiently large, the coloring $\mathrm {WL}_k(G)$ of $V^k$ does this for every k. This means that, at least implicitly, $\mathrm {WL}_k(G)$ contains the information about all properties $\mathcal {P}$ of G. It is, however, a subtle question whether any certificate of the membership of G in $\mathcal {P}$ can be extracted from $\mathrm {WL}_k(G)$ efficiently. Even when the isomorphism type of every graph in $\mathcal {P}$ is known to be identifiable by $k\text {-}\mathrm {WL}$ for some k, we can only be sure that $k\text {-}\mathrm {WL}$ distinguishes $\mathcal {P}$ from its complement, in the following sense: If $G\in \mathcal {P}$ and $H\notin \mathcal {P}$, then $\widehat{\mathrm {WL}}_{k}(G)\ne \widehat{\mathrm {WL}}_{k}(H)$. However, given the last inequality, we might never know whether $G\in \mathcal {P}$ and $H\notin \mathcal {P}$ or whether $H\in \mathcal {P}$ and $G\notin \mathcal {P}$. As a particular example, the fact that $2\text {-}\mathrm {WL}$ decides isomorphism of interval graphs or that $3\text {-}\mathrm {WL}$ decides isomorphism of planar graphs does not seem to imply, on its own, any efficient recognition algorithm for these classes.

We address the applicability of $k\text {-}\mathrm {WL}$ to recognition of properties saying that a graph is highly symmetric.

Deciding Vertex-Transitivity. A graph G is vertex-transitive if every vertex can be taken to any other vertex by an automorphism of G. It is unknown whether the class of vertex-transitive graphs is recognizable in polynomial time. The isomorphism problem for vertex-transitive graphs reduces to their recognition problem, and its complexity status is also open. In the case of graphs with a prime number p of vertices, a polynomial-time recognition algorithm is known due to Muzychuk and Tinhofer [18]. Their algorithm uses $2\text {-}\mathrm {WL}$ as preprocessing and then involves a series of algebraic-combinatorial operations to find a Cayley presentation of the input graph. It is known [19] that, if p is prime, then every vertex-transitive graph with p vertices is circulant, i.e., a Cayley graph of the cyclic group of order p. Our first result, Theorem 1, shows a very simple, purely combinatorial way to recognize vertex-transitivity of a graph G with p vertices. Indeed, vertex-transitivity can immediately be detected by looking at the outdegrees of the monochromatic digraphs in $\mathrm {WL}_2(G)$ and $\mathrm {WL}_2(G_u)$ for all copies of G with an individualized vertex u. Our algorithm takes time $O(p^4\log p)$, which is somewhat better than the running time $O(p^5\log ^2 p)$ of the algorithm presented in [18]. However, we believe that the main beneficial factor of our approach is its conceptual and technical simplicity.

Note that the research on circulant graphs has a long history; see, e.g., [2, 17]. This class of graphs can be recognized in polynomial time [7], but whether or not this can be done by means of $k\text {-}\mathrm {WL}$ is widely open. The dimension $k=2$ would clearly suffice if the algorithm could identify a cyclic order of the vertices in an input graph corresponding to its cyclic automorphism. However, it would be too naive to hope for this because such an order is, in general, not unique, not preserved by automorphisms and, hence, not canonical, even when the number of vertices is prime.

The analysis of our algorithm is based on the theory of coherent configurations (we provide a digest of main concepts in Sect. 3.1). In fact, our exposition, apart from the well-known facts on circulants of prime order, uses only several results about the schurity property of certain coherent configurations.

Lower Bounds for the WL Dimension. Since the work of Muzychuk and Tinhofer [18] the polynomial-time recognizability of vertex-transitive graphs with a prime number of vertices remains state-of-the-art in the sense that, to the best of our knowledge, no polynomial-time algorithm is currently known that recognizes vertex-transitivity on all n-vertex input graphs for infinitely many composite numbers n. Motivated by this fact, we complement our algorithmic result by exploring the limitations of the $k\text {-}\mathrm {WL}$-based combinatorial approach to vertex-transitivity. We prove that, if n is divisible by 16, then $k\text {-}\mathrm {WL}$ is unable to distinguish between vertex-transitive and non-vertex-transitive graphs with n vertices unless $k=\varOmega (\sqrt{n})$; see Theorem 7. This excludes extension of our positive result to graphs with an arbitrary number of vertices. Indeed, since the combination of $2\text {-}\mathrm {WL}$ with vertex individualization is subsumed by $3\text {-}\mathrm {WL}$, such an extension would readily imply that $3\text {-}\mathrm {WL}$ distinguishes any vertex-transitive graph from any non-vertex-transitive graph, contradicting our lower bound $k=\varOmega (\sqrt{n})$. This bound as well excludes any other combinatorial approach to recognizing vertex-transitivity as long as it is based solely on $k\text {-}\mathrm {WL}$ for a fixed dimension k. It shows that, if such an algorithm succeeds on the n-vertex input graphs for n in a set S, then S can contain only finitely many multiples of 16.

Our lower bound is based on the Cai-Fürer-Immerman construction [5], which converts a template graph F into a pair of non-isomorphic graphs G and H indistinguishable by $k\text {-}\mathrm {WL}$. To prove our lower bound for the WL dimension, we have to ensure that G is vertex-transitive and H is not. This is faced with two technical complications. First, the original CFI gadget [5, Fig. 3] involves vertices of different degrees and, hence, destroys vertex-transitivity even when the template graph F is vertex-transitive. This can be overcome by using a modified version of the CFI gadget with all vertex degrees equal, which apparently first appeared in [9]; see also the survey in [12]. Note that this approach has already been used to analyze vertex-transitivity of coherent configurations; see Evdokimov’s thesis [8].

The second point is more subtle. The CFI construction replaces each vertex of the template graph F with a cell of new vertices, and vertices in different cells receive different colors. In many contexts the vertex coloring can be removed by using additional gadgets, but this is hardly possible without losing the vertex-transitivity. The vertex colors constrain the automorphisms of the CFI graphs G and H and ensure that these graphs are non-isomorphic. We establish rather general conditions on a template graph F under which the CFI graphs retain their functionality even without colors. This result of independent interest provides a very straight way of making the CFI graphs colorless, which can be used in any of their numerous applications.

The analysis of the regularized and discolored version of the CFI construction and the proof of our lower bound (Theorem 7) can be found in a long version of this paper [11].

2 Notation and Definitions

We denote the vertex set of a graph G by V(G). The notation $\mathrm {Aut}(G)$ stands for the automorphism group of G.

Cayley Graphs. Let $\varGamma$ be a group and Z be a set of non-identity elements of $\varGamma$ such that $Z^{-1}=Z$, that is, any element belongs to Z only together with its inverse. The Cayley graph $\mathrm {Cay}(\varGamma ,Z)$ has the elements of $\varGamma$ as vertices, where x and y are adjacent if $x^{-1}y\in Z$. This graph is connected if and only if the connection set Z is a generating set of $\varGamma$. Every Cayley graph is obviously vertex-transitive.

The Weisfeiler-Leman Algorithm. The original version of the Weisfeiler-Leman algorithm, $2\text {-}\mathrm {WL}$, operates on the Cartesian square $V^2$ of the vertex set of an input graph G. Below it is supposed that G is undirected. We also suppose that G is endowed with a vertex coloring c, that is, each vertex $u\in V$ is assigned a color denoted by c(u). The case of uncolored graphs is covered by assuming that c(u) is the same for all u. $2\text {-}\mathrm {WL}$ starts by assigning each pair $(u,v)\in V^2$ the initial color $\mathrm {WL}_{2}^{0}(u,v)=( type , c(u), c(v))$, where type takes on one of three values, namely edge if u and v are adjacent, nonedge if distinct u and v are non-adjacent, and loop if $u=v$. The coloring of $V^2$ is then modified step by step. The $(r+1)$-th coloring is computed as

$$\begin{aligned} \mathrm {WL}_{2}^{r+1}(u,v)=\{\!\!\{(\mathrm {WL}_{2}^{r}(u,w),\,\mathrm {WL}_{2}^{r}(w,v))\}\!\!\}_{w\in V}, \end{aligned}$$

(1)

where $\{\!\!\{\}\!\!\}$ denotes the multiset. In words, the new color of a pair uv is a “superposition” of all old color pairs observable along the extensions of uv to a triangle uwv. Let $\mathcal {S}^r$ denote the partition of $V^2$ determined by the coloring $\mathrm {WL}_{2}^{r}(\cdot ,\cdot )$. It is easy to notice that $\mathrm {WL}_{2}^{r+1}(u,v)=\mathrm {WL}_{2}^{r+1}(u',v')$ implies $\mathrm {WL}_{2}^{r}(u,v)=\mathrm {WL}_{2}^{r}(u',v')$, which means that $\mathcal {S}^{r+1}$ is finer than or equal to $\mathcal {S}^r$. It follows that the partition stabilizes starting from some step $t\le n^2$, where $n=|V|$, that is, $\mathcal {S}^{t+1}=\mathcal {S}^t$, which implies that $\mathcal {S}^r=\mathcal {S}^t$ for all $r\ge t$. As the stabilization is reached, $2\text {-}\mathrm {WL}$ terminates and outputs the coloring $\mathrm {WL}_{2}^{t}(\cdot ,\cdot )$, which will be denoted by $\mathrm {WL}_2(\cdot ,\cdot )$.

Note that the length of $\mathrm {WL}_{2}^{r}(u,v)$ grows exponentially as r increases. The exponential blow-up is remedied by renaming the colors after each step.

Let $\phi$ be an automorphism of G. A simple induction on r shows that $\mathrm {WL}_{2}^{r}(\phi (u), \phi (v))=\mathrm {WL}_{2}^{r}(u,v)$ for all r and, hence

$$\begin{aligned} \mathrm {WL}_2(\phi (u),\phi (v))=\mathrm {WL}_2(u,v). \end{aligned}$$

(2)

In particular, if G is vertex-transitive, then the color $\mathrm {WL}_2(u,u)$ is the same for all $u\in V$. If the last condition is fulfilled, we say that $2\text {-}\mathrm {WL}$ does not split the diagonal on G, where by the diagonal we mean the set of all loops (u, u).

In general, the automorphism group $\mathrm {Aut}(G)$ of the graph G acts on the Cartesian square $V(G)^2$, and the orbits of this action are called 2-orbits of $\mathrm {Aut}(G)$. Thus, the partition of $V(G)^2$ into 2-orbits is finer than or equal to the stable partition $\mathcal {S}=\mathcal {S}^t$ produced by $2\text {-}\mathrm {WL}$.

3 Vertex-Transitivity on a Prime Number of Vertices

We begin with a few simple observations about the output produced by $2\text {-}\mathrm {WL}$ on an input graph G. Recall that in this paper we restrict our attention to undirected graphs. Even though G is undirected, the equality $\mathrm {WL}_2(u,v)=\mathrm {WL}_2(v,u)$ need not be true in general. Thus, the output of $2\text {-}\mathrm {WL}$ on G can naturally be seen as a complete colored directed graph on the vertex set V(G), which we denote by $\mathrm {WL}_2(G)$. That is, $\mathrm {WL}_2(G)$ contains every pair $(u,v)\in V(G)^2$ as an arc, i.e., a directed edge, and this arc has the color $\mathrm {WL}_2(u,v)$ returned by $2\text {-}\mathrm {WL}$. We will see $\mathrm {WL}_2(G)$ as containing no loops, but instead we assign each vertex u the color $\mathrm {WL}_2(u,u)$. Any directed subgraph of $\mathrm {WL}_2(G)$ formed by all arcs of the same color is called a constituent digraph.

Let (u, v) and $(u',v')$ be arcs of a constituent digraph C of $\mathrm {WL}_2(G)$. Note that the vertices u and $u'$ must be equally colored in $\mathrm {WL}_2(G)$. Indeed, since the color partition of $\mathrm {WL}_2(G)$ is stable, there must exist w such that $(\mathrm {WL}_2(u',w),\mathrm {WL}_2(w, v'))=(\mathrm {WL}_2(u,u),\mathrm {WL}_2(u,v))$. The equality $\mathrm {WL}_2(u',w)=\mathrm {WL}_2(u,u)$ can be fulfilled only by $w=u'$ because any non-loop $(u',w)$ is initially colored differently from the loop (u, u) and, hence, they are colored differently after all refinements.

Note also that, if u and v are equally colored in $\mathrm {WL}_2(G)$, then they have the same outdegree in every constituent digraph C; in particular, they simultaneously belong or do not belong to V(C). Otherwise, contrary to the assumption that the color partition of $\mathrm {WL}_2(G)$ is stable, the loops (u, u) and (v, v) would receive different colors in another refinement round of $2\text {-}\mathrm {WL}$. It follows that for each constituent digraph C there is an integer $d\ge 1$ such that all vertices in C with non-zero outdegree have outdegree d. We call d the outdegree of C.

Let $u\in V(G)$. A vertex-individualized graph $G_u$ is obtained from G by assigning the vertex u a special color, which does not occur in G. If G is vertex-transitive, then all vertex-individualized copies of G are obviously isomorphic.

Fig. 1.

The output of $2\text {-}\mathrm {WL}$ on input $G=\overline{C_7}$ and on its vertex-individualized copy $G_0$. In this example, the arcs between two equally colored vertices u and v (those with $\mathrm {WL}_2(u,u)=\mathrm {WL}_2(v,v)$) have equal colors in both directions, that is, $\mathrm {WL}_2(u,v)=\mathrm {WL}_2(v,u)$. If u and v are colored distinctly, then clearly $\mathrm {WL}_2(u,v)\ne \mathrm {WL}_2(v,u)$. As a general fact, $\mathrm {WL}_2(u,v)=\mathrm {WL}_2(u',v')$ exactly when $\mathrm {WL}_2(v,u)=\mathrm {WL}_2(v',u')$. This allows us to improve the visualization by showing only one of the two mutually reversed colors. (Color figure online)

Consider now a simple and still instructive example. Let $G=\overline{C_7}$ be the complement of the cycle graph on seven vertices $0,1,\ldots ,6$ passed in this order. It is not hard to see that $2\text {-}\mathrm {WL}$ splits $V(G)^2$ into the four 2-orbits of $\mathrm {Aut}(G)$; the diagonal $\{(u,u)\,:\,u\in V(G)\}$ is one of them. Note that the three constituent digraphs of $\mathrm {WL}_2(G)$ are of the same degree 2; see Fig. 1. Applying $2\text {-}\mathrm {WL}$ to the vertex-individualized graph $G_0$, it can easily be seen that $2\text {-}\mathrm {WL}$ again splits $V(G)^2$ into the 2-orbits of $\mathrm {Aut}(G_0)$. Note that $\mathrm {WL}_2(G_0)$ also has exactly three constituent digraphs of outdegree 2, while all other constituent digraphs of $\mathrm {WL}_2(G_0)$ have outdegree 1. We see that the outdegrees of the constituent digraphs for G and its vertex-individualized copies are distributed similarly. This similarity proves to be a characterizing property of vertex-transitive graphs on a prime number of vertices.

Theorem 1

Let p be a prime, and G be a graph with p vertices. Suppose that G is neither complete nor empty. Then G is vertex-transitive if and only if the following conditions are true:

• 1. If run on G, $2\text {-}\mathrm {WL}$ does not split the diagonal, that is, all vertices in $\mathrm {WL}_2(G)$ are equally colored.

• 2. All constituent digraphs of $\mathrm {WL}_2(G)$ have the same outdegree $d>1$ and, hence, there are $\frac{p-1}{d}$ constituent digraphs.

• 3. For every $u\in V(G)$, exactly $\frac{p-1}{d}$ constituent digraphs in $\mathrm {WL}_2(G_u)$ have outdegree d, and all others have outdegree 1.

Since the color partition of $\mathrm {WL}_2(G)$ for a p-vertex graph G can be computed in time $O(p^3\log p)$ [14], Conditions 1–3 can be verified in time $O(p^4\log p)$, which yields an algorithm of this time complexity for recognition of vertex-transitivity of graphs with a prime number of vertices.

As it will be discussed in Remark 6 below, there are graphs G and H with a prime number of vertices such that G is vertex-transitive, H is not, and still they are indistinguishable by $2\text {-}\mathrm {WL}$. This implies that Theorem 1 is optimal in that it uses as small WL dimension as possible and, also, that the condition involving the vertex individualization cannot be dropped. Note that $1\text {-}\mathrm {WL}$, which stands for the classical degree refinement, does not suffice even when run on G and all $G_u$ because the output of $1\text {-}\mathrm {WL}$ on these inputs is subsumed by the output of $2\text {-}\mathrm {WL}$ on G alone.

Theorem 1 is proved in Subsect. 3.2. The next subsection provides the necessary preliminaries.

3.1 Coherent Configurations

A detailed treatment of the material presented below can be found in [6]. The stable partition $\mathcal {S}_G$ of $V(G)^2$ produced by $2\text {-}\mathrm {WL}$ on an input graph G has certain regularity properties, which are equivalent to saying that the pair $(V,\mathcal {S})$ forms a coherent configuration. This concept is defined as follows.

A coherent configuration $\mathcal {X}=(V,\mathcal {S})$ is formed by a set V, whose elements are called points, and a partition $\mathcal {S}=\{S_1,\ldots ,S_m\}$ of the Cartesian square $V^2$, that is, $\bigcup _{i=1}^mS_i=V^2$ and any two $S_i$ and $S_j$ are disjoint. An element $S_i$ of $\mathcal {S}$ is referred to as a basis relation of $\mathcal {X}$. The partition $\mathcal {S}$ has to satisfy the following three conditions:

• (A) If a basis relation $S\in \mathcal {S}$ contains a loop (u, u), then all pairs in S are loops.

• (B) For every $S\in \mathcal {S}$, the transpose relation $S^*=\{(v,u)\,:\,(u,v)\in S\}$ is also in $\mathcal {S}$.

• (C) For each triple $R,S,T\in \mathcal {S}$, the number

  $$p(u,v)=|\{w\,:\,(u,w)\in R,\,(w,v)\in S\}|$$

  for a pair $(u,v)\in T$ does not depend on the choice of this pair in T.

In other words, if $\mathcal {S}$ is seen as a color partition of $V^2$, then such a coloring is stable under $2\text {-}\mathrm {WL}$ refinement.

We describe two important sources of coherent configurations. Let $\mathcal {T}$ be an arbitrary family of subsets of the Cartesian square $V^2$. There exists a unique coarsest partition $\mathcal {S}$ of $V^2$ such that every $T\in \mathcal {T}$ is a union of elements of $\mathcal {S}$ and $\mathcal {X}=(V,\mathcal {S})$ is a coherent configuration; see [6, Section 2.6.1]. We call $\mathcal {X}=(V,\mathcal {S})$ the coherent closure of $\mathcal {T}$ and denote it by $Cl (\mathcal {T})$.

Given a vertex-colored undirected graph G on the vertex set V, let $\mathcal {T}$ consist of the set of the pairs $(u,v)\in V^2$ such that $\{u,v\}$ is an edge of G and the sets of loops (u, u) for all vertices u of the same color in G. Then $Cl (\mathcal {T})$ is exactly the stable partition produced by $2\text {-}\mathrm {WL}$ on input G. We denote this coherent configuration by $Cl (G)$.

Given a coherent configuration $\mathcal {X}=(V,\mathcal {S})$ and a point $u\in V$, the coherent configuration $\mathcal {X}_u= Cl (\mathcal {S}\cup \{\{(u,u)\}\})$ is called a one-point extension of $\mathcal {X}$. This concept is naturally related to the notion of a vertex-individualized graph, in that

$$\begin{aligned} Cl (G_u)= Cl (G)_u. \end{aligned}$$

(3)

Another source of coherent configurations is as follows. Let K be a permutation group on a set V. Denote the set of 2-orbits of K by $\mathcal {S}$. Then $\mathcal {X}=(V,\mathcal {S})$ is a coherent configuration, which we denote by $\mathrm {Inv}(K)$. Coherent configurations obtained in this way are said to be schurian.

We define an automorphism of a coherent configuration $\mathcal {X}=(V,\mathcal {S})$ as a bijection $\alpha$ from V onto itself such that, for every $S\in \mathcal {S}$ and every $(u,v)\in S$, the pair $(\alpha (u),\alpha (v))$ also belongs to S. The group of all automorphisms of $\mathcal {X}$ is denoted by $\mathrm {Aut}(\mathcal {X})$. A coherent configuration $\mathcal {X}$ is schurian if and only if

$$\begin{aligned} \mathcal {X}=\mathrm {Inv}(\mathrm {Aut}(\mathcal {X})). \end{aligned}$$

(4)

Note also that the connection between the coherent closure of a graph and $2\text {-}\mathrm {WL}$ implies that

$$\begin{aligned} \mathrm {Aut}( Cl (G))=\mathrm {Aut}(G). \end{aligned}$$

(5)

A set of points $X\subseteq V$ is called a fiber of $\mathcal {X}$ if the set of loops $\{(x,x)\,:\,x\in X\}$ is a basis relation of $\mathcal {X}$. Denote the set of all fibers of $\mathcal {X}$ by $F(\mathcal {X})$. By Property A, $F(\mathcal {X})$ is a partition of V. Property C implies that for every basis relation S of $\mathcal {X}$ there are, not necessarily distinct, fibers X and Y such that $S\subseteq X\times Y$. We use the notation $N_{S}(x)=\{y\,:\,(x,y)\in S\}$ for the set of all points in Y that are in relation S with x. Note that $|N_{S}(x)|=|N_{S}(x')|$ for any $x,x'\in X$. We call this number the valency of S. If every basis relation S of $\mathcal {X}$ has valency 1, then $\mathcal {X}$ is called semiregular.

Proposition 2

(see [6, Exercise 2.7.35]). A semiregular coherent configuration is schurian.

Given a set of points $U\subseteq V$ that is a union of fibers, let $\mathcal {S}_U$ denote the set of all basis relations $S\in \mathcal {S}$ such that $S\subseteq X\times Y$ for some, not necessarily distinct, fibers $X\subseteq U$ and $Y\subseteq U$. As easily seen, $\mathcal {X}_U=(U,\mathcal {S}_U)$ is a coherent configuration.

If a coherent configuration has a single fiber, it is called association scheme.

3.2 Proof of Theorem 1

Necessity. Given a vertex-transitive graph G with p vertices, where p is prime, we have to check Conditions 1–3. Condition 1 follows immediately from vertex-transitivity; see the discussion in the end of Sect. 2. For Condition 2, we use two basic results on vertex-transitive graphs with a prime number of vertices. First, every such graph is isomorphic to a circulant graph, i.e., a Cayley graph of a cyclic group, because every transitive group of permutations of a set of prime cardinality p contains a p-cycle (Turner [19]). Let $\mathbb {F}_p$ denote the p-element field, $\mathbb {F}_p^+$ its additive group, i.e., the cyclic group of order p, and $\mathbb {F}_p^\times$ its multiplicative group, which is isomorphic to the cyclic group of order $p-1$. Another useful fact (Alspach [1]) is that, if a set $Z\subset \mathbb {F}_p$ is non-empty and $Z\ne \mathbb {F}_p^\times$, then the automorphism group of the circulant graph $\mathrm {Cay}(\mathbb {F}_p^+,Z)$ consists of the permutations

$$\begin{aligned} x\mapsto ax+b,\,x\in \mathbb {F}_p,\text { for all }a\in M,\,b\in \mathbb {F}_p^+, \end{aligned}$$

(6)

where $M=M(Z)$ is the largest subgroup of $\mathbb {F}_p^\times$ of even order such that Z is a union of cosets of M. This subgroup is well defined because the condition $Z=-Z$ implies that Z is split into pairs $\{z,-z\}$ and, hence, is a union of cosets of the multiplicative subgroup $\{1,-1\}$. For example, $\overline{C_7}=\mathrm {Cay}(\mathbb {F}_7^+,\{2,3,4,5\})$ and $M(\{2,3,4,5\})=\{1,-1\}$. Without loss of generality we assume that $G=\mathrm {Cay}(\mathbb {F}_p^+,Z)$ and denote $K=\mathrm {Aut}(G)$.

Let $\mathcal {X}=(\mathbb {F}_p^+,\mathcal {S})$ be the coherent closure of G. Recall that $\mathcal {S}$ is exactly the stable partition of $V(G)^2$ produced by $2\text {-}\mathrm {WL}$ on input G. The irreflexive basis relations of $\mathcal {X}$ are exactly the constituent digraphs of $\mathrm {WL}_2(G)$, and we have to prove that all of them have the same valency.

Condition 1 says that $\mathcal {X}$ is an association scheme. In general, not all association schemes with a prime number of points are schurian (see, e.g., [6, Section 4.5]). Nevertheless, the theorem by Leung and Man on the structure of Schur rings over cyclic groups implies the following fact.

Proposition 3

(see [6, Theorem 4.5.1]). Let $\mathcal {X}=(V,\mathcal {S})$ be an association scheme with a prime number of points. If $\mathrm {Aut}(\mathcal {X})$ acts transitively on V, then $\mathcal {X}$ is schurian.

By Equality (5), $\mathrm {Aut}(\mathcal {X})=K$. Since the group K is transitive, Proposition 3 implies that $\mathcal {X}$ is schurian, and we have $\mathcal {X}=\mathrm {Inv}(K)$ by Equality (4). This yields Condition 2 for $d=|M|$. Indeed, every irreflexive basis relation $S\in \mathcal {S}$ has valency |M|. To see this, it is enough to count the number of pairs (0, y) in S. Fix an arbitrary pair $(0,y)\in S$. A pair $(0,y')$ is in the 2-orbit containing (0, y) if and only if $y'=ay$ for $a\in M$, for which we have |M| possibilities.

It remains to prove Condition 3. By vertex-transitivity, all vertex-individualized copies of G are isomorphic and, therefore, it is enough to consider $G_0$. We have to count the frequencies of valencies in $\mathcal {X}_0$. Note that $\mathcal {X}_0= Cl (G_0)$ by Equality (3).

It is generally not true that a one-point extension of a schurian coherent configuration is schurian; see [6, Section 3.3.1]. Luckily, this is the case in our setting.

Proposition 4

(see [6, Theorem 4.4.14]). If $\mathcal {X}=\mathrm {Inv}(K)$, where K is the group of permutations of the form (6) for a subgroup M of $\mathbb {F}_p^\times$, then the one-point extension $\mathcal {X}_0$ is schurian.

Taking into account Equality (5), we have

$$ \mathrm {Aut}(\mathcal {X}_0)=\mathrm {Aut}( Cl (G_0))=\mathrm {Aut}(G_0)=\mathrm {Aut}(G)_0=K_0, $$

where $K_0$ is the one-point stabilizer of 0 in K, that is, the subgroup of K consisting of all permutations $\alpha \in K$ such that $\alpha (0)=0$. Obviously, $K_0=\{x\mapsto ax,\,x\in \mathbb {F}_p\}_{a\in M}$.

Let S be a 2-orbit of $K_0$. If S contains a pair (0, y), then it consists of all pairs $(0,y')$ for $y'\in My$ and, hence, has valency |M|. If S contains a pair (z, y) with $z\ne 0$ and $y\ne z$, then (z, y) is the only element of S with the first coordinate z, and S has valency 1. The proof of Condition 3 is complete.

Sufficiency. Let G be a graph satisfying Conditions 1–3 stated in the theorem. Let $\mathcal {X}= Cl (G)$. Condition 1 says that $\mathcal {X}$ is an association scheme. By Equality (5), it suffices to prove that the group $\mathrm {Aut}(\mathcal {X})$ is transitive. The proof is based on the following lemma.

Lemma 5

(see [16, Theorem 7.1]). Let $\mathcal {X}=(V,\mathcal {S})$ be an association scheme. Suppose that the following two conditions are true for every point $u\in V$:

• (I) the coherent configuration $(\mathcal {X}_u)_ {V\setminus \{u\}}$ is semiregular, and

• (II) $F(\mathcal {X}_u)=\{N_{S}(u)\,:\,S\in \mathcal {S}\}$.

Then the group $\mathrm {Aut}(\mathcal {X})$ acts transitively on V.

Let u be an arbitrary vertex of G. By Equality (3), $\mathcal {X}_u= Cl (G_u)$. Now, it suffices to derive Conditions I–II in the lemma from Conditions 1–3 in the theorem.

For a fiber $X\in F(\mathcal {X}_u)$, note that $\{u\}\times X$ must be a basis relation of $\mathcal {X}_u$. Since this relation has valency |X|, Condition 3 implies that every fiber in $F(\mathcal {X}_u)$ is either a singleton or consists of $d\ge 2$ points. Denote the number of singletons in $F(\mathcal {X}_u)$ by a. Besides of them, $F(\mathcal {X}_u)$ contains $(p-a)/d$ fibers of size d.

For every $X,Y\in F(\mathcal {X}_u)$ with $|X|=1$ and $|Y|=d$, $X\times Y$ is a basis relation of $\mathcal {X}_u$ of valency d. It follows from Condition 3 that

$$ \frac{p-1}{d}\ge \frac{a(p-a)}{d}. $$

Therefore, $p-1\ge a(p-a)$ or, equivalently, $p(a-1)\le (a-1)(a+1)$. Assume for a while that $a>1$. It immediately follows that $a\ge p-1$. Since the equality $a=p-1$ is impossible, we conclude that $a=p$. However, this implies that $d=1$, a contradiction. Thus, $a=1$. Consequently, every fiber of the coherent configuration $\mathcal {X}'=(\mathcal {X}_u)_ {V\setminus \{u\}}$ is of cardinality d, and $|F(\mathcal {X}')|=(p-1)/d$.

Let S be a basis relation of $\mathcal {X}$. If S is reflexive, then $N_{S}(u)=\{u\}$. If S is irreflexive, then $N_{S}(u)$ must be a union of fibers in $F(\mathcal {X}')$. By Condition 2, the number of irreflexive basis relations in $\mathcal {S}$ is $(p-1)/d$. It follows that $N_{S}(u)$ actually coincides with one of the fibers of $\mathcal {X}'$. This proves Condition II.

Since $\mathcal {X}_u$ contains $(p-1)/d$ basis relations of the kind $\{u\}\times X$ for $X\in F(\mathcal {X}')$, Condition 3 implies that every basis relation of $\mathcal {X}'$ is of valency 1, yielding Condition I.

The proof of Theorem 1 is complete.

Remark 6

We now argue that there is a vertex transitive graph G and a non-vertex-transitive graph H such that G and H are indistinguishable by $2\text {-}\mathrm {WL}$. Recall that a strongly regular graph with parameters $(n,d,\lambda ,\mu )$ is an n-vertex d-regular graph where every two adjacent vertices have $\lambda$ common neighbors, and every two non-adjacent vertices have $\mu$ common neighbors. As easily seen, two strongly regular graphs with the same parameters are indistinguishable by $2\text {-}\mathrm {WL}$, and our example will be given by G and H of this kind. Let p be a prime (or a prime power) such that $p\equiv 1\pmod 4$. The Paley graph on p vertices is the Cayley graph $\mathrm {Cay}(\mathbb {F}_p^+,Y_p)$ where $Y_p$ is the subgroup of $\mathbb {F}_p^\times$ formed by all quadratic residues modulo p. The assumption $p\equiv 1\pmod 4$ ensures that $-1$ is a quadratic residue modulo p and, hence, $Y_p=-Y_p$. The Paley graph on p vertices is strongly regular with parameters $(p,\frac{p-1}{2},\frac{p-5}{4},\frac{p-1}{4})$.

Let G be the Paley graph on 29 vertices. It is known (Bussemaker and Spence; see, e.g., [4, Section 9.9]) that there are 40 other strongly regular graphs with parameters (29, 14, 6, 7). Let H be one of them. We have only to show that H is not vertex-transitive. Otherwise, by Turner’s theorem [19] this would be a circulant graph, that is, we would have $H=\mathrm {Cay}(\mathbb {F}_p^+,Z)$ for some connection set Z. In this case, the coherent closure $Cl (H)$ must be schurian by Proposition 3. Since H is strongly regular, $2\text {-}\mathrm {WL}$ colors all pairs of adjacent vertices uniformly and, therefore, they form a 2-orbit of $\mathrm {Aut}(H)$. It follows that the stabilizer $\mathrm {Aut}(H)_0$ acts transitively on N(0), the neighborhood of 0 in H. The aforementioned result of Alspach [1], implies that Z is the subgroup of $\mathbb {F}_p^\times$ of order $(p-1)/2$, i.e., $M=Z$ in (6). This means that $Z=Y_p$ and $H=G$, a contradiction.

4 A Lower Bound for the WL Dimension

We now state a negative result on the recognizability of vertex-transitivity by $k\text {-}\mathrm {WL}$. We begin with a formal definition of the k-dimensional algorithm. Let $k\ge 2$. Given a graph G with vertex set V as input, $k\text {-}\mathrm {WL}$ operates on $V^k$. The initial coloring of ${\bar{u}}=(u_1,\ldots ,u_k)$ encodes the equality type of this k-tuple and the ordered isomorphism type of the subgraph of G induced by the vertices $u_1,\ldots ,u_k$. The color refinement is performed similarly to (1). Specifically, $k\text {-}\mathrm {WL}$ iteratively colors $V^k$ by $\mathrm {WL}_{k}^{r+1}({\bar{u}})=\{\!\!\{ (\mathrm {WL}_{k}^{r}({\bar{u}}_1^w),\dots ,\mathrm {WL}_{k}^{r}({\bar{u}}_k^w)) \}\!\!\}{w\in V(G)}$, where ${\bar{u}}_i^w=(u_1,\dots ,u_{i-1},w,u_{i+1},\dots ,u_k)$. If G has n vertices, the color partition stabilizes in $t\le n^k$ rounds, and $k\text {-}\mathrm {WL}$ outputs the coloring $\mathrm {WL}_k(\cdot )=\mathrm {WL}_{k}^{t}(\cdot )$.

We say that $k\text {-}\mathrm {WL}$ distinguishes graphs G and H if the final color palettes are different for G and H, that is, $\{\!\!\{\mathrm {WL}_k({\bar{u}})\}\!\!\}{{\bar{u}}\in V(G)^k}\ne \{\!\!\{\mathrm {WL}_k({\bar{u}})\}\!\!\}{{\bar{u}}\in V(H)^k}$ (note that color renaming in each refinement round must be performed on G and H synchronously).

Theorem 7

1. :

For every n divisible by 16 there are n-vertex graphs G and H such that G is vertex-transitive, H is not, and G and H are indistinguishable by $k\text {-}\mathrm {WL}$ as long as $k\le 0.01\,\sqrt{n}$.

2. :

For infinitely many n there are n-vertex graphs G and H such that G is vertex-transitive, H is not, and G and H are indistinguishable by $k\text {-}\mathrm {WL}$ as long as $k\le 0.001\,n$.

5 Concluding Discussion

We have suggested a new, very simple combinatorial algorithm recognizing, in polynomial time, vertex-transitivity of graphs with a prime number of vertices. The algorithm consists, in substance, in running $2\text {-}\mathrm {WL}$ on an input graph and all its vertex-individualized copies. This is perhaps the first non-trivial example of using the Weisfeiler-Leman algorithm for recognition of a natural graph property rather than for isomorphism testing.

One can consider another, conceptually even simpler approach. If an input graph G is vertex-transitive, then $k\text {-}\mathrm {WL}$ colors all diagonal k-tuples $(u,\ldots ,u)$, $u\in V(G)$, in the same color. Is this condition for a possibly large, but fixed k sufficient to claim vertex-transitivity? In general, a negative answer immediately follows from Theorem 7. Does there exist a fixed dimension k such that the answer is affirmative for graphs with a prime number of vertices? This is apparently a hard question; it seems that we cannot even exclude that $k=3$ suffices.

Another interesting question is whether $k\text {-}\mathrm {WL}$ is able to efficiently recognize vertex-transitivity on n-vertex input graphs for n in a larger range than the set of primes. The lower bound of Theorem 7 excludes this only for n divisible by 16, in particular, for the range of n of the form 16p for a prime p. Can $k\text {-}\mathrm {WL}$ be successful on the inputs with 2p vertices? Conversely, can the negative result of Theorem 7 be extended to a larger range of n?¹

Finally, we remark that the results similar to Theorems 1 and 7 can be obtained for recognition of arc-transitivity. We refer an interested reader to a long version of this paper [11].