一種面向動態(tài)異構(gòu)信息網(wǎng)絡(luò)的高效極大motif團挖掘方法

丁 晨，周軍鋒，杜 明

(東華大學(xué)，上海 201620)

0 引言

當(dāng)前社會處于信息時代，數(shù)據(jù)類型繁雜多樣，異構(gòu)信息網(wǎng)絡(luò)[1-2]是一種把頂點與類型標(biāo)簽相連的數(shù)據(jù)圖，用于刻畫不同類型對象間的復(fù)雜限制語義。相比于頂點類型單一的數(shù)據(jù)圖，異構(gòu)信息網(wǎng)絡(luò)可以用不同類型的實體及實體間聯(lián)系表達出多元化、交互性高的信息。

異構(gòu)信息網(wǎng)絡(luò)常與motif[3-5]結(jié)合，motif用于給定不同類型頂點間的限制關(guān)系，通過發(fā)現(xiàn)極大motif團[6]可以在異構(gòu)信息網(wǎng)絡(luò)上挖掘有價值的信息。常見的異構(gòu)信息網(wǎng)絡(luò)，如生物網(wǎng)絡(luò)、書目數(shù)據(jù)庫和共同購物圖等，已被應(yīng)用于各種領(lǐng)域[7-9]。如圖1所示，在異構(gòu)信息網(wǎng)絡(luò)G中，頂點類型分為三類：作者類型、論文類型、會議類型，給定motif M所示的頂點關(guān)系，通過挖掘極大motif團，可以找到有合作關(guān)系的作者。

圖1 異構(gòu)信息網(wǎng)絡(luò)Fig.1 heterogeneous information network

異構(gòu)信息網(wǎng)絡(luò)和極大 motif團有很高的實用價值。然而，異構(gòu)信息網(wǎng)絡(luò)不是一成不變的，它在實際應(yīng)用中會頻繁更新，由此衍生出如何實時更新極大motif團的問題。現(xiàn)有算法META（the maximal m-clique enumeration algorithm）可以在靜態(tài)圖上快速發(fā)現(xiàn)極大 motif團，但不支持在動態(tài)圖上更新極大 motif團。為了實現(xiàn)更新操作，該算法需要在圖變化后重新枚舉極大 motif團，這種做法存在大量冗余，效率不高。

針對現(xiàn)有算法的不足，本文提出一種支持極大motif團更新的高效算法UMMD（the algorithm of updating maximal motif-clique on dynamic HINs）。該算法主要由加邊策略、減邊策略構(gòu)成。其基本思想是：在加減邊時，只處理與邊兩端頂點關(guān)聯(lián)的極大 motif團，從而縮小更新范圍，避免枚舉操作。實驗結(jié)果表明，本文提出的算法可以高效地在動態(tài)異構(gòu)信息網(wǎng)絡(luò)上挖掘極大motif團。

1 背景知識和相關(guān)工作

1.1 相關(guān)概念和問題定義

定義 1 異構(gòu)信息網(wǎng)絡(luò)：異構(gòu)信息網(wǎng)絡(luò)是一個四元組G=(V, E, T, F)，V代表圖G中頂點的非空有限集合，E代表圖G中邊的有限集合，T代表圖G中頂點類型的非空有限集合，F(xiàn)是一個類型函數(shù)，用于對圖中每個頂點分配一個T中的頂點類型，每個頂點的類型在給定后不改變。本文的異構(gòu)信息網(wǎng)絡(luò)均是無向圖。

如圖1所示，G是一個異構(gòu)信息網(wǎng)絡(luò)，其包含三種類型的頂點。

定義2 motif：對于異構(gòu)信息網(wǎng)絡(luò)G=(V, E, T,F)，motif是一個四元組M=(Vm, Em, Tm, Fm)，Vm代表M中頂點的非空有限集合，|Vm|不大于|V|；Tm代表M中頂點類型的非空有限集合，Tm?T；Fm是一個類型函數(shù)，用于對M中每個頂點分配一個Tm中的類型；Em代表M中邊的有限集合，對于?(um, vm)?Em，F(xiàn)(um)類型的頂點與F(vm)類型的頂點在G中允許相連。

定義3 motif匹配點集：給定異構(gòu)信息網(wǎng)絡(luò)G=(V, E, T, F)、motif M=(Vm, Em, Tm, Fm)，對于一個非空點集H?V，如果|H|=|Vm|，且H與Vm存在一種雙射關(guān)系f，即對?u∈H，F(xiàn)(u)=Fm(f(u))，那么H是motif匹配點集。

例如，對于圖1的G，點集{1,3,4}、點集{1,4,5}均是motif匹配點集，點集{4,5,8}則不是motif匹配點集。

定義4 motif導(dǎo)出子圖：給定異構(gòu)信息網(wǎng)絡(luò)G=(V, E, T, F)、motif M=(Vm, Em, Tm, Fm)，G′=(V′,E′, T′, F′)是 G 的一個導(dǎo)出子圖，如果|V′|=|Vm|，且V′與Vm存在一種雙射關(guān)系f，即對于?u∈V′，F(xiàn)(u)=Fm(f(u))且?u, v∈V′，(u, v) ∈E′，(f(u),f(v))∈Em，那么G′是一個motif導(dǎo)出子圖。

例如，在圖1的G中可以找到4個motif導(dǎo)出子圖，它們對應(yīng)的點集分別是{1,3,4}、{2,3,4}、{3,4,6}、{4,5,6}。

定義5 motif團：給定異構(gòu)信息網(wǎng)絡(luò)G=(V, E,T, F)、motif M=(Vm, Em, Tm, Fm)，G′=(V′, E′, T′, F′)是G的一個導(dǎo)出子圖，如果|T′|=|Tm|，G′中至少有一個motif匹配點集，且G′的每個motif匹配點集都是motif導(dǎo)出子圖，G′是一個motif團。

例如，對于圖1的G，點集{1,2,3,4}構(gòu)成的子圖是motif團，但點集{3,4,5,6}、點集{4,6,8}構(gòu)成的子圖均不是motif團。

定義6 候選頂點：對于一個motif導(dǎo)出子圖，如果一個頂點能與它組成 motif團，則稱該頂點為此motif導(dǎo)出子圖的候選頂點。

定義7 極大motif團：如果一個motif團不被圖中的其他 motif團包含，那么它是一個極大motif團。

例如，對于圖1的G，點集{1,2,3,4,6}、點集{4,5,6}構(gòu)成的子圖均是極大motif團。G中作者類型頂點與論文類型頂點的邊，代表某作者撰寫了某論文；論文類型頂點間的邊，代表兩篇論文的研究方向相似。給定 M 所示的頂點關(guān)系，一個motif導(dǎo)出子圖代表一個作者撰寫了兩篇研究方向相似的論文，一個極大 motif團可以代表有合作關(guān)系的作者們共同撰寫了數(shù)篇方向相似的論文。當(dāng)找到G中所有的極大motif團時，也就找到了全部合作過的作者以及他們撰寫的論文。

問題定義給定動態(tài)異構(gòu)信息網(wǎng)絡(luò)G=(V, E,T, F)、motif M=(Vm, Em, Tm, Fm)、已有的極大 motif團，在G發(fā)生變化后更新極大motif團。

文中符號的含義如表1所示。

表1 符號解釋Tab.1 symbol interpretation

1.2 相關(guān)工作

motif是大型信息網(wǎng)絡(luò)的基本構(gòu)建模塊，常被應(yīng)用于神經(jīng)科學(xué)、生物學(xué)、社會網(wǎng)絡(luò)等領(lǐng)域。Gurukar[10]等人研究了動態(tài)交互網(wǎng)絡(luò)中通信 motif的挖掘，并開發(fā)了COMMIT技術(shù)。COMMIT技術(shù)將動態(tài)網(wǎng)絡(luò)轉(zhuǎn)換為序列數(shù)據(jù)庫，從而更快地在網(wǎng)絡(luò)中發(fā)現(xiàn)motif。Benson A R[11]通過使用motif解決了 motif-aware的圖聚類問題，Stefani L[12]解決了計算motif頻率的問題。

胡佳峰等人首次提出了文獻[6]中的極大motif團發(fā)現(xiàn)算法META，該算法的輸入是異構(gòu)信息網(wǎng)絡(luò)G、motif M，輸出是圖中所有的極大motif團。如圖1所示，META可以根據(jù)給定的G和M，快速枚舉出 G中所有的極大 motif團，即mmc{1,2,3,4,6}、mmc{4,5,6}。

META算法的基本思想如下：根據(jù)現(xiàn)有的子圖匹配算法 VF3[13]，找到圖中所有的 motif導(dǎo)出子圖，對每一個motif導(dǎo)出子圖，仿照BK算法[14]，通過維護三個不同功能的點集 U、C、NOT來枚舉求解它的極大motif團。點集U用來存放當(dāng)前正在被枚舉的 motif團，U里的點可以構(gòu)成一個motif團，但不一定是一個極大motif團，U的初始狀態(tài)是空集；點集C是候選頂點集，C里的每個頂點都可以加入U中的motif團，C的初始狀態(tài)是所有頂點的集合；點集NOT是禁止集，NOT里的每個頂點也都可以加入U中的motif團，但如果一個頂點被存放在NOT里，意味著包含該點的所有極大motif團已經(jīng)被枚舉過，NOT的初始狀態(tài)是空集。在枚舉過程中，當(dāng)點集C與點集NOT都為空時，U里存放的便是一個極大motif團。

2 支持極大 motif團更新的高效算法UMMD

對于動態(tài)異構(gòu)信息網(wǎng)絡(luò)的變化，本文研究圖加邊、減邊兩種情況。加邊指的是每次在圖中添加一條不存在的邊；減邊指的是每次從圖中刪去一條存在的邊?，F(xiàn)有算法在圖發(fā)生變化后會重新枚舉，其更新范圍是全圖，且枚舉過程存在冗余。針對上述問題，本文提出以下更新策略。

2.1 加邊策略

本文的加邊策略通過選擇性更新來剪枝更新范圍，即只更新與新邊兩端頂點相連的原有極大motif團，并通過枚舉候選頂點補充更新結(jié)果。

根據(jù)定義，極大motif團可看作由motif導(dǎo)出子圖構(gòu)成。如圖1所示，G中的 mmc{1,2,3,4,6}是由 me{1,3,4}、me{2,3,4}和 me{3,4,6}構(gòu)成。易知，圖中出現(xiàn)了新的 motif導(dǎo)出子圖后，才會出現(xiàn)新極大motif團。用(u, v)表示邊，在動態(tài)異構(gòu)信息網(wǎng)絡(luò)上加邊后，當(dāng)圖中先出現(xiàn)包含點u和點v的新motif導(dǎo)出子圖后，才會出現(xiàn)新極大motif團，這說明新極大motif團一定是包含點u和點v的。因此，與點u和點v均不相連的原有極大motif團不會變化，只需選擇性更新包含點u或點v的原有極大 motif團。具體來說，對于包含點 u的極大 motif團，判斷點 v能否加入其中；對于包含點v的極大motif團，判斷點u能否加入其中。

上述方法雖然縮小了更新范圍，但可能會出現(xiàn)更新過程中丟失極大 motif團的問題。如圖 2所示，G中的原有極大motif團是mmc{1,3,4,5}、mmc{2,4,6}，在G上插入邊(2,5)后，選擇性更新原有極大 motif團，即 mmc{1,3,4,5}、mmc{2,4,6}，判斷點2不能加入mmc{1,3,4,5}，因此mmc{1,3,4,5}不發(fā)生變化；判斷點5可以加入mmc{2,4,6}，從而將mmc{2,4,6}變?yōu)閙mc{2,4,5,6}。更新過程結(jié)束，但新極大 motif團 mmc{1,2,4,5}未發(fā)現(xiàn)。造成這種情況的原因是新邊的頂點可能與原有極大motif團的子集結(jié)合，從而形成新極大motif團。

通過枚舉未發(fā)現(xiàn)的新 motif導(dǎo)出子圖的候選頂點可以解決上述問題。例如，圖2的G加入邊(2,5)后，圖中出現(xiàn)新motif導(dǎo)出子圖me{2,4,5}、me{2,5,6}，它們的候選頂點是點1、點4、點6。而新極大motif團mmc{2,4,5,6}包含了點4、點6，不包含點 1，說明還有包含點 1的新極大 motif團未發(fā)現(xiàn)。通過現(xiàn)有的枚舉算法可以找出mmc{1,2,4,5}，從而完善更新結(jié)果。

圖2 候選頂點示例Fig.2 examples of candidate vertices

算法 1詳細(xì)介紹了加邊策略的過程。將新motif導(dǎo)出子圖的候選頂點存進cands（第1行）。如果cands為空，說明新motif導(dǎo)出子圖沒有候選頂點，它本身便是一個極大motif團（第2-4行）。選擇性更新極大motif團，并維護cands（第5-13行）。如果cands不為空，進行枚舉操作補充更新結(jié)果（第14-15行）。本文在判斷一個點能否加入motif團、枚舉候選頂點時使用了文獻[6]的方法。

下面以圖3為例介紹UMMD-insert的算法過程。給定動態(tài)異構(gòu)信息網(wǎng)絡(luò)G、motif M，假設(shè)在G上插入邊(3,5)，原有極大motif團是mmc{1,2,3,4,6}、mmc{4,5,6}。圖中新出現(xiàn)的motif導(dǎo)出子圖是me{3,5,6}，它的候選頂點是點4，將其存進cands。更新 mmc{1,2,3,4,6}，判斷點 5能否加入其中，點 5不可以加入，mmc{1,2,3,4,6}不變化；更新mmc{4,5,6}，判斷點3能否加入其中，點3可以加入，將mmc{4,5,6}變?yōu)閙mc{3,4,5,6}，并將點4從 cands中刪去。因為 cands為空，直接輸出mmcs作為更新后的極大motif團。

圖3 圖更新示例Fig.3 examples of graph updating

2.2 減邊策略

本文減邊策略也通過選擇性更新剪枝更新范圍。在動態(tài)異構(gòu)信息網(wǎng)絡(luò)上減邊后，只處理同時包含邊兩端頂點的原有極大 motif團，對其進行更新操作。

用(u, v)表示邊，在動態(tài)異構(gòu)信息網(wǎng)絡(luò)上減邊后，對一個原有極大motif團mmc的更新操作可以具化為刪除其中的點u或點v。對于一個頂點，如果mmc中不存在包含該點的motif導(dǎo)出子圖，說明它無法與mmc中的其他點構(gòu)成motif團，需將其從mmc中刪除，反之，將該點保留在mmc中。

例如，假設(shè)在圖 1中刪除邊(2,4)，選擇性更新原有 mmc{1,2,3,4,6}。me{2,3,4}不再成立，點2在mmc中沒有其他關(guān)聯(lián)的motif導(dǎo)出子圖，故將點2從mmc{1,2,3,4,6}中刪去；點4在mmc中與me{1,3,4}、{3,4,6}有關(guān)聯(lián)，故保留在mmc{1,3,4,6}中。mmc{1,3,4,6}是一個圖更新后的極大motif團。但是，對于一個極大motif團，經(jīng)歷上述操作后，也可能被刪減為其他原極大 motif團的子集。因此，在更新結(jié)束后，需要把更新結(jié)果與其他原極大 motif團比較，去除結(jié)果中的偽極大motif團。

算法2詳細(xì)介紹了減邊策略的過程。用(u, v)表示邊，在動態(tài)異構(gòu)信息網(wǎng)絡(luò)上減邊后，設(shè)置set存儲更新結(jié)果，使其初始值為空集，找出同時包含點u和點v的極大motif團mmc，對其進行更新操作（第1-3行）。選擇性更新極大motif團（第2-8行）。當(dāng)set不為空時，通過與原有極大motif團比較，判斷它們中是否存在偽極大motif團（第9-13行）。

下面以圖3為例介紹UMMD-delete的算法過程。給定異構(gòu)信息網(wǎng)絡(luò)G、motif M，假設(shè)從G中刪去邊(3,5)，原有的極大 motif團是 mmc{1,2,3,4,6}、mmc{3,4,5,6}。在G上刪除邊(3,5)后，更新mmc{3,4,5,6}。因為 me{3,4,6}、me{4,5,6}是mmc{3,4,5,6}的子集，將mc{4,5,6}、mc{3,4,6}存進set，并把mmc{3,4,5,6}從mmcs中刪除。再通過比較發(fā)現(xiàn) mc{3,4,6}是原有極大 motif團mmc{1,2,3,4,6}的子集，即 mc{3,4,6}是一個偽極大motif團，而mc{4,5,6}不是任何原有極大motif團的子集，mc{4,5,6}可作為一個新極大motif團，更新結(jié)束。

2.3 算法分析

給定動態(tài)異構(gòu)信息網(wǎng)絡(luò)G、motif M，在G上插入邊后，UMMD算法的平均算法時間復(fù)雜度為O(|Nmmc|·|Vmmc|·|V/E|)；在 G 上刪除邊后，UMMD算法時間復(fù)雜度為 O(|Nmmc|·|Nme|·lg|Vmmc|)。|Nmmc|代表 G中包含點邊兩端頂點的極大 motif團的個數(shù)，|Vmmc|代表 G中極大 motif團的平均點數(shù)，|Nme|代表G中motif導(dǎo)出子圖的個數(shù)，|V/E|代表 G中頂點的平均度數(shù)，其中|V|代表 G的點數(shù)，|E|代表G的邊數(shù)。

使用基礎(chǔ)算法META枚舉極大motif團的最壞時間復(fù)雜度是O(n!·n2)，最好時間復(fù)雜度也要大于 O(n2)，其中n為圖的頂點數(shù)。因此，UMMD算法的更新效率更高。

3 實驗

3.1 實驗環(huán)境

實驗所使用的硬件配置是Inter Core i7主頻為2.60GHz的CPU，16GB的RAM內(nèi)存，Windows 10 64位系統(tǒng)；實驗的運行環(huán)境為Microsoft Visual Studio 2017，解決方案是Release，解決方案平臺是x64。

實驗用于比較的算法：（1）META算法；（2）UMMD算法。以上算法均采用C++語言實現(xiàn)。

3.2 數(shù)據(jù)集

本文使用12個實驗數(shù)據(jù)集進行實驗，數(shù)據(jù)集基于4個真實異構(gòu)信息網(wǎng)絡(luò)，分別是Reactome、Amazon、Yeast、Instacart。異構(gòu)信息網(wǎng)絡(luò)與motif相結(jié)合，motif的頂點規(guī)模會影響算法挖掘極大motif團的效率，所以本文將一個異構(gòu)信息網(wǎng)絡(luò)與點數(shù)3、點數(shù)5、點數(shù)7的motif相關(guān)聯(lián)，生成12個數(shù)據(jù)集。例如，用 Reactome-3、Reactome-5、Reactome-7表示Reactome不變，將其分別與點數(shù)為3、5、7的motif相關(guān)聯(lián)。

數(shù)據(jù)集Reactome是一個生物信息網(wǎng)絡(luò)，主要描述了蛋白質(zhì)大分子、生物行為作用、不同物種間的交互信息；數(shù)據(jù)集 Amazon來自于亞馬遜網(wǎng)站，圖中共有4種不同類型的頂點，商品類型頂點之間的邊代表兩個商品是在同一次購物過程中購買的。數(shù)據(jù)集 Yeast是一個蛋白質(zhì)分子生物網(wǎng)絡(luò)，共有71種頂點類型；數(shù)據(jù)集Instacart是一個購物網(wǎng)站的異構(gòu)信息網(wǎng)絡(luò)，頂點類型有21種，商品類型頂點之間的邊代表兩個商品被同時購買超過 200次。4個基本異構(gòu)信息網(wǎng)絡(luò)的相關(guān)統(tǒng)計信息如表2所示，其中|V|和|E|分別表示圖中的頂點數(shù)以及邊數(shù)。

表2 數(shù)據(jù)集統(tǒng)計信息Tab.2 statistics for the dataset

3.3 性能分析與比較

本文為了直觀顯示更新效率，以更新極大motif團的時間開銷作為算法性能指標(biāo)。此外，本文實驗還研究圖變化次數(shù)對算法性能的影響。本章將以不同的加減邊數(shù)目進行實驗，對于加邊，本文隨機在圖中插入 100/1 000條原本不存在的邊；對于減邊，隨機在圖中刪除100/1 000條已存在的邊。用于對比的算法有META算法、UMMD算法。規(guī)定時間單位為秒，UMMD算法的更新時間精確到小數(shù)點后一位，Inf表示算法在 30 000秒內(nèi)沒有輸出更新結(jié)果。

各算法在圖增加 100條邊的更新時間如表3所示。觀察發(fā)現(xiàn)，在增加100條邊時，UMMD算法的更新效率比META算法快約2個數(shù)量級。在較大數(shù)據(jù)集Amazon-3、Amazon-5上，UMMD算法比 META算法分別快 234倍、238倍，在Reactome-3數(shù)據(jù)集上，UMMD算法比META算法快768倍，在Yeast-3、Instacart-3等較小數(shù)據(jù)集上，UMMD算法約快300倍。

表3 插入100條邊的更新時間Tab.3 the update time of inserting 100 edges

以上說明，UMMD算法的更新效率均比META算法更高。這主要是因為本文的更新策略可以縮小更新范圍，只處理與邊兩端頂點相連的極大motif團，而META算法是對全圖進行重新枚舉，存在冗余。

各算法在圖上刪除100條邊的更新時間如表4所示。在大部分?jǐn)?shù)據(jù)集上，UMMD算法的效率比META算法快2個數(shù)量級。在Yeast-3數(shù)據(jù)集上UMMD算法快327倍，在Instacart-5數(shù)據(jù)集上快249倍，在Amazon-5數(shù)據(jù)集上快781倍，在Reactome-5數(shù)據(jù)集上快54倍。

表4 刪除100條邊的更新時間Tab.4 the update time of deleting 100 edges

各算法在圖上插入1 000條邊的更新時間如表5所示。META算法在 Amazon-3、Amazon-4等多組數(shù)據(jù)集上無法在 Inf時間內(nèi)完成更新，但UMMD算法在這些數(shù)據(jù)集上的最長更新時間是Amazon-4的78.4 s。UMMD算法的更新效率在插入1 000次邊的條件下，比META算法約快3個數(shù)量級。在Yeast-3上UMMD算法快1364倍，在Instacart-3上快569倍。

表5 插入1 000條邊的更新時間Tab.5 the update time of inserting 1 000 edges

各算法在圖上刪除1 000條邊的更新時間如表6所示。觀察實驗結(jié)果，UMMD算法的更新效率比META算法快3個數(shù)量級左右。UMMD算法比META算法在Instacart-7上快1 910倍，在Amazon-7上快944倍。

表6 刪除1 000條邊的更新時間Tab.6 The update time of deleting 1000 edges

UMMD算法設(shè)計了合理有效的加邊、減邊策略，縮小了更新范圍，避免了枚舉操作。相比之下，META算法的更新方案，即重新枚舉極大motif團，冗余度較高，效率較低。因為枚舉是一個時間復(fù)雜度很高的操作，重新枚舉又存在大量冗余，隨著圖更新次數(shù)的增加，META算法更新極大 motif團的時間開銷會大幅增長。例如，在加減1 000次邊時，META算法要進行相應(yīng)次數(shù)的重新枚舉。但UMMD算法基于現(xiàn)有的極大motif團進行更新操作，算法延展性良好。圖更新次數(shù)變多時，UMMD算法的更新時間增加得較平緩。

4 結(jié)論

針對實際應(yīng)用中異構(gòu)信息網(wǎng)絡(luò)動態(tài)變化，且現(xiàn)有極大 motif團挖掘算法不支持高效更新的問題，本文研究面向動態(tài)異構(gòu)信息網(wǎng)絡(luò)的極大motif團挖掘算法。本文提出了新的加邊策略、減邊策略，并設(shè)計了相應(yīng)的算法。實驗結(jié)果表明，在12個異構(gòu)信息網(wǎng)絡(luò)數(shù)據(jù)集上，UMMD算法的更新效率比基礎(chǔ)算法META更加高效。例如，對圖增刪邊時，在 Amazon、Reactome、Yeast、Instacart等數(shù)據(jù)集上，UMMD算法比META算法約快2-3個數(shù)量級。