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.
翻译:量化两个图形之间的相似性是许多基于图形的数据分析任务的核心一个根本的算法问题。 在本文中,我们研究了基于两个图形之间不匹配的相似度测量组的计算复杂性。 其中一个重要例子是基于图形编辑距离的相似性。 编辑距离计算“ 全球”不匹配, 即对称差异的边缘数, 我们的主要重点是“ 本地” 测量计算每个顶点的最大不匹配值。 从理论上讲, 我们的相似度测量最能用相匹配矩阵表示: 图表之间的“ 对称差异” 表示其相匹配性矩阵的差异( 在一个最佳对称情况下), 我们用一些矩阵规范来衡量。 粗略地说, 图表编辑距离等全球测量标准与诸如Frobenius 规范的入门性矩阵规范以及像光谱规范一样的本地措施符合操作者规范。 我们证明, 相近似度的测量尺度最好用相匹配的矩阵表表示: 相匹配性是其相近度矩阵的偏差性( ) 。