Finite-round one-dimensional Weisfeiler–Leman color refinement

Let $G=(V,E,\mathrm{\ell })$ and $H=(W,F,m)$ be finite vertex-labeled simple undirected graphs with labels in a common set $\mathrm{\Sigma }$. Define color sets recursively by $C_0=\mathrm{\Sigma }$ and $C_{t+1}=C_t\times {\mathsf{M}}_{\mathrm{f}\mathrm{i}\mathrm{n}}(C_t)$ for each integer $t\ge 0$. Set $c_0^G(v)=\mathrm{\ell }(v)$ and $c_0^H(w)=m(w)$; for $t\ge 0$, update

$c_{t+1}^G(v)=(c_t^G(v),\{\text{\hspace{0.17em}⁣}\{c_t^G(u):u\in N_G(v)\}\text{\hspace{0.17em}⁣}\}),c_{t+1}^H(w)=(c_t^H(w),\{\text{\hspace{0.17em}⁣}\{c_t^H(z):z\in N_H(w)\}\text{\hspace{0.17em}⁣}\})\mathrm{.}$

The graph color multiset at round $t$ is $C_t(G)=\{\text{\hspace{0.17em}⁣}\{c_t^G(v):v\in V\}\text{\hspace{0.17em}⁣}\}$, and likewise for $H$. One-dimensional Weisfeiler–Leman color refinement distinguishes $G$ and $H$ at round $t$ when $C_t(G)\mathrm{\ne }{C}_t(H)$; it distinguishes the pair when this holds for some finite $t$. If no finite round distinguishes them, they are one-WL-indistinguishable. In the unlabeled case, take $\mathrm{\Sigma }$ to be a singleton. The tuple update is the canonical collision-free color encoding.

finite vertex-labeled simple undirected graphs and neighborhoods

finite multisets and color multiplicities

Xu, Hu, Leskovec, and Jegelka, “How Powerful are Graph Neural Networks?”, §2

Morris et al., “Weisfeiler and Leman Go Neural,” §2, Eq. (1)

Li and Leskovec, Graph Representation Learning, Chapter 5 §5.3.3