Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
By Christoph Berkholz, Paul S. Bonsma, Martin Grohe. 2013
89 citations recorded by the source corpus.
An assignment of colours to the vertices of a graph is stable if any two vertices of the same colour have identically coloured neighbourhoods. The goal of colour refinement is to find a stable colouring that uses a minimum number of colours. This is a widely used subroutine for graph isomorphism testing algorithms, since any automorphism needs to be colour preserving. We give an O((m + n)log n) algorithm for finding a canonical version of such a stable colouring, on graphs with n vertices and m edges. We show that no faster algorithm is possible, under some modest assumptions about the type of algorithm, which captures all known colour refinement algorithms.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Graph Learning, Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Christopher Morris
- Petra Mutzel
- Muhan Zhang
- Yixin Chen
- Gaurav Rattan
- Kristian Kersting
- Roman Garnett
- Sandra Kiefer
In Computational Theory and Mathematics
- Christopher Morris
- Muhan Zhang
- Yixin Chen
- Petra Mutzel
- Gaurav Rattan
- Kristian Kersting
- Pascal Schweitzer
- Sandra Kiefer
In Graph Learning
- Christopher Morris
- Muhan Zhang
- Yixin Chen
- Petra Mutzel
- Kristian Kersting
- Gaurav Rattan
- Roman Garnett
- Pascal Schweitzer
In Algorithms & Complexity
- Christopher Morris
- Muhan Zhang
- Yixin Chen
- Sandra Kiefer
- Pascal Schweitzer
- Erkal Selman
- Kristian Kersting
- Petra Mutzel
Citations in the corpus
- Power Iterated Color Refinement (2014, methodology): “…well as the path to the solution — and the graph theory view already led to quasi-linear O((m + n) log n) algorithms for finding FGAs of (weighted) graphs with n vertices and m edges due to asynchronous color updates, see e.g. (Berkholz, Bonsma, and Grohe 2013; Grohe et al. 2013) for more details.”
- Glocalized Weisfeiler-Lehman Graph Kernels: Global-Local Feature Maps of Graphs (2017, unknown): “, see [46].”
- Graphs Identified by Logics with Counting (2015, methodology): “Proof: Color refinement can be performed in time O((m+ n) log n) (see [5]).”
- Weisfeiler-Lehman Neural Machine for Link Prediction (2017, methodology): “Second, there exists O (( | E | + | V | ) log | V | ) time implementation of WL using some special data structure [22].”
- Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, background): “Moreover, upper bounds on the running time for k = 1 (Berkholz et al., 2013; Kiefer & McKay, 2020), and the number of iterations for the folklore k = 2 (Kiefer & Schweitzer, 2016; Lichter et al., 2019) have been shown.”