Document Open Access Logo

Logarithmic Weisfeiler-Leman Identifies All Planar Graphs

Authors Martin Grohe , Sandra Kiefer

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.134.pdf
  • Filesize: 0.81 MB
  • 20 pages

Document Identifiers

Author Details

Martin Grohe
  • RWTH Aachen University, Germany
Sandra Kiefer
  • University of Warsaw, Poland
  • RWTH Aachen University, Germany

Funding

  • Kiefer, Sandra: supported by the European Research Council under the European Union’s Horizon 2020 research and innovation programme (ERC consolidator grant LIPA, agreement no. 683080).

Cite As Get BibTex

Martin Grohe and Sandra Kiefer. Logarithmic Weisfeiler-Leman Identifies All Planar Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 134:1-134:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.134

Abstract

The Weisfeiler-Leman (WL) algorithm is a well-known combinatorial procedure for detecting symmetries in graphs and it is widely used in graph-isomorphism tests. It proceeds by iteratively refining a colouring of vertex tuples. The number of iterations needed to obtain the final output is crucial for the parallelisability of the algorithm. 
We show that there is a constant k such that every planar graph can be identified (that is, distinguished from every non-isomorphic graph) by the k-dimensional WL algorithm within a logarithmic number of iterations. This generalises a result due to Verbitsky (STACS 2007), who proved the same for 3-connected planar graphs.
The number of iterations needed by the k-dimensional WL algorithm to identify a graph corresponds to the quantifier depth of a sentence that defines the graph in the (k+1)-variable fragment C^{k+1} of first-order logic with counting quantifiers. Thus, our result implies that every planar graph is definable with a C^{k+1}-sentence of logarithmic quantifier depth.

Subject Classification

ACM Subject Classification
  • Theory of computation → Finite Model Theory
  • Mathematics of computing → Graph theory
Keywords
  • Weisfeiler-Leman algorithm
  • finite-variable logic
  • isomorphism testing
  • planar graphs
  • quantifier depth
  • iteration number

Metrics

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

Related Versions

References

  1. B. Ahmadi, K. Kersting, M. Mladenov, and S. Natarajan. Exploiting symmetries for scaling loopy belief propagation and relational training. Machine Learning Journal, 92(1):91-132, 2013. URL: https://doi.org/10.1007/s10994-013-5385-0.
  2. A. Atserias and E. N. Maneva. Sherali-Adams relaxations and indistinguishability in counting logics. SIAM Journal on Computing, 42(1):112-137, 2013. URL: https://doi.org/10.1137/120867834.
  3. A. Atserias and J. Ochremiak. Definable ellipsoid method, sums-of-squares proofs, and the isomorphism problem. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS '18), pages 66-75, 2018. URL: https://doi.org/10.1145/3209108.3209186.
  4. L. Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC '16), pages 684-697, 2016. URL: https://doi.org/10.1145/2897518.2897542.
  5. J. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12:389-410, 1992. URL: https://doi.org/10.1007/BF01305232.
  6. G. Chen and I. Ponomarenko. Lectures on coherent configurations. Lecture notes available at http://www.pdmi.ras.ru/~inp/ccNOTES.pdf, 2019.
  7. P. T. Darga, M. H. Liffiton, K. A. Sakallah, and I. L. Markov. Exploiting structure in symmetry detection for CNF. In Proceedings of the 41st Design Automation Conference (DAC '04), pages 530-534. ACM, 2004. URL: https://doi.org/10.1145/996566.996712.
  8. H. Dell, M. Grohe, and G. Rattan. Lovász meets Weisfeiler and Leman. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP '18), pages 40:1-40:14, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.40.
  9. R. Diestel. Graph Theory. Springer Verlag, 5th edition, 2016. Google Scholar
  10. Z. Dvorák. On recognizing graphs by numbers of homomorphisms. Journal of Graph Theory, 64(4):330-342, 2010. URL: https://doi.org/10.1002/jgt.20461.
  11. M. Elberfeld, A. Jakoby, and T. Tantau. Logspace versions of the theorems of Bodlaender and Courcelle. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS '10), pages 143-152, 2010. URL: https://doi.org/10.1109/FOCS.2010.21.
  12. S. Evdokimov, I. N. Ponomarenko, and G. Tinhofer. Forestal algebras and algebraic forests (on a new class of weakly compact graphs). Discrete Mathematics, 225(1-3):149-172, 2000. URL: https://doi.org/10.1016/S0012-365X(00)00152-7.
  13. M. Grohe. Fixed-point logics on planar graphs. In Proceedings of the 13th IEEE Symposium on Logic in Computer Science (LICS '98), pages 6-15, 1998. URL: https://doi.org/10.1109/LICS.1998.705639.
  14. M. Grohe. Isomorphism testing for embeddable graphs through definability. In Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC '00), pages 63-72, 2000. URL: https://doi.org/10.1145/335305.335313.
  15. M. Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, volume 47 of Lecture Notes in Logic. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781139028868.
  16. M. Grohe. The logic of graph neural networks. In Proceedings of the 36th ACM-IEEE Symposium on Logic in Computer Science (LICS '21)), 2021. arXiv version at URL: https://arxiv.org/abs/2104.14624.
  17. M. Grohe and S. Kiefer. A linear upper bound on the Weisfeiler-Leman dimension of graphs of bounded genus. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP '19), pages 117:1-117:15, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.117.
  18. M. Grohe and J. Mariño. Definability and descriptive complexity on databases of bounded tree-width. In Proceedings of the 7th International Conference on Database Theory (ICDT '99), volume 1540 of Lecture Notes in Computer Science, pages 70-82. Springer, 1999. URL: https://doi.org/10.1007/3-540-49257-7_6.
  19. M. Grohe and D. Neuen. Canonisation and definability for graphs of bounded rank width. In Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS '19), pages 1-13, 2019. URL: https://doi.org/10.1109/LICS.2019.8785682.
  20. M. Grohe and M. Otto. Pebble games and linear equations. Journal of Symbolic Logic, 80(3):797-844, 2015. URL: https://doi.org/10.1017/jsl.2015.28.
  21. M. Grohe and O. Verbitsky. Testing graph isomorphism in parallel by playing a game. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP '06), pages 3-14, 2006. URL: https://doi.org/10.1007/11786986_2.
  22. N. Immerman and E. Lander. Describing graphs: A first-order approach to graph canonization. In Complexity theory retrospective, pages 59-81. Springer-Verlag, 1990. Google Scholar
  23. T. A. Junttila and P. Kaski. Engineering an efficient canonical labeling tool for large and sparse graphs. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX '07). SIAM, 2007. URL: https://doi.org/10.1137/1.9781611972870.13.
  24. S. 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.
  25. S. Kiefer and B. D. McKay. The iteration number of Colour Refinement. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP '20), 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.
  26. S. Kiefer and D. Neuen. The power of the Weisfeiler-Leman algorithm to decompose graphs. In Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS '19), volume 138 of Leibniz International Proceedings in Informatics (LIPIcs), pages 45:1-45:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.45.
  27. S. Kiefer, I. Ponomarenko, and P. 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.
  28. S. Kiefer and P. Schweitzer. Upper bounds on the quantifier depth for graph differentiation in first-order logic. Log. Methods Comput. Sci., 15(2), 2019. URL: https://doi.org/10.23638/LMCS-15(2:19)2019.
  29. J. Köbler and O. Verbitsky. From invariants to canonization in parallel. In Proceedings of the 3rd International Computer Science Symposium in Russia (CSR '08), 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.
  30. M. Lichter, I. Ponomarenko, and P. Schweitzer. Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm. In Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS '19), pages 1-13. IEEE, 2019. URL: https://doi.org/10.1109/LICS.2019.8785694.
  31. B. D. McKay. Practical graph isomorphism. Congressus Numerantium, 30:45-87, 1981. Google Scholar
  32. B. D. McKay and A. Piperno. Practical graph isomorphism, II. J. Symb. Comput., 60:94-112, 2014. URL: https://doi.org/10.1016/j.jsc.2013.09.003.
  33. C. Morris, M. Ritzert, M. Fey, W. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, 2019. URL: https://doi.org/10.1609/aaai.v33i01.33014602.
  34. N. Shervashidze, P. Schweitzer, E. J. van Leeuwen, K. Mehlhorn, and K. M. Borgwardt. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12:2539-2561, 2011. Google Scholar
  35. W. T. Tutte. Graph Theory. Addison-Wesley, 1984. Google Scholar
  36. O. Verbitsky. Planar graphs: Logical complexity and parallel isomorphism tests. In Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS '07), pages 682-693, 2007. URL: https://doi.org/10.1007/978-3-540-70918-3_58.
  37. B. Weisfeiler and A. 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.
  38. H. Whitney. Congruent graphs and the connectivity of graphs. American Journal of Mathematics, 54:150-168, 1932. Google Scholar
  39. K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In Proceedings of the 7th International Conference on Learning Representations (ICLR '19), 2019. Google Scholar
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 About DROPS Imprint Privacy Contact