color refinement algorithm

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

let $c_i(0)=f(\cdot ,\{x_i\})\mathrm{\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)\}\})\mathrm{\forall }i\in V$

• assign colors based on previously assigned colors

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

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

step $t=0$:

step $t=1$:

Evaluate: did the colors change?

• Yes: continue!

step $t=2$:

Evaluate: did the colors change?

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

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

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

step $t=0$: assign colors based on node features:

step $t=1$:

evaluate: did the colors change?

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

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