[Paper Review] A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants

Outlines

• Reference
• 1. Weisfeiler-Lehman Graph Isomorphism Test
  • 1.1. WL Test
  • 1.2. k-WL Test
  • 1.3. k-FWL Test
  • 1.4. Comparison between k-WL and k-FWL

Reference

• A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants, Huang et al, 2022

1. Weisfeiler-Lehman Graph Isomorphism Test

• Graph Isomorphism

  

    Graph 1 and 2 are isomorphic, meaning that their adjacency matrices are equivalent under permutation.

  • Two graphs G and H are isomorphic if there exists a bijective mapping $\large f\, :\, V(G) \rightarrow V(H)$ between their vertex sets that preserves the adjacency relationships.

  • More formally, for two graphs $\large G(V, E, X_{v})$ and $\large G’(V’, E’, X_{v}’)$, there exists a permutation $\large \Pi$ such that $\large \Pi V \, = \, V’, \, \Pi E \, = \, E’, \, \Pi X_{v} \, = \, X_{v}’$ where $\large \Pi(u,v) \, = \, (\Pi u, \Pi v)$.

• Graph Automorphism

  • An automorphism of a graph G is an isomorphism from G to itself.

  • Permutation of the vertices of the graph that preserves the graph’s structure.

• Notations

  • $\large G(V, E, X_{v})$ : a graph with vertex set $\large V$, edge set $\large E$, and node features $\large X_{v} \, \in \, \mathbb{R}^{d}$.

  • $\large \vec{v} \, = \, (v_{1}, v_{2}, …, v_{k}) \, \in \, \mathbb{R}^{k}$ : a k-tuple of nodes

  • $\large c_{v}^{l}$ : state of node $\large v$ or $\large \vec{v}$ at iteration $\large l$.

  • $\large hash \, : \, X_{v} \rightarrow c_{v}^{l}$ : a bijective function that maps colors to nodes (or k-tuples of nodes) based on the node features or multiset of node features.

  • {{}} : a multiset (set that allows multiplicity). Two multisets are equal (their hash values are equal) if they share same elements with same multiplicities. (Any multisets are sorted before hashed.)

1.1. WL Test

• WL test (1-WL test) is a classical isomorphism based on color refinement where the color of each node is updated in each iteration based on the aggregated color representation of its neighboring nodes.

  (t is a iteration)

• Iterates the same process untill the refinement stabilizes with no further update from previous states.

  

1.2. k-WL Test

• The problem of 1-WL test where the hash function only refers to the state of a single node is that it’s too heuristic and fails to distinguish non-isomorphism in a simple case where two graphs have same number of nodes and every node has same degree.

• A straightforward solution to this is simply to extend the set of nodes referred to update the state from a single node to k-tuples of nodes.

  • $\large c_{v}^{l} \, = \, hash(X_{v})$ for $\large v \, \in \, V$   $\large \rightarrow$   $\large c_{\vec{v}}^{l} \, = \, hash(G(\vec{v}))$ where $\large \vec{v}$ is k-dimensional.

  • Neighborhood of $\large \vec{v}$, $\large N_{i}(\vec{v})$ is defined as the set of k-tuple of nodes that differ with $\large \vec{v}$ only in the position $\large i$.

     

    • $\large N_{i}(\vec{v}) \, \in \, \mathbb{R}^{n \times k \times k}$

    • Example : $\large N_{i}(\vec{v})$ for k = 2, n = 6 (just focus on the dimensions)

       

• Except for the fact that coloring is performed based on the k-tuples of nodes, the basic algorithm of color refinement is identical with the 1-WL test.

  

1.3. k-FWL Test

• k-FWL (folklore-WL) is almost idential to the k-WL with a slight difference in the definition of neighborhood.

   

  • $\large N_{i}^{F}(\vec{v}) \, \in \, \mathbb{R}^{k \times n \times k}$

    • Example of $\large N_{i}^{F}(\vec{v})$ for the same case (k = 2, node = 6)

      

• Algorithm

  

  

1.4. Comparison between k-WL and k-FWL

• This seemingly trivial change in the definition of neighborhood distinguishes k-FWL from k-WL, such that the discriminating power of k-WL is equivalent to the one of (k-1)-FWL for k greater than 3.

• Let’s take a closer look at how can these two algorithms differ in terms of dicriminating isomorphism with an example provided with a great detail.

• These two graphs G and H are non-isomorphic example that the classical WL test and 2-WL test fails to distinguish, but 2-FWL succeeds.

• Intially, there are only two isomorphic types in both cases. 1. Connected colored in yellow, 2.Not Connected colored in gray. (All nodes have either 0 or 2 degree).

• First Iteration of Color Refinement in 2-WL

  

  • As shown in the figure above, All 2-tuples of nodes share same multiset, which gives the same neighborhoods for all nodes.

    

  • Then the color update in $\large G_{1}$ and $\large H_{1}$ depends on the initial isomorphic type (gray or yellow).

    • $\large hash(grey, \, c_{\vec{v}, 1}^{1}, \, c_{\vec{v}, 2}^{1})$   →   orange

    • $\large hash(yellow, \, c_{\vec{v}, 1}^{1}, \, c_{\vec{v}, 2}^{1})$   →   brown

  • Thus, color pattern doesn’t change for every node and the 2-WL terminates, concluding that two graphs are isomorphic.

• First Iteration of Color Refinement in 2-FWL

  • In contrast, the first color update in 2-FWL where neighborhood contains k n-dimensional elements gives different color pattern for each graph.

    

    • $\large G^{1}$ has 3 isomorphic types.

      • hash(grey, 4 mixed, 2 grey)   →   orange

      • hash(grey, 2 yellow, 4 grey)   →   brown

      • hash(yellow, 2 mixed, 1 yellow, 3 grey)   →   blue

    • $\large H^{1}$ has 4 isomorphic types.

      • hash(grey, 4 mixed, 2 grey)   →   orange

      • hash(grey, 2 yellow, 4 grey)   →   brown

      • hash(yellow, 4 mixed, 2 grey)   →   purple

      • hash(grey, 2 mixed, 1 yellow, 3 grey)   →   green

  • Unlike 2-WL, 2-FWL succeeds to distingush two graphs at first iteration.

  • As the refinement stabilizes in one step, 2-FWL terminates with a conclusion that two graphs are non-isomorphic.