王 宇，劉燕麗，2*，陳劭武

（1.武漢科技大學理學院，武漢 430081；2.冶金工業(yè)過程系統科學湖北省重點實驗室（武漢科技大學），武漢 430081）

（?通信作者電子郵箱yanlil2008@163.com）

0 引言

圖被廣泛應用于描述事物的結構或事物之間的復雜關系，如互聯網、社交網絡、蛋白質交互網絡、化學分子結構、電力網、公路網、圖像處理中的屬性圖等［1］。給定模式圖和目標圖，子圖同構問題是判斷在目標圖中是否存在與模式圖完全同構的子圖。最大公共子圖（Maximum Common induced Subgraph，MCS）問題是子圖同構問題的優(yōu)化形式，即在模式圖和目標圖中找到滿足同構條件的最大子圖。

圖匹配問題廣泛應用于圖像處理［2-3］、生物化學［4］、信息檢索［5］、模式識別［6］、社交網絡［7］等領域。圖匹配問題可以識別數據集成中元數據或模型的對應關系。在生物學和生物化學領域，基因序列中每個基因可以表示為圖的頂點，若染色體上兩個基因相鄰，則圖中對應的頂點之間存在邊。利用圖匹配可以發(fā)現基因組中是否含有相同的基因。在模式識別中，圖匹配可以提取多個圖像中相似的對象。在Facebook等社交網絡中，頂點表示每個用戶，有向邊表示用戶之間的好友關系。利用已有的社交關系，為用戶推薦好友，也是圖匹配問題的應用之一。

文獻［8］提出了基于約束規(guī)劃（Constraint Programming，CP）模型的樹搜索算法。對于給定的模式圖P和目標圖T，每次選擇一個〈v，w〉（v∈VP，w∈VT）頂點匹配對作為空間搜索樹的分支點；界函數計算子樹含有的頂點的最大待匹配對個數，作為剪枝操作的上界。提高CP 類算法效率的關鍵工作是分支順序和定界函數的設計。文獻［9］提出了尋找給定子圖大小的帶有回溯的樹搜索算法-。文獻［10］提出了帶有回溯的樹搜索和頂點覆蓋相結合的技術。文獻［11］提出了一種基于標簽類的快速劃分算法McSplit（Maximum common induced subgraph Split），利用標簽類的劃分，快速實現了全局邊約束條件。相較傳統的存儲模式圖中每個頂點的值域以及值域過濾的方法，McSplit 算法大幅度降低了內存消耗，將MCS 算法的求解速度提高了若干數量級。

啟發(fā)式策略是提高基于CP 模型的MCS 算法效率的關鍵步驟。本文研究圍繞頂點沖突關系，解決了確定沖突頂點范圍、量化頂點沖突關系等關鍵問題，設計了基于頂點沖突的頂點匹配順序。實驗結果表明，基于頂點沖突的新匹配順序可以更有效地解決大規(guī)模稀疏圖的MCS問題。

1 最大公共子圖問題

本章介紹最大公共子圖問題相關的術語和基于分支定界的約束模型算法框架［12］。

1.1 相關術語

定義1圖G是由頂點的有窮非空集合和邊集合組成的，記為G=〈V，E〉。V是圖G的頂點集合，E是圖G的邊集合，（a，b）∈E，（a，b）表示頂點a和b之間存在連接邊。|V|表示頂點數，|E|表示邊數。

定義2給定模式圖Gp=〈Vp，Ep〉和目標圖Gt=〈Vt，Et〉，頂點匹配對〈v，w〉是頂點的笛卡兒積，v∈Vp，w∈Vt，且v和w具有相同的標簽屬性。

定義3給定模式圖Gp=〈Vp，Ep〉和目標圖Gt=〈Vt，Et〉，最大公共子圖問題是找到含有最多頂點匹配對的子圖Gs=〈Vs，Es〉，即任意匹配對〈v，w〉和〈k，j〉∈Vs，滿足（〈v，w〉，〈k，j〉）∈Es，當且僅當（v，k）∈Ep，（w，j）∈Et。該約束條件也被稱之為邊約束。

定義4頂點v的鄰域是與頂點v有邊相連的頂點的集合，記為N（v）。|N（v）|表示頂點v的鄰居個數。

定義5頂點域是由模式圖和目標圖中具有相同標簽屬性的頂點構成的集合，記為domain。由若干頂點域構成的集合稱之為域集，記為Domains。

1.2 基于分支定界的MCS算法

基于分支定界的MCS 算法是帶回溯的深度遍歷搜索樹空間的算法。算法1描述了MCS算法流程［11］。

算法1 MCS（Gp，Gt，Domains）。

輸入 模式圖Gp、目標圖Gt和初始域集Domains。

輸出Gp和Gt的最大公共子圖。

算法1 的初始域集Domains是根據頂點的標簽屬性劃分的頂點域集合。若輸入的Gp和Gt是無向非標定圖，那么Domains只有1個頂點域，即包含所有的模式圖頂點和目標圖頂點。若Gp和Gt是標簽圖，那么根據不同的標簽屬性，頂點被劃分到不同的頂點域中。curSolution記錄搜索過程中的當前解，初始為空；maxSolution是目前為止得到的最優(yōu)解，初始為空；bound（）返回在搜索樹當前分支點，所有頂點域可提供的最大匹配數之和，而每個頂點域的最大匹配數是該域中模式圖的頂點數和目標圖的頂點數兩者之中的較小值。ChooseDomain（）依據啟發(fā)式策略，從當前域集Domains中選出某個頂點域domain；ChooseV（）則返回依據啟發(fā)式策略，從domain中選擇的模式圖頂點v。filterDomains（）將搜索樹當前層的域集，依據與分支點的鄰接關系，劃分產生新的頂點域newDomains。

MCS 的求解過程是:首先根據模式圖Gp和目標圖Gt的標簽信息，建立初始域集Domains，如例1 中的D0。如果當前解大于目前的最優(yōu)解，那么更新最優(yōu)解為當前解（第1）～3）行）；否則，計算當前分支層的上界（第4）行）。上界是從樹根到當前分支點路徑上的匹配對數，與當前域集的最大可匹配對之和。如果上界小于等于目前的最優(yōu)解，表明該路徑不能提供比目前的最優(yōu)解更好的解，程序進入回溯，搜索樹剪枝（第5）～7）行）。

若不滿足剪枝條件，算法1 依據分支策略，從當前域集中選擇某個頂點域domain，然后再選取模式圖中某個頂點v，與目標圖中的可匹配頂點w逐一匹配，當前解增加匹配對〈v，w〉，滿足邊約束條件下，對剩余的頂點域進行劃分，并遞歸調用MCS 函數搜索新分支（第11）～13）行）。遍歷完v的所有匹配可能性后，移除v（第16）行）；若當前頂點域不再包含任何模式圖頂點，表明該域的所有匹配可能性已被遍歷，從域集中移除當前頂點域（第17）～19）行）；然后同樣方式遍歷其余的頂點域（第20）～22）行）。當算法遍歷完搜索空間，全局變量maxSolution記錄了最終的最優(yōu)解。

例1 說明了在搜索過程中，bound（）的計算方法和filterDomains（）產生新域集的過程。輸入的模式圖和目標圖均為無向圖。

例1 如圖1 所示，模式圖Gp的頂點集Vp=｛1，2，3，4，5｝，邊集Ep=｛（1，2）（1，3）（1，4）（2，3）（2，5）｝；目標圖Gt的頂點集Vt=｛a，b，c，d，e，f｝，邊集Et=｛（a，b）（a，c）（a，e）（b，d）（b，e）（c，d）（c，f）｝。

圖1 頂點域的圖例Fig.1 Instance of vertex domain

因為模式圖和目標圖是無向圖，頂點標簽屬性相同，所以Gp的每個頂點均可與Gt的頂點匹配，初始域集只包含1 個頂點域D0=｛1，2，3，4，5，a，b，c，d，e，f｝。顯然，D0可提供的最多匹配對是5（bound函數的返回值）。依據頂點度的降序策略，首先選擇〈1，a〉作為搜索樹第一個分支點。根據邊約束，產生與分支點〈1，a〉相鄰的頂點域D11=｛2，3，4，b，c，e｝，不相鄰的頂點域D12=｛5，d，f｝，所以filterDomains返回的新域集是｛D11，D12｝，該域集的bound函數返回值是3+1=4。

2 匹配沖突的學習

絕大多數傳統的MCS 算法選擇圖的靜態(tài)屬性作為分支策略的依據，如頂點鄰接性、頂點度、頂點或邊的標定值，而基于沖突學習的頂點匹配策略以強化學習的思想為核心，優(yōu)先選擇沖突高的頂點，以加速最優(yōu)解的計算。

2.1 強化學習

強化學習是智能體與環(huán)境交互，從環(huán)境中獲取學習的反饋信號；通過不斷的試錯，獲得行為的強化信號，最終達到累計獎勵最大化的目標［13-15］。強化學習中的要素:智能體、動作、環(huán)境、獎勵和目標。對于搜索樹空間，MCS 算法作為智能體，每次分支動作是在不斷地試錯，以達到快速找到最優(yōu)解的目標。如何定義搜索中，分支動作每次獲得的獎勵？如何獲得累計獎勵是需要解決的關鍵問題。

2.2 匹配的沖突

一旦匹配對造成搜索分支提供的最大可匹配對減少，則稱之為匹配沖突。匹配沖突代表了匹配動作對搜索環(huán)境的影響。例1 中，域集Dold=｛D11，D12｝的最大可匹配對是4。選擇〈5，d〉作為第二個分支點，滿足邊約束條件，D11被劃分為D21=｛2，b，c｝和D22=｛3，4，e｝；對D12劃分，沒有滿足邊約束條件的新頂點域產生。最終，形成新域集Dnew=｛D21，D22｝，且最大匹配對是1+1=2。Dold-Dnew=4-(2+1)=1，最大可匹配對減少1，其中等式左邊的1 代表分支點。同樣方法分析，若選擇〈2，d〉作為第二個分支點，產生新域集｛｛3，e｝｛4，c｝｛5，d｝｝，4-(3+1)=0，最大可匹配對未減少。

匹配的沖突說明分支頂點的匹配動作對搜索子樹的大小具有不同的影響。生成的子樹越小，bound函數獲得質量更好的上界，算法1 更快達到搜索的葉節(jié)點。同時，分析沖突的原因，搜索路徑上的每個分支點對當前子圖的產生均有作用。從子圖的角度分析，搜索樹空間相當于是待映射頂點構成的子圖。圖2 是去除分支點〈1，a〉和〈5，d〉的子圖，直觀地顯示了如果優(yōu)先選擇對環(huán)境影響大的頂點進行匹配，那么算法將獲得滿足邊約束條件、更加簡單的子空間。

圖2 去除分支點的子圖Fig.2 Subgraphs excluding branching nodes

3 基于沖突學習的頂點匹配策略

本章基于對匹配沖突的學習，設計獎勵函數，使得算法（智能體）獲得最大的獎勵。

3.1 獎勵函數

對于?v∈Vp(?w∈Vt)，本文定義頂點的獎勵函數來計算頂點每次從環(huán)境中獲得的獎勵，記為Rp(v)(Rt(w))。價值函數用于統計頂點累計獲得的獎勵，記為Sp(v)(St(w))，且初始化為0。具體地，頂點的累計獎勵包括兩個部分:

1）頂點v和w的獎勵是在完成〈v，w〉匹配后，上界的減少:

其中:Dold表示選擇分支之前的域集；Dnew表示頂點v和w匹配后，Dold被劃分產生的新域集；bound（）返回分支前、后的最大可匹配數，1 表示匹配對〈v，w〉。獲得分支頂點的獎勵后，更新頂點的累計獎勵。

該獎勵主要考慮分支動作對搜索環(huán)境的影響，上界的差值體現了分支動作造成的影響大小。

2）算法1執(zhí)行第1）～3）行時，找到了比之前部分搜索獲得的解更優(yōu)的公共子圖，而這是由于當前搜索路徑上的匹配動作造成的。因此，出現在搜索路徑上的頂點獲得獎勵。對匹配對∈curSolution，v∈Vp，w∈Vt，更新頂點的累計獎勵:

從約束條件進一步分析，依據與分支點〈1，a〉、〈5，d〉的相鄰性，圖2 中頂點2 與頂點c、b 可以匹配。對于待匹配的頂點，分支點限制了它們是否可以進行匹配，因此，匹配沖突往往是由多個分支點累計造成的。

3.2 新分支策略

引入頂點沖突學習后，采用新分支策略的MCS 算法流程如圖3所示。

圖3 采用新分支策略的MCS算法流程Fig.3 FLow chart of MCS algorithm with new branching strategy

新的分支策略分為兩步:首先確定頂點域；其次從該頂點域中分別選擇一個模式圖頂點和目標圖頂點進行匹配。

設域集DS=｛D0，D1，…，Dm｝，分別計算頂點域Di（i=0，1，…，m）中包括的模式圖頂點數和目標圖頂點數，i=0，1，…，m｝返回匹配操作復雜度較小的頂點域。max 函數返回每個頂點域的模式圖頂點數和目標圖頂點數兩者中較大值，min函數則再取max函數值域中的最小值（算法1中的ChooseDomain函數）。該頂點域的選擇策略糅合了最小頂點域策略和鄰域策略的優(yōu)點，既考慮了頂點域中每個頂點需匹配的最大次數，又考慮了最小頂點域。

從被選中的頂點域中，分別選擇模式圖頂點v和目標圖頂點w進行匹配。具體地，優(yōu)先選擇分數最高的頂點v（w），一旦出現平局，則選擇頂點度最大的作為分支點。

與傳統的分支策略不同，新分支策略不再依賴于圖的靜態(tài)屬性頂點度，而是對頂點在歷史搜索中產生的影響力進行學習，指導后續(xù)的搜索方向。

4 新分支策略的評估

實驗平臺是Intel Xeon CPUs E5-2680V4@2.40 GHz，內存4 GB，Linux 系統（Ubuntu 14.04）。每個算例的計算限制時間是1 800 s。

4.1 對比算法

實驗對比選擇了3種算法:

1）McSplit 算法［11］:McCreesh 等［11］于2017 年提出的求解最大公共子圖算法，采用了緊湊鄰域方法存儲每個模式圖頂點v的值域，并提出了基于劃分產生新的頂點域方法。該算法是目前處于先進水平的MCS算法。

2）McSplitSBS（McSplit Solution-Biased Search）算法［16］:是McSplit的改進版，采用偏好值順序和記錄非優(yōu)策略。

3）McSplitRLR（McSplit Reinforcement Learning and Routing）算法:本文在McSplit的基礎上，采用了基于頂點沖突學習的新分支策略。

4.2 算例集

算例集包含21 543個算例，來自生物化學、圖像、地勢、無線網格網絡等7 種工業(yè)問題（算例集下載地址http://liris.cnrs.fr/csolnon/SIP.html）。依據算例是否為有向圖，劃分為以下兩個子集:

1）生物化學（簡記為Bio）:來自biomodels.net，有136個有向、無標簽圖，是描述生物化學反應的網絡圖。頂點數的范圍是9～386。

2）大規(guī)模子圖同構和最大公共子圖算例:包括由隨機模型生成或由實際問題轉換而來的稀疏圖。模式圖的頂點數范圍是4～900，目標圖的頂點數范圍是10～6 671，共計12 227 個算例。依據實際問題的來源不同，含有6 278 個Images 算例，1 225 個LV 算例，3 430 個largerLV 算例，24 個PR15 算例，100個Scalefree算例，1 170個Si算例。

4.3 算法對比

表1 給出了3 個算法求解實際問題或隨機圖的求解個數和平均求解時間對比。第3、5、7 列的數據分別是在限定時間1 800 s 內對比算法求出最優(yōu)解的算例數，第4、6、8 列則是平均求解時間（單位為s）。平時求解時間=所有被解決算例的CPU時間之和/被解決的算例數。

如表1所示，相較于McSplit、McSplitSBS算法，McSplitrRLR在相同機器和求解限制時間條件下，多解決了109、33 個算例。對于不同類型的算例，對比算法的平均求解時間差異很小，這表明頂點獎勵的計算代價較小。McSplitRLR 和McSplit僅分支策略不同，實驗驗證了新分支策略的有效性。

表1 不同算法解決算例數和平均求解時間的對比Tab.1 Comparison of number of instances solved and average solving time of different algorithms

表1 中有7 396 個簡單算例均被McSplitrRLR、McSplit 和McSplitSBS 三個算法在10 s 之內解決，平均求解時間依次是0.48 s、0.45 s、0.57 s。這表明三種算法在簡單算例上求解效率是同一數量級，沖突學習并未降低求解簡單算例的效率。同時，圖4 給出了三個對比算法在困難算例求解上的效率，McSplitRLR 比McSplit、McSplitSBS 多解決了5.6%、1.6%的困難算例（算法解決的算例個數-7396），驗證了沖突學習策略有效地改進了困難算例的求解。

圖4 三個算法解決的困難算例數的對比Fig.4 Number comparison of hard instances solved by three algorithms

4.4 結果分析

影響分支定界算法的關鍵因素是上界和下界的確定。算法1 中第5）行表示當上界小等于下界（maxSolution）時，進行剪枝。如果算法更快地找到最優(yōu)解則獲得高質量的上界UB，在回溯過程中，更有利于滿足剪枝條件，提高剪枝率。

圖5 顯示了對于求解時間大于10 s 的困難算例，在相同的時間內，McSplitRLR 算法相較McSplit 和McSplitSBS 找到了更多算例的最優(yōu)解。

圖5 三種算法第一次找到最優(yōu)解的算例數對比Fig.5 Number comparison of instances of optimal solution first found by three algorithms

進一步地分析，圖6顯示頂點的多樣性選擇有利于算法1更快地找到最優(yōu)解，并進行有效的剪枝。圖6 中每個實心點對應Images 算例集的一個算例，該算例均被McSplit 和McSplitRLR 算法在時間t（10 s≤t≤1 800 s）內解決。實心點的坐標x（y）表示在McSplit（McSplitRLR）算法中頂點被選作分支次數的標準差，即:

圖6 模式圖頂點被選作分支點的次數的標準差對比Fig.6 Comparison of standard deviation of number of vertices in pattern graph selected as branch nodes

其中:n是在時間t內被McSplit 和McSplitRLR 找到最優(yōu)解的算例數；bvi表示模式圖的頂點vi作為分支點的次數是頂點作為分支點的平均次數

McSplit和McSplitRLR 算法僅分支策略不同，前者每次選擇度最大的頂點，而后者每次優(yōu)先選擇累計獎勵最大的頂點。在圖6中，更多的點出現在副對角線的下方，表明McSplitRLR算法的頂點標準差較小，即在搜索過程中，更多的頂點參與了分支過程，換句話說，基于頂點沖突學習的分支策略給度小的頂點更多的機會。

5 結語

最大公共子圖問題是解決眾多工業(yè)問題的基礎子問題，也是經典的NP-難度問題之一。不同頂點匹配動作對于搜索空間有不同的影響程度。本文所提出的基于頂點沖突學習的新分支策略解決了如何衡量匹配動作影響力、計算動作獎勵以及使用動作獎勵等問題。相較于傳統的、基于圖的靜態(tài)屬性的分支策略，新分支策略提供了一種新的學習方式和改進基于分支定界MCS 算法效率的途徑。學習歷史搜索經驗和開辟新搜索空間兩者之間的關系本質上是探索和利用的平衡。后續(xù)將對搜索中出現的局部最優(yōu)解做進一步的研究。