Document Open Access Logo

Graph Similarity and Approximate Isomorphism

Authors Martin Grohe , Gaurav Rattan , Gerhard J. Woeginger

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.20.pdf
  • Filesize: 478 kB
  • 16 pages

Document Identifiers

Author Details

Martin Grohe
  • RWTH Aachen University, Aachen, Germany
Gaurav Rattan
  • RWTH Aachen University, Aachen, Germany
Gerhard J. Woeginger
  • RWTH Aachen University, Aachen, Germany

Cite As Get BibTex

Martin Grohe, Gaurav Rattan, and Gerhard J. Woeginger. Graph Similarity and Approximate Isomorphism. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.20

Abstract

The graph similarity problem, also known as approximate graph isomorphism or graph matching problem, has been extensively studied in the machine learning community, but has not received much attention in the algorithms community: Given two graphs G,H of the same order n with adjacency matrices A_G,A_H, a well-studied measure of similarity is the Frobenius distance dist(G,H):=min_{pi}|A_G^{pi}-A_H|_F, where pi ranges over all permutations of the vertex set of G, where A_G^pi denotes the matrix obtained from A_G by permuting rows and columns according to pi, and where |M |_F is the Frobenius norm of a matrix M. The (weighted) graph similarity problem, denoted by GSim (WSim), is the problem of computing this distance for two graphs of same order. This problem is closely related to the notoriously hard quadratic assignment problem (QAP), which is known to be NP-hard even for severely restricted cases.
It is known that GSim (WSim) is NP-hard; we strengthen this hardness result by showing that the problem remains NP-hard even for the class of trees. Identifying the boundary of tractability for WSim is best done in the framework of linear algebra. We show that WSim is NP-hard as long as one of the matrices has unbounded rank or negative eigenvalues: hence, the realm of tractability is restricted to positive semi-definite matrices of bounded rank. Our main result is a polynomial time algorithm for the special case where the associated (weighted) adjacency graph for one of the matrices has a bounded number of twin equivalence classes. The key parameter underlying our algorithm is the clustering number of a graph; this parameter arises in context of the spectral graph drawing machinery.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Graph Similarity
  • Quadratic Assignment Problem
  • Approximate Graph Isomorphism

Metrics

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

Related Versions

References

  1. H.A. Almohamad and S.O. Duffuaa. A linear programming approach for the weighted graph matching problem. IEEE Transactions on pattern analysis and machine intelligence, 15(5):522-525, 1993. Google Scholar
  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 B. Rovan, V. Sassone, and P. Widmayer, editors, Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science, volume 7464 of Lecture Notes in Computer Science, pages 100-111. Springer Verlag, 2012. Google Scholar
  4. L. Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC '16), pages 684-697, 2016. Google Scholar
  5. R.E. Burkard, E. Cela, G. Rote, and G.J. Woeginger. The quadratic assignment problem with a monotone anti-monge and a symmetric toeplitz matrix: easy and hard cases. Mathematical Programming, 82:125-158, 1998. Google Scholar
  6. E. Cela. The Quadratic Assignment Problem: Theory and Algorithms. Kluwer Academic Publishers, Dordrecht, The Netherlands, 1998. Google Scholar
  7. E. Cela, V.G. Deineko, and G.J. Woeginger. Well-solvable cases of the qap with block-structured matrices. Discrete Applied Mathematics, 186:56-65, 2015. Google Scholar
  8. E. Cela, N. Schmuck, S. Wimer, and G.J. Woeginger. The wiener maximum quadratic assignment problem. Discrete Optimization, 8:411-416, 2011. Google Scholar
  9. P. Codenotti, H. Katebi, K. A. Sakallah, and I. L. Markov. Conflict analysis and branching heuristics in the search for graph automorphisms. In 2013 IEEE 25th International Conference on Tools with Artificial Intelligence, Herndon, VA, USA, November 4-6, 2013, pages 907-914, 2013. Google Scholar
  10. 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(3):265-298, 2004. Google Scholar
  11. A.N. Elshafei. Hospital layout as a quadratic assignment problem. Operational Research Quarterly, 28:167-179, 1977. Google Scholar
  12. M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979. Google Scholar
  13. A.M. Geoffrion and G.W. Graves. Scheduling parallel production lines with changeover costs: Practical application of a quadratic assignment/lp approach. Operational Research, 24:595-610, 1976. Google Scholar
  14. S. Gold and A. Rangarajan. A graduated assignment algorithm for graph matching. IEEE Transactions on pattern analysis and machine intelligence, 18(4):377-388, 1996. Google Scholar
  15. T. Junttila and P. Kaski. Engineering an efficient canonical labeling tool for large and sparse graphs. In Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics, pages 135-149. SIAM, 2007. Google Scholar
  16. P. Keldenich. Random robust graph isomorphism. Master’s thesis, Department of Compter Science, RWTH Aachen University, 2015. Google Scholar
  17. Y. Koren. Drawing graphs by eigenvectors: theory and practice. Computers and Mathematics with Applications, 49(11):1867-1888, 2005. Google Scholar
  18. J. Krarup and Pruzan P.M. Computer-aided layout design. Mathematical Programming Study, 9:75-94, 1978. Google Scholar
  19. 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
  20. D.W. Matula. Subtree isomorphism in o(n^5/2). In P. H. B. Alspach and D. Miller, editors, Algorithmic Aspects of Combinatorics, volume 2 of Annals of Discrete Mathematics, pages 91-106. Elsevier, 1978. Google Scholar
  21. B. McKay. Practical graph isomorphism. Congressus Numerantium, 30:45-87, 1981. Google Scholar
  22. B. D. McKay and A. Piperno. Practical graph isomorphism, II. J. Symb. Comput., 60:94-112, 2014. Google Scholar
  23. S. Melnik, H. Garcia-Molina, and E. Rahm. Similarity flooding: A versatile graph matching algorithm and its application to schema matching. In Proceedings. 18th International Conference on Data Engineering, pages 117-128, 2002. Google Scholar
  24. 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
  25. D. Neuen and P. Schweitzer. Benchmark graphs for practical graph isomorphism. ArXiv (CoRR), arXiv:1705.03686 [cs.DS], 2017. Google Scholar
  26. 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
  27. M.A. Pollatschek, N. Gershoni, and Y.T. Radday. Optimization of the typewriter keyboard by simulation. Angewandte Informatik, 17:438-439, 1976. Google Scholar
  28. F. Rendl and H. Wolkowicz. Applications of parametric programming and Eigenvalue maximization to the quadratic assignment problem. Mathematical Programming, 53:63-78, 1992. Google Scholar
  29. 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
  30. M. Zaslavskiy, F. Bach, and J.-P. Vert. A path following algorithm for the graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(12):2227-2242, 2009. 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