Document Open Access Logo

The Iteration Number of Colour Refinement

Authors Sandra Kiefer, Brendan D. McKay

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2020.73.pdf
  • Filesize: 0.56 MB
  • 19 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Combinatorial algorithms
  • Mathematics of computing → Graph theory
Keywords
  • Colour Refinement
  • iteration number
  • Weisfeiler-Leman algorithm
  • quantifier depth

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

The Colour Refinement procedure and its generalisation to higher dimensions, the Weisfeiler-Leman algorithm, are central subroutines in approaches to the graph isomorphism problem. In an iterative fashion, Colour Refinement computes a colouring of the vertices of its input graph. 
A trivial upper bound on the iteration number of Colour Refinement on graphs of order n is n-1. We show that this bound is tight. More precisely, we prove via explicit constructions that there are infinitely many graphs G on which Colour Refinement takes |G|-1 iterations to stabilise. Modifying the infinite families that we present, we show that for every natural number n ≥ 10, there are graphs on n vertices on which Colour Refinement requires at least n-2 iterations to reach stabilisation.

Cite As Get BibTex

Sandra Kiefer and Brendan D. McKay. The Iteration Number of Colour Refinement. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 73:1-73:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.73

Author Details

Sandra Kiefer
  • RWTH Aachen University, Germany
Brendan D. McKay
  • Australian National University, Canberra, Australia

References

  1. Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On Weisfeiler-Leman invariance: Subgraph counts and related graph properties. In Fundamentals of Computation Theory - 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14, 2019, Proceedings, pages 111-125, 2019. URL: https://doi.org/10.1007/978-3-030-25027-0_8.
  2. Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky. Graph isomorphism, color refinement, and compactness. Computational Complexity, 26(3):627-685, 2017. URL: https://doi.org/10.1007/s00037-016-0147-6.
  3. László Babai, Paul Erdős, and Stanley M. Selkow. Random graph isomorphism. SIAM Journal on Computing, 9(3):628-635, 1980. URL: https://doi.org/10.1137/0209047.
  4. Christoph Berkholz and Jakob Nordström. Near-optimal lower bounds on quantifier depth and Weisfeiler-Leman refinement steps. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, New York, NY, USA, July 5-8, 2016, pages 267-276, 2016. URL: https://doi.org/10.1145/2933575.2934560.
  5. Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992. Google Scholar
  6. Alain Cardon and Maxime Crochemore. Partitioning a graph in O(|A| log |A|). Theoretical Computer Science, 19:85-98, 1982. URL: https://doi.org/10.1016/0304-3975(82)90016-0.
  7. Paul T. Darga, Mark H. Liffiton, Karem A. Sakallah, and Igor L. Markov. Exploiting structure in symmetry detection for CNF. In Proceedings of the 41th Design Automation Conference, DAC 2004, San Diego, CA, USA, June 7-11, 2004, pages 530-534. ACM, 2004. URL: https://doi.org/10.1145/996566.996712.
  8. Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. Local WL invariance and hidden shades of regularity. CoRR, abs/2002.04590, 2020. URL: http://arxiv.org/abs/2002.04590.
  9. Martin Fürer. Weisfeiler-Lehman refinement requires at least a linear number of iterations. In Automata, Languages and Programming, 28th International Colloquium, ICALP 2001, Crete, Greece, July 8-12, 2001, Proceedings, volume 2076 of Lecture Notes in Computer Science, pages 322-333. Springer, 2001. URL: https://doi.org/10.1007/3-540-48224-5_27.
  10. Martin Fürer. On the combinatorial power of the Weisfeiler-Lehman algorithm. In Dimitris Fotakis, Aris Pagourtzis, and Vangelis Th. Paschos, editors, Proceedings of the Tenth International Conference on Algorithms and Complexity, volume 10236 of Lecture Notes in Computer Science, pages 260-271. Springer Verlag, 2017. URL: https://doi.org/10.1007/978-3-319-57586-5_22.
  11. Maximilian Gödicke. The iteration number of the Weisfeiler-Lehman-algorithm. Master’s thesis, RWTH Aachen University, 2015. Google Scholar
  12. Christopher D. Godsil. Compact graphs and equitable partitions. Linear Algebra Appl., 255:259-266, 1997. URL: https://doi.org/10.1016/S0024-3795(97)83595-1.
  13. Martin Grohe. Fixed-point definability and polynomial time on graphs with excluded minors. J. ACM, 59(5):27, 2012. URL: https://doi.org/10.1145/2371656.2371662.
  14. Martin Grohe, Kristian Kersting, Martin Mladenov, and Erkal Selman. Dimension reduction via colour refinement. In Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, volume 8737 of Lecture Notes in Computer Science, pages 505-516. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-44777-2_42.
  15. Martin Grohe and Sandra Kiefer. A linear upper bound on the Weisfeiler-Leman dimension of graphs of bounded genus. In Proceedings of the Forty-Sixth International Colloquium on Automata, Languages, and Programming, pages 117:1-117:15, July 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.117.
  16. Martin Grohe and Daniel Neuen. Canonisation and definability for graphs of bounded rank width. In Proceedings of the Thirty-Fourth Annual ACM/IEEE Symposium on Logic in Computer Science, pages 1-13, June 2019. URL: https://doi.org/10.1109/LICS.2019.8785682.
  17. Martin Grohe and Oleg Verbitsky. Testing graph isomorphism in parallel by playing a game. In Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, pages 3-14, 2006. URL: https://doi.org/10.1007/11786986_2.
  18. Neil Immerman and Eric Lander. Describing graphs: A first-order approach to graph canonization. In Alan L. Selman, editor, Complexity theory retrospective, pages 59-81. Springer, 1990. URL: https://doi.org/10.1007/978-1-4612-4478-3_5.
  19. Tommi A. Junttila and Petteri Kaski. Engineering an efficient canonical labeling tool for large and sparse graphs. In Proceedings of the Nine Workshop on Algorithm Engineering and Experiments, ALENEX 2007, New Orleans, Louisiana, USA, January 6, 2007. SIAM, 2007. URL: https://doi.org/10.1137/1.9781611972870.13.
  20. Sandra Kiefer. Power and Limits of the Weisfeiler-Leman Algorithm. PhD thesis, RWTH Aachen University, Aachen, 2020. URL: https://doi.org/10.18154/RWTH-2020-03508.
  21. Sandra Kiefer and Brendan D. McKay. The iteration number of Colour Refinement. CoRR, 2020. URL: http://arxiv.org/abs/2005.10182.
  22. Sandra Kiefer and Pascal Schweitzer. Upper bounds on the quantifier depth for graph differentiation in first order logic. In Proceedings of the Thirty-First Annual ACM/IEEE Symposium on Logic in Computer Science, pages 287-296, July 2016. URL: https://doi.org/10.1145/2933575.2933595.
  23. Sandra Kiefer and Pascal Schweitzer. Upper bounds on the quantifier depth for graph differentiation in first-order logic. Logical Methods in Computer Science, 15(2), 2019. URL: https://lmcs.episciences.org/5522, URL: https://doi.org/10.23638/LMCS-15(2:19)2019.
  24. Sandra Kiefer, Pascal Schweitzer, and Erkal Selman. Graphs identified by logics with counting. In Proceedings of the Fortieth International Symposium on Mathematical Foundations of Computer Science, volume 9234 of Lecture Notes in Computer Science, pages 319-330. Springer, August 2015. URL: https://doi.org/10.1007/978-3-662-48057-1_25.
  25. Johannes Köbler and Oleg Verbitsky. From invariants to canonization in parallel. In Computer Science - Theory and Applications, Third International Computer Science Symposium in Russia, CSR 2008, Moscow, Russia, June 7-12, 2008, Proceedings, volume 5010 of Lecture Notes in Computer Science, pages 216-227. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-79709-8_23.
  26. Andreas Krebs and Oleg Verbitsky. Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth. In Proceedings of the Thirtieth Annual ACM/IEEE Symposium on Logic in Computer Science, pages 689-700, 2015. URL: https://doi.org/10.1109/LICS.2015.69.
  27. Wenchao Li, Hossein Saidi, Huascar Sanchez, Martin Schäf, and Pascal Schweitzer. Detecting similar programs via the Weisfeiler-Leman graph kernel. In Software Reuse: Bridging with Social-Awareness - 15th International Conference, ICSR 2016, Limassol, Cyprus, June 5-7, 2016, Proceedings, pages 315-330, 2016. URL: https://doi.org/10.1007/978-3-319-35122-3_21.
  28. Moritz Lichter, Ilia N. Ponomarenko, and Pascal Schweitzer. Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm. In Proceedings of the Thirty-Fourth Annual ACM/IEEE Symposium on Logic in Computer Science, pages 1-13, June 2019. URL: https://doi.org/10.1109/LICS.2019.8785694.
  29. Brendan D. McKay. Practical graph isomorphism. Congressus Numerantium, 30:45-87, 1981. Google Scholar
  30. Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II. Journal of Symbolic Computation, 60:94-112, 2014. URL: https://doi.org/10.1016/j.jsc.2013.09.003.
  31. Harry L. Morgan. 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, 1965. URL: https://doi.org/10.1021/c160017a018.
  32. Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan E. Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, January 2019. URL: https://doi.org/10.1609/aaai.v33i01.33014602.
  33. Motakuri V. Ramana, Edward R. Scheinerman, and Daniel Ullman. Fractional isomorphism of graphs. Discrete Mathematics, 132(1-3):247-265, 1994. URL: https://doi.org/10.1016/0012-365X(94)90241-0.
  34. Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12:2539-2561, 2011. URL: http://dl.acm.org/citation.cfm?id=2078187.
  35. Gottfried Tinhofer. A note on compact graphs. Discrete Applied Mathematics, 30(2-3):253-264, 1991. URL: https://doi.org/10.1016/0166-218X(91)90049-3.
  36. Oleg Verbitsky. Planar graphs: Logical complexity and parallel isomorphism tests. In STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings, pages 682-693, 2007. URL: https://doi.org/10.1007/978-3-540-70918-3_58.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact