Document Open Access Logo

Graph Similarity Based on Matrix Norms

Authors Timo Gervens , Martin Grohe

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.52.pdf
  • Filesize: 0.76 MB
  • 15 pages

Document Identifiers

Author Details

Timo Gervens
  • RWTH Aachen University, Germany
Martin Grohe
  • RWTH Aachen University, Germany

Funding

  • Gervens, Timo: This work was supported by the DFG grant GR 1492/20-1.

Cite As Get BibTex

Timo Gervens and Martin Grohe. Graph Similarity Based on Matrix Norms. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.52

Abstract

Quantifying the similarity between two graphs is a fundamental algorithmic problem at the heart of many data analysis tasks for graph-based data. In this paper, we study the computational complexity of a family of similarity measures based on quantifying the mismatch between the two graphs, that is, the "symmetric difference" of the graphs under an optimal alignment of the vertices. An important example is similarity based on graph edit distance. While edit distance calculates the "global" mismatch, that is, the number of edges in the symmetric difference, our main focus is on "local" measures calculating the maximum mismatch per vertex.
Mathematically, our similarity measures are best expressed in terms of the adjacency matrices: the mismatch between graphs is expressed as the difference of their adjacency matrices (under an optimal alignment), and we measure it by applying some matrix norm. Roughly speaking, global measures like graph edit distance correspond to entrywise matrix norms like the Frobenius norm and local measures correspond to operator norms like the spectral norm.
We prove a number of strong NP-hardness and inapproximability results even for very restricted graph classes such as bounded-degree trees.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
  • Theory of computation → Complexity theory and logic
Keywords
  • graph similarity
  • approximate graph isomorphism
  • graph matching

Metrics

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

Related Versions

References

  1. Noga Alon and Assaf Naor. Approximating the cut-norm via grothendieck’s inequality. SIAM J. Comput., 35(4):787-803, April 2006. URL: https://doi.org/10.1137/S0097539704441629.
  2. S. Arora, A. Frieze, and H. Kaplan. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. Mathematical Programming, 92(1):1-36, 2002. Google Scholar
  3. V. Arvind, J. Köbler, S. Kuhnert, and Y. Vasudev. Approximate graph isomorphism. In Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS 2012), volume 7464, pages 100-111, 2012. Google Scholar
  4. László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 684-697. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897542.
  5. Amélie Barbe, Marc Sebban, Paulo Gonçalves, Pierre Borgnat, and Rémi Gribonval. Graph diffusion wasserstein distances. In Frank Hutter, Kristian Kersting, Jefrey Lijffijt, and Isabel Valera, editors, Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2020, Ghent, Belgium, September 14-18, 2020, Proceedings, Part II, volume 12458 of Lecture Notes in Computer Science, pages 577-592. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-67661-2_34.
  6. H. Bunke. On a relation between graph edit distance and maximum common subgraph. Pattern Recognition Letters, 18:689-694, 1997. Google Scholar
  7. D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty years of graph matching in pattern recognition. International journal of pattern recognition and artificial intelligence, 18(03):265-298, May 2004. Google Scholar
  8. F. Emmert-Streib, M. Dehmer, and Y. Shi. Fifty years of graph matching, network alignment and network comparison. Information Sciences, 346:180-197, 2016. Google Scholar
  9. P. Foggia, G. Percannella, and M. Vento. Graph matching and learning in pattern recognition in the last 10 years. International Journal of Pattern Recognition and Artificial Intelligence, 28(1), 2014. Google Scholar
  10. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979. Google Scholar
  11. Timo Gervens and Martin Grohe. Graph similarity based on matrix norms, 2022. URL: https://doi.org/10.48550/ARXIV.2207.00090.
  12. M. Grohe. word2vec, node2vec, graph2vec, x2vec: Towards a theory of vector embeddings of structured data. In D. Suciu, Y. Tao, and Z. 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.
  13. M. Grohe, G. Rattan, and G. J. Woeginger. Graph similarity and approximate isomorphism. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117, pages 20:1-20:16, 2018. Google Scholar
  14. Martin Grohe and Pascal Schweitzer. The graph isomorphism problem. Communications of the ACM, 63(11):128-134, 2020. URL: https://doi.org/10.1145/3372123.
  15. P. Keldenich. Random robust graph isomorphism. Master’s thesis, Department of Computer Science, RWTH Aachen University, 2015. Google Scholar
  16. A. Kolla, I. Koutis, V. Madan, and A. K. Sinop. Spectrally Robust Graph Isomorphism. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107, pages 84:1-84:13, 2018. Google Scholar
  17. N.M. Kriege, F.D Johansson, and C. Morris. A survey on graph kernels. ArXiv, arXiv:1903.11835 [cs.LG], 2019. Google Scholar
  18. C.-L. Lin. Hardness of approximating graph transformation problem. In D.-T. Du and X.-S. Zhang, editors, Proceedings of the 5th International Symposium on Algorithms and Computation, volume 834 of Lecture Notes in Computer Science, pages 74-82. Springer, 1994. Google Scholar
  19. L. Lovász. Large Networks and Graph Limits. American Mathematical Society, 2012. Google Scholar
  20. László Lovász. Large Networks and Graph Limits, volume 60 of Colloquium Publications. American Mathematical Society, 2012. URL: http://www.ams.org/bookstore-getitem/item=COLL-60.
  21. E. M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences, 25(1):42-65, 1982. Google Scholar
  22. K. Makarychev, R. Manokaran, and M. Sviridenko. Maximum quadratic assignment problem: Reduction from maximum label cover and lp-based approximation algorithm. ACM Transactions on Algorithms, 10(4):18, 2014. Google Scholar
  23. Hermina Petric Maretic, Mireille El Gheche, Giovanni Chierchia, and Pascal Frossard. GOT: an optimal transport framework for graph comparison. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 13876-13887, 2019. URL: https://proceedings.neurips.cc/paper/2019/hash/fdd5b16fc8134339089ef25b3cf0e588-Abstract.html.
  24. D. W. Matula. Subtree isomorphism in o(n^5/2). In B. Alspach, P. Hell, and D.J. Miller, editors, Algorithmic Aspects of Combinatorics, volume 2, pages 91-106. Elsevier, 1978. Google Scholar
  25. Facundo Mémoli. Gromov-wasserstein distances and the metric approach to object matching. Found. Comput. Math., 11(4):417-487, 2011. URL: https://doi.org/10.1007/s10208-011-9093-5.
  26. V. Nagarajan and M. Sviridenko. On the maximum quadratic assignment problem. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 516-524, 2009. Google Scholar
  27. 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
  28. D. Sangiorgi. Introduction to Bisimulation and Coinduction. Cambridge University Press, 2012. Google Scholar
  29. A. Tsitsulin, D. Mottin, P. Karras, A. Bronstein, and E. Müller. Netlsd: Hearing the shape of a graph. In Y. Guo and F. Farooq, editors, Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 2347-2356, 2018. Google Scholar
  30. S. Umeyama. An eigendecomposition approach to weighted graph matching problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 10(5):695-703, 1988. Google Scholar
  31. R.J. van Glabbeek. The linear time - branching time spectrum I. The semantics of concrete, sequential processes. In J.A. Bergstra, A. Ponse, and S.A. Smolka, editors, Handbook of Process Algebra, chapter 1, pages 3-99. Elsevier, 2001. Google Scholar
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