Grohe, Martin ;
Rattan, Gaurav ;
Woeginger, Gerhard J.
Graph Similarity and Approximate Isomorphism
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 wellstudied 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 NPhard even for severely restricted cases.
It is known that GSim (WSim) is NPhard; we strengthen this hardness result by showing that the problem remains NPhard 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 NPhard as long as one of the matrices has unbounded rank or negative eigenvalues: hence, the realm of tractability is restricted to positive semidefinite 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.
BibTeX  Entry
@InProceedings{grohe_et_al:LIPIcs:2018:9602,
author = {Martin Grohe and Gaurav Rattan and Gerhard J. Woeginger},
title = {{Graph Similarity and Approximate Isomorphism}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {20:120:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9602},
URN = {urn:nbn:de:0030drops96021},
doi = {10.4230/LIPIcs.MFCS.2018.20},
annote = {Keywords: Graph Similarity, Quadratic Assignment Problem, Approximate Graph Isomorphism}
}
27.08.2018
Keywords: 

Graph Similarity, Quadratic Assignment Problem, Approximate Graph Isomorphism 
Seminar: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Issue date: 

2018 
Date of publication: 

27.08.2018 