A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk)

Author Martin Grohe



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.2.pdf
  • Filesize: 372 kB
  • 1 pages

Document Identifiers

Author Details

Martin Grohe
  • RWTH Aachen University, Germany

Cite AsGet BibTex

Martin Grohe. A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk). In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.2

Abstract

The Weisfeiler-Leman algorithm is a well-known combinatorial graph isomorphism test going back to work of Weisfeiler and Leman in the late 1960s. The algorithm has a surprising number of seemingly unrelated characterisations in terms of logic, algebra, linear and semi-definite programming, and graph homomorphisms. Due to its simplicity and efficiency, it is an important subroutine of all modern graph isomorphism tools. In recent years, further applications in linear optimisation, probabilistic inference, and machine learning have surfaced. In my talk, I will introduce the Weisfeiler-Leman algorithm and some extensions. I will discuss its expressiveness and the various characterisations, and I will speak about its applications.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
  • Theory of computation → Logic
Keywords
  • Weisfeiler-Leman algorithm
  • graph isomorphism
  • counting homomorphisms
  • finite variable logics

Metrics

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

References

  1. Martin Grohe. word2vec, node2vec, graph2vec, x2vec: Towards a theory of vector embeddings of structured data. In Dan Suciu, Yufei Tao, and Zhewei Wei, editors, Proceedings of the 39th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 1-16, 2020. URL: https://doi.org/10.1145/3375395.3387641.
  2. Martin Grohe. The logic of graph neural networks. In Proceedings of the 36th ACM-IEEE Symposium on Logic in Computer Science, 2021. Google Scholar
  3. Martin Grohe, Kristian Kersting, Martin Mladenov, and Pascal Schweitzer. Color refinement and its applications. In G. Van den Broeck, K. Kersting, S. Natarajan, and D. Poole, editors, An Introduction to Lifted Probabilistic Inference. Cambridge University Press, 2021. To appear. URL: https://www.lics.rwth-aachen.de/global/show_document.asp?id=aaaaaaaaabbtcqu.
  4. Martin Grohe, Pascal Schweitzer, and Daniel Wiebking. Deep Weisfeiler Leman. In Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms, pages 2600-2614, 2021. URL: https://doi.org/10.1137/1.9781611976465.154.
  5. Sandra Kiefer. The Weisfeiler-Leman algorithm: An exploration of its power. ACM SIGLOG News, 7(3):5-27, 2020. Google Scholar
  6. Christopher Morris, Matthias Fey, and Nils M. Kriege. The power of the Weisfeiler-Leman algorithm for machine learning with graphs. ArXiv, 2105.05911, 2021. URL: http://arxiv.org/abs/2105.05911.
  7. B.Y. Weisfeiler and A.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