图同构

一般定义

只有节点数目相同(即同阶)的两个图才有可能同构。两个简单图${\displaystyle G}$ 和${\displaystyle H}$ 称为是同构的，当且仅当存在一个将${\displaystyle G}$ 的节点 ${\displaystyle 1,\ldots ,n}$  映射到${\displaystyle H}$ 的节点${\displaystyle 1,\ldots ,n}$ 的一一对应${\displaystyle \sigma }$ ，使得${\displaystyle G}$ 中任意两个节点${\displaystyle i}$ 和${\displaystyle j}$ 相连接，当且仅当${\displaystyle H}$ 中对应的两个节点${\displaystyle \sigma (i)}$ 和${\displaystyle \sigma (j)}$ 相连接。同构可记作${\displaystyle G\simeq H}$ 。

图同构是图上的等价关系，可以据此将图划分为等价类。一组彼此同构的图可称为同构图。

如果${\displaystyle G}$ 和${\displaystyle H}$ 是有向图，那么同构的定义中还进一步要求对于${\displaystyle G}$ 中任意两个相连的节点${\displaystyle i}$ 和${\displaystyle j}$ ，边${\displaystyle (i,j)}$ 与它在${\displaystyle H}$ 中对应的边${\displaystyle (\sigma (i),\sigma (j))}$ 方向相同。类似地可以定义两个多重图的同构关系。

一个具体的例子如下，为方便起见，两图中对应节点被染成了相同的颜色：

要注意的一点是，在图论中，一幅图经常可以有多种不同的方式在纸上或屏幕上画出来，所以两个看起来很不同的图也可能是同构的。尤其当图的节点数比较大时，很难一眼从画出的图上判断它们是否同构。

带标签的图同构

对于带标签的图，它们的同构有两种定义。第一种定义，同构保留边的双射，同时包含标签双射。第二种定义，具有相同标签的顶点集合被映射到同样具有相同标签的顶点集合，且该映射是双射；对于边也相同。例如，两个顶点被标记为1和2的两个${\displaystyle K_{2}}$ ，在第一种顶一下仅有其自身为同构图，在第二种定义下，双方互为同构图。

在某些情况下，当图中顶点或边被赋予唯一且互相不同的标签时，我们将忽略标签存在，根据图的基础结构进行图同构的判定。

同构的概念主要关注的是，忽略一个对象中不可分割的“原子”部分的个体差异性，探索图结构的一致性和差异性问题。这点能使我们区分图形结构本身的属性和与图形结构相关联结构的属性（例如图形绘制、图标记、数据结构相关的图等）。据此，图同构保留了一些图中的一些结构性的关键信息：角，点或边的标签，有根树的根等等。

在计算机科学、数学和统计学中，图同构问题是复杂度理论研究中经常讨论的热点话题之一。图同构问题容易和图匹配问题混淆：

• 判定图同构(Graph Isomorphism)问题：只需判断两个图之间是否是同构的，但如果同构的话，并不要求具体找出任何做成同构的对应关系
• 图匹配(Graph Matching)问题：判断两个图是否同构，如果同构，找出至少一个使得两者做成同构的节点间的一一对应关系

严格地说，两个问题是不同的，显然后者是比前者更进一步的问题，但也有一些论文将两者混同并用Graph Isomorphism一词指代Graph Matching问题。迄今尚无人严格证明两者难度在P/NP意义下是相等的(要证明这一点，就必须证明第一个问题的答案可被多项式时间约化为第二个问题的答案，即：存在一个正常数${\displaystyle d>0}$ ，使得对于任何一个可以判定两个图是否同构的算法${\displaystyle {\cal {J}}}$ ，若${\displaystyle {\cal {J}}}$ 输出的判定为真，那么在参考${\displaystyle {\cal {J}}}$ 输出的结果的基础上再花费至多${\displaystyle O(n^{d})}$ 时间就可找出至少一个做成图同构的一一对应)。

计算复杂度

判定图同构(Graph Isomorphism)的计算复杂度是未知的，因此现在仅能被粗略地归类为NP^[1]；图匹配(Graph Matching)问题本身的复杂度同样是未知的，但在机器学习领域非常流行的一种约化版本将其视为NP困难的QAP（英语：Quadratic assignment problem）问题的特殊情形

${\displaystyle \min _{P\in \{0,1\}^{n\times n},P^{T}P=I}\left\|G-PHP^{T}\right\|_{F}}$ 

其中${\displaystyle \|\cdot \|_{F}}$ 表示矩阵的Frobenius模。该QAP约化相当于问：要求找到从${\displaystyle G}$ 到${\displaystyle H}$ 的一一映射，使得在此映射下两个图最相似。显然图匹配问题是该QAP问题的一种特殊情形，因为当两个图并不同构时，寻找两图间同构映射的尝试是没有意义的，但寻找两图间的一个最大化相似度的“最优映射”仍然是有意义的。尤其在当所给的数据并非图的精确观测而是被随机误差污染时，更常用该约化形式并予以近似求解^[2]。另有与两个问题相关的更进一步的问题：

• 子图同构(Subgraph Isomorphism)问题：给定图${\displaystyle G}$ 和图${\displaystyle H}$ ，图${\displaystyle G}$ 的节点数目小于图${\displaystyle H}$ ，问是否存在${\displaystyle H}$ 的某一子图(subgraph)，其与图${\displaystyle G}$ 同构

子图同构已被证明是NP完全问题。

2015年，芝加哥大学教授、匈牙利裔计算机科学家László Babai（英语：László Babai）宣布证明了图同构问题可以在准多项式(Quasi-polynomial)时间内求解^[3]。哈洛德·贺欧夫各特指出了文中的一处错误，随后Babai宣布修正了该错误并更新了论文^[4]。

对于以下的特殊情形，图同构问题是可以多项式时间甚至快速求解的：

• 树
• 平面图
• 区间生成图（英语：Interval graph）
• 置换生成图（英语：Permutation graph）
• 循环对称图（英语：Circulant graph）
• 以及当任意一个下面列举的描述图结构性特征的统计量被不随节点数增长的常数上限约束时，图同构问题可被多项式时间求解：
  • 图的树分解（英语：Tree decomposition）的宽度（英语：Treewidth）
  • 亏格
  • 最大的节点度数 (这被认为是图同构理论迄今为止取得的最重要突破性进展之一) ^[5]
  • 图的邻接矩阵或任何一种拉普拉斯矩阵的特征值的最大重数^[6]

惠特尼图同构定理

惠特尼图同构定理^[7]是由Hassler Whitney提出的。该定理内容是，两个图同构当且仅当它们的线性图是同构的且不不包括K₃和 K_1,3。该定理可以扩展到超图。

实用解法

与理论研究主要关注计算复杂度不同，对实用解法的研究主要关注具体应用中的实践计算速度。P/NP问题只关注时间复杂度中${\displaystyle n}$ 的指数，而不关注其系数大小。即使一个算法是多项式时间的，它也可能因${\displaystyle n}$ 的系数过大导致的速度太慢及/或数值上不稳定，而在实践中根本没有用处；反之，一个优秀的实用解法，即使不能保证是多项式时间的，在很多应用上也可能比一些多项式时间的解法快得多。

在图同构问题上，目前处于领先性能的实用解法是由澳大利亚计算机科学家Brendan McKay（英语：Brendan McKay）在1980年代提出的NAUTY^[8]，其对每一个图${\displaystyle G}$ 估计其节点的一个标准索引排列(Canonical Indexing，或称Canonical Labeling)。标准索引可以非常耗时，而NAUTY算法通过探索图的自同构性群的性质，对索引步骤进行剪枝，大大加快了标准索引的计算速度。NAUTY自从提出以来，成为了几乎每一篇研究图同构和图匹配问题实用解法的论文必定要进行比较的竞争对手。

其它流行的方法包括：各色启发式算法^[9]；对QAP约化进行SDP（英语：Semidefinite programming）松弛^[10][11]；近似计算图之间的某种不依赖于节点顺序的距离，例如图之间的编辑距离和cut distance等，这些距离的精确计算通常是NP困难的。

1. ^ László Babai. Groups, Graphs, Algorithms: The Graph Isomorphism Problem. ICM 2018. 
2. ^ Lyzinski, Vince, Information Recovery in Shuffled Graphs via Graph Matching, 2016, arXiv:1605.02315   
3. ^ Babai, László, Graph Isomorphism in Quasipolynomial Time, 2015, arXiv:1512.03547   
4. ^ Babai, László, Graph isomorphism update, January 9, 2017 [2018-10-28], （原始内容存档于2018-10-14） 
5. ^ Luks, Eugene M. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of computer and system sciences. 1982, 25 (1): 42––65. 
6. ^ László Babai; D. Yu. Grigoryev; David M. Mount. Isomorphism of graphs with bounded eigenvalue multiplicity. Proceedings of the fourteenth annual ACM symposium on Theory of computing. 1982: 310––324. 
7. ^ Whitney, Hassler. Congruent Graphs and the Connectivity of Graphs. American Journal of Mathematics. January 1932, 54 (1): 150–168. JSTOR 2371086. doi:10.2307/2371086. hdl:10338.dmlcz/101067. 
8. ^ NAUTY -- Graph Isomorphism. [2018-10-28]. （原始内容存档于2018-03-04）. 
9. ^ D. Conte; P. Foggia; C. Sansone; M. Vento. Thirty Years Of Graph Matching In Pattern Recognition. International journal of pattern recognition and artificial intelligence. 2004, 18 (3): 265––298. 
10. ^ Lyzinski, Vince; Fishkind, Donniell; Fiori, Marcelo; Vogelstein, Joshua; Priebe, Carey; Sapiro, Guillermo. Graph matching: Relax at your own risk. IEEE Transactions on Pattern Analysis \& Machine Intelligence. 2016. 
11. ^ Aflalo, Yonathan; Bronstein, Alexander; Kimmel, Ron. On convex relaxation of graph isomorphism. Proceedings of the National Academy of Sciences. 2015, 112 (10): 2942––2947.