基于頂點沖突學(xué)習(xí)的最大公共子圖算法

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

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

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

0 引言

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

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

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

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

1 最大公共子圖問題

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

1.1 相關(guān)術(shù)語

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

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

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

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

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

1.2 基于分支定界的MCS算法

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

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

輸入 模式圖Gp、目標(biāo)圖Gt和初始域集Domains。

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

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

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

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

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

例1 如圖1 所示，模式圖Gp的頂點集Vp=｛1，2，3，4，5｝，邊集Ep=｛（1，2）（1，3）（1，4）（2，3）（2，5）｝；目標(biāo)圖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

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

2 匹配沖突的學(xué)習(xí)

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

2.1 強(qiáng)化學(xué)習(xí)

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

2.2 匹配的沖突

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

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

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

3 基于沖突學(xué)習(xí)的頂點匹配策略

本章基于對匹配沖突的學(xué)習(xí)，設(shè)計獎勵函數(shù)，使得算法（智能體）獲得最大的獎勵。

3.1 獎勵函數(shù)

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

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

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

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

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

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

3.2 新分支策略

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

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

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

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

從被選中的頂點域中，分別選擇模式圖頂點v和目標(biāo)圖頂點w進(jìn)行匹配。具體地，優(yōu)先選擇分?jǐn)?shù)最高的頂點v（w），一旦出現(xiàn)平局，則選擇頂點度最大的作為分支點。

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

4 新分支策略的評估

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

4.1 對比算法

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

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

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

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

4.2 算例集

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

1）生物化學(xué)（簡記為Bio）:來自biomodels.net，有136個有向、無標(biāo)簽圖，是描述生物化學(xué)反應(yīng)的網(wǎng)絡(luò)圖。頂點數(shù)的范圍是9～386。

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

4.3 算法對比

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

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

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

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

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

4.4 結(jié)果分析

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

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

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

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

圖6 模式圖頂點被選作分支點的次數(shù)的標(biāo)準(zhǔn)差對比Fig.6 Comparison of standard deviation of number of vertices in pattern graph selected as branch nodes

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

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

5 結(jié)語

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