Graph Similarity and Approximate Isomorphism

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 \[ \mathrm{dist}(G,H):=\min_π\|A_G^π-A_H\|_F, \] where $π$ ranges over all permutations of the vertex set of $G$, where $A_G^π$ denotes the matrix obtained from $A_G$ by permuting rows and columns according to $π$, and where $\|M\|_F$ is the Frobenius norm of a matrix $M$. The (weighted) graph similarity problem, denoted by SIM (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 SIM (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 one of the matrices has a bounded clustering number, a parameter arising from spectral graph drawing techniques.