多樣性度量的Top-K區分子圖挖掘*

王章輝，趙宇海，王國仁，李 源

東北大學 計算機科學與工程學院，沈陽 110819

多樣性度量的Top-K區分子圖挖掘*

王章輝，趙宇海+，王國仁，李 源

東北大學 計算機科學與工程學院，沈陽 110819

圖挖掘；圖分類；子圖模式；區分子圖；多樣性

1 引言

圖數據是用來表示數據對象之間復雜關系的一種通用的數據結構，其廣泛應用于各項科學研究領域中[1-3]。比如，在藥物分子設計、蛋白質交互網絡、社交網絡等各項應用中，都使用圖數據結構進行數據的分析與處理。

在大量圖數據的應用中，經常使用不同的子圖模式對圖數據進行查詢、管理與分析。頻繁子圖模式可以用來構建高效的索引結構，幫助用戶查詢管理大量的圖數據[4-5]；顯著子圖模式可以幫助研究者對圖數據進行深入的分析[6-8]；在大量的圖數據中，區分子圖模式可以用來構建有效的分類模型，從而幫助研究者快速地實現對海量圖數據的分類[7]。總之，圖數據中隱含的圖模式信息可以幫助研究人員更好地分析、處理與理解這些圖結構信息。因此，從圖數據庫中進行圖模式的挖掘具有重要的研究意義和應用價值。

目前，已有的圖模式挖掘工作主要集中在頻繁子圖模式挖掘與顯著子圖模式挖掘兩方面。其中，頻繁子圖挖掘工作是基于用戶給定的頻繁度閾值，從圖數據庫中找到所有滿足支持度閾值的子圖模式，通常情況下，頻繁子圖挖掘會產生大量的子圖模式，不利于后續的分析與應用。而顯著子圖模式基于一定的度量方法（如統計方法等），對搜索空間使用采樣或者近似過濾的技術，從而減少目標輸出圖模式的數量[8]。

在圖分類的相關研究中，區分子圖作為一種具有顯著區分能力的圖模式，已有大量研究使用區分子圖來構建高效的分類模型[6-9]。通常的做法首先從圖數據庫中挖掘Top-K個具有最大區分能力的圖模式，而后利用這些圖模式構建圖分類模型。不幸的是，現有的區分子圖挖掘算法往往只關心目標模式所具有的區分能力的大小，并以此作為選擇是否輸出的唯一標準。這顯然會造成輸出結果中存在一定的冗余圖模式，不利于構建高效的圖分類器。

在進行Top-K圖模式的挖掘工作時，傳統方法往往根據目標圖模式度量值的大小進行排序，輸出前K個目標圖模式[10-11]。這些方法忽略了圖模式之間的相關性：其一，這些圖模式本身之間可能非常相似，當得到其中一個圖模式后，就會對相似的圖模式失去研究的意義，這與研究者希望得到多樣化的輸出結果相悖[12]；其二，在進行圖分類應用中，雖然這些圖模式的結構本身并不相似，但它們的支持集十分相似，從構建高效的圖分類器的角度來講，這將會造成大量的圖特征的過擬合現象，從而不利于構建高效的圖分類器。

為了克服傳統Top-K圖模式挖掘所面對的問題，本文提出了基于多樣性度量的Top-K區分子圖挖掘方法，其聯合了結構多樣性與支持集多樣性的雙重約束，避免了輸出模式之間的相似、相關問題。本文首先討論了結構相似性度量與支持集相似性度量，并結合二者給出了一個統一的多樣性度量標準，從而實現了挖掘結果之間的結構多樣性與支持集多樣性。為了高效地實現挖掘多樣性度量的Top-K區分子圖，本文提出了兩個算法Greedy-TopK與Leap-TopK。其中，Greedy-TopK算法采用兩步的增量貪婪方法挖掘K個區分子圖模式，即首先從圖數據庫中產生大量的區分子圖模式，而后從這些區分子圖中增量貪婪地得到K個多樣性區分子圖模式結果，當第一步得到的區分子圖模式數量巨大時，Greedy-TopK方法會面對效率低與可擴展性差的問題。Leap-TopK避免了Greedy-TopK分兩步方法的缺點，通過在挖掘過程中限制與結果集結構相似模式的擴展，實現了在搜索空間的跳躍搜索，從而避免了冗余模式的生成與計算工作，實現了在挖掘過程中增量地得到多樣性度量的Top-K區分子圖模式集合。顯然，因為Leap-TopK方法通過一遍挖掘就可以得到結果，從效率方面要明顯優于Greedy-TopK方法。

實驗結果表明，本文提出的多樣性度量的Top-K區分子圖挖掘在結果質量與構建分類器的準確度方面都遠遠優于傳統的區分子圖挖掘方法。同時，Leap-TopK方法比Greedy-TopK方法擁有較高的運行效率。

本文組織結構如下：第2章介紹了區分子圖挖掘的相關概念，并給出問題的形式化描述；第3章分別介紹兩個多樣性度量的Top-K區分子圖挖掘算法Greedy-TopK和Leap-TopK；第4章通過實驗對提出的算法進行有效性與高效性分析；第5章介紹相關工作；第6章對全文進行總結。

2 問題描述

本章首先介紹一些區分子圖挖掘相關概念，接下來對多樣性度量的Top-K區分子圖挖掘進行形式化定義。

2.1 基礎概念

本文主要考慮簡單的連通無向標簽圖，一個標簽圖G可以定義為一個四元組G=(V,E,Σ,F)。其中，V是頂點集合；E?V×V是邊集合；Σ是標簽集合；F:V?E→Σ是一個函數，用來對圖中頂點和邊分配相應的標簽。圖G中邊的集合可以用E(G)表示，|E(G)|則表示圖G中邊的數量。此外，一個圖還可以屬于唯一的類別。圖1給出了一個二類示例圖數據庫 D，其中G1、G2、G3和G4屬于正類圖集合，用 D+表示；G5、G6、G7和 G8屬于負類圖集合，用 D-表示。本文算法采用二類圖數據進行分析與研究，通過對算法進行簡單的修改，其同樣適用于多類圖數據庫。

Fig.1 Graph database D圖1 圖數據庫D

定義1（子圖同構）給定兩個圖G1=(V,E,Σ,F)和 G2=(V′,E′,Σ′,F′)，如果存在一個映射函數 f:V→V′和G2的一個子圖S，滿足 f是從G1到S的同構，則稱 f是一個從G1到G2的子圖同構，也稱G1子圖同構于G2。

如果存在一個從G1到G2的子圖同構，稱G1是G2的子圖，G2是G1的超圖或者G2支持G1，表示為G1?G2。

定義2（頻繁度）給定一個圖數據庫D=D++D-={G1,G2,…,Gn}和一個圖模式g，支持圖模式g的集合記作Cov(g)={Gi|g?Gi,Gi∈D}。圖模式 g的支持度為|Cov(g)|，表示為sup(g)；圖模式g在圖數據庫的頻繁度為|Cov(g)|/|D|，表示為 freq(g)。

同理，freq(g,D+)表示圖模式g在正類圖集合中的頻繁度；freq(g,D-)表示圖模式g在負類圖集合中的頻繁度。

定義3（區分子圖）給定一個子圖模式g，其在正類圖集合中的頻繁度遠遠高于其所在負類圖集合中的頻繁度，稱該子圖模式g為區分子圖模式，為表達方便，簡稱為區分子圖。

區分子圖g的區分能力函數可以用式（1）來計算，dscore(g)取值越大，說明其具有的區分能力越大。為了避免分母為0的現象，可以為圖數據庫中負類圖集合添加一個包含所有子圖模式的圖。

區分子圖挖掘問題就是從一個給定的圖數據庫中，按照給定的區分能力函數，把dscore值大于0的所有子圖模式都挖掘出來的過程。而對于Top-K區分子圖挖掘則是按照每個子圖的dscore值的大小進行排序，選擇取值最高的前K個子圖的挖掘過程。

2.2 問題定義

本節給出了多樣性度量的Top-K區分子圖挖掘問題。首先引入圖結構相似性與支持集相似性概念，接下來給出圖的相關性與多樣性描述，最后給出本文的全局目標。

定義4（圖結構相似性）給定兩個子圖模式g1與g2，其結構相似性表示兩個子圖模式在結構方面的相似度，可以用式（2）來表示。

兩個子圖的結構相似性可以用兩個子圖模式邊的Jaccard關聯系數來表示，該系數越大，說明這兩個子圖模式從結構上越相似。

定義5（圖支持集相似性）給定兩個子圖模式g1與g2，其支持集相似性表示兩個子圖模式在支持集方面的相似度，可以用式（3）來表示。

與圖的結構相似性類似，圖的支持集相似性同樣用它們的Jaccard關聯系數來表示，相對較大的關聯系數表明它們具有比較相似的支持集。

給定兩個子圖模式的結構相似性與支持集相似性的定義，就可以設計一個度量標準來對兩個子圖的相關性進行綜合度量。本文引入一個λ變量來綜合考慮兩個子圖模式在結構與支持集方面相似性的影響程度，兩個子圖模式g1與g2的相關性可以用式（4）來表示。

通常情況下，λ的取值為0.5，表示綜合考慮了兩個子圖模式的結構相似性與支持集相似性。本文如無特殊說明，λ取值為0.5。

給定一組子圖模式，顯然任意兩個子圖模式g1與g2的偏離程度（多樣性）可以用式（5）來表示。

通常情況下，兩個子圖的div偏離程度值越小，說明兩個子圖的相關性越小。當div值選擇為1時，說明這兩個子圖沒有任何的相關性。通常情況下，選擇一個小于1的實數，本文默認選擇div的取值為0.8。在給定的一組子圖模式中，任意兩個子圖模式的偏離值都大于0.8時，則說明它們之間具有較大的偏離程度，這樣的一組子圖模式可以稱為具有多樣性的子圖模式組。

問題定義：給定一個圖數據庫D，一個指定的K值與div值，多樣性度量的Top-K區分子圖挖掘問題是找到一個子圖模式集合S(1≤|S|≤K)，該子圖模式集合S滿足以下3條標準：

（1）1≤|S|≤K

（2）?g1?S,g2?S,div(g1,g2)≥div

（3）max∑g?Sdscore(g)

多樣性度量的Top-K區分子圖挖掘需要找到一組不多于K個子圖模式的結果集合，其中任意一個子圖模式都是一個區分子圖模式，并且要求結果集的區分能力之和是最大的；任意兩個子圖模式都是不相關的，是具有一定偏離度的；最大化一組子圖模式的區分能力和是一個NP-難問題，該問題可以通過最大覆蓋問題進行規約。

3 多樣性度量的Top-K區分子圖挖掘

既然多樣性度量的Top-K區分子圖挖掘問題是一個NP-難問題，因此需要設計近似算法或者啟發式算法進行求解。本文提出了兩個高效算法Greedy-TopK與Leap-TopK進行多樣性的Top-K區分子圖挖掘。其中Greedy-TopK方法采用兩階段的策略，而Leap-TopK方法通過在挖掘過程中限制與結果集結構相似模式的擴展，實現了在搜索空間的跳躍搜索，從而避免了冗余模式的生成與計算。

3.1 Greedy-TopK算法

Greedy-TopK算法采用的是兩階段的貪婪式搜索方法，如算法1所示。其首先需要通過某個區分子圖挖掘算法[13-14]從圖數據庫中挖掘出大量的區分子圖集合F；接下來按照每個區分子圖的區分能力從大到小進行排序；最后從區分子圖集合F中增量地選擇K個具有多樣性度量標準的區分子圖。

算法1 Greedy-TopK算法

輸入：圖數據庫D、K值與div值。

輸出：多樣性的最大化區分能力之和的K個區分子圖集合S。

1.挖掘大量區分能力大于0的區分子圖模式集合F；

2.對集合F中的區分子圖按照區分能力從大到小進行排序；

3.S=?；

4.if|S|＜Kdo

5.如果F為空集，則退出；

6.從F中選擇一個區分能力最大的子圖模式g，并把g從F中刪除；

7.如果g與S中的子圖模式滿足多樣性約束，并且可以增大S的區分能力之和；

8. S=S?{g}；

9.end if

10.輸出集合S。

在增量地選擇K個區分子圖時，既要考慮最大化結果集合S的區分能力之和，還要同時保證結果集合S中任意兩個區分子圖都是不相關的（即結果集具有多樣性）這兩個標準。

3.2 Leap-TopK算法

Greedy-TopK算法是一種兩階段算法，其實現首先需要產生大量具有區分能力的子圖模式。在第一階段產生的區分子圖數量規模不大的情況下，Greedy-TopK算法具有較高的效率。而當第一階段區分子圖挖掘算法產生大量的子圖模式時，使得Greedy-TopK算法在效率方面面對極大的挑戰，往往不能在合理的時間內完成算法，限制了該算法的可擴展性和可用性。針對Greedy-TopK算法存在的不足，本節提出了高效的Leap-TopK算法。

Leap-TopK算法是一個整體的算法，通過在挖掘過程中限制與當前結果集結構相似模式的擴展，實現了在搜索空間的跳躍式搜索，從而避免了冗余模式的生成與計算工作，實現了在挖掘過程中增量地得到多樣性度量的Top-K區分子圖模式集合。

Leap-TopK算法首先是一種圖模式的分支界限搜索算法，因此其需要采用一種具體的搜索框架，用來確保目標模式可以被搜索與發現，在搜索框架的基礎上，可以應用各種削減策略加速搜索過程的完成。DFS（depth first search）編碼樹搜索框架是一種高效的并得到廣泛應用的搜索框架[5]。在DFS編碼搜索樹中，可以使用最小DFS編碼實現圖同構問題的檢測。Leap-TopK算法在挖掘多樣性度量的Top-K區分子圖時，采用DFS編碼樹搜索框架進行子圖模式的搜索。

Leap-TopK算法維護一個大小為K的小頂堆作為結果集S，其中堆頂元素為堆中dscore值最小的區分子圖。在搜索子圖模式空間時，逐漸產生K個互不相關的區分子圖模式加入堆中；接下來計算新產生的子圖模式區分能力dscore值的大小，并與堆頂的區分子圖相比較，如果dscore值大于堆頂區分子圖的dscore值，則需要根據其與結果集中已有的區分子圖模式的相關性來決定是否添加并更新結果集S。

性質1在進行區分子圖模式空間搜索時，如果當前子圖模式g與結果集S中的任一子圖模式g′的圖結構相似性大于一定閾值，則可以直接跳過該子圖模式的計算過程，該閾值可以通過式（6）得到。

證明 當前子圖模式g如果要添加或者更新結果集S，則必須要求與結果集S內元素首先是不相關的，要求任意 div(g,g′)g′?S=1-corr(g,g′)g′?S≥div ，則corr(g,g′)g′?S≤1-div。而任意兩個子圖的相關性由式（4）可知，包含圖結構相似性與圖支持集相似性兩部分，因為圖支持集相似性是非負的，所以可以得出λsimS(g,g′)g′?S≤1-div，即要求兩個子圖模式的結構相似性

當進行區分子圖模式空間搜索時，每擴展生成一個新的子圖模式時，首先需要計算生成的子圖模式與當前結果集S中的子圖模式的圖結構相似性值，如果與結果集S中的子圖模式存在相關性大于式（6）這個閾值的情況，則可直接跳過該子圖模式的計算過程，用來加速搜索過程的完成。

Leap-TopK算法的技術集成在gSpan[5]的DFS編碼搜索框架中，完整算法如算法2所示。首先算法需要維護一個大小為K的小頂堆作為結果集S，初始化該集合為空。接下來遍歷搜索DFS編碼樹生成子圖模式，生成K個互不相關的區分子圖加入結果集S中，并按照它們的dscore值的大小調整堆。當產生一個新的子圖模式時，需要按照性質1判斷該子圖模式是否與結果集S中的子圖模式結構相似，從而判斷該子圖模式是否可以直接被削減。當該子圖與結果集S中的子圖模式結構并不相似時，則需要計算它的dscore值，如果dscore值大于堆頂元素的dscore值，并且滿足問題定義的第2條標準，則需要把該子圖模式加入并替換結果集，同時對新結果集合S進行堆更新。

算法2 Leap-TopK算法

輸入：圖數據庫D、K值與div值。

輸出：多樣性的最大化區分能力之和的K個區分子圖集合S。

1.大小為K的堆S=?；

2.搜索DFS編碼樹；

3.產生一個新的子圖模式g；

4.按照性質1與式（6）進行削減；

5.獲得一個與結果集S不相關的區分子圖g；

6.如果|S|≠K并且滿足問題定義的第2條標準，則S=S?{g}并調整結果集堆S；

7.如果g的dscore值大于集合S中堆頂元素的dscore值并且滿足問題定義的第2條標準，S=S?{g}并調整結果集堆S；

8.end搜索結束；

9.輸出集合S。

4 實驗結果及分析

本文進行了大量的實驗來考察提出算法的高效性和有效性，以及不同參數對算法的影響。本文算法采用基于標準模板庫（STL）的C++編程實現，實驗環境為聯想PC機器，3.5 GHz雙核處理器，4 GB內存，Window 7操作系統。

4.1 實驗數據集

本文采用了PubChem（http://pubhem.ncbi.nlm.nih.gov）數據庫上的一系列圖結構數據集作為實驗數據集。PubChem數據庫是一個維護良好的記錄生物活動的平臺，包括各種分子生物活性檢測、抗癌生物檢測等記錄。其中每個數據集根據其抗癌檢測可以分為活躍和不活躍兩類，表1對11個美國國家癌癥研究所（NCI）檢測數據集進行簡單介紹。

Table 1 Anti-cancer screen datasets表1 抗癌檢測數據集

從表1中可以看出，每一種癌癥檢測活躍化合物的數目都遠遠小于不活躍化合物的數目，比例大約只占5%。大量區分子圖挖掘算法[9,13-14]中實驗部分均采用等比例的數據集，因此對每一個癌癥檢測數據集都隨機選擇1 000個活躍化合物和1 000個不活躍化合物組成新的平衡數據集。這樣就重新組成11個規模為2 000的二類圖數據集。接下來的實驗中，均采用重新組合的數據集來度量本文算法的各項性能。

4.2 算法的效率

在進行算法效率分析實驗時，由于Greedy-TopK算法是一種兩階段算法，其首先需要由已有的區分子圖挖掘算法得到大量的區分子圖，才能從這些區分子圖中貪婪地選擇K個多樣性的區分子圖結果集。在Greedy-TopK算法生成大量區分子圖階段，本文采用高效率的 LTS（learning to search）算法[14]為Greedy-TopK算法生成大量的區分子圖，每次實驗中都默認產生1 000個區分子圖作為Greedy-TopK算法的候選區分子圖集合。本文實驗中所用到的參數變化及參數默認取值如表2所示，其中黑體數值代表相應參數默認的取值。

在進行算法的效率分析時，因為Greedy-TopK算法需要借助LTS算法生成的區分子圖集合才能完成，所以Greedy-TopK算法的運行時間包括LTS算法生成區分子圖集合的時間。首先比較了Greedy-TopK算法和Leap-TopK算法在檢測ID 1生成的平衡數據集上隨著K值變化的運行效率。從圖2中可以看出，Leap-TopK算法明顯優于Greedy-TopK算法，這得益于Leap-TopK算法的整體性和使用的結構相似性削減及跳躍式搜索，極大地縮減了算法的運行時間。同時，Greedy-TopK算法受K值變化的影響不大，這也說明了Greedy-TopK算法所需要的大量時間是在LTS算法產生大量區分子圖候選集合階段，而在貪婪查找K個多樣性的區分子圖時耗時隨K值變化影響不大。

Table 2 Experimental parameter values表2 實驗參數值

Fig.2 Runtime vs.varying K圖2 K值變化時的執行時間

從圖3中算法運行時間可以看出，Greedy-TopK算法與Leap-TopK算法的運行時間都隨著多樣性div值的變大而增加，即隨著對多樣性要求越嚴格（div值越大），兩種算法所需要的執行時間都呈現顯著增大的趨勢。

同時對在表1中對應數據集生成的11個新的平衡數據集進行運行效率的對比。對LTS算法生成的1 000個區分子圖按照區分能力大小排序，取前K個區分子圖的方式得到對應的LTS-TopK算法。從圖4中可以看出，Greedy-TopK算法在所有數據集上都具有較高的執行效率，而LTS-TopK算法與Greedy-TopK算法在絕大多數數據集上擁有相當的執行效率。

Fig.3 Runtime vs.varyingdiv圖3 div值變化時的執行時間

Fig.4 Runtime comparison in different datasets圖4 在不同數據集上的執行時間對比

4.3 算法的有效性

首先對本文提出的兩種挖掘多樣性度量的Top-K區分子圖算法所產生的輸出結果數量隨著div值的變化進行了實驗，其中K值的默認值為50，實驗結果是在11個數據集上得到的平均值。

從圖5中可以看出，隨著div值的增大，也就是隨著對多樣性度量標準的增加，Greedy-TopK算法不能很好地進行工作，也就是輸出的區分子圖模式數量遠遠低于指定的K值，尤其當div值選擇為1時，Greedy-TopK算法的輸出結果顯得更加糟糕。而Leap-TopK算法相比較Greedy-TopK算法有一定的改善，特別當div多樣性度量約束稍加放松時表現得更加明顯。

最后，從分類應用的角度出發，進一步考察本文算法的有效性。基于算法得到的K個區分子圖模式和支持向量機算法，可以構建相對應的圖分類器，對數據集中的測試集進行分類評價。本文使用參數C介于[2-10,210]的支持向量機LIBSVM（http://www.csie.ntu.edu.tw/～cjlin/libsvm/）構建圖分類器，通過構建的圖分類器在測試數據集上的分類精度對比，證明本文算法的有效性。為了避免單次實驗的偶然性，所有實驗均重復進行5次，并進行平均計算。

Fig.5 Result number vs.varyingdiv圖5 div值變化時結果數量

Table 3 AverageAUCscores表3 AUC平均得分

本文使用接收者操作特征（ROC）曲線下的面積（AUC）[6]作為分類精度的度量標準。AUC是一個介于0到1之間的實數，數值越大，說明分類器的分類精度越高，一個好的分類器產生的AUC值接近于1。

表3給出了使用3種算法產生圖模式利用SVM算法構建的圖分類器在不同數據集上的平均分類精度。從表3中可以看出，基于Greedy-TopK算法產生的區分子圖模式的平均分類精度基本與Leap-TopK算法相當，但二者都明顯優于LTS-TopK算法產生的分類精度。這就說明多樣性度量的區分子圖更加有利于構建高效的圖分類器。同時也說明Leap-TopK算法與Greedy-TopK算法所產生的結果集質量差異不大，并且具有十分接近的分類性能。

5 相關工作

近年來，區分子圖模式挖掘問題的相關研究一直備受眾多研究者的關注[6-7,9,13-14]。文獻[15]介紹了從頻繁子圖挖掘區分子圖模式的方法，雖然這種方法可以獲得所有的區分子圖模式，但是十分浪費時間。文獻[16]采用一定數量的對應組度量子圖模式的區分能力，可以獲得理論上的最優結果。文獻[7]使用相對高支持度閾值從小規模數據組中挖掘區分子圖模式。文獻[6]基于結構近似導致區分能力近似的假設，大幅度削減模式搜索空間，快速得到挖掘結果。以上所有區分子圖模式挖掘算法都未考慮挖掘結果之間可能出現高度相關的情況。而關于挖掘結果多樣性的研究越來越得到研究者的關注，大量優秀的研究成果表明，多樣性的挖掘可以提高結果的可分析性與可利用性[17-19]。目前為止，多樣性的區分子圖模式挖掘問題尚未得到廣泛的研究。

6 結束語

本文提出了多樣性度量的Top-K區分子圖挖掘問題，并給出兩個高效算法Greedy-TopK和Leap-TopK挖掘多樣性度量的Top-K區分子圖。實驗結果表明，Leap-TopK算法的效率明顯優于兩階段的Greedy-TopK算法。在可用性方面，利用Leap-TopK算法與Greedy-TopK算法挖掘結果構建的圖分類器具有相似的分類精度，且都優于傳統區分子圖挖掘算法產生的結果，從而證明了提出的多樣性度量Top-K區分子圖挖掘算法的有效性。

接下來的研究工作側重于處理大規模圖數據的分類問題，包括大規模數據處理框架設計，統計顯著性區分子圖挖掘方法等方面。

[1]Huan Jun,Wang Wei,Bandyopadhyay D,et al.Mining protein family specific residue packing patterns from proteinstructure graphs[C]//Proceedings of the 8th Annual International Conference on Research in Computational Molecular Biology,San Diego,USA,Mar 27-31,2004.New York:ACM,2004:308-315.

[2]Borgelt C,Berthold M R.Mining molecular fragments:finding relevant substructures of molecules[C]//Proceedings of the 2002 IEEE International Conference on Data Mining,Maebashi City,Japan,Dec 9-12,2002.Washington:IEEE Computer Society,2002:51-58.

[3]Deshpande M,Kuramochi M,Wale N,et al.Frequent substructure-based approaches for classifying chemical compounds[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(8):1036-1050.

[4]Kuramochi M,Karypis G.Frequent subgraph discovery[C]//Proceedings of the 2001 International Conference on Data Mining，San Jose,USA,Nov 29-Dec 2,2001.Washington:IEEE Computer Society,2001:313-320.

[5]Yan Xifeng,Han Jiawei.gSpan:graph-based substructure pattern mining[C]//Proceedings of the 2002 International Conference on Data Mining,Maebashi City,Japan,Dec 9-12,2002.Washington:IEEE Computer Society,2002:721-724.

[6]Yan Xifeng,Cheng Hong,Han Jiawei,et al.Mining significant graph patterns by leap search[C]//Proceedings of the 2008 International Conference on Management of Data,Vancouver,Canada,Jun 9-12,2008.New York:ACM,2008:433-444.

[7]Ranu S,Singh A K.Graphsig:a scalable approach to mining significant subgraphs in large graph databases[C]//Proceedings of the 2009 International Conference on Data Engineering,Shanghai,Mar 29-Apr 2,2009.Washington:IEEE Computer Society,2009:844-855.

[8]Hasan M A,Zaki M J.Output space sampling for graph patterns[J].Very Large Database Endowment,2009,2(1):730-741.

[9]Jin Ning,Young C,Wang Wei.Graph classification based on pattern co-occurrence[C]//Proceedings of the 18th Conference on Information and Knowledge Management,Hong Kong,China,Nov 2-6,2009.New York:ACM,2009:573-582.

[10]Zhu Yuanyuan,Qin Lu,Yu J X,et al.Finding top-k similar graphs in graph databases[C]//Proceedings of the 15th International Conference on Extending Database Technology,Berlin,Mar 27-30,2012.New York:ACM,2012:456-467.

[11]Ding Bolin,Yu J X,Wang Shan,et al.Finding top-k mincost connected trees in databases[C]//Proceedings of the 23rd International Conference on Data Engineering,Istanbul,Turkey,Apr 15-20,2007.Washington:IEEE Computer Society,2007:836-845.

[12]Fraternali P,Martinenghi D,Tagliasacchi M.Top-k bounded diversification[C]//Proceedings of the 2012 International Conference on Management of Data,Scottsdale,USA,May 20-24,2012.New York:ACM,2012:421-432.

[13]Jin Ning,Young C,Wang Wei.GAIA:graph classification using evolutionary computation[C]//Proceedings of the 2010 International Conference on Management of Data,Indianapolis,USA,Jun 6-10,2010.New York:ACM,2010:879-890.

[14]Jin Ning,Wang Wei.LTS:discriminative subgraph mining by learning from search history[C]//Proceedings of the 27th International Conference on Data Engineering,Hannover,Germany,Apr 11-16,2011.Washington:IEEE Computer Society,2011:207-218.

[15]Thoma M,Cheng H,Gretton A,et al.Discriminative frequent subgraph mining with optimality guarantees[J].StatisticalAnalysis and Data Mining,2010,3(5):302-318.

[16]Thoma M,Cheng Hong,Gretton A,et al.Near-optimal supervised feature selection among frequent subgraphs[C]//Proceedings of the 2009 International Conference on Data Mining,Sparks,USA,Apr 30-May 2,2009.Philadelphia,USA:SIAM,2009:1076-1087.

[17]Qin Lu,Yu J X,Chang Lijun.Diversifying top-k results[J].Proceedings of the VLDB Endowment,2012,5(11):1124-1135.

[18]Huang Xin,Cheng Hong,Li Ronghua,et al.Top-k structural diversity search in large networks[J].Proceedings of the VLDB Endowment,2013,6(13):1618-1629.

[19]Yuan Long,Qin Lu,Lin Xuemin,et al.Diversified top-k clique search[C]//Proceedings of the 31st International Conference on Data Engineering,Seoul,Apr 13-17,2015.Piscataway,USA:IEEE,2015:387-398.

WANG Zhanghui was born in 1985.He is a Ph.D.candidate at Northeastern University.His research interests include data mining and graph data analysis,etc.

王章輝（1985—），男，河南新鄉人，東北大學博士研究生，主要研究領域為數據挖掘，圖數據分析等。

ZHAO Yuhai was born in 1975.He is an associate professor at School of Computer Science and Engineering,Northeastern University,and the senior member of CCF.His research interests include data mining and bioinformatics,etc.

趙宇海（1975—），男，浙江舟山人，東北大學計算機科學與工程學院副教授，CCF高級會員，主要研究領域為數據挖掘，生物信息等。

WANG Guoren was born in 1966.He is a professor at School of Computer Science and Engineering,Northeastern University,and the senior member of CCF.His research interests include XML data management,massive data management,high-dimensional indexing and uncertain data management,etc.

王國仁（1966—），男，遼寧沈陽人，東北大學計算機科學與工程學院教授、博士生導師，CCF高級會員，主要研究領域為XML數據管理，海量數據管理，高維索引，不確定數據管理等。

LI Yuan was born in 1986.He is a Ph.D.candidate at Northeastern University.His research interests include data mining and bioinformatics,etc.

李源（1986—），男，遼寧沈陽人，東北大學博士研究生，主要研究領域為數據挖掘，生物信息等。

Top-K Discriminative Subgraph Mining Based on Diversity Measure*

WANG Zhanghui,ZHAO Yuhai+,WANG Guoren,LI Yuan
School of Computer Science and Engineering,Northeastern University,Shenyang 110819,China

Discriminative subgraph can be used to characterize complex graph structures and construct efficient graph classification model.This paper proposes the Top-K discriminative subgraph mining problem based on diversity measure.The diversity measure can be used to mine low correlation subgraph patterns in the mining result,which can enhance the usefulness of the discriminative subgraph patterns.By exploiting the graph structure similarity and support set similarity restraints,this paper introduces the criterion of graph pattern diversity measure.Then this paper proposes two efficient algorithms,Greedy-TopK and Leap-TopK,for the problem.Greedy-TopK algorithm employs two step strategies to incrementally and greedily mine K discriminative subgraphs.By limiting the structure similarity graph pattern extension in the discriminative subgraph mining process,Leap-TopK algorithm can leap the graph pattern searching space.Extensive experimental results demonstrate that Leap-TopK algorithm is more efficient than Greedy-TopK algorithm.Besides,when the mining results of discriminative subgraphs are considered,the classification accuracies of the two algorithms are almost the same.But they are all superior to the traditional discriminative subgraph mining algorithm in terms of usefulness.

graph mining;graph classification;subgraph pattern;discriminative subgraph;diversity

2016-07, Accepted 2017-03.

A

TP311

+Corresponding author:E-mail:zhaoyuhai@ise.neu.edu.cn

WANG Zhanghui,ZHAO Yuhai,WANG Guoren,et al.Top-K discriminative subgraph mining based on diversity measure.Journal of Frontiers of Computer Science and Technology,2017,11(9)：1379-1388.

10.3778/j.issn.1673-9418.1607016

*The National Natural Science Foundation of China under Grant Nos.61272182,61332014,61173029(國家自然科學基金);the Key Program of National Natural Science of China under Grant No.U1401256(國家自然科學重點項目);the Fundamental Research Funds for the Central Universities of China under Grant No.N150402002(中央高校基本科研業務費專項資金).

CNKI網絡優先出版: 2017-03-07, http://kns.cnki.net/kcms/detail/11.5602.TP.20170307.1405.008.html

摘 要：區分子圖可以用來描述復雜的圖數據結構和構建高效的圖分類模型。提出了多樣性度量的Top-K區分子圖挖掘問題，避免了挖掘結果之間出現高度相關的子圖模式，提高了區分子圖模式的可用性。通過組合圖結構相似性與支持集相似性約束，給出圖模式的多樣性度量標準。提出兩個高效算法Greedy-TopK和Leap-TopK挖掘多樣性度量的Top-K區分子圖。Greedy-TopK算法采用兩階段的增量式貪婪方法快速挖掘K個區分子圖模式。Leap-TopK算法通過在挖掘過程中限制擴展結構相似的圖模式，實現了跳躍搜索子圖模式空間。實驗結果表明，Leap-TopK算法的效率明顯優于Greedy-TopK算法；在可用性方面，利用Leap-TopK算法與Greedy-TopK算法挖掘結果構建的圖分類器具有相似的分類精度，且都優于傳統區分子圖挖掘算法產生的結果。