Weisfeiler-Lehman algorithm

Weisfeiler Lehman graph isomorphism test

The idea is iteratively assigning a fingerprint for each node based on the previous fingerprints (attributes) of itself and its neighbors. This process is not guaranteed to converge especially in the case of regular and symmetric graphs, but when it converges, it can tell us about Graph isomorphism. Essentially, if the fingerprints differ between two graphs at any stage, we can conclude that the two graphs are not isomophic.

Using this idea, one can define Graph kernel called Weisfeiler Lehman graph kernels.

$$k(G, G') = \sum_{i=1}^{d}\lambda_d \sum_{v \in V} \sum_{v' \in V'} \delta(a(v,i), a(v', i)),$$

where $a(v,i)$ denotes the attribute (fingerprint) of vertex $v$ at $i$‘s iteration. $\lambda_d$ adjusts the importance of each subsequent iteration.

• http://blog.smola.org/post/33412570425/the-weisfeiler-lehman-algorithm-and-estimation-on

This idea is linked to many methods for Machine learning with graphs, including Graph neural network. See Morris2021Weisfeiler for a review.