图同构

维基百科,自由的百科全书
跳到导航 跳到搜索

图同构(Graph Isomorphism)描述的是图论中,两个之间的完全等价关系。在图论的观点下,两个同构的被当作同一个图来研究。

定义[编辑]

只有节点数目相同(即同阶)的两个才有可能同构。两个简单图称为是同构的,当且仅当存在一个将的节点 映射到的节点一一对应,使得中任意两个节点相连接,当且仅当中对应的两个节点相连接。如果是有向图,那么同构的定义中还进一步要求对于中任意两个相连的节点,边与它在中对应的边方向相同。类似地可以定义两个多重图的同构关系。

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

从图到图的同构映射
Graph isomorphism a.svg Graph isomorphism b.svg

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

图同构问题[编辑]

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

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

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

计算复杂度[编辑]

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

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

  • 子图同构(Subgraph Isomorphism)问题:给定图和图,图的节点数目小于图,问是否存在的某一子图(subgraph),其与图同构

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

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

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

实用解法[编辑]

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

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

其它流行的方法包括:各色启发式算法[8];对QAP约化进行SDP英语Semidefinite programming松弛[9][10];近似计算图之间的某种不依赖于节点顺序的距离,例如图之间的编辑距离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 
  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. ^ NAUTY -- Graph Isomorphism. 
  8. ^ 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. 
  9. ^ 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. 
  10. ^ Aflalo, Yonathan; Bronstein, Alexander; Kimmel, Ron. On convex relaxation of graph isomorphism. Proceedings of the National Academy of Sciences. 2015, 112 (10): 2942––2947.