Colour refinement algorithm: Difference between revisions

From HandWiki
url
 
update
 
Line 2: Line 2:


== History ==
== History ==
The colour refinement algorithm appears in a chemistry paper in 1965<ref>{{Cite journal |last=Morgan |first=H. L. |date=1965-05-01 |title=The Generation of a Unique Machine Description for Chemical Structures-A Technique Developed at Chemical Abstracts Service. |url=https://doi.org/10.1021/c160017a018 |journal=Journal of Chemical Documentation |volume=5 |issue=2 |pages=107–113 |doi=10.1021/c160017a018 |issn=0021-9576|url-access=subscription }}</ref>.
The first appearance of color refinement is in Stephen H. Unger's program GIT
for graph isomorphism, where it is called the {{smallcaps|Extend}} method.<ref
name="unger">{{cite journal |last=Unger |first=Stephen H. |title=GIT&mdash;A Heuristic Program for Testing Pairs of Directed Line Graphs for Isomorphism
|journal=[[Communications of the ACM]] |volume=7 |issue=1 |pages=26–34
|year=1964|doi=10.1145/363872.363899}}</ref>
It was described again, immediately after, in a chemistry paper.<ref>{{Cite journal |last=Morgan |first=H. L. |date=1965-05-01 |title=The Generation of a Unique Machine Description for Chemical Structures-A Technique Developed at Chemical Abstracts Service. |url=https://doi.org/10.1021/c160017a018 |journal=Journal of Chemical Documentation |volume=5 |issue=2 |pages=107–113 |doi=10.1021/c160017a018 |issn=0021-9576|url-access=subscription }}</ref>


== Description ==
== Description ==
Line 28: Line 33:
==Equivalent Characterizations==
==Equivalent Characterizations==


For two graphs <math>G</math> and <math>H</math>, the following conditions are equivalent:
For two graphs <math>G</math> and <math>H</math> with the same number of vertices, the following conditions are equivalent:
* <math>G</math> and <math>H</math> are indistinguishable by colour refinement.
* <math>G</math> and <math>H</math> are indistinguishable by colour refinement.
* The minimum fibration bases of <math>G</math> and <math>H</math> are isomorphic.
* <math>G</math> and <math>H</math> are [[Fractional graph isomorphism|fractionally isomorphic]].<ref>{{cite journal |last1=Tinhofer |first1=Gottfried |title=Graph isomorphism and theorems of Birkhoff type |journal=Computing |date=December 1986 |volume=36 |issue=4 |pages=285–300 |doi=10.1007/BF02240204 |url=https://link.springer.com/article/10.1007/BF02240204|url-access=subscription }}</ref><ref>{{cite journal |last1=Tinhofer |first1=Gottfried |title=A note on compact graphs |journal=Discrete Applied Mathematics |date=February 1991 |volume=30 |issue=2–3 |pages=253–264|doi=10.1016/0166-218X(91)90049-3 |url=https://dx.doi.org/10.1016/0166-218X%2891%2990049-3|url-access=subscription }}</ref>
* <math>G</math> and <math>H</math> are [[Fractional graph isomorphism|fractionally isomorphic]].<ref>{{cite journal |last1=Tinhofer |first1=Gottfried |title=Graph isomorphism and theorems of Birkhoff type |journal=Computing |date=December 1986 |volume=36 |issue=4 |pages=285–300 |doi=10.1007/BF02240204 |url=https://link.springer.com/article/10.1007/BF02240204|url-access=subscription }}</ref><ref>{{cite journal |last1=Tinhofer |first1=Gottfried |title=A note on compact graphs |journal=Discrete Applied Mathematics |date=February 1991 |volume=30 |issue=2–3 |pages=253–264|doi=10.1016/0166-218X(91)90049-3 |url=https://dx.doi.org/10.1016/0166-218X%2891%2990049-3|url-access=subscription }}</ref>
* <math>G</math> and <math>H</math> have a common coarsest [[Fractional graph isomorphism#Equivalence to coarsest equitable partition|equitable partition]].  
* <math>G</math> and <math>H</math> have a common coarsest [[Fractional graph isomorphism#Equivalence to coarsest equitable partition|equitable partition]].  
* <math>G</math> and <math>H</math> have the same [[Covering graph#Universal cover|universal cover]].<ref>{{cite book |last1=Krebs |first1=Andreas |last2=Verbitsky |first2=Oleg |chapter=Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth |title=2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science |date=2015 |volume=30 |pages=689–700 |doi=10.1109/LICS.2015.69 |isbn=978-1-4799-8875-4 |chapter-url=https://dl.acm.org/doi/10.1109/LICS.2015.69}}</ref>
* <math>G</math> and <math>H</math> have the same [[Covering graph#Universal cover|universal cover]].<ref>{{cite book |last1=Krebs |first1=Andreas |last2=Verbitsky |first2=Oleg |chapter=Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth |title=2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science |date=2015 |volume=30 |pages=689–700 |doi=10.1109/LICS.2015.69 |isbn=978-1-4799-8875-4 |chapter-url=https://dl.acm.org/doi/10.1109/LICS.2015.69}}</ref>
* For all [[Tree (graph theory)|trees]] <math>T</math>, there are an equal number of [[Graph homomorphism|homomorphisms]] from <math>T</math> to <math>G</math> as there are from <math>T</math> to <math>H</math>. <ref>{{cite book |last1=Dell |first1=Holger |last2=Grohe |first2=Martin |last3=Rattan |first3=Gaurav |title=Lovász Meets Weisfeiler and Leman |series=Leibniz International Proceedings in Informatics (LIPIcs) |date=2018 |volume=45 |pages=40:1–40:14 |publisher=Schloss Dagstuhl – Leibniz-Zentrum für Informatik |doi=10.4230/LIPIcs.ICALP.2018.40 |isbn=978-3-95977-076-7 |doi-access=free }}</ref>  
* For all [[Tree (graph theory)|trees]] <math>T</math>, there are an equal number of [[Graph homomorphism|homomorphisms]] from <math>T</math> to <math>G</math> as there are from <math>T</math> to <math>H</math>.<ref>{{cite book |last1=Dell |first1=Holger |last2=Grohe |first2=Martin |last3=Rattan |first3=Gaurav |title=Lovász Meets Weisfeiler and Leman |series=Leibniz International Proceedings in Informatics (LIPIcs) |date=2018 |volume=45 |pages=40:1–40:14 |publisher=Schloss Dagstuhl – Leibniz-Zentrum für Informatik |doi=10.4230/LIPIcs.ICALP.2018.40 |isbn=978-3-95977-076-7 |doi-access=free }}</ref>  
* <math>G</math> and <math>H</math> cannot be distinguished by the [[Two-variable logic|two variable fragment of first order logic]] with [[Counting quantification|counting]].<ref>Grohe, Martin. "Finite variable logics in descriptive complexity theory." Bulletin of Symbolic Logic 4.4 (1998): 345-398.</ref>
* <math>G</math> and <math>H</math> cannot be distinguished by the [[Two-variable logic|two variable fragment of first order logic]] with [[Counting quantification|counting]].<ref>Grohe, Martin. "Finite variable logics in descriptive complexity theory." Bulletin of Symbolic Logic 4.4 (1998): 345-398.</ref>
* Any [[Graph neural network#Message passing layers|message passing graph neural network]] will map <math>G</math> and <math>H</math> to the same output, if the input node features are the initial colours <math>\lambda_0</math>. <ref>{{Cite conference | last1 = Morris | first1 = Christopher | last2 = Ritzert | first2 = Martin | last3 = Fey | first3 = Matthias | last4 = Hamilton | first4 = William L. | last5 = Lenssen | first5 = Jan Eric | last6 = Rattan | first6 = Gaurav | last7 = Grohe | first7 = Martin | title = Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks | book-title = Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence | series = AAAI'19 | publisher = AAAI Press | location = Honolulu, Hawaii, USA | year = 2019 | isbn = 978-1-57735-809-1 | pages = 565–572 | doi = 10.1609/aaai.v33i01.33014602 | url = https://doi.org/10.1609/aaai.v33i01.33014602 | arxiv = 1810.02244 }}</ref><ref>{{Cite conference | last1 = Xu | first1 = Keyulu | last2 = Hu | first2 = Weihua | last3 = Leskovec | first3 = Jure | last4 = Jegelka | first4 = Stefanie | title = How Powerful are Graph Neural Networks? | book-title = International Conference on Learning Representations (ICLR) | year = 2019 | url = https://openreview.net/forum?id=ryGs6iA5Km
* Any [[Graph neural network#Message passing layers|message passing graph neural network]] will map <math>G</math> and <math>H</math> to the same output, if the input node features are the initial colours <math>\lambda_0</math>.<ref>{{Cite conference | last1 = Morris | first1 = Christopher | last2 = Ritzert | first2 = Martin | last3 = Fey | first3 = Matthias | last4 = Hamilton | first4 = William L. | last5 = Lenssen | first5 = Jan Eric | last6 = Rattan | first6 = Gaurav | last7 = Grohe | first7 = Martin | title = Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks | book-title = Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence | series = AAAI'19 | publisher = AAAI Press | location = Honolulu, Hawaii, USA | year = 2019 | isbn = 978-1-57735-809-1 | pages = 565–572 | doi = 10.1609/aaai.v33i01.33014602 | url = https://doi.org/10.1609/aaai.v33i01.33014602 | arxiv = 1810.02244 }}</ref><ref>{{Cite conference | last1 = Xu | first1 = Keyulu | last2 = Hu | first2 = Weihua | last3 = Leskovec | first3 = Jure | last4 = Jegelka | first4 = Stefanie | title = How Powerful are Graph Neural Networks? | book-title = International Conference on Learning Representations (ICLR) | year = 2019 | url = https://openreview.net/forum?id=ryGs6iA5Km
}}</ref>
}}</ref>
 
* 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.<ref
== History ==
name="boldivigna_effective">{{cite conference |last1=Boldi |first1=Paolo
 
|last2=Vigna |first2=Sebastiano |title=An Effective Characterization of Computability in Anonymous Networks |book-title=Distributed Computing (DISC 2001)
|series=Lecture Notes in Computer Science|volume=2180
|year=2001|pages=33–47|publisher=Springer-Verlag|doi=10.1007/3-540-45414-4_3}}</ref>


==References==
==References==

Latest revision as of 13:55, 14 April 2026

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

History

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]

Description

The algorithm takes as an input a graph G with n 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 λi as follows:

  • λ0 is the initial colouring. If the graph is unlabelled, the initial colouring assigns a trivial colour λ0(v) to each vertex v. If the graph is labelled, λ0 is the label of vertex v.
  • For all vertices v, we set λi+1(v)=(λi(v),{{λi(w)∣w is a neighbor of v}}).

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., λi+1(u)=λi+1(v) if and only if λi(u)=λi(v). 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 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 G and H 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 n vertex graph as input, a stable colouring is produced after at most n−1 iterations. Conversely, there exist graphs where this bound is realised.[4] This leads to a O((n+m)log⁡n) implementation where n is the number of vertices and m the number of edges.[5] This complexity has been proven to be optimal under reasonable assumptions.[6]

Expressivity

We say that two graphs G and H are distinguished by colour refinement if the algorithm yields a different output on G as on H. 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 [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 n increases, the proportion of graphs that are not identified by colour refinement decreases exponentially in order n.[9]

Equivalent Characterizations

For two graphs G and H with the same number of vertices, the following conditions are equivalent:

References

  1. ↑ 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. 
  2. ↑ Unger, Stephen H. (1964). "GIT—A Heuristic Program for Testing Pairs of Directed Line Graphs for Isomorphism". Communications of the ACM 7 (1): 26–34. doi:10.1145/363872.363899. 
  3. ↑ Morgan, H. L. (1965-05-01). "The Generation of a Unique Machine Description for Chemical Structures-A Technique Developed at Chemical Abstracts Service.". Journal of Chemical Documentation 5 (2): 107–113. doi:10.1021/c160017a018. ISSN 0021-9576. https://doi.org/10.1021/c160017a018. 
  4. ↑ Kiefer, Sandra; McKay, Brendan D. (2020-05-20), The Iteration Number of Colour Refinement 
  5. ↑ 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. 
  6. ↑ 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. 
  7. ↑ 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. 
  8. ↑ 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. 
  9. ↑ Babai, L.; Kucera, K. (1979). "Canonical labelling of graphs in linear average time". 20th Annual Symposium on Foundations of Computer Science (SFCS 1979). pp. 39–46. doi:10.1109/SFCS.1979.8. https://ieeexplore.ieee.org/document/4567999/;jsessionid=3nsdXVGO6TSsLdiJnZQ6slDYPxa-Qyh0XugyK5ti0b5TpRiyrKyo!-452107954. Retrieved 2024-01-18. 
  10. ↑ Tinhofer, Gottfried (December 1986). "Graph isomorphism and theorems of Birkhoff type". Computing 36 (4): 285–300. doi:10.1007/BF02240204. https://link.springer.com/article/10.1007/BF02240204. 
  11. ↑ Tinhofer, Gottfried (February 1991). "A note on compact graphs". Discrete Applied Mathematics 30 (2–3): 253–264. doi:10.1016/0166-218X(91)90049-3. https://dx.doi.org/10.1016/0166-218X%2891%2990049-3. 
  12. ↑ Krebs, Andreas; Verbitsky, Oleg (2015). "Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth". 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science. 30. pp. 689–700. doi:10.1109/LICS.2015.69. ISBN 978-1-4799-8875-4. https://dl.acm.org/doi/10.1109/LICS.2015.69. 
  13. ↑ Dell, Holger; Grohe, Martin; Rattan, Gaurav (2018). Lovász Meets Weisfeiler and Leman. Leibniz International Proceedings in Informatics (LIPIcs). 45. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 40:1–40:14. doi:10.4230/LIPIcs.ICALP.2018.40. ISBN 978-3-95977-076-7. 
  14. ↑ Grohe, Martin. "Finite variable logics in descriptive complexity theory." Bulletin of Symbolic Logic 4.4 (1998): 345-398.
  15. ↑ Morris, Christopher; Ritzert, Martin; Fey, Matthias; Hamilton, William L.; Lenssen, Jan Eric; Rattan, Gaurav; Grohe, Martin (2019). "Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks". Honolulu, Hawaii, USA: AAAI Press. pp. 565–572. doi:10.1609/aaai.v33i01.33014602. ISBN 978-1-57735-809-1. https://doi.org/10.1609/aaai.v33i01.33014602. 
  16. ↑ Xu, Keyulu; Hu, Weihua; Leskovec, Jure; Jegelka, Stefanie (2019). "How Powerful are Graph Neural Networks?". https://openreview.net/forum?id=ryGs6iA5Km. 
  17. ↑ Boldi, Paolo; Vigna, Sebastiano (2001). "An Effective Characterization of Computability in Anonymous Networks". 2180. Springer-Verlag. pp. 33–47. doi:10.1007/3-540-45414-4_3. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Colour_refinement_algorithm&oldid=4297194"