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)=i=1dλdvVvVδ(a(v,i),a(v,i)), 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)a(v,i) denotes the attribute (fingerprint) of vertex vv at ii‘s iteration. λd\lambda_d adjusts the importance of each subsequent iteration.