Color refinement algorithm

The first appearance of color refinement is in Stephen H. Unger's program GIT for graph isomorphism, where it is called the Extend method.^[2] It was described again, immediately after, in a chemistry paper.^[3]

The algorithm takes as an input a graph ${\displaystyle G}$ with ${\displaystyle n}$ vertices. It proceeds in iterations and in each iteration produces a new coloring of the vertices. Formally a "coloring" is a function from the vertices of this graph into some set (of "colors"). In each iteration, we define a sequence of vertex colorings ${\displaystyle \lambda _{i}}$ as follows:

• ${\displaystyle \lambda _{0}}$ is the initial coloring. If the graph is unlabelled, the initial coloring assigns a trivial color ${\displaystyle \lambda _{0}(v)}$ to each vertex ${\displaystyle v}$. If the graph is labelled, ${\displaystyle \lambda _{0}}$ is the label of vertex ${\displaystyle v}$.
• For all vertices ${\displaystyle v}$, we set ${\displaystyle \lambda _{i+1}(v)=\left(\lambda _{i}(v),\{\{\lambda _{i}(w)\mid w{\text{ is a neighbor of }}v\}\}\right)}$.

In other words, the new color of the vertex ${\displaystyle v}$ is the pair formed from the previous color and the multiset of the colors of its neighbours. This algorithm keeps refining the current coloring. At some point it stabilises, i.e., ${\displaystyle \lambda _{i+1}(u)=\lambda _{i+1}(v)}$ if and only if ${\displaystyle \lambda _{i}(u)=\lambda _{i}(v)}$. This final coloring is called the stable coloring.

Color refinement can be used as a subroutine for an important computational problem: graph isomorphism. In this problem we have as input two graphs ${\displaystyle G,H}$ 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 ${\displaystyle G}$ and ${\displaystyle H}$ are isomorphic we could try the following. Run color refinement on both graphs. If the stable colorings produced are different we know that the two graphs are not isomorphic. However, it could be that the same stable coloring is produced despite the two graphs not being isomorphic; see below.

It is easy to see that if color refinement is given a ${\displaystyle n}$ vertex graph as input, a stable coloring is produced after at most ${\displaystyle n-1}$ iterations. Conversely, there exist graphs where this bound is realised.^[4] This leads to a ${\displaystyle O((n+m)\log n)}$ implementation where ${\displaystyle n}$ is the number of vertices and ${\displaystyle m}$ the number of edges.^[5] This complexity has been proven to be optimal under reasonable assumptions.^[6]

We say that two graphs ${\displaystyle G}$ and ${\displaystyle H}$ are distinguished by color refinement if the algorithm yields a different output on ${\displaystyle G}$ as on ${\displaystyle H}$. There are simple examples of graphs that are not distinguished by color refinement. For example, it does not distinguish a cycle of length 6 from a pair of triangles (example V.1 in ^[7]). Despite this, the algorithm is very powerful in that a random graph will be identified by the algorithm asymptotically almost surely.^[8] Even stronger, it has been shown that as ${\displaystyle n}$ increases, the proportion of graphs that are not identified by color refinement decreases exponentially in order ${\displaystyle n}$.^[9]

For two graphs ${\displaystyle G}$ and ${\displaystyle H}$ with the same number of vertices, the following conditions are equivalent:

• ${\displaystyle G}$ and ${\displaystyle H}$ are indistinguishable by color refinement.
• The minimum fibration bases of ${\displaystyle G}$ and ${\displaystyle H}$ are isomorphic.
• ${\displaystyle G}$ and ${\displaystyle H}$ are fractionally isomorphic.^[10][11]
• ${\displaystyle G}$ and ${\displaystyle H}$ have a common coarsest equitable partition.
• ${\displaystyle G}$ and ${\displaystyle H}$ have the same universal cover.^[12]
• For all trees ${\displaystyle T}$, there are an equal number of homomorphisms from ${\displaystyle T}$ to ${\displaystyle G}$ as there are from ${\displaystyle T}$ to ${\displaystyle H}$.^[13]
• ${\displaystyle G}$ and ${\displaystyle H}$ cannot be distinguished by the two variable fragment of first order logic with counting.^[14]
• Any message passing graph neural network will map ${\displaystyle G}$ and ${\displaystyle H}$ to the same output, if the input node features are the initial colors ${\displaystyle \lambda _{0}}$.^[15][16]
• Any synchronous anonymous algorithm with broadcast/mailbox message passing in which the input depends on the color only will generate an output that depends, again, on the initial color only.^[17]