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

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

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

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

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

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

圖挖掘；圖分類；子圖模式；區(qū)分子圖；多樣性

1 引言

圖數(shù)據(jù)是用來表示數(shù)據(jù)對象之間復(fù)雜關(guān)系的一種通用的數(shù)據(jù)結(jié)構(gòu)，其廣泛應(yīng)用于各項科學(xué)研究領(lǐng)域中[1-3]。比如，在藥物分子設(shè)計、蛋白質(zhì)交互網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等各項應(yīng)用中，都使用圖數(shù)據(jù)結(jié)構(gòu)進行數(shù)據(jù)的分析與處理。

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

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

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

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

為了克服傳統(tǒng)Top-K圖模式挖掘所面對的問題，本文提出了基于多樣性度量的Top-K區(qū)分子圖挖掘方法，其聯(lián)合了結(jié)構(gòu)多樣性與支持集多樣性的雙重約束，避免了輸出模式之間的相似、相關(guān)問題。本文首先討論了結(jié)構(gòu)相似性度量與支持集相似性度量，并結(jié)合二者給出了一個統(tǒng)一的多樣性度量標(biāo)準(zhǔn)，從而實現(xiàn)了挖掘結(jié)果之間的結(jié)構(gòu)多樣性與支持集多樣性。為了高效地實現(xiàn)挖掘多樣性度量的Top-K區(qū)分子圖，本文提出了兩個算法Greedy-TopK與Leap-TopK。其中，Greedy-TopK算法采用兩步的增量貪婪方法挖掘K個區(qū)分子圖模式，即首先從圖數(shù)據(jù)庫中產(chǎn)生大量的區(qū)分子圖模式，而后從這些區(qū)分子圖中增量貪婪地得到K個多樣性區(qū)分子圖模式結(jié)果，當(dāng)?shù)谝徊降玫降膮^(qū)分子圖模式數(shù)量巨大時，Greedy-TopK方法會面對效率低與可擴展性差的問題。Leap-TopK避免了Greedy-TopK分兩步方法的缺點，通過在挖掘過程中限制與結(jié)果集結(jié)構(gòu)相似模式的擴展，實現(xiàn)了在搜索空間的跳躍搜索，從而避免了冗余模式的生成與計算工作，實現(xiàn)了在挖掘過程中增量地得到多樣性度量的Top-K區(qū)分子圖模式集合。顯然，因為Leap-TopK方法通過一遍挖掘就可以得到結(jié)果，從效率方面要明顯優(yōu)于Greedy-TopK方法。

實驗結(jié)果表明，本文提出的多樣性度量的Top-K區(qū)分子圖挖掘在結(jié)果質(zhì)量與構(gòu)建分類器的準(zhǔn)確度方面都遠遠優(yōu)于傳統(tǒng)的區(qū)分子圖挖掘方法。同時，Leap-TopK方法比Greedy-TopK方法擁有較高的運行效率。

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

2 問題描述

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

2.1 基礎(chǔ)概念

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

Fig.1 Graph database D圖1 圖數(shù)據(jù)庫D

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

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

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

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

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

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

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

2.2 問題定義

本節(jié)給出了多樣性度量的Top-K區(qū)分子圖挖掘問題。首先引入圖結(jié)構(gòu)相似性與支持集相似性概念，接下來給出圖的相關(guān)性與多樣性描述，最后給出本文的全局目標(biāo)。

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

兩個子圖的結(jié)構(gòu)相似性可以用兩個子圖模式邊的Jaccard關(guān)聯(lián)系數(shù)來表示，該系數(shù)越大，說明這兩個子圖模式從結(jié)構(gòu)上越相似。

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

與圖的結(jié)構(gòu)相似性類似，圖的支持集相似性同樣用它們的Jaccard關(guān)聯(lián)系數(shù)來表示，相對較大的關(guān)聯(lián)系數(shù)表明它們具有比較相似的支持集。

給定兩個子圖模式的結(jié)構(gòu)相似性與支持集相似性的定義，就可以設(shè)計一個度量標(biāo)準(zhǔn)來對兩個子圖的相關(guān)性進行綜合度量。本文引入一個λ變量來綜合考慮兩個子圖模式在結(jié)構(gòu)與支持集方面相似性的影響程度，兩個子圖模式g1與g2的相關(guān)性可以用式（4）來表示。

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

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

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

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

（1）1≤|S|≤K

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

（3）max∑g?Sdscore(g)

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

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

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

3.1 Greedy-TopK算法

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

算法1 Greedy-TopK算法

輸入：圖數(shù)據(jù)庫D、K值與div值。

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

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

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

3.S=?；

4.if|S|＜Kdo

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

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

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

8. S=S?{g}；

9.end if

10.輸出集合S。

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

3.2 Leap-TopK算法

Greedy-TopK算法是一種兩階段算法，其實現(xiàn)首先需要產(chǎn)生大量具有區(qū)分能力的子圖模式。在第一階段產(chǎn)生的區(qū)分子圖數(shù)量規(guī)模不大的情況下，Greedy-TopK算法具有較高的效率。而當(dāng)?shù)谝浑A段區(qū)分子圖挖掘算法產(chǎn)生大量的子圖模式時，使得Greedy-TopK算法在效率方面面對極大的挑戰(zhàn)，往往不能在合理的時間內(nèi)完成算法，限制了該算法的可擴展性和可用性。針對Greedy-TopK算法存在的不足，本節(jié)提出了高效的Leap-TopK算法。

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

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

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

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

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

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

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

算法2 Leap-TopK算法

輸入：圖數(shù)據(jù)庫D、K值與div值。

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

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

2.搜索DFS編碼樹；

3.產(chǎn)生一個新的子圖模式g；

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

5.獲得一個與結(jié)果集S不相關(guān)的區(qū)分子圖g；

6.如果|S|≠K并且滿足問題定義的第2條標(biāo)準(zhǔn)，則S=S?{g}并調(diào)整結(jié)果集堆S；

7.如果g的dscore值大于集合S中堆頂元素的dscore值并且滿足問題定義的第2條標(biāo)準(zhǔn)，S=S?{g}并調(diào)整結(jié)果集堆S；

8.end搜索結(jié)束；

9.輸出集合S。

4 實驗結(jié)果及分析

本文進行了大量的實驗來考察提出算法的高效性和有效性，以及不同參數(shù)對算法的影響。本文算法采用基于標(biāo)準(zhǔn)模板庫（STL）的C++編程實現(xiàn)，實驗環(huán)境為聯(lián)想PC機器，3.5 GHz雙核處理器，4 GB內(nèi)存，Window 7操作系統(tǒng)。

4.1 實驗數(shù)據(jù)集

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

Table 1 Anti-cancer screen datasets表1 抗癌檢測數(shù)據(jù)集

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

4.2 算法的效率

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

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

Table 2 Experimental parameter values表2 實驗參數(shù)值

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

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

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

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

Fig.4 Runtime comparison in different datasets圖4 在不同數(shù)據(jù)集上的執(zhí)行時間對比

4.3 算法的有效性

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

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

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

Fig.5 Result number vs.varyingdiv圖5 div值變化時結(jié)果數(shù)量

Table 3 AverageAUCscores表3 AUC平均得分

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

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

5 相關(guān)工作

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

6 結(jié)束語

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

接下來的研究工作側(cè)重于處理大規(guī)模圖數(shù)據(jù)的分類問題，包括大規(guī)模數(shù)據(jù)處理框架設(shè)計，統(tǒng)計顯著性區(qū)分子圖挖掘方法等方面。

[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—），男，河南新鄉(xiāng)人，東北大學(xué)博士研究生，主要研究領(lǐng)域為數(shù)據(jù)挖掘，圖數(shù)據(jù)分析等。

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—），男，浙江舟山人，東北大學(xué)計算機科學(xué)與工程學(xué)院副教授，CCF高級會員，主要研究領(lǐng)域為數(shù)據(jù)挖掘，生物信息等。

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—），男，遼寧沈陽人，東北大學(xué)計算機科學(xué)與工程學(xué)院教授、博士生導(dǎo)師，CCF高級會員，主要研究領(lǐng)域為XML數(shù)據(jù)管理，海量數(shù)據(jù)管理，高維索引，不確定數(shù)據(jù)管理等。

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—），男，遼寧沈陽人，東北大學(xué)博士研究生，主要研究領(lǐng)域為數(shù)據(jù)挖掘，生物信息等。

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(國家自然科學(xué)基金);the Key Program of National Natural Science of China under Grant No.U1401256(國家自然科學(xué)重點項目);the Fundamental Research Funds for the Central Universities of China under Grant No.N150402002(中央高校基本科研業(yè)務(wù)費專項資金).

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2017-03-07, http://kns.cnki.net/kcms/detail/11.5602.TP.20170307.1405.008.html

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