  Notions of graph similarity provide alternative perspective on the graph
isomorphism problem and vice-versa. In this paper, we consider measures of
similarity arising from mismatch norms as studied in Gervens and Grohe: the
edit distance $\delta_{\mathcal{E}}$, and the metrics arising from
$\ell_p$-operator norms, which we denote by $\delta_p$ and $\delta_{|p|}$. We
address the following question: can these measures of similarity be used to
design polynomial-time approximation algorithms for graph isomorphism? We show
that computing an optimal value of $\delta_{\mathcal{E}}$ is \NP-hard on pairs
of graphs with the same number of edges. In addition, we show that computing
optimal values of $\delta_p$ and $\delta_{|p|}$ is \NP-hard even on pairs of
$1$-planar graphs with the same degree sequence and bounded degree. These two
results improve on previous known ones, which did not examine the restricted
case where the pairs of graphs are required to have the same number of edges.
  Finally, we study similarity problems on strongly regular graphs and prove
some near optimal inequalities with interesting consequences on the
computational complexity of graph and group isomorphism.
