圖同構(英語:graph isomorphism)描述的是圖論中,兩個之間的完全等價關係。在圖論的觀點下,兩個同構的被當作同一個圖來研究。

定義

一般定義

只有節點數目相同(即同階)的兩個才有可能同構。兩個簡單圖  稱為是同構的,若且唯若存在一個將 的節點   映射到 的節點 一一對應 ,使得 中任意兩個節點  相連接,若且唯若 中對應的兩個節點  相連接。同構可記作 

圖同構是圖上的等價關係,可以據此將圖劃分為等價類。一組彼此同構的圖可稱為同構圖

如果  是有向圖,那麼同構的定義中還進一步要求對於 中任意兩個相連的節點  ,邊 與它在 中對應的邊 方向相同。類似地可以定義兩個多重圖的同構關係。

一個具體的例子如下,為方便起見,兩圖中對應節點被染成了相同的顏色:

    從圖 到圖 的同構映射 
     

 

 

 

 

 

 

 

要注意的一點是,在圖論中,一幅圖經常可以有多種不同的方式在紙上或屏幕上畫出來,所以兩個看起來很不同的圖也可能是同構的。尤其當圖的節點數比較大時,很難一眼從畫出的圖上判斷它們是否同構。

帶標籤的圖同構

對於帶標籤的圖,它們的同構有兩種定義。第一種定義,同構保留邊的雙射,同時包含標籤雙射。第二種定義,具有相同標籤的頂點集合被映射到同樣具有相同標籤的頂點集合,且該映射是雙射;對於邊也相同。例如,兩個頂點被標記為1和2的兩個 ,在第一種定義下僅有其自身為同構圖,在第二種定義下,雙方互為同構圖。

在某些情況下,當圖中頂點或邊被賦予唯一且互相不同的標籤時,我們將忽略標籤存在,根據圖的基礎結構進行圖同構的判定。

研究動機

同構的概念主要關注的是,忽略一個對象中不可分割的「原子」部分的個體差異性,探索圖結構的一致性和差異性問題。這點能使我們區分圖形結構本身的屬性和與圖形結構相關聯結構的屬性(例如圖形繪製、圖標記、資料結構相關的圖等)。據此,圖同構保留了一些圖中的一些結構性的關鍵信息:角,點或邊的標籤,有根樹的根等等。

圖同構問題

計算機科學數學統計學中,圖同構問題是複雜度理論研究中經常討論的熱點話題之一。圖同構問題容易和圖匹配問題混淆:

  • 判定圖同構(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]

對於以下的特殊情形,圖同構問題是可以多項式時間甚至快速求解的:

惠特尼圖同構定理

 
The exception of Whitney's theorem: these two graphs are not isomorphic but have isomorphic line graphs.

惠特尼圖同構定理[7]是由Hassler Whitney提出的。該定理內容是,兩個圖同構若且唯若它們的線性圖是同構的且不不包括K3K1,3。該定理可以擴展到超圖

實用解法

與理論研究主要關注計算複雜度不同,對實用解法的研究主要關注具體應用中的實踐計算速度。P/NP問題只關注時間複雜度中 的指數,而不關注其係數大小。即使一個算法是多項式時間的,它也可能因 的係數過大導致的速度太慢及/或數值上不穩定,而在實踐中根本沒有用處;反之,一個優秀的實用解法,即使不能保證是多項式時間的,在很多應用上也可能比一些多項式時間的解法快得多。

在圖同構問題上,目前處於領先性能的實用解法是由澳大利亞計算機科學家Brendan McKay英語Brendan McKay在1980年代提出的NAUTY[8],其對每一個圖 估計其節點的一個標準索引排列(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.