Interest along Weisfeiler-Leman Graph Isomorphism Test

[Becheler]

Hi Graphies,

I received a feature request from a graph scientist: the Weisfeiler-Leman (WL) graph isomorphism test, a popular heuristic for detecting non-isomorphic graphs. From what I understand, WL quickly proves non-isomorphism in polynomial time, so one can skip exponential exact algorithm most of the time. So it should problably complement existing BGL algorothms like:

• isomorphism() Exact algorithm, worst-case exponential time
• vf2_sub_graph_iso() Subgraph matching, even slower

Literature

• Founding article: Weisfeiler & Leman, 1968
• Power and Limits: Kiefer 2020

What do you think ?