Lovász Meets Weisfeiler and Leman

Authors Holger Dell , Martin Grohe , Gaurav Rattan



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.40.pdf
  • Filesize: 432 kB
  • 14 pages

Document Identifiers

Author Details

Holger Dell
  • Saarland University and Cluster of Excellence (MMCI), Saarbrücken, Germany
Martin Grohe
  • RWTH Aachen University, Aachen, Germany
Gaurav Rattan
  • RWTH Aachen University, Aachen, Germany

Cite AsGet BibTex

Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász Meets Weisfeiler and Leman. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.40

Abstract

In this paper, we relate a beautiful theory by Lovász with a popular heuristic algorithm for the graph isomorphism problem, namely the color refinement algorithm and its k-dimensional generalization known as the Weisfeiler-Leman algorithm. We prove that two graphs G and H are indistinguishable by the color refinement algorithm if and only if, for all trees T, the number Hom(T,G) of homomorphisms from T to G equals the corresponding number Hom(T,H) for H. There is a natural system of linear equations whose nonnegative integer solutions correspond to the isomorphisms between two graphs. The nonnegative real solutions to this system are called fractional isomorphisms, and two graphs are fractionally isomorphic if and only if the color refinement algorithm cannot distinguish them (Tinhofer 1986, 1991). We show that, if we drop the nonnegativity constraints, that is, if we look for arbitrary real solutions, then a solution to the linear system exists if and only if, for all t, the two graphs have the same number of length-t walks. We lift the results for trees to an equivalence between numbers of homomorphisms from graphs of tree width k, the k-dimensional Weisfeiler-Leman algorithm, and the level-k Sherali-Adams relaxation of our linear program. We also obtain a partial result for graphs of bounded path width and solutions to our system where we drop the nonnegativity constraints. A consequence of our results is a quasi-linear time algorithm to decide whether, for two given graphs G and H, there is a tree T with Hom(T,G)!=Hom(T,H).

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Graph theory
Keywords
  • graph isomorphism
  • graph homomorphism numbers
  • tree width

Metrics

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

References

  1. Samson Abramsky, Anuj Dawar, and Pengming Wang. The pebbling comonad in finite model theory. In Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, pages 1-12. IEEE Computer Society, 2017. URL: http://dx.doi.org/10.1109/LICS.2017.8005129.
  2. Dana Angluin. Local and global properties in networks of processors (extended abstract). In Raymond E. Miller, Seymour Ginsburg, Walter A. Burkhard, and Richard J. Lipton, editors, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, pages 82-93. ACM, 1980. URL: http://dx.doi.org/10.1145/800141.804655.
  3. Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Yadu Vasudev. Approximate graph isomorphism. In Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science, volume 7464 of Lecture Notes in Computer Science, pages 100-111. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-32589-2_12.
  4. Albert Atserias and Elitza N. Maneva. Sherali-Adams relaxations and indistinguishability in counting logics. SIAM Journal on Computing, 42(1):112-137, 2013. URL: http://dx.doi.org/10.1137/120867834.
  5. László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 684-697. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897542.
  6. Paul Beame, Russell Impagliazzo, Jan Krajíček, Toniann Pitassi, and Pavel Pudlák. Lower bounds on Hilbert’s Nullstellensatz and propositional proofs. Proceedings of the London Mathematical Society, s3-73(1):1-26, 1996. URL: http://dx.doi.org/10.1112/plms/s3-73.1.1.
  7. Christoph Berkholz and Martin Grohe. Limitations of algebraic approaches to graph isomorphism testing. In 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. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_13.
  8. Samuel R. Buss. Lower bounds on Nullstellensatz proofs via designs. In Proof Complexity and Feasible Arithmetics, pages 59-71. American Mathematical Society, 1998. Google Scholar
  9. Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento. Thirty years of graph matching in pattern recognition. IJPRAI, 18(3):265-298, 2004. URL: http://dx.doi.org/10.1142/S0218001404003228.
  10. Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci., 329(1-3):315-323, 2004. URL: http://dx.doi.org/10.1016/j.tcs.2004.08.008.
  11. Martin Grohe, Kristian Kersting, Martin Mladenov, and Pascal Schweitzer. Color refinement and its applications. To appear. URL: https://lii.rwth-aachen.de/images/Mitarbeiter/pub/grohe/cr.pdf.
  12. Martin Grohe and Martin Otto. Pebble games and linear equations. Journal of Symbolic Logic, 80(3):797-844, 2015. URL: http://dx.doi.org/10.1017/jsl.2015.28.
  13. Martin Grohe and Wied Pakusa. The descriptive complexity of solving linear equation systems and its applications. In Proceedings of the 32nd ACM-IEEE Symposium on Logic in Computer Science, 2017. URL: http://dx.doi.org/10.1109/LICS.2017.8005081.
  14. Neil Immerman and Eric Lander. Describing graphs: A first-order approach to graph canonization. In Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988, pages 59-81. Springer New York, 1990. URL: http://dx.doi.org/10.1007/978-1-4612-4478-3_5.
  15. Andreas Krebs and Oleg 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. IEEE Computer Society, 2015. URL: http://dx.doi.org/10.1109/LICS.2015.69.
  16. László Lovász. Operations with structures. Acta Mathematica Hungarica, 18:321-328, 1967. Google Scholar
  17. László Lovász. Large Networks and Graph Limits. American Mathematical Society, 2012. Google Scholar
  18. Peter N. Malkin. Sherali-Adams relaxations of graph isomorphism polytopes. Discrete Optimization, 12:73-97, 2014. URL: http://dx.doi.org/10.1016/j.disopt.2014.01.004.
  19. Viswanath Nagarajan and Maxim Sviridenko. On the maximum quadratic assignment problem. Math. Oper. Res., 34(4):859-868, 2009. URL: http://dx.doi.org/10.1287/moor.1090.0418.
  20. Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12:2539-2561, 2011. URL: https://dl.acm.org/citation.cfm?id=2078187.
  21. Gottfried Tinhofer. Graph isomorphism and theorems of Birkhoff type. Computing, 36(4):285-300, 1986. URL: http://dx.doi.org/10.1007/BF02240204.
  22. Gottfried Tinhofer. A note on compact graphs. Discrete Applied Mathematics, 30(2-3):253-264, 1991. URL: http://dx.doi.org/10.1016/0166-218X(91)90049-3.
  23. Edwin R. Van Dam and Willem H. Haemers. Which graphs are determined by their spectrum? Linear Algebra and its applications, 373:241-272, 2003. URL: http://dx.doi.org/10.1016/S0024-3795(03)00483-X.
  24. S. V. N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, and Karsten M. Borgwardt. Graph kernels. Journal of Machine Learning Research, 11:1201-1242, 2010. URL: https://portal.acm.org/citation.cfm?id=1859891.
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