Spectrally Robust Graph Isomorphism

2018/05/01 by Kolla, Alexandra, Koutis, Ioannis, Madan, Vivek +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1805.00181

Abstract

We initiate the study of spectral generalizations of the graph isomorphism problem. (a)The Spectral Graph Dominance (SGD) problem: On input of two graphs G and H does there exist a permutation π such that G\preceq π(H)? (b) The Spectrally Robust Graph Isomorphism (SRGI) problem: On input of two graphs G and H, find the smallest number κ over all permutations π such that π(H) \preceq G\preceq κc π(H) for some c. SRGI is a natural formulation of the network alignment problem that has various applications, most notably in computational biology. Here 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 κ-approximation algorithm for SRGI for the case when both G and H are bounded-degree trees. The algorithm runs in polynomial time when κ is a constant.

Related

• On spectral properties for graph matching and graph isomorphism problems
• Continuous optimization methods for the graph isomorphism problem
• Graph Similarity and Approximate Isomorphism
• A Simple Algorithm for a Computationally Hard Problem
• A graph isomorphism invariant based on neighborhood aggregation