Document Open Access Logo

Graph Similarity and Homomorphism Densities

Author Jan Böker

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.32.pdf
  • Filesize: 0.76 MB
  • 17 pages

Document Identifiers

Author Details

Jan Böker
  • RWTH Aachen University, Germany

Acknowledgements

The author would like to thank Yufei Zhao for pointing out how a non-quantitative inverse counting lemma for the cut distance follows from the compactness of the graphon space and the anonymous reviewers for their helpful comments.

Cite AsGet BibTex

Jan Böker. Graph Similarity and Homomorphism Densities. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.32

Abstract

We introduce the tree distance, a new distance measure on graphs. The tree distance can be computed in polynomial time with standard methods from convex optimization. It is based on the notion of fractional isomorphism, a characterization based on a natural system of linear equations whose integer solutions correspond to graph isomorphism. By results of Tinhofer (1986, 1991) and Dvořák (2010), two graphs G and H are fractionally isomorphic if and only if, for every tree T, the number of homomorphisms from T to G equals the corresponding number from T to H, which means that the tree distance of G and H is zero. Our main result is that this correspondence between the equivalence relations "fractional isomorphism" and "equal tree homomorphism densities" can be extended to a correspondence between the associated distance measures. Our result is inspired by a similar result due to Lovász and Szegedy (2006) and Borgs, Chayes, Lovász, Sós, and Vesztergombi (2008) that connects the cut distance of graphs to their homomorphism densities (over all graphs), which is a fundamental theorem in the theory of graph limits. We also introduce the path distance of graphs and take the corresponding result of Dell, Grohe, and Rattan (2018) for exact path homomorphism counts to an approximate level. Our results answer an open question of Grohe (2020) and help to build a theoretical understanding of vector embeddings of graphs. The distance measures we define turn out be closely related to the cut distance. We establish our main results by generalizing our definitions to graphons, which are limit objects of sequences of graphs, as this allows us to apply techniques from functional analysis. We prove the fairly general statement that, for every "reasonably" defined graphon pseudometric, an exact correspondence to homomorphism densities can be turned into an approximate one. We also provide an example of a distance measure that violates this reasonableness condition. This incidentally answers an open question of Grebík and Rocha (2021).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
Keywords
  • graph similarity
  • homomorphism densities
  • cut distance

Metrics

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

Related Versions

References

  1. Jöran Bergh and Jörgen Löfström. Interpolation Spaces: An Introduction. Die Grundlehren Der Mathematischen Wissenschaften in Einzeldarstellungen. Springer-Verlag, 1976. URL: https://doi.org/10.1007/978-3-642-66451-9.
  2. Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós, Balázs Szegedy, and Katalin Vesztergombi. Graph limits and parameter testing. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC '06, page 261–270, New York, NY, USA, 2006. Association for Computing Machinery. URL: https://doi.org/10.1145/1132516.1132556.
  3. Christian Borgs, Jennifer T. Chayes, László Lovász, Vera T. Sós, and Katalin Vesztergombi. Convergent sequences of dense graphs i: Subgraph frequencies, metric properties and testing. Advances in Mathematics, 219(6):1801-1851, 2008. URL: https://doi.org/10.1016/j.aim.2008.07.008.
  4. Jan Böker. Graph similarity and homomorphism densities, 2021. URL: http://arxiv.org/abs/2104.14213.
  5. Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, page 210–223, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3055399.3055502.
  6. Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. Theoretical Computer Science, 329(1):315-323, 2004. URL: https://doi.org/10.1016/j.tcs.2004.08.008.
  7. 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), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1-40:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.40.
  8. Richard M. Dudley. Real Analysis and Probability. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2 edition, 2002. URL: https://doi.org/10.1017/CBO9780511755347.
  9. Nelson Dunford and Jacob T. Schwartz. Linear Operators, Part 2: Spectral Theory, Self Adjoint Operators in Hilbert Space. Linear Operators. Interscience Publishers, 1963. Google Scholar
  10. Zdeněk Dvořá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. Tanja Eisner, Bálint Farkas, Markus Haase, and Rainer Nagel. Operator Theoretic Aspects of Ergodic Theory. Graduate Texts in Mathematics. Springer International Publishing, 2015. URL: https://doi.org/10.1007/978-3-319-16898-2.
  12. Alan Frieze and Ravindran Kannan. Quick approximation to matrices and applications. Combinatorica, 19:175-220, February 1999. URL: https://doi.org/10.1007/s004930050052.
  13. Jan Grebík and Israel Rocha. Fractional isomorphism of graphons, 2021. Accepted to Combinatorica. URL: http://arxiv.org/abs/1909.04122.
  14. Martin Grohe. Counting bounded tree depth homomorphisms. In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '20, page 507–520, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3373718.3394739.
  15. Martin Grohe. Word2vec, node2vec, graph2vec, x2vec: Towards a theory of vector embeddings of structured data. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS'20, page 1–16, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3375395.3387641.
  16. Svante Janson. Graphons, cut norm and distance, couplings and rearrangements. New York Journal of Mathematics, 4, 2013. Google Scholar
  17. Sandra Kiefer, Pascal Schweitzer, and Erkal Selman. Graphs identified by logics with counting. In Giuseppe F Italiano, Giovanni Pighizzini, and Donald T. Sannella, editors, Mathematical Foundations of Computer Science 2015, pages 319-330, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-662-48057-1_25.
  18. László Lovász. Operations with structures. Acta Mathematica Hungarica, 18(3-4):321-328, 1967. URL: https://doi.org/10.1007/BF02280291.
  19. László Lovász and Balázs Szegedy. Szemerédi’s lemma for the analyst. GAFA Geometric And Functional Analysis, 17:252-270, 2007. URL: https://doi.org/10.1007/s00039-007-0599-6.
  20. László Lovász. Large Networks and Graph Limits, volume 60 of Colloquium Publications. American Mathematical Society, 2012. URL: https://doi.org/10.1090/coll/060.
  21. László Lovász and Balázs Szegedy. Limits of dense graph sequences. Journal of Combinatorial Theory, Series B, 96(6):933-957, 2006. URL: https://doi.org/10.1016/j.jctb.2006.05.002.
  22. Laura Mančinska and David E. Roberson. Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 661-672, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00067.
  23. Viswanath Nagarajan and Maxim Sviridenko. On the maximum quadratic assignment problem. Mathematics of Operations Research, 34(4):859-868, 2009. URL: https://doi.org/10.1287/moor.1090.0418.
  24. Yurii Nesterov and Arkadii Nemirovskii. Interior-point Polynomial Algorithms in Convex Programming. Studies in Applied Mathematics. Society for Industrial and Applied Mathematics, 1994. URL: https://doi.org/10.1137/1.9781611970791.
  25. Martin Otto. Canonization for two variables and puzzles on the square. Annals of Pure and Applied Logic, 85(3):243-282, 1997. URL: https://doi.org/10.1016/S0168-0072(96)00047-4.
  26. Gottfried Tinhofer. Graph isomorphism and theorems of birkhoff-type. Computing, 36(4):285–300, 1986. URL: https://doi.org/10.1007/BF02240204.
  27. Gottfried Tinhofer. A note on compact graphs. Discrete Applied Mathematics, 30(2):253-264, 1991. URL: https://doi.org/10.1016/0166-218X(91)90049-3.
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 Imprint Privacy Contact