Refine node colours until neighbourhoods stop distinguishing them

The standard cheap check for non-isomorphism: different final colour multisets prove the graphs differ. The converse fails – regular graphs of equal degree are indistinguishable – and that failure is exactly the expressiveness ceiling of message-passing graph networks.

Usage

Sgtwlk(A, labels0 = NULL, max_iter = 3)

Arguments

A

Adjacency.

labels0

Starting colours; all zero by default.

max_iter

Refinement rounds.

Value

List with labels_t, estimate, history, n.

Details

Determinism: each round hashes the sorted neighbour-colour multiset to a canonical string and reassigns colours by first appearance, so no hash-seed randomness enters.

Formula: h^(t+1)(v) = hash(h^t(v), {{h^t(u): u in N(v)}}).

References

Weisfeiler & Leman (1968) Nauchno-Tekh Inform 2(9):12-16; Xu, Hu, Leskovec & Jegelka (2019) ICLR.

Examples

V <- c(1, 2, 3, 4, 5, 6, 7, 8)
Sgtwlk(V)
#> $labels_t
#> [1] 0 1 1 1 1 1 1 1
#> 
#> $estimate
#> [1] 2
#> 
#> $history
#> [1] 1 2 2 2
#> 
#> $n
#> [1] 8
#> 
#> $method
#> [1] "Weisfeiler-Leman colour refinement"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"