2026-07-22T01:29:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4829 2024-03-06T10:35:22Z ddc:004 open_access

Colour Refinement: A Simple Partitioning Algorithm with Applications From Graph Isomorphism Testing to Machine Learning (Invited Talk) Grohe, Martin Color Refinement Graph Isomorphism Machine Learning Colour refinement is a simple algorithm that partitions the vertices of a graph according their "iterated degree sequence." It has very efficient implementations, running in quasilinear time, and a surprisingly wide range of applications. The algorithm has been designed in the context of graph isomorphism testing, and it is used an important subroutine in almost all practical graph isomorphism tools. Somewhat surprisingly, other applications in machine learning, probabilistic inference, and linear programming have surfaced recently. In the first part of my talk, I will introduce the basic algorithm as well as higher dimensional extensions known as the k-dimensional Weisfeiler-Lehman algorithm. I will also discuss an unexpected connection between colour refinement and a natural linear programming approach to graph isomorphism testing. In the second part of my talk, I will discuss various applications of colour refinement. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Grohe 2014 Is Part Of LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2014.31 urn:nbn:de:0030-drops-48290 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.31 eng https://creativecommons.org/licenses/by/3.0/legalcode