WL refinement: color(v) ← hash(color(v), sorted colors of neighbors)
Graph G₁
Graph G₂
Run WL to check isomorphism
|V₁|, |E₁|—
|V₂|, |E₂|—
Color classes G₁—
Color classes G₂—
WL stable?—
1-WL test: repeatedly recolor each vertex by a hash of its current color and the multiset of neighbor colors. If color histograms differ → NOT isomorphic. If histograms match → possibly isomorphic (WL can't always decide). GNN expressiveness ≡ 1-WL (Xu et al. 2019). CFI graphs defeat 1-WL.