最大公共子图（MCS）的大小、子图编辑距离和嵌入距离

最大公共子图（MCS）的大小、子图编辑距离和嵌入距离是图匹配和图相似性度量中的常见概念，它们用于比较两个图之间的相似性。以下是它们的定义：

1. 最大公共子图（MCS）的大小：

   • 定义： 最大公共子图是两个图中具有相同结构的最大子图。即，在两个图中找到一个共同的子图，使得这个子图不能再扩展，即没有更多的节点或边可以添加到子图中。
   • 应用： MCS 的大小是一种衡量两个图结构相似性的指标。较大的 MCS 表示两个图结构更为相似。

2. 子图编辑距离：

   • 定义： 子图编辑距离是通过一系列编辑操作（添加、删除、替换节点或边）将一个图转换为另一个图所需的最小操作次数。编辑操作的代价通常与节点或边的相似性有关。
   • 应用： 子图编辑距离衡量了两个图之间结构的差异，它对图的结构变化和拓扑变化都较为敏感。

3. 嵌入距离：

   • 定义： 嵌入距离通常用于衡量图的嵌入表示之间的相似性。如果两个图在嵌入空间中的表示越接近，它们的嵌入距离就越小。
   • 应用： 嵌入距离适用于使用图神经网络等技术生成的低维嵌入表示，用于比较图的结构相似性。

这些概念和度量方法在图匹配、图相似性计算、图数据库查询等领域有着广泛的应用。选择合适的度量方法取决于具体的应用场景和问题要求。