A spectral assignment approach for the graph isomorphism problem

Stefan Klus*, Tuhin Sahai

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

In this paper, we propose algorithms for the graph isomorphism (GI) problem that are based on the eigendecompositions of the adjacency matrices. The eigenvalues of isomorphic graphs are identical. However, two graphs GA and GB can be isospectral but non-isomorphic. We first construct a GI testing algorithm for friendly graphs and then extend it to unambiguous graphs. We show that isomorphisms can be detected by solving a linear assignment problem (LAP). If the graphs possess repeated eigenvalues, which typically correspond to graph symmetries, finding isomorphisms is much harder. By repeatedly perturbing the adjacency matrices and by using properties of eigenpolytopes, it is possible to break symmetries of the graphs and iteratively assign vertices of GA to vertices of GB, provided that an admissible assignment exists. This heuristic approach can be used to construct a permutation which transforms GA into GB if the graphs are isomorphic. The methods will be illustrated with several guiding examples.

Original languageEnglish
Pages (from-to)689-706
Number of pages18
JournalInformation and Inference
Volume7
Issue number4
DOIs
Publication statusPublished - Dec 2018

Keywords

  • Friendly graphs
  • Graph isomorphism problem
  • Linear assignment problem

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Analysis
  • Applied Mathematics
  • Statistics and Probability
  • Numerical Analysis

Fingerprint

Dive into the research topics of 'A spectral assignment approach for the graph isomorphism problem'. Together they form a unique fingerprint.

Cite this