Document Open Access Logo

Homomorphism Tensors and Linear Equations

Authors Martin Grohe , Gaurav Rattan , Tim Seppelt

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.70.pdf
  • Filesize: 0.85 MB
  • 20 pages

Document Identifiers

Author Details

Martin Grohe
  • RWTH Aachen University, Germany
Gaurav Rattan
  • RWTH Aachen University, Germany
Tim Seppelt
  • RWTH Aachen University, Germany

Funding

  • Rattan, Gaurav: DFG Research Grants Program RA 3242/1-1 via project number 411032549.
  • Seppelt, Tim: German Research Council (DFG) within Research Training Group 2236 (UnRAVeL).

Acknowledgements

We thank Andrei Bulatov for many fruitful discussions on the foundations of theory developed here and its relation to the algebraic theory of valued constraint satisfaction problems. Moreover, we thank Jan Böker for discussions about linear systems of equations and basal graphs. Finally, we thank the anonymous reviewers for suggestions for improvement.

Cite As Get BibTex

Martin Grohe, Gaurav Rattan, and Tim Seppelt. Homomorphism Tensors and Linear Equations. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 70:1-70:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.70

Abstract

Lovász (1967) showed that two graphs G and H are isomorphic if and only if they are homomorphism indistinguishable over the class of all graphs, i.e. for every graph F, the number of homomorphisms from F to G equals the number of homomorphisms from F to H. Recently, homomorphism indistinguishability over restricted classes of graphs such as bounded treewidth, bounded treedepth and planar graphs, has emerged as a surprisingly powerful framework for capturing diverse equivalence relations on graphs arising from logical equivalence and algebraic equation systems. 
In this paper, we provide a unified algebraic framework for such results by examining the linear-algebraic and representation-theoretic structure of tensors counting homomorphisms from labelled graphs. The existence of certain linear transformations between such homomorphism tensor subspaces can be interpreted both as homomorphism indistinguishability over a graph class and as feasibility of an equational system. Following this framework, we obtain characterisations of homomorphism indistinguishability over several natural graph classes, namely trees of bounded degree, graphs of bounded pathwidth (answering a question of Dell et al. (2018)), and graphs of bounded treedepth.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Discrete mathematics
Keywords
  • homomorphisms
  • labelled graphs
  • treewidth
  • pathwidth
  • treedepth
  • linear equations
  • Sherali-Adams relaxation
  • Wiegmann-Specht Theorem
  • Weisfeiler-Leman

Metrics

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

Related Versions

References

  1. Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and Süleyman Cenk Sahinalp. Biomolecular network motif counting and discovery by color coding. In Proceedings 16th International Conference on Intelligent Systems for Molecular Biology (ISMB), Toronto, Canada, July 19-23, 2008, pages 241-249, 2008. URL: https://doi.org/10.1093/bioinformatics/btn163.
  2. Albert Atserias, Laura Mančinska, David E. Roberson, Robert Sámal, Simone Severini, and Antonios Varvitsiotis. Quantum and non-signalling graph isomorphisms. J. Comb. Theory, Ser. B, 136:289-328, 2019. URL: https://doi.org/10.1016/j.jctb.2018.11.002.
  3. 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.
  4. Paul Beaujean, Florian Sikora, and Florian Yger. Scaling up graph homomorphism for classification via sampling. ArXiv, 2104.04040, 2021. URL: https://doi.org/10.48550/arXiv.2104.04040.
  5. Jan Böker. Graph Similarity and Homomorphism Densities. 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 32:1-32:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.32.
  6. A. Bulatov, P. Jeavons, and A. Krokhin. Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34:720-742, 2005. URL: https://doi.org/10.1137/S0097539700376676.
  7. A.A. Bulatov. A Dichotomy Theorem for Nonuniform CSPs. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, pages 319-330, 2017. URL: https://doi.org/10.1109/FOCS.2017.37.
  8. Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. J. ACM, 60(5):34:1-34:41, 2013. URL: https://doi.org/10.1145/2528400.
  9. Andrei A. Bulatov and Stanislav Zivný. Approximate counting CSP seen from the other side. ACM Trans. Comput. Theory, 12(2):11:1-11:19, 2020. URL: https://doi.org/10.1145/3389390.
  10. Gang Chen and Ilia Ponomarenko. Lectures on Coherent Configurations. Central China Normal University Press, Wuhan, 2018. URL: https://www.pdmi.ras.ru/~inp/ccNOTES.pdf.
  11. Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 210-223. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055502.
  12. Anuj Dawar, Tomás Jakl, and Luca Reggio. Lovász-type theorems and game comonads. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1-13. IEEE, 2021. URL: https://doi.org/10.1109/LICS52264.2021.9470609.
  13. 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.
  14. Zdeněk Dvořák. On recognizing graphs by numbers of homomorphisms. Journal of Graph Theory, 64(4):330-342, August 2010. URL: https://doi.org/10.1002/jgt.20461.
  15. M. Freedman, L. Lovász, and A. Schrijver. Reflection positivity, rank connectivity, and homomorphism of graphs. Journal of the American Mathematical Society, 20:37-51, 2007. URL: https://doi.org/10.1090/S0894-0347-06-00529-7.
  16. G. Frobenius and I. Schur. Über die Äquivalenz der Gruppen linearer Substitutionen. Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften zu Berlin, 1:209-217, 1906. URL: https://www.biodiversitylibrary.org/item/93364.
  17. Martin Grohe. Counting Bounded Tree Depth Homomorphisms. In Holger Hermanns, Lijun Zhang, Naoki Kobayashi, and Dale Miller, editors, LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, July 8-11, 2020, pages 507-520. ACM, 2020. URL: https://doi.org/10.1145/3373718.3394739.
  18. 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-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, pages 1-16. ACM, 2020. URL: https://doi.org/10.1145/3375395.3387641.
  19. 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.
  20. Martin Grohe, Kristian Kersting, Martin Mladenov, and Pascal Schweitzer. Color Refinement and Its Applications. In An Introduction to Lifted Probabilistic Inference. The MIT Press, August 2021. URL: https://doi.org/10.7551/mitpress/10548.003.0023.
  21. 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.
  22. Martin Grohe, Gaurav Rattan, and Tim Seppelt. Homomorphism tensors and linear equations. ArXiv, 2111.11313, 2021. URL: https://doi.org/10.48550/ARXIV.2111.11313.
  23. Donald G. Higman. Coherent algebras. Linear Algebra and its Applications, 93:209-239, August 1987. URL: https://doi.org/10.1016/S0024-3795(87)90326-0.
  24. Nils M. Kriege, Fredrik D. Johansson, and Christopher Morris. A survey on graph kernels. Appl. Netw. Sci., 5(1):6, 2020. URL: https://doi.org/10.1007/s41109-019-0195-3.
  25. Pascal Kühner. Graph embeddings based on homomorphism counts. Master’s thesis, Department of Computer Science, RWTH Aachen University, 2021. Google Scholar
  26. Tsit-Yuen Lam. A First Course in Noncommutative Rings. Number 131 in Graduate texts in mathematics. Springer, New York, NY, 2. ed edition, 2001. URL: https://doi.org/10.1007/978-1-4419-8616-0.
  27. László Lovász. Operations with structures. Acta Mathematica Academiae Scientiarum Hungarica, 18(3):321-328, September 1967. URL: https://doi.org/10.1007/BF02280291.
  28. László Lovász. Large Networks and Graph Limits. American Mathematical Society, 2012. URL: https://doi.org/10.1090/coll/060.
  29. László Lovász and Alexander Schrijver. Graph parameters and semigroup functions. Eur. J. Comb., 29(4):987-1002, 2008. URL: https://doi.org/10.1016/j.ejc.2007.11.008.
  30. László Lovász and Balázs Szegedy. Contractors and connectors of graph algebras. Journal of Graph Theory, 60(1):11-30, 2009. URL: https://doi.org/10.1002/jgt.20343.
  31. Peter N. Malkin. Sherali-Adams Relaxations of Graph Isomorphism Polytopes. Discrete Optimization, 12:73-97, 2014. URL: https://doi.org/10.1016/j.disopt.2014.01.004.
  32. Laura Mančinska and David E. Roberson. Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 661-672. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00067.
  33. Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: simple building blocks of complex networks. Science, 298(5594):824-827, 2002. URL: https://doi.org/10.1126/science.298.5594.824.
  34. Yoàv Montacute and Nihil Shah. The pebble-relation comonad in finite model theory. ArXiv, 2110.08196, 2021. URL: https://doi.org/10.48550/arXiv.2110.08196.
  35. 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, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, pages 4602-4609. AAAI Press, 2019. URL: https://doi.org/10.1609/aaai.v33i01.33014602.
  36. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity: graphs, structures, and algorithms. Number 28 in Algorithms and combinatorics. Springer, Heidelberg ; New York, 2012. OCLC: ocn773019512. URL: https://doi.org/10.1007/978-3-642-27875-4.
  37. Hoang Nguyen and Takanori Maehara. Graph homomorphism convolution. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 7306-7316. PMLR, 2020. URL: http://proceedings.mlr.press/v119/nguyen20c.html.
  38. Christopher J Pappacena. An Upper Bound for the Length of a Finite-Dimensional Algebra. Journal of Algebra, 197(2):535-545, 1997. URL: https://doi.org/10.1006/jabr.1997.7140.
  39. Marc Roth and Philip Wellnitz. Counting and finding homomorphisms is universal for parameterized complexity theory. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2161-2180. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.133.
  40. Alexander Schrijver. Graph invariants in the spin model. Journal of Combinatorial Theory, Series B, 99:502-511, 2009. URL: https://doi.org/10.1016/j.jctb.2008.10.003.
  41. Wilhelm Specht. Zur Theorie der Matrizen. II. Jahresbericht der Deutschen Mathematiker-Vereinigung, 50:19-23, 1940. URL: http://gdz.sub.uni-goettingen.de/dms/load/toc/?PPN=PPN37721857X_0050&DMDID=dmdlog6.
  42. J. Thapper and S. Živný. The complexity of finite-valued csps. Journal of the ACM, 63(4), 2016. URL: https://doi.org/10.1145/2974019.
  43. Gottfried Tinhofer. Graph isomorphism and theorems of Birkhoff type. Computing, 36(4):285-300, December 1986. URL: https://doi.org/10.1007/BF02240204.
  44. Gottfried Tinhofer. A note on compact graphs. Discret. Appl. Math., 30(2-3):253-264, 1991. URL: https://doi.org/10.1016/0166-218X(91)90049-3.
  45. N. A. Wiegmann. Necessary and sufficient conditions for unitary similarity. Journal of the Australian Mathematical Society, 2(1):122-126, 1961. Edition: 2009/04/09 Publisher: Cambridge University Press. URL: https://doi.org/10.1017/S1446788700026422.
  46. 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.
  47. Dmitriy Zhuk. A proof of CSP dichotomy conjecture. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, pages 331-342, 2017. URL: https://doi.org/10.1109/FOCS.2017.38.
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