Relevance of Weisfeiler–Lehman Graph Isomorphism Test limitation for Graph Neural Networks

Question

Graph Neural Networks power is limited by the power of Weisfeiler–Lehman Graph Isomorphism algorithm. Quoting wikipedia:

It has been demonstrated that GNNs cannot be more expressive than the Weisfeiler–Lehman Graph Isomorphism Test. In practice, this means that there exist different graph structures (e.g., molecules with the same atoms but different bonds) that cannot be distinguished by GNNs.

What are the practical implications of this limitation? Is it an academic example providing no obstacle in real-life applications of GNNs (e.g. to drug discovery) or are there any instances in which it plays a big role? If the latter, please provide an example of such a limitation.

Answer 1

Firstly, as already stated in the Wikipedia quote: Observing that a type of GNN is as expressive as the Weisfeiler–Lehman (WL) Test, means in practice that two graphs $\mathcal{G}_1$ and $\mathcal{G}_2$ cannot be differentiated by the GNN, if the 1-WL Test cannot differentiate them. Therefore, if $\mathcal{G}_1$ and $\mathcal{G}_2$ are labelled differently, your model cannot ever learn to classify both correctly.

In real life applications, this often doesn't matter too much and Zopf et al. provide a nice analysis of that and there you can see that most datasets contain 100% distinguishable graphs. But the 1-WL-Test struggles with the Molecular data of the MUTAG dataset (s. Table II). However, it seems that most of the time 1-WL expressivity will be enough.

There is another distinction to be made here: In real-world applications, we want encodings of graphs that reflect their similarity, meaning two similar graphs $\mathcal{G}_1$ and $\mathcal{G}_2$ should be encoded as similar vectors in the embedding space. If $\mathcal{G}_1$ and $\mathcal{G}_2$ are very slightly different, the vectors should still be close by. This then provides a tool that generalizes to unseen graphs. The WL-Test cannot do this kind of encoding but the GNN can. Here it makes sense to think about expressivity of GNNs as the ability to do this smooth encoding. And one aspect of that is this upper bound of expressivity as stated by the quote you provide.

I hope that was understandable, feel free to follow up on that.