The Weisfeiler–Leman algorithm
Lax119563.WeisfeilerLeman · concepts/Lax119563/WeisfeilerLeman.lean · lax-119563
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
Fix and a colored graph . For and , let be the tuple obtained by replacing the -th entry by .
The atomic type of records which entries are equal, which entries are adjacent, and the colors of the entries; thus if and only if is a partial isomorphism.
The -dimensional Weisfeiler–Leman algorithm (-WL) computes colorings of for , starting from and setting
where denotes a multiset. Colors are defined syntactically, so colors of tuples in different graphs can be compared.
For colored graphs and , -WL distinguishes and after rounds if some color satisfies
and -WL distinguishes and if it does so after some number of rounds.
Each coloring refines . We say that -WL stabilizes after rounds on if and induce the same partition of .
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Data.Multiset.Basic |
| 2 | import Mathlib.Data.Fintype.Pi |
| 3 | import Mathlib.SetTheory.Cardinal.Finite |
| 4 | import Lax119563.ColoredGraphs |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: The Weisfeiler–Leman algorithm |
| 9 | type: definition |
| 10 | --- |
| 11 | Fix and a colored graph . For and |
| 12 | , let be the tuple obtained by replacing the -th entry by . |
| 13 | |
| 14 | The *atomic type* of records which entries are equal, |
| 15 | which entries are adjacent, and the colors of the entries; thus |
| 16 | if and only if |
| 17 | is a partial isomorphism. |
| 18 | |
| 19 | The *-dimensional Weisfeiler–Leman algorithm* (-WL) computes colorings |
| 20 | of for , starting from |
| 21 | and setting |
| 22 | |
| 23 | |
| 24 | where denotes a multiset. Colors are defined syntactically, so colors of |
| 25 | tuples in different graphs can be compared. |
| 26 | |
| 27 | For colored graphs and , -WL *distinguishes and after rounds* |
| 28 | if some color satisfies |
| 29 | |
| 30 | |
| 31 | and -WL *distinguishes* and if it does so after some number of rounds. |
| 32 | |
| 33 | Each coloring refines . We say that -WL |
| 34 | *stabilizes after rounds* on if and induce the |
| 35 | same partition of . |
| 36 | |
| 37 | # Implementation notes |
| 38 | |
| 39 | The definitions are stated for every ; they are the -WL algorithm for . For |
| 40 | they are not the usual algorithms (for , the atomic type of a single |
| 41 | vertex records no adjacency, so this is not color refinement); statements about -WL assume |
| 42 | where it matters, and the problems in `Lax119563.WLProblems` include these |
| 43 | degenerate dimensions only as inputs. |
| 44 | -/ |
| 45 | |
| 46 | open Lax119563.ColoredGraphs |
| 47 | |
| 48 | namespace Lax119563.WeisfeilerLeman |
| 49 | |
| 50 | /-- The atomic type of a `k`-tuple: which entries are equal, which entries are adjacent, |
| 51 | and the colors of the entries. -/ |
| 52 | structure AtomicType (k : ℕ) where |
| 53 | eq : Fin k → Fin k → Bool |
| 54 | adj : Fin k → Fin k → Bool |
| 55 | color : Fin k → ℕ |
| 56 | |
| 57 | open Classical in |
| 58 | /-- The atomic type `atp_G(p̄)` of a tuple of vertices. -/ |
| 59 | noncomputable 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`. -/ |
| 65 | def 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`. |
| 70 | The tuple `Function.update p i q` is `p̄[q/i]`. -/ |
| 71 | noncomputable 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 |
| 78 | different number of times among the `k`-tuples of `G` and of `H`. -/ |
| 79 | def 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`. -/ |
| 85 | def 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` |
| 89 | induce the same partition of the `k`-tuples of vertices. -/ |
| 90 | def 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 | |
| 93 | end Lax119563.WeisfeilerLeman |
| 94 |
Implementation notes
The definitions are stated for every ; they are the -WL algorithm for . For they are not the usual algorithms (for , the atomic type of a single vertex records no adjacency, so this is not color refinement); statements about -WL assume where it matters, and the problems in include these degenerate dimensions only as inputs.
Builds on
Used by
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments