Abstract
Quantifying the similarity between two graphs is a fundamental algorithmic problem at the heart of many data analysis tasks for graphbased 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 NPhardness and inapproximability results even for very restricted graph classes such as boundeddegree trees.
BibTeX  Entry
@InProceedings{gervens_et_al:LIPIcs.MFCS.2022.52,
author = {Gervens, Timo and Grohe, Martin},
title = {{Graph Similarity Based on Matrix Norms}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {52:152:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772563},
ISSN = {18688969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16850},
URN = {urn:nbn:de:0030drops168509},
doi = {10.4230/LIPIcs.MFCS.2022.52},
annote = {Keywords: graph similarity, approximate graph isomorphism, graph matching}
}
Keywords: 

graph similarity, approximate graph isomorphism, graph matching 
Collection: 

47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) 
Issue Date: 

2022 
Date of publication: 

22.08.2022 