图具有强大的表达能力，经常被用来构建实体以及实体之间的关系。当物体结构用图来表示时，衡量两个物体的相似性就被转化为计算两个图的相似性。今天我们来聊聊怎么计算图的相似性。

怎样衡量图的相似性

两个图怎么算相似？我们需要首先知道两个图怎么算同构（相同）。假设有两个属性图G和H,如果存在一个从G中节点到H中节点的一一对应θ，使得(x,y)是G中一条边当且仅当(θ(x),θ(y))是H中一条边，且相对应的点、边的标签、属性完全相同，则这两个图称为是同构的，可以把它们看成一个图来处理。

图同构可以用来判断两个图是否相同。要是两个图不是同构的，那么怎样衡量它们的相似性呢？

最大公共子图可以用来衡量两个图的相似程度。将一个图的一部分点或者边删除，得到的图就是原来图的一个子图。如果一个图同时是另外两个图的子图，且它是满足条件的子图中节点数最多的，则称之为后两个图的最大公共子图。

两个图通常情况下并不存在同构关系，但是肯定存在最大公共子图，而且显然两个图之间的最大公共子图越大，两个图之间的相似程度越高。

当然根据实际场景的需要，可以再加一些限定条件，比如最大公共边子图、最大公共连通子图、最大公共连通诱导子图等。

由于使用图来表示事物时可能受到噪声的影响，而且最大公共子图的条件相对来说比较苛刻（当然也可以弱化条件来计算最大公共子图，比如在匹配节点的时候只要求匹配部分属性），在图相似性计算中一种比较好的替代方法是使用图编辑距离来进行对噪声容忍的图匹配。

一般情况下,图的编辑操作包括删除、插入和替换，编辑操作不仅可以用于节点,还可以用于边。图G 与图H之间的编辑距离是指将图G 转变成图H需要的最少的编辑操作数目。显然，两个图之间的编辑距离越短，两个图的相似程度就越高。

另外一种求两个图的相似性的方法是将求它们的最大公共子图问题转化为求最大团问题。其思路是先构造两个图的关联图。关联图的构造步骤如下：

给定两个图G和H及其节点集V(G)和V(H),

Step1. 对图G中的任意一个节点v，遍历图H中的每一个节点u，若v与u具有相同的属性值，则将节点对(v,u)作为关联图的一个节点；

Step2. 任取关联图中的两个节点(𝑢1,𝑢2)和(𝑣1,𝑣2)，若𝑢1≠𝑣1，𝑢2≠𝑣2，且图G中的边 (𝑢1,𝑣1)与图H中的边 (𝑢2,𝑣2)具有相同的属性值，或图G中的节点𝑢1和𝑣1、图H中的节点𝑢2和𝑣2都不相邻，则在关联图的这两个节点之间添加一条边。

按上述步骤构造完关联图之后，关联图中的最大团就对应于图G和H的最大公共子图，因此求最大公共子图问题就转换为求关联图的最大团问题。

图的相似性算法研究

目前对图相似性的研究分为两个分支：一种是精确算法的研究，另一种是近似最优解算法的研究，由于图相似性有很多的度量方法、计算图的相似性与图的规模和密度密切相关等原因，只有少量文献对部分算法的性能进行过比较，我们需要根据自己的业务和需求选择合适的度量方法和相应的算法。

GES提供的相关算法

GES是华为自研的图数据库产品，集成了非常丰富的图算法，提供的与图的相似性有关的算法是最大团算法和最大公共连通诱导子图算法（MCCIS），已经在解决方案和CAD模型检索场景有成功的落地应用。

例如，对上述两个图G1和G2，如果只考虑结构的相似性，应用GES的MCCIS算法，计算得到他们的最大公共连通诱导子图如下所示：

G1和G2的节点个数都是9，它们的最大公共连通诱导子图的节点个数是7，可以按公式

Similarity = 2*|V(MCCIS)| / (|V(G1)| + |V(G2)|) = 7/9计算得到两个图的相似度。

应用场景

图相似性计算应用的领域非常广泛，包括化学结构分析、基于事例的推理、机器学习、规划、语义网络、概念图、计算机网络监控、计算机视觉、模式识别、解决方案、CAD检索等等。

参考文献：

1. 图匹配技术研究（2018）

2. Maximum Common Subgraph Isomorphism Algorithms: A Review（2017）

3. A Fast Algorithm for Large Common Connected Induced Subgraphs（2017）

4. A performance analysis on maximal common subgraph algorithms（2011）

5. A Comparison of Algorithms for Maximum Common Subgraph on Randomly Connected Graphs（2002）

6. Challenging complexity of maximum common subgraph detection algorithms: A performance analysis of three algorithms on a wide database of graphs.（2007）

7. Enumerating all connected maximal common subgraphs in two graphs（2001）

8. GLSearch: Maximum Common Subgraph Detection via Learning to Search（2021）