Weisfeiler-Leman Graph Isomorphism Test

[[concept]]

Weisfeiler-Leman Graph Isomorphism Test

The Weisfeiler-Leman graph isomorphism test consists of running the color refinement algorithm for two graphs.

Motivation eigenvalue-based heuristic doesn't work for some graphs, a simple heuristic that does work is counting degrees. Then the problem amounts to comparing the multisets of node degree counts.

Since the

If the outputs of the algorithm are not the same, then the two graphs are not isomorphic.

are the same, this is not an indicator that the two graphs are isomorphic! It means the test is inconclusive

If the outputs of the algorithm for the two graphs

In this example, the two graphs have different outputs. Thus, we may conclude that they are not isomorphic.

Example

Color refinement for $G_1$

No node features, so assume all 1. First, Assign colors based on node features.

step $t=0$: $c_{1}(0) = c_{2}(0)=c_{3}(0) = f(\cdot, 1) = k_{1}$$

step $t=1$: $\begin{aligned} c_{1}(1) &= f(k_{1}, { k_{1} }) &= k_{1} \ c_{3}(1) &= f(k_{1}, { k_{1} }) &= k_{1} \ c_{2}(1) &= f(k_{1}, { k_{1}, k_{1} }) &= k_{2} \end{aligned}$$ Evaluate: did the colors change?

• Yes: continue!

step $t=2$: $\begin{aligned} c_{1}(2) &= f(k_{1}, { k_{1} }) &= k_{1} \ c_{3}(2) &= f(k_{1}, { k_{1} }) &= k_{1} \ c_{2}(2) &= f(k_{2}, { k_{1}, k_{1} }) &= k_{2} \end{aligned}$$ Evaluate: did the colors change?

• No - so we are done!
• This is the final coloring.

return $\{k_1,k_1,k_2\}$

Color refinement for $G_2$ Again, there are no node features, so we assume the signals are all $1$.

step $t=0$: assign colors based on node features: c_{1}(0) = c_{2}(0)=c_{3}(0) = f(\cdot, 1) = k_{1}$$ `step` t=1$:$\begin{aligned} c_{1}(1) = c_{2}(1) = c_{3}(1) = f(\cdot, { k_{1}, k_{1} }) = k_{1} \end{aligned}$$

evaluate: did the colors change?

• No - so we are done
• This is the final coloring

return $\{k_1,k_1,k_1\}$

Mentions

TABLE
FROM [[]]
 
FLATTEN choice(contains(artist, this.file.link), 1, "") + choice(contains(author, this.file.link), 1, "") + choice(contains(director, this.file.link), 1, "") + choice(contains(source, this.file.link), 1, "") as direct_source
 
WHERE !direct_source