Document Open Access Logo

A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors Martin Grohe, Sandra Kiefer

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.117.pdf
  • Filesize: 0.64 MB
  • 15 pages

Document Identifiers

Author Details

Martin Grohe
  • RWTH Aachen University, Aachen, Germany
Sandra Kiefer
  • RWTH Aachen University, Aachen, Germany

Cite As Get BibTex

Martin Grohe and Sandra Kiefer. A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 117:1-117:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.117

Abstract

The Weisfeiler-Leman (WL) dimension of a graph is a measure for the inherent descriptive complexity of the graph. While originally derived from a combinatorial graph isomorphism test called the Weisfeiler-Leman algorithm, the WL dimension can also be characterised in terms of the number of variables that is required to describe the graph up to isomorphism in first-order logic with counting quantifiers.
It is known that the WL dimension is upper-bounded for all graphs that exclude some fixed graph as a minor [M. Grohe, 2017]. However, the bounds that can be derived from this general result are astronomic. Only recently, it was proved that the WL dimension of planar graphs is at most 3 [S. Kiefer et al., 2017].
In this paper, we prove that the WL dimension of graphs embeddable in a surface of Euler genus g is at most 4g+3. For the WL dimension of graphs embeddable in an orientable surface of Euler genus g, our approach yields an upper bound of 2g + 3.

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
  • bounded genus

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. Google Scholar
  2. V. Arvind, J. Köbler, G. Rattan, and O. Verbitsky. On Tinhofer’s Linear Programming Approach to Isomorphism Testing. In G. F. Italiano, G. Pighizzini, and D. Sannella, editors, Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS, Part II, volume 9235 of Lecture Notes in Computer Science, pages 26-37. Springer Verlag, 2015. Google Scholar
  3. V. Arvind, J. Köbler, G. Rattan, and O. Verbitsky. Graph Isomorphism, Color Refinement, and Compactness. Computational Complexity, 26(3):627-685, 2017. Google Scholar
  4. A. Atserias and E. Maneva. Sherali-Adams relaxations and indistinguishability in counting logics. SIAM J. Comput., 42(1):112-137, 2013. Google Scholar
  5. 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, pages 66-75, 2018. Google Scholar
  6. 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. Google Scholar
  7. C. Berkholz and M. Grohe. Limitations of Algebraic Approaches to Graph Isomorphism Testing. In M. M. Halldórsson, K. Iwama, N. Kobayashi, and B. Speckmann, editors, Proceedings of the 42nd International Colloquium on Automata, Languages and Programming, Part I, volume 9134 of Lecture Notes in Computer Science, pages 155-166. Springer Verlag, 2015. Google Scholar
  8. 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. Google Scholar
  9. 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, pages 530-534. ACM, 2004. URL: http://dx.doi.org/10.1145/996566.996712.
  10. H. Dell, M. Grohe, and G. Rattan. Lovász Meets Weisfeiler and Leman. In I. Chatzigiannakis, C. Kaklamanis, D. Marx, and D. Sannella, editors, Proceedings of the 45th International Colloquium on Automata, Languages and Programming (Track A), volume 107 of LIPIcs, pages 40:1-40:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  11. R. Diestel. Graph Theory. Springer Verlag, 4th edition, 2010. Google Scholar
  12. M. Fürer. On the Combinatorial Power of the Weisfeiler-Lehman Algorithm. In D. Fotakis, A. Pagourtzis, and V. Th. Paschos, editors, Proceedings of the 10th International Conference on Algorithms and Complexity, volume 10236 of Lecture Notes in Computer Science, pages 260-271. Springer Verlag, 2017. Google Scholar
  13. E. Grädel, M. Grohe, B. Pago, and W. Pakusa. A Finite-Model-Theoretic View on Propositional Proof Complexity, 2018. URL: http://arxiv.org/abs/1802.09377.
  14. M. Grohe. Fixed-point logics on planar graphs. In Proceedings of the 13th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 6-15, 1998. Google Scholar
  15. M. Grohe. Isomorphism testing for embeddable graphs through definability. In Proceedings of the 32nd ACM Symposium on Theory of Computing, pages 63-72, 2000. Google Scholar
  16. M. Grohe. Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors. Journal of the ACM, 59(5), 2012. Google Scholar
  17. M. Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, volume 47 of Lecture Notes in Logic. Cambridge University Press, 2017. Google Scholar
  18. M. Grohe and S. Kiefer. A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus, 2019. URL: http://arxiv.org/abs/1904.07216.
  19. M. Grohe and J. Mariño. Definability and descriptive complexity on databases of bounded tree-width. In C. Beeri and P. Buneman, editors, Proceedings of the 7th International Conference on Database Theory, volume 1540 of Lecture Notes in Computer Science, pages 70-82. Springer-Verlag, 1999. Google Scholar
  20. M. Grohe and D. Neuen. Canonisation and Definability for Graphs of Bounded Rank Width, 2019. URL: http://arxiv.org/abs/1901.10330.
  21. M. Grohe and M. Otto. Pebble Games and Linear Equations. Journal of Symbolic Logic, 80(3):797-844, 2015. Google Scholar
  22. W. L. Hamilton, Z. Ying, and J. Leskovec. Inductive Representation Learning on Large Graphs. In Proceedings of the 31st Conference on Neural Information Processing Systems, pages 1025-1035, 2017. URL: http://papers.nips.cc/paper/6703-inductive-representation-learning-on-large-graphs.
  23. N. Immerman. Descriptive Complexity. Springer Verlag, 1999. Google Scholar
  24. N. Immerman and E. Lander. Describing graphs: A first-order approach to graph canonization. In A. Selman, editor, Complexity theory retrospective, pages 59-81. Springer-Verlag, 1990. Google Scholar
  25. T. A. Junttila and P. Kaski. Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs. In Proceedings of the 9th SIAM Workshop on Algorithm Engineering and Experiments. SIAM, 2007. URL: http://dx.doi.org/10.1137/1.9781611972870.13.
  26. S. Kiefer, I. Ponomarenko, and P. Schweitzer. The Weisfeiler-Leman dimension of planar graphs is at most 3. In Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017. Google Scholar
  27. S. Kiefer and P. Schweitzer. Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic. In M. Grohe, E. Koskinen, and N. Shankar, editors, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pages 287-296, 2016. Google Scholar
  28. S. Kiefer, P. Schweitzer, and E. Selman. Graphs Identified by Logics with Counting. In G. F. Italiano, G. Pighizzini, and D. Sannella, editors, Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS, Part I, volume 9235 of Lecture Notes in Computer Science, pages 319-330. Springer Verlag, 2015. Google Scholar
  29. T. N. Kipf and M. Welling. Semi-Supervised Classification with Graph Convolutional Networks. In Proceedings of the 5th International Conference on Learning Representations, 2017. URL: https://openreview.net/forum?id=SJU4ayYgl.
  30. J. Köbler, S. Kuhnert, B. Laubner, and O. Verbitsky. Interval graphs: Canonical representations in logspace. SIAM Journal on Computing, 40(5):1292-1315, 2011. Google Scholar
  31. A. Krebs and O. Verbitsky. Universal Covers, Color Refinement, and Two-Variable Counting Logic: Lower Bounds for the Depth. In Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 689-700, 2015. Google Scholar
  32. B. Laubner. Capturing Polynomial Time on Interval Graphs. In Proceedings of the 25th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 199-208, 2010. Google Scholar
  33. P. Malkin. Sherali-Adams relaxations of graph isomorphism polytopes. Discrete Optimization, 12:73-97, 2014. Google Scholar
  34. B. D. McKay. Practical graph isomorphism. Congressus Numerantium, 30:45-87, 1981. Google Scholar
  35. B. D. McKay and A. Piperno. Practical graph isomorphism, II. J. Symb. Comput., 60:94-112, 2014. URL: http://dx.doi.org/10.1016/j.jsc.2013.09.003.
  36. B. Mohar and C. Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001. Google Scholar
  37. 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. Google Scholar
  38. R. O'Donnell, J. Wright, C. Wu, and Y. Zhou. Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1659-1677, 2014. Google Scholar
  39. M. Otto. Bounded variable logics and counting - A study in finite models, volume 9 of Lecture Notes in Logic. Springer Verlag, 1997. Google Scholar
  40. 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
  41. 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.
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