While this submission is a draft, it cannot be used by other submissions.

The Weisfeiler–Leman algorithm

Lax119563.WeisfeilerLeman · concepts/Lax119563/WeisfeilerLeman.lean · lax-119563

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Definition

    Fix k≥2k \geq 2 and a colored graph GG. For pˉ=(p1,…,pk)∈V(G)k\bar p = (p_1, \dots, p_k) \in V(G)^k and q∈V(G)q \in V(G), let pˉ[q/i]\bar p[q/i] be the tuple obtained by replacing the ii-th entry by qq.

    The atomic type atp⁡G(pˉ)\operatorname{atp}_G(\bar p) of pˉ\bar p records which entries are equal, which entries are adjacent, and the colors of the entries; thus atp⁡G(pˉ)=atp⁡H(qˉ)\operatorname{atp}_G(\bar p) = \operatorname{atp}_H(\bar q) if and only if pi↦qip_i \mapsto q_i is a partial isomorphism.

    The kk-dimensional Weisfeiler–Leman algorithm (kk-WL) computes colorings χk(r)[G]\chi^{(r)}_k[G] of V(G)kV(G)^k for r≥0r \geq 0, starting from χk(0)[G](pˉ)=atp⁡G(pˉ)\chi^{(0)}_k[G](\bar p) = \operatorname{atp}_G(\bar p) and setting

    χk(r+1)[G](pˉ)=(χk(r)[G](pˉ),  {{(χk(r)[G](pˉ[q/1]),…,χk(r)[G](pˉ[q/k])):q∈V(G)}}),\chi^{(r+1)}_k[G](\bar p) = \Bigl(\chi^{(r)}_k[G](\bar p),\; \{\{ (\chi^{(r)}_k[G](\bar p[q/1]), \dots, \chi^{(r)}_k[G](\bar p[q/k])) : q \in V(G) \}\}\Bigr),

    where {{⋅}}\{\{\cdot\}\} denotes a multiset. Colors are defined syntactically, so colors of tuples in different graphs can be compared.

    For colored graphs G,HG, H and r≥0r \geq 0, kk-WL distinguishes GG and HH after rr rounds if some color cc satisfies

    ∣{pˉ∈V(G)k:χk(r)[G](pˉ)=c}∣≠∣{qˉ∈V(H)k:χk(r)[H](qˉ)=c}∣,\bigl|\{\bar p \in V(G)^k : \chi^{(r)}_k[G](\bar p) = c\}\bigr| \neq \bigl|\{\bar q \in V(H)^k : \chi^{(r)}_k[H](\bar q) = c\}\bigr|,

    and kk-WL distinguishes GG and HH if it does so after some number of rounds.

    Each coloring χk(r+1)[G]\chi^{(r+1)}_k[G] refines χk(r)[G]\chi^{(r)}_k[G]. We say that kk-WL stabilizes after rr rounds on GG if χk(r)[G]\chi^{(r)}_k[G] and χk(r+1)[G]\chi^{(r+1)}_k[G] induce the same partition of V(G)kV(G)^k.

    Concept map
    2 concepts
    100%
    DefinitionThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    Lean source view on GitHub

    1import Mathlib.Data.Multiset.Basic
    2import Mathlib.Data.Fintype.Pi
    3import Mathlib.SetTheory.Cardinal.Finite
    4import Lax119563.ColoredGraphs
    5
    6/-!
    7---
    8title: The Weisfeiler–Leman algorithm
    9type: definition
    10---
    11Fix k≥2k \geq 2 and a colored graph GG. For pˉ=(p1,…,pk)∈V(G)k\bar p = (p_1, \dots, p_k) \in V(G)^k and
    12q∈V(G)q \in V(G), let pˉ[q/i]\bar p[q/i] be the tuple obtained by replacing the ii-th entry by qq.
    13
    14The *atomic type* atp⁡G(pˉ)\operatorname{atp}_G(\bar p) of pˉ\bar p records which entries are equal,
    15which entries are adjacent, and the colors of the entries; thus
    16atp⁡G(pˉ)=atp⁡H(qˉ)\operatorname{atp}_G(\bar p) = \operatorname{atp}_H(\bar q) if and only if
    17pi↦qip_i \mapsto q_i is a partial isomorphism.
    18
    19The *kk-dimensional Weisfeiler–Leman algorithm* (kk-WL) computes colorings
    20χk(r)[G]\chi^{(r)}_k[G] of V(G)kV(G)^k for r≥0r \geq 0, starting from
    21χk(0)[G](pˉ)=atp⁡G(pˉ)\chi^{(0)}_k[G](\bar p) = \operatorname{atp}_G(\bar p) and setting
    22χk(r+1)[G](pˉ)=(χk(r)[G](pˉ),  {{(χk(r)[G](pˉ[q/1]),…,χk(r)[G](pˉ[q/k])):q∈V(G)}}),\chi^{(r+1)}_k[G](\bar p) = \Bigl(\chi^{(r)}_k[G](\bar p),\; \{\{ (\chi^{(r)}_k[G](\bar p[q/1]), \dots, \chi^{(r)}_k[G](\bar p[q/k])) : q \in V(G) \}\}\Bigr),
    23
    24where {{⋅}}\{\{\cdot\}\} denotes a multiset. Colors are defined syntactically, so colors of
    25tuples in different graphs can be compared.
    26
    27For colored graphs G,HG, H and r≥0r \geq 0, kk-WL *distinguishes GG and HH after rr rounds*
    28if some color cc satisfies
    29∣{pˉ∈V(G)k:χk(r)[G](pˉ)=c}∣≠∣{qˉ∈V(H)k:χk(r)[H](qˉ)=c}∣,\bigl|\{\bar p \in V(G)^k : \chi^{(r)}_k[G](\bar p) = c\}\bigr| \neq \bigl|\{\bar q \in V(H)^k : \chi^{(r)}_k[H](\bar q) = c\}\bigr|,
    30
    31and kk-WL *distinguishes* GG and HH if it does so after some number of rounds.
    32
    33Each coloring χk(r+1)[G]\chi^{(r+1)}_k[G] refines χk(r)[G]\chi^{(r)}_k[G]. We say that kk-WL
    34*stabilizes after rr rounds* on GG if χk(r)[G]\chi^{(r)}_k[G] and χk(r+1)[G]\chi^{(r+1)}_k[G] induce the
    35same partition of V(G)kV(G)^k.
    36
    37# Implementation notes
    38
    39The definitions are stated for every kk; they are the kk-WL algorithm for k≥2k \geq 2. For
    40k∈{0,1}k \in \{0, 1\} they are not the usual algorithms (for k=1k = 1, the atomic type of a single
    41vertex records no adjacency, so this is not color refinement); statements about kk-WL assume
    42k≥2k \geq 2 where it matters, and the problems in `Lax119563.WLProblems` include these
    43degenerate dimensions only as inputs.
    44-/
    45
    46open Lax119563.ColoredGraphs
    47
    48namespace Lax119563.WeisfeilerLeman
    49
    50/-- The atomic type of a `k`-tuple: which entries are equal, which entries are adjacent,
    51and the colors of the entries. -/
    52structure AtomicType (k : ℕ) where
    53 eq : Fin k → Fin k → Bool
    54 adj : Fin k → Fin k → Bool
    55 color : Fin k → ℕ
    56
    57open Classical in
    58/-- The atomic type `atp_G(p̄)` of a tuple of vertices. -/
    59noncomputable def atp (G : ColoredGraph) {k : ℕ} (p : Fin k → Fin G.n) : AtomicType k :=
    60 { eq := fun i j => decide (p i = p j)
    61 adj := fun i j => decide (G.graph.Adj (p i) (p j))
    62 color := fun i => G.color (p i) }
    63
    64/-- The colors used by `k`-WL in round `r`. -/
    65def Color (k : ℕ) : ℕ → Type
    66 | 0 => AtomicType k
    67 | r + 1 => Color k r × Multiset (Fin k → Color k r)
    68
    69/-- The coloring `χ^{(r)}_k[G]` of `k`-tuples computed by `k`-WL in round `r`.
    70The tuple `Function.update p i q` is `p̄[q/i]`. -/
    71noncomputable def color (G : ColoredGraph) {k : ℕ} : (r : ℕ) → (Fin k → Fin G.n) → Color k r
    72 | 0, p => atp G p
    73 | r + 1, p =>
    74 (color G r p,
    75 (Finset.univ : Finset (Fin G.n)).val.map fun q i => color G r (Function.update p i q))
    76
    77/-- `k`-WL distinguishes `G` and `H` after `r` rounds: some color of round `r` occurs a
    78different number of times among the `k`-tuples of `G` and of `H`. -/
    79def DistinguishesAfter (k r : ℕ) (G H : ColoredGraph) : Prop :=
    80 ∃ c : Color k r,
    81 Nat.card {p : Fin k → Fin G.n // color G r p = c} ≠
    82 Nat.card {q : Fin k → Fin H.n // color H r q = c}
    83
    84/-- `k`-WL distinguishes `G` and `H`. -/
    85def Distinguishes (k : ℕ) (G H : ColoredGraph) : Prop :=
    86 ∃ r, DistinguishesAfter k r G H
    87
    88/-- `k`-WL stabilizes after `r` rounds on `G`: the colorings of rounds `r` and `r + 1`
    89induce the same partition of the `k`-tuples of vertices. -/
    90def StabilizesAfter (k r : ℕ) (G : ColoredGraph) : Prop :=
    91 ∀ p q : Fin k → Fin G.n, color G r p = color G r q ↔ color G (r + 1) p = color G (r + 1) q
    92
    93end Lax119563.WeisfeilerLeman
    94

    Implementation notes

    The definitions are stated for every kk; they are the kk-WL algorithm for k≥2k \geq 2. For k∈{0,1}k \in \{0, 1\} they are not the usual algorithms (for k=1k = 1, the atomic type of a single vertex records no adjacency, so this is not color refinement); statements about kk-WL assume k≥2k \geq 2 where it matters, and the problems in Lax119563.WLProblemsLax119563.WLProblems include these degenerate dimensions only as inputs.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…