Document Open Access Logo

Spectrally Robust Graph Isomorphism

Authors Alexandra Kolla, Ioannis Koutis, Vivek Madan, Ali Kemal Sinop

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2018.84.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Network Alignment
  • Graph Isomorphism
  • Graph Similarity

Metrics

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

Abstract

We initiate the study of spectral generalizations of the graph isomorphism problem.
b) The Spectral Graph Dominance (SGD) problem: On input of two graphs G and H does there exist a permutation pi such that G preceq pi(H)?
c) The Spectrally Robust Graph Isomorphism (kappa-SRGI) problem: On input of two graphs G and H, find the smallest number kappa over all permutations pi such that pi(H) preceq G preceq kappa c pi(H) for some c. SRGI is a natural formulation of the network alignment problem that has various applications, most notably in computational biology.
 G preceq c H means that for all vectors x we have x^T L_G x <= c x^T L_H x, where L_G is the Laplacian G.
 We prove NP-hardness for SGD. We also present a kappa^3-approximation algorithm for SRGI for the case when both G and H are bounded-degree trees. The algorithm runs in polynomial time when kappa is a constant.

Cite As Get BibTex

Alexandra Kolla, Ioannis Koutis, Vivek Madan, and Ali Kemal Sinop. Spectrally Robust Graph Isomorphism. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 84:1-84:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.84

Author Details

Alexandra Kolla
  • Department of Computer Science, University of Colorado at Boulder
Ioannis Koutis
  • Department of Computer Science, New Jersey Institute of Technology
Vivek Madan
  • Department of Computer Science, University of Illinois, Urbana-Champaign
Ali Kemal Sinop
  • TOBB University of Economics and Technology, Ankara, Turkey

Funding

  • Kolla, Alexandra: Supported by NSF CAREER grant CCF-1452923.
  • Koutis, Ioannis: Supported by NSF CAREER grant CCF-1319376.

References

  1. László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 684-697, 2016. Google Scholar
  2. Joshua Batson, Daniel A. Spielman, Nikhil Srivastava, and Shang-Hua Teng. Spectral sparsification of graphs: Theory and algorithms. Commun. ACM, 56(8):87-94, 2013. URL: http://dx.doi.org/10.1145/2492007.2492029.
  3. Adolfo Piperno Brendan D. Mckay. Faster isomorphism testing of strongly regular graphs. Journal of Symbolic Computation archive, 60:94-112, 2014. Google Scholar
  4. P. G. Doyle and J. L. Snell. Random Walks and Electric Networks. ArXiv Mathematics e-prints, 2000. URL: http://arxiv.org/abs/math/0001057.
  5. Frank Emmert-Streib, Matthias Dehmer, and Yongtang Shi. Fifty years of graph matching, network alignment and network comparison. Inf. Sci., 346(C):180-197, 2016. URL: http://dx.doi.org/10.1016/j.ins.2016.01.074.
  6. Soheil Feizi, Gerald Quon, Mariana Recamonde Mendoza, Muriel Médard, Manolis Kellis, and Ali Jadbabaie. Spectral alignment of networks. CoRR, abs/1602.04181, 2016. URL: http://arxiv.org/abs/1602.04181.
  7. S. Fortin. The graph isomorphism problem. Technical Report 96-20, 1996. Google Scholar
  8. Stephen Guattery and Gary L. Miller. Graph embeddings and laplacian eigenvalues. SIAM J. Matrix Analysis Applications, 21(3):703-723, 2000. Google Scholar
  9. Israel Hanukoglu. Electron transfer proteins of cytochrome p450 systems. In E. Edward Bittar, editor, Physiological Functions of Cytochrome P450 in Relation to Structure and Regulation, volume 14 of Advances in Molecular and Cell Biology, pages 29-56. Elsevier, 1996. URL: http://dx.doi.org/10.1016/S1569-2558(08)60339-2.
  10. Claire Kenyon, Yuval Rabani, and Alistair Sinclair. Low distortion maps between point sets. In SIAM J. Comput, volume 39(4), page 1617–1636, 2004. Google Scholar
  11. J. Kobler, U. Schoning, and J. Toran. The graph isomorphism problem: Its structural complexity. Progress in Theoretical Computer Science, 1993. Google Scholar
  12. Alexandra Kolla, Ioannis Koutis, Vivek Madan, and Ali Kemal Sinop. Spectrally robust graph isomorphism. CoRR, abs/1805.00181, 2018. URL: https://arxiv.org/abs/1805.00181.
  13. Ioannis Koutis. Combinatorial and algebraic tools for optimal multilevel algorithms. PhD thesis, Carnegie Mellon University, Pittsburgh, May 2007. CMU CS Tech Report CMU-CS-07-131. Google Scholar
  14. Ioannis Koutis, Gary L. Miller, and Richard Peng. A fast solver for a class of linear systems. Commun. ACM, 55(10):99-107, 2012. URL: http://dx.doi.org/10.1145/2347736.2347759.
  15. Eugene M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci., 25(1):42-65, 1982. Google Scholar
  16. Ryan O'Donnell, John Wright, Chenggang Wu, and Yuan Zhou. Hardness of robust graph isomorphism, lasserre gaps, and asymmetry of random graphs. In Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '14, pages 1659-1677, 2014. Google Scholar
  17. Christos H Papadimitriou and Umesh V Vazirani. On two geometric problems related to the travelling salesman problem. Journal of Algorithms, 5(2):231-246, 1984. Google Scholar
  18. Robert Patro and Carl Kingsford. Global network alignment using multiscale spectral signatures. Bioinformatics, 28(23):3105-3114, 2012. URL: http://dx.doi.org/10.1093/bioinformatics/bts592.
  19. Daniel A. Spielman. Faster isomorphism testing of strongly regular graphs. Proc. 28th ACM STOC, 215:576–584, 1995. Google Scholar
  20. Charalampos E. Tsourakakis. Toward quantifying vertex similarity in networks. Internet Mathematics, 10(3-4):263-286, 2014. URL: http://dx.doi.org/10.1080/15427951.2013.836581.
  21. Regina I. Tyshkevich Viktor N. Zemlyachenko, Nikolai M. Korneenko. Graph isomorphism problem. Zapiski Nauchnykh Seminarov LOMI, 215:83-158, 1982. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact