Colour refinement algorithm
In graph theory and theoretical computer science, the colour refinement algorithm also known as the naive vertex classification, or the 1-dimensional version of the Weisfeiler-Leman algorithm, is a routine used for testing whether two graphs are isomorphic.[1]
Description
The algorithm takes as an input a graph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ n }[/math] vertices. It proceeds in iterations and in each iteration produces a new colouring of the vertices. Formally a "colouring" is a function from the vertices of this graph into some set (of "colours"). In each iteration, we define a sequence of vertex colourings [math]\displaystyle{ \lambda_i }[/math] as follows:
- [math]\displaystyle{ \lambda_0 }[/math] is the initial colouring. If the graph is unlabelled, the initial colouring assigns a trivial colour [math]\displaystyle{ \lambda_0(v) }[/math] to each vertex [math]\displaystyle{ v }[/math]. If the graph is labelled, [math]\displaystyle{ \lambda_0 }[/math] is the label of vertex [math]\displaystyle{ v }[/math].
- For all vertices [math]\displaystyle{ v }[/math], we set [math]\displaystyle{ \lambda_{i+1} = \left(\lambda_i(v), \{\{ \lambda_i(w) \mid w \text{ is a neighbor of } v\}\}\right) }[/math].
In other words, the new colour of the vertex [math]\displaystyle{ v }[/math] is the pair formed from the previous colour and the multiset of the colours of its neighbours. This algorithm keeps refining the current colouring. At some point it stabilises, i.e., [math]\displaystyle{ \lambda_{i+1} = \lambda_i }[/math]. This final colouring is called the stable colouring.
Graph Isomorphism
Colour refinement can be used as a subroutine for an important computational problem: graph isomorphism. In this problem we have as input two graphs [math]\displaystyle{ G, H }[/math] and our task is to determine whether they are isomorphic. Informally, this means that the two graphs are the same up to relabelling of vertices.
To test if [math]\displaystyle{ G }[/math] and [math]\displaystyle{ H }[/math] are isomorphic we could try the following. Run colour refinement on both graphs. If the stable colourings produced are different we know that the two graphs are not isomorphic. However, it could be that the same stable colouring is produced despite the two graphs not being isomorphic; see below.
Complexity
It is easy to see that if colour refinement is given a [math]\displaystyle{ n }[/math] vertex graph as input, a stable colouring is produced after at most [math]\displaystyle{ n-1 }[/math] iterations. Conversely, there exist graphs where this bound is realised.[2] This leads to a [math]\displaystyle{ O((n+m)\log n) }[/math] implementation where [math]\displaystyle{ n }[/math] is the number of vertices and [math]\displaystyle{ m }[/math] the number of edges.[3] This complexity has been proven to be optimal under reasonable assumptions.[4]
Expressivity
We same that two graphs [math]\displaystyle{ G }[/math] and [math]\displaystyle{ H }[/math] are distinguished by colour refinement if the algorithm yields a different output on [math]\displaystyle{ G }[/math] as on [math]\displaystyle{ H }[/math]. There are simple examples of graphs that are not distinguished by colour refinement. For example, it does not distinguish a cycle of length 6 from a pair of triangles (example V.1 in [5]). Despite this, the algorithm is very powerful in that a random graph will be identified by the algorithm asymptotically almost surely.[6] Even stronger, it has been shown that as [math]\displaystyle{ n }[/math] increases, the proportion of graphs that are not identified by colour refinement decreases exponentially in order [math]\displaystyle{ n }[/math].[7]
The expressivity of colour refinement also has a logical characterisation: two graphs can be distinguished by colour refinement if and only if they can be distinguished by the two variable fragment of first order logic with counting.[8]
History
References
- ↑ Grohe, Martin; Kersting, Kristian; Mladenov, Martin; Schweitzer, Pascal (2021). "Color Refinement and Its Applications". An Introduction to Lifted Probabilistic Inference. doi:10.7551/mitpress/10548.003.0023. ISBN 9780262365598. https://doi.org/10.7551/mitpress/10548.003.0023.
- ↑ Kiefer, Sandra; McKay, Brendan D. (2020-05-20), The Iteration Number of Colour Refinement, http://arxiv.org/abs/2005.10182, retrieved 2024-01-18
- ↑ Cardon, A.; Crochemore, M. (1982-07-01). "Partitioning a graph in O(¦A¦log2¦V¦)" (in en). Theoretical Computer Science 19 (1): 85–98. doi:10.1016/0304-3975(82)90016-0. ISSN 0304-3975.
- ↑ Berkholz, Christoph; Bonsma, Paul; Grohe, Martin (2017-05-01). "Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement" (in en). Theory of Computing Systems 60 (4): 581–614. doi:10.1007/s00224-016-9686-0. ISSN 1433-0490.
- ↑ Grohe, Martin (2021-06-29). "The Logic of Graph Neural Networks". 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). LICS '21. New York, NY, USA: Association for Computing Machinery. pp. 1–17. doi:10.1109/LICS52264.2021.9470677. ISBN 978-1-6654-4895-6. https://doi.org/10.1109/LICS52264.2021.9470677.
- ↑ Babai, László; Erdo˝s, Paul; Selkow, Stanley M. (August 1980). "Random Graph Isomorphism" (in en). SIAM Journal on Computing 9 (3): 628–635. doi:10.1137/0209047. ISSN 0097-5397. https://epubs.siam.org/doi/10.1137/0209047.
- ↑ Babai, L.; Kucera, K.. "Canonical labelling of graphs in linear average time | IEEE Conference Publication | IEEE Xplore". https://ieeexplore.ieee.org/document/4567999/;jsessionid=3nsdXVGO6TSsLdiJnZQ6slDYPxa-Qyh0XugyK5ti0b5TpRiyrKyo!-452107954.
- ↑ Grohe, Martin. "Finite variable logics in descriptive complexity theory." Bulletin of Symbolic Logic 4.4 (1998): 345-398.
 |  |
