color refinement algorithm

[[concept]]

Color refinement algorithm

The color refinement algorithm is an algorithm to assign colorings to nodes.

Given graph $G=(V,E)$ with node features $x$

let $c_i(0)=f(\cdot ,\{x_i\})\forall i\in V$ (assign colors based on node feature values) let $t=0$

while True:

1. let $c_i(t)=f(c_i(t-1),\{\{c_j(t-1),j\in N(i)\}\})\forall i\in V$

• assign colors based on previously assigned colors

2. if $c_i(t)==c_i(t-1)\forall i$, break. else, $t=t+1$

Here, $f$ is a hash function that assigns colors.

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$:

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$:

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$:

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