Colour refinement algorithm

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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. While it solves graph isomorphism on almost all graphs, there are graphs such as all regular graphs that cannot be distinguished using colour refinement.

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. While it solves graph isomorphism on almost all graphs, there are graphs such as all regular graphs that cannot be distinguished using colour refinement. For all vertices v , we set \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 colour of the vertex v 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., \lambda_{i+1}(u)=\lambda_{i+1}(v) if and only if \lambda_i(u)=\lambda_i(v) . This final colouring is called the stable colouring.

Equivalent Characterizations

For two graphs G and H with the same number of vertices, the following conditions are equivalent: G and H are indistinguishable by colour refinement. The minimum fibration bases of G and H are isomorphic. G and H are fractionally isomorphic. G and H have a common coarsest equitable partition. G and H have the same universal cover. For all trees T , there are an equal number of homomorphisms from T to G as there are from T to H . G and H cannot be distinguished by the two variable fragment of first order logic with counting. Any message passing graph neural network will map G and H to the same output, if the input node features are the initial colours \lambda_0 . 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.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1367493274 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001367493274 · captured 1785749998.0 · version history

Cite this page as: encyclopegia.org, “Colour refinement algorithm”, snapshot enwiki-001367493274. https://encyclopegia.org/a/colour-refinement-algorithm

Sources cited in this revision

10 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.