The Weisfieler-Lehman (WL) algorithms are a family of algorithms that are one of the most successful frameworks for approximate isomorphism testing
Steps of the WL algorithm:
- Given two graphs G1 and G2, assign an initial label to each node (this is usually the node degree)
- Iteratively assign a new label to each node in each graph by hashing the multi-set of the current labels within the node’s neighborhood, as well as the node’s current label
- Repeat the previous step until the labels for all nodes in both graphs converge
- Construct multisets summarizing all the node labels in each graph. 
If the multi-sets for both graphs are identical, graphs G1 and G2 are isomorphic

University of Virginia, Charlottesville

Graph isomorphism testing gives us a way to quantify the representational power of different learning approaches

Given 2 learned representations z_g1 and z_g2 for two corresponding graphs:
- a "perfect" algorithm would have z_g1 = z_g2 if and only if g1 is isomorphic to g2

However, there is no "perfect" representation learning algorithm, but there are several ways to connect it to graph isomorphism testing and approximate its power, such as the The Weisfieler-Lehman (WL) Algorithm

Representational Capacity

Hamilton, W.L. Graph Representation Learning. *Synthesis Lectures on Artificial Intelligence and Machine Learning*. 2020, 14(3), 1–159. https://doi.org/10.2200/S01045ED1V01Y202009AIM046

Learn Before

Related