Document Open Access Logo

A Study of Weisfeiler-Leman Colorings on Planar Graphs

Authors Sandra Kiefer , Daniel Neuen

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.81.pdf
  • Filesize: 0.83 MB
  • 20 pages

Document Identifiers

Author Details

Sandra Kiefer
  • Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany
Daniel Neuen
  • School of Computing Science, Simon Fraser University, Burnaby, Canada

Cite AsGet BibTex

Sandra Kiefer and Daniel Neuen. A Study of Weisfeiler-Leman Colorings on Planar Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 81:1-81:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.81

Abstract

The Weisfeiler-Leman (WL) algorithm is a combinatorial procedure that computes colorings on graphs, which can often be used to detect their (non-)isomorphism. Particularly the 1- and 2-dimensional versions 1-WL and 2-WL have received much attention, due to their numerous links to other areas of computer science. Knowing the expressive power of a certain dimension of the algorithm usually amounts to understanding the computed colorings. An increase in the dimension leads to finer computed colorings and, thus, more graphs can be distinguished. For example, on the class of planar graphs, 3-WL solves the isomorphism problem. However, the expressive power of 2-WL on the class is poorly understood (and, in particular, it may even well be that it decides isomorphism). In this paper, we investigate the colorings computed by 2-WL on planar graphs. Towards this end, we analyze the graphs induced by edge color classes in the graph. Based on the obtained classification, we show that for every 3-connected planar graph, it holds that: a) after coloring all pairs with their 2-WL color, the graph has fixing number 1 with respect to 1-WL, or b) there is a 2-WL-definable matching that can be used to transform the graph into a smaller one, or c) 2-WL detects a connected subgraph that is essentially the graph of a Platonic or Archimedean solid, a prism, a cycle, or a bipartite graph K_{2,𝓁}. In particular, the graphs from case (a) are identified by 2-WL.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
  • Theory of computation → Finite Model Theory
  • Theory of computation → Graph algorithms analysis
Keywords
  • Weisfeiler-Leman algorithm
  • planar graphs
  • edge-transitive graphs
  • fixing number

Metrics

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

Related Versions

References

  1. Babak Ahmadi, Kristian Kersting, Martin Mladenov, and Sriraam Natarajan. Exploiting symmetries for scaling loopy belief propagation and relational training. Mach. Learn., 92(1):91-132, 2013. URL: https://doi.org/10.1007/s10994-013-5385-0.
  2. Markus Anders and Pascal Schweitzer. Engineering a fast probabilistic isomorphism test. In Martin Farach-Colton and Sabine Storandt, editors, Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2021, Virtual Conference, January 10-11, 2021, pages 73-84. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976472.6.
  3. Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On Weisfeiler-Leman invariance: Subgraph counts and related graph properties. J. Comput. Syst. Sci., 113:42-59, 2020. URL: https://doi.org/10.1016/j.jcss.2020.04.003.
  4. Albert Atserias and Elitza N. Maneva. Sherali-Adams relaxations and indistinguishability in counting logics. SIAM J. Comput., 42(1):112-137, 2013. URL: https://doi.org/10.1137/120867834.
  5. Albert Atserias and Joanna Ochremiak. Definable ellipsoid method, sums-of-squares proofs, and the isomorphism problem. In Anuj Dawar and Erich Grädel, editors, Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018, pages 66-75. ACM, 2018. URL: https://doi.org/10.1145/3209108.3209186.
  6. László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 684-697. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897542.
  7. Béla Bollobás. Distinguishing vertices of random graphs. In Graph theory (Cambridge, 1981), volume 62 of North-Holland Math. Stud., pages 33-49. North-Holland, Amsterdam-New York, 1982. URL: https://doi.org/10.1016/S0304-0208(08)73545-X.
  8. Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Comb., 12(4):389-410, 1992. URL: https://doi.org/10.1007/BF01305232.
  9. Gang Chen and Ilia N. Ponomarenko. Lectures on coherent configurations. Lecture notes available at http://www.pdmi.ras.ru/~inp/ccNOTES.pdf, 2019.
  10. Paul T. Darga, Mark H. Liffiton, Karem A. Sakallah, and Igor L. Markov. Exploiting structure in symmetry detection for CNF. In Sharad Malik, Limor Fix, and Andrew B. Kahng, editors, 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.
  11. Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász meets Weisfeiler and Leman. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 40:1-40:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.40.
  12. Zdenek Dvorák. On recognizing graphs by numbers of homomorphisms. J. Graph Theory, 64(4):330-342, 2010. URL: https://doi.org/10.1002/jgt.20461.
  13. Sergei Evdokimov, Ilia N. Ponomarenko, and Gottfried Tinhofer. Forestal algebras and algebraic forests (on a new class of weakly compact graphs). Discret. Math., 225(1-3):149-172, 2000. URL: https://doi.org/10.1016/S0012-365X(00)00152-7.
  14. Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm. SIAM J. Discret. Math., 35(3):1792-1853, 2021. URL: https://doi.org/10.1137/20M1327550.
  15. Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. Local WL invariance and hidden shades of regularity. Discret. Appl. Math., 305:191-198, 2021. URL: https://doi.org/10.1016/j.dam.2021.08.037.
  16. Martin Fürer. On the combinatorial power of the Weisfeiler-Lehman algorithm. In Dimitris Fotakis, Aris Pagourtzis, and Vangelis Th. Paschos, editors, Algorithms and Complexity - 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings, volume 10236 of Lecture Notes in Computer Science, pages 260-271, 2017. URL: https://doi.org/10.1007/978-3-319-57586-5_22.
  17. Alexander L. Gavrilyuk, Roman Nedela, and Ilia N. Ponomarenko. The Weisfeiler-Leman dimension of distance-hereditary graphs. CoRR, abs/2005.11766, 2020. URL: http://arxiv.org/abs/2005.11766.
  18. Martin Grohe. Fixed-point logics on planar graphs. In Thirteenth Annual IEEE Symposium on Logic in Computer Science, Indianapolis, Indiana, USA, June 21-24, 1998, pages 6-15. IEEE Computer Society, 1998. URL: https://doi.org/10.1109/LICS.1998.705639.
  19. Martin Grohe. Fixed-point definability and polynomial time on graphs with excluded minors. J. ACM, 59(5):27:1-27:64, 2012. URL: https://doi.org/10.1145/2371656.2371662.
  20. Martin Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, volume 47 of Lecture Notes in Logic. Association for Symbolic Logic, Ithaca, NY; Cambridge University Press, Cambridge, 2017. URL: https://doi.org/10.1017/9781139028868.
  21. Martin Grohe. The logic of graph neural networks. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1-17. IEEE, 2021. URL: https://doi.org/10.1109/LICS52264.2021.9470677.
  22. Martin Grohe and Sandra Kiefer. A linear upper bound on the Weisfeiler-Leman dimension of graphs of bounded genus. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 117:1-117:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.117.
  23. Martin Grohe and Sandra Kiefer. Logarithmic Weisfeiler-Leman identifies all planar graphs. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 134:1-134:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.134.
  24. Martin Grohe and Daniel Neuen. Canonisation and definability for graphs of bounded rank width. In 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, BC, Canada, June 24-27, 2019, pages 1-13. IEEE, 2019. URL: https://doi.org/10.1109/LICS.2019.8785682.
  25. Martin Grohe and Martin Otto. Pebble games and linear equations. J. Symb. Log., 80(3):797-844, 2015. URL: https://doi.org/10.1017/jsl.2015.28.
  26. Branko Grünbaum and Geoffrey C. Shephard. Edge-transitive planar graphs. J. Graph Theory, 11(2):141-155, 1987. URL: https://doi.org/10.1002/jgt.3190110204.
  27. Lauri Hella. Logical hierarchies in PTIME. Inf. Comput., 129(1):1-19, 1996. URL: https://doi.org/10.1006/inco.1996.0070.
  28. Neil Immerman. Expressibility as a complexity measure: results and directions. In Proceedings of the Second Annual Conference on Structure in Complexity Theory, Cornell University, Ithaca, New York, USA, June 16-19, 1987, pages 194-202. IEEE Computer Society, 1987. Google Scholar
  29. Neil Immerman and Eric Lander. Describing graphs: A first-order approach to graph canonization. In Alan L. Selman, editor, Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988, pages 59-81. Springer New York, New York, NY, 1990. URL: https://doi.org/10.1007/978-1-4612-4478-3_5.
  30. 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.
  31. Sandra Kiefer. The Weisfeiler-Leman algorithm: an exploration of its power. ACM SIGLOG News, 7(3):5-27, 2020. URL: https://doi.org/10.1145/3436980.3436982.
  32. Sandra Kiefer and Daniel Neuen. The power of the Weisfeiler-Leman algorithm to decompose graphs. SIAM J. Discret. Math., 36(1):252-298, 2022. URL: https://doi.org/10.1137/20M1314987.
  33. Sandra Kiefer and Daniel Neuen. A study of Weisfeiler—Leman colorings on planar graphs. CoRR, abs/2206.10557, 2022. URL: http://arxiv.org/abs/2206.10557.
  34. Sandra Kiefer, Ilia N. Ponomarenko, and Pascal Schweitzer. The Weisfeiler-Leman dimension of planar graphs is at most 3. J. ACM, 66(6):44:1-44:31, 2019. URL: https://doi.org/10.1145/3333003.
  35. Brendan D. McKay. Practical graph isomorphism. Congr. Numer., 30:45-87, 1981. Google Scholar
  36. 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.
  37. 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, Honolulu, Hawaii, USA, January 27 - February 1, 2019, pages 4602-4609. AAAI Press, 2019. URL: https://doi.org/10.1609/aaai.v33i01.33014602.
  38. Joachim Redies. Defining PTIME problems on planar graphs with few variables. Master’s thesis, RWTH Aachen University, 2014. Google Scholar
  39. 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.
  40. Oleg Verbitsky. Planar graphs: Logical complexity and parallel isomorphism tests. In Wolfgang Thomas and Pascal Weil, editors, STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings, volume 4393 of Lecture Notes in Computer Science, pages 682-693. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-70918-3_58.
  41. Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. NTI, Series 2, 1968. English translation by G. Ryabov available at URL: https://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf.
  42. Hassler Whitney. Congruent Graphs and the Connectivity of Graphs. Amer. J. Math., 54(1):150-168, 1932. URL: https://doi.org/10.2307/2371086.
  43. Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL: https://openreview.net/forum?id=ryGs6iA5Km.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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