Qfyilyi

There are instances when WL algorithm fails. For example graphs G1 and G2 below have the same coloring after WL-1 algorithm.

However, one of these graphs is disconnected. So what are the instances of undirected connected graphs for which WL algorithm fails?

Connect all vertices to a common one.

Yes, there are non-isomorphic connected graphs that cannot be distinguished by Weisfeiler–Lehman. The following construction is due to Cai, Fürer and Immerman (An Optimal Lower Bound on the Number of Variables for Graph Identification, Combinatorica 12(4):389–410, 1992; PDF).

Take any connected, $3$-regular graph $G=(V,E)$. We will produce non-isomorphic graphs $G_parallel$ and $G_times$ from $G$, that are indistinguishable by Weisfeiler–Lehman. These will be made by producing a gadget for each vertex of $G$ and, for each edge $xyin E$, connecting the gadgets for $x$ and $y$ by a pair of parallel edges.

The vertices of $G_parallel$ are is defined as follows.

• For each $xyin E$, we create four (distinct) vertices, $a_{x,y}$, $a_{y,x}$, $b_{x,y}$ and $b_{y,x}$.




• For each $xin V$, we create a vertex $c_{x,S}$ for each odd-cardinality subset of $Gamma(x)$ (the neighbours of $x$ in $G$). So, if $x$'s neighbours are $u$, $v$ and $w$, we create vertices $c_{x,{u}}$, $c_{x,{v}}$, $c_{x,{w}}$ and $c_{x,{u,v,w}}$.

The edges of $G_parallel$ are defined as follows. For each edge $xyin E$, we add:

• the two edges $a_{x,y}a_{y,x}$ and $b_{x,y}b_{y,x}$;


• the edges $a_{x,y}c_{x,S}$ for each $S$ such that $yin S$;


• the edges $b_{x,y}c_{x,S}$ for each $S$ such that $ynotin S$.

Note that $G$ is undirected so if $xyin E$, then $yxin E$ also, and we follow the above rules twice for each edge of $G$.

Now, let $xy$ be any edge in $G$ and let $G_{xy}$ be the graph made from $G_parallel$ by deleting the edges $a_{x,y}a_{y,x}$ and $b_{x,y}b_{y,x}$ and replacing them with the "cross" edges $a_{x,y}b_{y,x}$ and $b_{x,y}a_{y,x}$. The following lemma is the key point of the construction.

Lemma 1. For any edges $uv,xyin E$, the graphs $G_{uv}$ and $G_{xy}$ are isomorphic.

Proof sketch. You can move the cross edge around the graph in the following sense. For any pair of edges $ij,jkin E$, there's an isomorphism of $G_{ij}$ that exchanges $a_{j,i}$ and $b_{j,i}$ and exchanges $a_{j,k}$ and $b_{j,k}$. This isomorphism is a permutation of the vertices $c_{j,S}$, and it fixes every other vertex in $G_{ij}$. If you draw the fragment of the graph corresponding to vertex $j$ and its incident edges, the isomorphism should be pretty obvious.

This means that $G_{ij}simeq G_{jk}$, because the isomorphism "uncrosses" the edge $ij$ and "crosses" the edge $jk$. Since $G$ is connected, it contains a path whose first edge is $uv$ and whose last edge is $xy$, and we can use the isomorphisms corresponding to each adjacent pair of edges in this path to move the cross in $G_{uv}$ to $xy$. $Box$

By Lemma 1, we're entitled to use the name $G_times$ for an arbitrary graph $G_{xy}$. We now have the graphs $G_parallel$ and $G_times$; it remains to show that they're non-isomorphic and that they're indistinguishable to Weisfeiler–Lehman.

Lemma 2. For any connected, 3-regular graph $G$, we have $G_parallel notsimeq G_times$.

Proof sketch. It turns out that the only isomorphisms of $G_parallel$ and $G_times$ are isomorphisms induced by isomorphisms of $G$, and isomorphisms of the form used in the proof of Lemma 1. But no such isomorphism can transform $G_times$ into $G_parallel$ because $G_times$ has a cross edge and $G_parallel$ does not. $Box$

Now, indistinguishability. Weisfeiler–Lehman is definable in so-called "fixed-point logic with counting." This is first-order logic plus:

• counting quantifiers: for each natural number $n$, you can write $exists^{geq n}x,varphi(x)$, meaning "There exist at least $n$ values of $x$ that satisfy $varphi$." This can already be expressed in ordinary first-order logic, just by saying that there exist distinct $x_1, dots, x_n$ that all satisfy $varphi$, but the (rather subtle) point here is that the counting quantifier only uses just one variable, whereas the "pure" first-order expression uses $n$ distinct variables.




• inductive definitions. These let you build up a relation $R$ as follows. You start with $R=emptyset$. Then, you add to $R$ all the tuples that satisfy a formula $varphi$, and keep doing that until you run out of tuples to add. $varphi$ itself can depend on $R$, so you can build up some interesting things.

In particular, you can build up an equivalence relation corresponding to the colour-classes of Weisfeiler–Lehman. The counting quantifiers let you talk about the numbe of neighbours of each colour, and the inductive definitions let you recursively refine the colouring based on the number of neighbours of each colour in the previous step.

A separator of a graph $G=(V,E)$ is a set $Ssubseteq V$ such that no component of $G-S$ has more than $|V|/2$ vertices. In the following, I say "less than about $2k$" because I'm silently translating from fixed-point logic with counting to so-called "infinitary logic with counting", which roughly doubles the number of variables. I don't remember the exact details, and it's not important enough to hunt them down.

Theorem 3. Let $varphi$ be a formula of fixed-point logic with counting, using $k$ distinct variables. If $G$ is a graph with no separator of size less than about $2k$, then $varphi$ cannot distinguish $G_parallel$ from $G_times$.

Proof sketch. Very roughly speaking, while you're evaluating the formula $varphi$ on $G_parallel$ or $G_times$, you might need to consider $k$ vertices as being the value of some variables at the current iteration of an inductive construction and $k$ more variables as being the value of the variables at the previous iteration. The fact that $G$ has no small separators means that, even if we fix those vertices, we can still move the cross around in a large component of the rest of the graph, without the formula "knowing" that we've done that, so the formula can never "see" the cross, so it can never tell the difference between the graph with the cross and the graph without it. $Box$

For any fixed $d$, $d$-dimensional Weisfeiler–Lehman can be expressed as a formula of fixed-point logic with counting, using some number $k$ of variables ($kapprox 2d$ is enough, as I recall). Since that formula can't tell the difference between the non-isomorphic graphs $G_parallel$ and $G_times$ as long as $G$ has no small separators, nor can Weisfeiler–Lehman.

_{Guess who got a PhD doing this kind of stuff...}