weisfeiler_leman (1204B)
1 # Weisfeiler-Leman algorithm 2 3 https://en.wikipedia.org/wiki/Weisfeiler_Leman_graph_isomorphism_test 4 5 aka "color refinement" 6 7 - initially all vertices have the same color 8 - then distinguish vertices based on the multiset of their neighboring colors 9 - two vertices with different colors will never be mappable to each other 10 - in fact you don't need to remember all the colors, you just want to iterate a partitioning 11 - |V| rounds of refinement at most until convergence 12 - but can be implemented in O(|G| log |G|) where |G| = |V| + |E| 13 - related to [automaton_minimization] 14 - the coloring can be made canonical (cf [graph_canonical_labeling]) 15 - of course if all vertices have same [degree] then this does not distinguish anything 16 - simple example: one 6-[cycle] vs two disjoint [triangles] 17 18 ## Power 19 20 [color_refinement_power] 21 22 ## Expressiveness 23 24 [color_refinement_expressive_power] 25 26 ## Multidimensional version 27 28 [weisfeiler_leman_multidimensional] 29 30 ## Other 31 32 - [color_refinement_query_evaluation] 33 34 Up: [graph] 35 36 See also: [graph_isomorphism], [proof_complexity], [machine_learning], [games], [logic], [fok], [fok_counting], [homomorphism_count] 37 38 Aliases: color refinement, color refinement algorithm