LIPIcs.ICALP.2021.15.pdf
- Filesize: 0.81 MB
- 15 pages
Document
Comparative Design-Choice Analysis of Color Refinement Algorithms Beyond the Worst Case
Authors
-
Part of:
Volume:
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-07-02
Cite AsGet BibTex
Markus Anders, Pascal Schweitzer, and Florian Wetzels. Comparative Design-Choice Analysis of Color Refinement Algorithms Beyond the Worst Case. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.15
https://doi.org/10.4230/LIPIcs.ICALP.2021.15
Abstract
Color refinement is a crucial subroutine in symmetry detection in theory as well as practice. It has further applications in machine learning and in computational problems from linear algebra.
While tight lower bounds for the worst case complexity are known [Berkholz, Bonsma, Grohe, ESA2013] no comparative analysis of design choices for color refinement algorithms is available.
We devise two models within which we can compare color refinement algorithms using formal methods, an online model and an approximation model. We use these to show that no online algorithm is competitive beyond a logarithmic factor and no algorithm can approximate the optimal color refinement splitting scheme beyond a logarithmic factor.
We also directly compare strategies used in practice showing that, on some graphs, queue based strategies outperform stack based ones by a logarithmic factor and vice versa. Similar results hold for strategies based on priority queues.
Subject Classification
ACM Subject Classification
- Theory of computation → Design and analysis of algorithms
- Theory of computation → Online algorithms
Keywords
- Color refinement
- Online algorithms
- Graph isomorphism
- Lower bounds
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Markus Anders and Pascal Schweitzer. Engineering a fast probabilistic isomorphism test. In 2021 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), pages 73-84. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976472.6.
- Markus Anders, Pascal Schweitzer, and Florian Wetzels. Comparative design-choice analysis of color refinement algorithms beyond the worst case. CoRR, abs/2103.10244, 2021. full version of the paper. URL: http://arxiv.org/abs/2103.10244.
- Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, and Gaurav Rattan. The parameterized complexity of fixing number and vertex individualization in graphs. In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, volume 58 of LIPIcs, pages 13:1-13:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.MFCS.2016.13.
- Christoph Berkholz, Paul S. Bonsma, and Martin Grohe. Tight lower and upper bounds for the complexity of canonical colour refinement. Theory Comput. Syst., 60(4):581-614, 2017. URL: https://doi.org/10.1007/s00224-016-9686-0.
- Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identifications. Comb., 12(4):389-410, 1992. URL: https://doi.org/10.1007/BF01305232.
- Martin Grohe. Equivalence in finite-variable logics is complete for polynomial time. In 37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington, Vermont, USA, 14-16 October, 1996, pages 264-273. IEEE Computer Society, 1996. URL: https://doi.org/10.1109/SFCS.1996.548485.
- 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.
-
J.E. Hopcroft. An n log n algorithm for minimizing states in a finite automaton. In Theory of Machines and Computations, pages 189-196. Academic Press, 1971.
- 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.
- Sandra Kiefer and Brendan D. McKay. The iteration number of colour refinement. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 73:1-73:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.73.
-
Brendan D. McKay. Practical graph isomorphism. In 10th. Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, 1980), pages 45-87, 1981.
- Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II. J. Symb. Comput., 60:94-112, 2014. URL: https://doi.org/10.1016/j.jsc.2013.09.003.
- Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, pages 4602-4609. AAAI Press, 2019. URL: https://doi.org/10.1609/aaai.v33i01.33014602.
- Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 475-484. ACM, 1997. URL: https://doi.org/10.1145/258533.258641.
- Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lehman graph kernels. J. Mach. Learn. Res., 12:2539-2561, 2011. URL: http://dl.acm.org/citation.cfm?id=2078187.