  Quantifying the similarity between two graphs is a fundamental algorithmic
problem at the heart of many data analysis tasks for graph-based data. In this
paper, we study the computational complexity of a family of similarity measures
based on quantifying the mismatch between the two graphs, that is, the
"symmetric difference" of the graphs under an optimal alignment of the
vertices. An important example is similarity based on graph edit distance.
While edit distance calculates the "global" mismatch, that is, the number of
edges in the symmetric difference, our main focus is on "local" measures
calculating the maximum mismatch per vertex. Mathematically, our similarity
measures are best expressed in terms of the adjacency matrices: the mismatch
between graphs is expressed as the difference of their adjacency matrices
(under an optimal alignment), and we measure it by applying some matrix norm.
Roughly speaking, global measures like graph edit distance correspond to
entrywise matrix norms like the Frobenius norm and local measures correspond to
operator norms like the spectral norm. We prove a number of strong NP-hardness
and inapproximability results even for very restricted graph classes such as
bounded-degree trees.
