  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_{\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 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.
