A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants
  Graph neural networks are designed to learn functions on graphs. Typically,
the relevant target functions are invariant with respect to actions by
permutations. Therefore the design of some graph neural network architectures
has been inspired by graph-isomorphism algorithms. The classical
Weisfeiler-Lehman algorithm (WL) -- a graph-isomorphism test based on color
refinement -- became relevant to the study of graph neural networks. The WL
test can be generalized to a hierarchy of higher-order tests, known as $k$-WL.
This hierarchy has been used to characterize the expressive power of graph
neural networks, and to inspire the design of graph neural network
architectures. A few variants of the WL hierarchy appear in the literature. The
goal of this short note is pedagogical and practical: We explain the
differences between the WL and folklore-WL formulations, with pointers to
existing discussions in the literature. We illuminate the differences between
the formulations by visualizing an example.
