面向大圖的Top-Rank-K 頻繁模式挖掘算法

鄒杰軍,王 欣,石俊豪,蘭 卓,方 宇,張 翀,謝文波,沈玲珍

（西南石油大學計算機科學學院，成都，610500）

頻繁模式挖掘（Frequent Pattern Mining，FPM）是知識發現和圖挖掘的重要問題之一，其目的是從給定數據集中挖掘支持度不小于用戶指定閾值的所有模式.FPM 主要有兩種不同的設定：基于圖集的FPM 和基于單個大圖的FPM.近年來，后者廣泛應用于社交網絡［1］、計算機化學［2］、生物信息學［3］、網絡安全［4］等領域，備受關注.現有的方法大多遵循組合模式的枚舉范式，然而在某些實際應用場景，如社交網絡中，枚舉所有頻繁模式的代價是昂貴且非必要的［5］.

在頻繁模式挖掘任務中，頻繁模式被定義為支持度不小于給定閾值的模式，因此支持度閾值是頻繁模式挖掘任務中的一個重要輸入參數.通常模式的支持度度量應滿足反單調性，即父模式的支持度不小于子模式的支持度.基于該特性，挖掘算法能有效地進行搜索空間的剪枝，然而，在算法運行之初，確定合適的支持度閾值難度較大.

例1圖1a 展示了一個社交網絡圖G，其中每個頂點表示一個具有特定ID 和職稱的用戶（如項目經理（PM）、數據庫管理員（DBA）、程序員（PRG）、業務分析師（BA）和軟件測試人員（ST））.圖中的邊表示人與人之間的好友關系.特別地，頂點v1～v5被分組在一起，表示他們具有相同的職稱BA；類似地，頂點v16～v30表示他們具有的相同職稱DBA.兩個不同分組間的聯系表明，組內用戶與鄰接組內的任意用戶都存在好友關系.在圖G上執行不同支持度閾值下的FPM任務時，頻繁模式的數量存在顯著差別.例如，當θ=5 時，可挖掘出Q1到Q100共計100 個模式（如圖1b 所示）.值得注意的是，如果Q1～Q100全部被返回，那么用戶將不得不面對大量的頻繁模式，這些頻繁模式不僅包含“冗余”信息，而且計算代價昂貴.與此同時，當θ=15 時，僅僅挖掘出七個模式(Q1，…，Q7).因此，根據實際應用需求，明確合適的支持度閾值往往較為困難.

上述例子表明：（1）支持度閾值設置過大會導致返回的模式數量過少，且模式中單邊模式的占比過大，實際應用價值偏低；（2）一個過小的支持度閾值會返回過多的模式，使用戶難以找到滿意的模式，還會增加算法的搜索空間和計算開銷，嚴重的甚至可能導致程序因內存溢出而崩潰.

此外，現有的Top-Rank-K 頻繁模式挖掘算法（如NTK［6］和iNTK［7］）主要應用于事務型數據庫的頻繁項集挖掘.隨著圖數據對描述關系的優勢日漸顯現，頻繁模式挖掘的研究逐漸擴展到包含圖結構數據的領域，已提出多種針對Top-K 頻繁模式 挖掘的算法（如PBSM［8］，Resling［9］和Dminer［10］），但它們都需要預先設定一個初始支持度閾值，并且僅用模式自身的支持度來衡量模式的價值，導致挖掘結果偏向小而頻繁的模式.

以上觀察激發了本文對單一大圖上的Top-Rank-K 頻繁模式挖掘問題的探究，即在無初始支持度閾值的情況下高效地挖掘排名前k的頻繁模式.為此，本文需要解決以下兩個關鍵問題.

（1）設計一個興趣度指標來對模式進行排名，該指標在理想狀態下能同時考慮模式的支持度和模式的大小.

（2）設計一種有效的算法，在沒有初始支持度閾值輸入時也能高效地進行頻繁模式挖掘.

本文的具體貢獻如下.

（1）提出一種基于模式大小和模式支持度的模式興趣度度量指標.

（2）提出一種無須設置初始支持度閾值的Top-Rank-K 模式挖掘算法ItrMiner，只須輸入圖G和一個整數k就能返回興趣度排名在前k名的模式.對無初始支持度閾值可能導致的大量低興趣度模式問題，ItrMiner 采用興趣度優先的樹模式識別策略和一種新穎的模式擴展約束條件，有效減少了低興趣度候選模式的生成，顯著提升了挖掘效率.

（3）在真實圖和人工合成圖數據集上進行了廣泛的實驗研究，驗證了ItrMiner 的性能.首先，ItrMiner 模式的擴展約束有效性較高，和無擴展約束優化的ItrMinernopt相比，效率提升最高可達9.5 倍；其次，與Grami 算法進行了對比，驗證了ItrMiner 的有效性和可行性，為傳統頻繁模式挖掘提供了一種有價值的替代方案；另外，ItrMiner的執行效率和可擴展性表現良好，尤其在稠密的數據集上，其時間開銷僅為基線算法Top-K Graph Miner（TKG）的13.2%.

1 相關工作

Top-Rank-K 頻繁模式挖掘最早由Deng and Fang［11］提出，以模式的支持度作為排名的參考，用于在事務型數據庫中尋找排名前k的頻繁項集.還有大量集中在頻繁項集上的Top-Rank-K模式挖掘研究，主要分兩個方向擴展：第一種是算法性能優化，如NTK［6］，iNTK［7］和TK-FIN 算法［12］等；第二種是橫向功能上的擴展，例如從不確定數據中挖掘Top-Rank-K 模式的UFAE 算法［13］和用于挖掘帶權重的頻繁項集等的TFWIN+算法［14］.

圖數據在描述數據關系方面的卓越表現日益凸顯，頻繁模式挖掘的研究方向逐漸從傳統的事務型數據庫擴展到包含圖結構數據的領域，單一大圖數據的頻繁模式挖掘問題受到了眾多學者的關注.其中，Sigram［15］和Grami［16］是兩種代表性算法.Sigram 采用支持度大于指定閾值的頂點來擴展模式并生成候選模式，通過搜索候選模式的匹配來計算其支持度，然而，采用存儲模式匹配來計算支持度的方式會消耗大量內存.為了解決這一問題，Elseidy et al［16］提出Grami 算法，將子圖同構查找問題轉換為約束滿足問題CSP（Constraint Satisfaction Problem），通過MNI（Minimum Image）支持度規則，找到足夠的證據來證明該模式是頻繁的部分匹配.

隨著圖結構數據規模的增大，為了提高在單圖上進行頻繁模式挖掘的效率，Arabesque［17］，Fractal［18］和ScaleMine［19］等分布式挖掘算法被提出.其中，Arabesque 采 用BFS（Breadth First Search）策略來識別頻繁模式，導致每個工作站點需要生成并存儲大量的中間狀態，內存開銷較大.為了解決該問題，Fractal 采用DFS（Depth First Search）以及模式重復生成策略，有效降低了內存消耗，并且使用局部感知的任務竊取策略來實現動態負載均衡.另一個分布式系統Scale-Mine 將模式挖掘分成近似挖掘和精確挖掘兩個階段工作，通過近似挖掘的結果來指導精確挖掘階段的負載分配，實現更好的負載平衡，提升了算法的執行效率.和上述分布式算法相比，G-Miner［20］采用一種細粒度的圖劃分方法來保證分割子圖的局部性，并通過任務竊取策略來實現負載均衡.該方法不再需要每個工作站點都加載完整的輸入圖，可以有效地處理數據規模超過單機內存的超大單圖.此外，與G-Miner 采用的圖劃分方法不同，李玲等［21］提出一種基于垂直分解框架的分布式框架，并設計了Desu-FSM 算法，旨在挖掘大規模圖中的封閉子圖.

實際應用中用戶通常只關注最感興趣的前k個模式，因此，Top-K 模式挖掘的重要性逐漸顯現.例如，為了降低枚舉成本，Chen et al［8］引入基于等價頂點的圖壓縮技術對數據進行預處理來挖掘前k個最頻繁的子圖.為了滿足用戶對不同興趣度指標的需求，Natarajan and Ranu［9］開發了一個名為Resling 的通用框架，通過基于隨機游走的算法對模式進行多樣性排名來挖掘前k個最具代表性的頻繁模式.與Resling 類似，Wang et al［10］重新定義模式的多樣性，設計了一種多樣性挖掘前k個頻繁模式的Dminer 算法.為了進一步提高算法的執行效率，AprTopK［22］采用逐層擴展策略，近似挖掘滿足支持度閾值的前k個最大頻繁模式.

對于頻繁模式挖掘，還有部分工作專注于避免支持度閾值設置的困擾，提出了無須設置初始支持度閾值的算法.其中，TGP［23］采用名為Lexicographical Pattern Net 的結構來存儲所有子圖的DFS 代碼，并利用該結構來挖掘前k個最頻繁的封閉子圖，但由于TGP 需要顯示生成所有模式，執行效率不高.為了解決這一問題，Saha and Al Hasan［24］提出一種基于MCMC（Markov Chain Monte Carlo）抽樣的方法FS3來挖掘概率意義上的前k個最頻繁的子圖.FS3通過采樣再挖掘的方式，有效地提升了算法的運行效率，但無法準確發現所有的模式.因此，Fournier-Viger et al［25］提出一種采用動態規劃策略實現快速提升支持度閾值的精確挖掘算法TKG.此外，FastPat［26］引入元索引的概念，通過預先指定核心模式，在知識圖譜中挖掘出前k個支持度最大的頻繁模式.

雖然現有方法可以識別滿足支持度閾值的全部或前k個頻繁模式以及通過一些約束條件在不設定支持度閾值的情況下識別前k個最頻繁的模式，但它們都沒能有效解決在不設置支持度閾值的情況下綜合考慮模式的大小和支持度以挖掘用戶更滿意的模式的問題.本文提出基于圖數據的新型頻繁模式挖掘方法，實現了在無支持度閾值的情況下準確地挖掘興趣度排名在前k的頻繁模式.該方法引入一項結合模式大小和支持度的“興趣度”函數來評估模式的價值，改進了僅使用支持度度量模式的傳統方法.此外，為了提高挖掘效率，還設計了一項有效的剪枝過濾技術.

2 基本概念

本文研究的數據集包含帶標簽的圖，每個點都有一個標簽來描述其屬性.首先回顧圖、模式和模式匹配的概念，再對頻繁模式挖掘進行形式化描述.

2.1 圖、模式與模式匹配

定義1 圖和子圖給定三元組標簽圖G=(V，E，L)，其中，V是頂點集合；E?V×V是邊集合；V中每個節點v攜帶L(v)，表示其標簽或內容.

圖G的子圖Gs表示為Gs=(Vs，Es，Ls)的 三元組，其中，Vs?V，Es?E，針對每個節點v∈Vs，都有Ls(v)=L(v)，稱圖Gs為圖G的一個子圖.

定義2 模式和子模式給定一個模式Q=(Vp，Ep，fv)，其中，Vp和Ep分別是節點和邊的集合；針對每一個u∈Vp，fv(u)被定義為′A=a′形式的原子公式的連結，A表示節點u的一個屬性，a是屬性A對應的值.通過一次模式擴展，可以得到模式Q′=(Vp′，Ep′，f v′)，其中，Q′?Q.Q′比模式Q多一條邊和一個頂點（也可能只多一條邊）.同時，模式Q稱為父模式，模式Q′稱為子模式.

定義3 模式匹配給定圖G=(V，E，L)和模式Q=(Vp，Ep，fv)，如果G中節點v滿足Q中節點u的查詢條件，即對于每一個fv(u)中的原子公式A=a，在L(v)中都有對應的屬性A，使得v.A=a，則稱v是u的匹配，并用v～u表示兩者間的匹配關系.

圖G中模式Q的匹配是一個從Q到G的同構映射f，使得：

（1）對于每個節點u∈Vp，fv(u)～L(f(u))；

（2）對于每個模式邊(u，u′) ∈Ep當且僅當(f(u)，f(u′))∈E.

這樣，當模式Q與G的子圖Gs=(Vs，Es，Ls)存在同構映射關系f時，Gs為Q在G中的一個匹配.

模式Q在G中的匹配通常不止一個，本文使用M(Q，G)表示模式Q在圖G中的所有匹配.

例2圖2a的圖Ga中存在一個具有點集{BA，PM，DBA，ST}的模式Q，能找到八個匹配，分別為Gs-1到Gs-（8圖2c）.每個匹配的頂點與模式Q的點相互對應.例如Gs-1中的點集{v2，v5，v9，v12}分別對應Q的點集{BA，PM，DBA，ST}.

圖2 樣本圖、模式、模式定義域及其模式匹配Fig2 .A sample of graph，patterns，domains and their matches

定義4 前向擴展和后向擴展給定模式Q，可以通過從其節點u對Q進行深度優先搜索來構建其DFS 樹Tq，稱Tq中的邊為前向邊，稱Q中的其余邊為后向邊.因此，前向擴展通過引入一條從Q中的現有頂點到新引入的頂點的新邊來擴大Q，擴展出來的模式形如樹狀結構，被稱為樹模式.后向擴展從Q的兩個現有頂點引入新邊，擴展出來的模式，其結構中包含回邊，不再是樹狀結構，被稱為非樹模式.

例3如圖2b 所示，θ=15 時存在三個模式Q1，Q2和Q7.Q2可以通過前向擴展從具有邊集{(DBA，PRG)}的模式Q1生成，該過程增加了一個頂點ST 和一條邊(PRG，ST)；Q2還可以通 過后向擴展，在不增加節點的情況下，增加一條新邊(DAB，ST)，生成新的模式Q7.

定義5 模式大小給定模式Q=(Vp，Ep，fv)，其模式大小定義為 |Q|=|Ep|，其中，|Ep|為模式的邊數.

不少工作中，模式的大小被定義為點集與邊集大小的和，而本文對此進行調整，主要因為模式無論通過前向還是后向擴展，其邊數都會增加1，而點數在后向擴展時保持不變，故采用邊集的數量來描述模式大小的增長會更平滑.因此，本文將模式大小 |Q|定義為 |Q|=|Ep|.

2.2 頻繁模式挖掘

定義6 支持度給定模式Q和圖G，支持度表示模式Q在圖G中對應匹配出現的頻率，記為Sup(Q，G).

基于圖像的最小支持度［27］是一個廣泛使用的度量標準，它保證了模式擴展的反單調性.本文用其來計算模式的支持度，其定義如下所示：

其中，P(u)表示模式中頂點u在圖G上的匹配去重后的節點集合.

例4如圖2b 所示，模式Q在圖G上的匹配去重之后得到的結果為：

定義7 反單調性給定圖G的任意兩個模式Q，Q′，如 果Q′是Q的子模式，則一定存在Sup(Q，G)≥Sup(Q′，G)，即子模式頻繁，父模式也一定頻繁，稱模式具有反單調性.

定義8 域給定圖G和具有節點集Vp的模式Q，Q的域(Domain)用D(Q，G)表示.模式Q的域將Q在G中 的所有 匹配M(Q，G)重新組 織為一個表，表的列頭和列體分別對應模式節點ui(ui∈Vp)和它的映射P(ui).

例5如圖2c 所示，模式Q在圖Ga中的所有匹配M(Q，Ga)包括Gs-1到Gs-8，共計八個匹配，而Q的域D(Q，Ga)（圖2b）是一個比M(Q，Ga)更緊湊的數據結構.

定義9 頻繁模式挖掘給定圖G和支持度閾值θ，頻繁模式挖掘旨在從圖G中發現一個頻繁模式集合S，S中的任意模式Q的支持度滿足Sup(Q，G)≥θ.

表1 給出了本文中重要的符號及其含義.

表1 本文使用的符號Table 1 Summary of notation

3 Top-Rank-K 模式挖掘算法

3.1 問題描述下面給出Top-Rank-K 模式挖掘問題的形式化描述.

輸入：單個大圖G和一個整數k.

輸出：一個從G中發現的頻繁模式集合Sk，該集合中的任意模式Q的rank，即R(Q)滿足R(Q)≤k.

這里，R(Q)是模式Q的興趣度排名，具體定義如下所示：

其中，I是一個由所有模式的不同興趣度組成的集合.模式Q的R(Q)被定義為興趣度大于等于Itr(Q)的不同興趣度的數量.特別地，當兩個模式的興趣度相同時，它們的rank 相同.模式Q的興趣度的定義如下所示：

其中，Sup(Q，G)為模式Q的支持度，是一個由系數α(α＞1)和模式大小 |Q|共同決定的衰減系數.

直觀上，Top-Rank-K 模式挖掘任務旨在從圖G中找到所有rank 不大于k的模式.

在設計模式興趣度時，從應用出發，考慮兩個因素：（1）模式的支持度越大，興趣度越高；（2）模式的規模越大，興趣度越高.然而，隨著模式規模的增長，支持度必然會單調遞減.對此，基于削減小模式支持度收益的思想，本文設計了如式（3）所示的興趣度度量函數，在考慮模式大小的同時，盡可能降低不具備反單調性的影響，使基于傳統支持度剪枝的效果可以有效地保留.

本文中參數α的值預設為2.0.計算可得α=2.0，模 式大小為1 時（單邊模式），Itr(Q)≈Sup(Q，G)×0.67；模式大小趨近無窮大時，Itr(Q)≈Sup(Q，G).因此，本文選擇α=2.0，在平衡模式大小和支持度兩方面具有一定優勢，可以弱化小模式支持度過大以及大模式支持度偏低帶來的影響，這個選擇既符合實際需求，又易于計算.后文的實驗部分將更深入地討論參數α對算法性能的影響.

例6圖1b 中的兩個模式Q7和Q100在圖G中（圖1a）的支持度分別為15 和5.通過式（3）計算可得Itr(Q7)=13.35，Itr(Q100)=4.95.由 于Itr(Q7)＞Itr(Q100)，因此，對于用戶，Q7被認為是更有價值和更有趣的模式.

命題1Top-Rank-K 模式挖掘是NP-hard問題.

證明子圖同構（Subgraph Isomorphism，SISO）可以檢測圖G中是否存在子圖與Gs同構.該問題被嵌入Top-Rank-K 模式挖掘問題，則Top-Rank-K 模式挖掘問題至少與SISO 問題具有相同的難度，由于SISO 是一個NP-hard 問題［28］，因此Top-Rank-K 模式挖掘問題也是NP-hard 問題.

由于算法無須輸入支持度閾值，故其無法直接用支持度閾值進行搜索空間的剪枝.另一方面，直接對整個搜索空間進行窮舉顯然不可取.為了糾正這一點，算法采用興趣度優先的樹模式識別方法并結合嚴格的模式擴展約束來降低不必要的搜索開銷，具體將在下文中詳細介紹.

3.2 整體框架如算法1 中的偽代碼所示，ItrMiner 以圖G和整數k為輸入，返回一組rank 不大于k的模式作為輸出.挖掘過程中ItrMiner 執行三項主要任務：初始化（第1～4 行）、興趣度引導的樹模式識別（第5～15 行）和非樹模式挖掘（第16 和17 行）.所有模式都被組織在一個動態維護的有向樹T（稱為編碼樹）中，T的增長遵循自上而下的方式，從“種子”模式開始（單邊模式）.

3.3 初始化算法1 一共初始化了Sc,Sk,L,T，sEdges和minItr六個參數.首先，在第1 行，初始化兩個空的優先隊列Sc和Sk以及用來存儲中間過程生成的候選模式的空集合L；在第2 行，創建一個空的編碼樹T；在第3 行，初始化圖G中的所有單邊sEdges，并將最小興趣度minItr設定為1.Sc存儲待擴展的候選模式并以支持度作為比較條件，模式支持度越高，排名越靠前.Sk存放迭代的Top-Rank-K 模式，算法結束時最終返回的結果為Sk中的模式，并以模式的興趣度為比較條件，興趣度越低，排名越靠前.值得注意的是，Sk的大小由不同興趣度的個數決定且最大值為k，當Sk超過k時，移除隊首元素（最小值）.然后，在第4 行，ItrMiner 進行單邊初始化，計算每個單邊模式（即“種子”模式）的支持度和興趣度，按它們各自的大小依次加入Sc和Sk，并添加對應種子模式的節點到編碼樹T.注意，在這個過程中，若Sk的大小達到k，則用Sk中最小的興趣度更新minItr.

例7圖1a所示的社交網絡上圖G上，ItrMiner首先識別出八個“種子”模式Q1～Q（8如圖3 所示），它們的興趣度如表2 所示.根據它們各自的興趣度將其分別插入Sc和Sk(k=4).由于k=4，Q5和Q8的rank 排名分別為5 和6，因此不插入Sk.模式Q2，Q3和Q7的興趣度最低，為6.70，放置于Sk的隊首；模式Q6的興趣度最高，為13.40，放置于Sk的隊尾.Sc中Q6的支持度最高，為20，放置于隊首；Q2的支持度最低，為10，放置于隊尾.值得注意的是，Q5和Q8的支持度小于Sk當前的最小興趣度6.70，因此不插入Sc，因為后續無論怎么擴展，它們的模式的興趣度都不會大于6.70.

表2 種子模式的支持度，興趣度和rank 排名Table 2 Support，interestingness and ranking of seed patterns

圖3 編碼樹生成和隊列更新Fig.3 Coding tree generation and queue update

3.4 興趣度優先的樹模式識別在這一階段，ItrMiner 以興趣度為優先級，通過函數FwTree-Gen 擴展當前支持度最高的模式，以盡快提升最小興趣度minItr并剪掉低興趣度的模式.具體地，當Sc≠?時，算法1 第6 行不斷地從Sc中彈出頂部元素（當前支持度最大的模式）Q，并執行以下操作：（1）算法1 第7 行和第8 行，驗證Q的支持度，如果Sup(Q，G)＜minItr，則結束while 循環，因為后續的模式無論怎么擴展，其興趣度都小于minItr；（2）算法1 第9 行調用函數FwTreeGen 對模式Q進行前向擴展，生成一組候選模式L，在這個過程中，每個新模式的域會基于模式Q的域進行更新；（3）對于L中的每個候選模式Qe，算法1第10～13 行檢查Qe是否出現過，如果它是一個新模式并滿足Itr(Q)≥minItr，則將Qe添加到Sk和Sc，并通過Sc來更新T.此外，算法1 第14～15 行對Sk的大小進行驗證，如果Sk≥k，則更新minItr.

例8如圖3 所示，將八個種子模式Q1～Q8存儲進編碼樹，然后ItrMiner 以興趣度優先的樹模式識別方式逐一調用函數FwTreeGen 前向擴展編碼樹T上的模式來不斷地生成候選模式.例如，模式Q6的支持度最高，先從Sc出隊，由于擴展約束的限制，Q6不能擴展（詳見4.6）.接著，Q1出隊，通過前向擴展得到模式Q11，然后計算Q11的支持度和興趣度，將其分別插入Sk(k=4)和Sc.由圖可見，經過步驟①，Sk(k=4)的興趣度集合由 (13.40，10.72，10.05，6.70)更新為(13.40，12.80，1 0.72，10.05)，刪除了6.70，增添了Q11的興趣度12.80.對于Sc，Q6和Q1出隊，新模式Q11加入隊列并按照其支持度大小放置在相應的位置.值得注意的是，Q2，Q3和Q7的支持度（10）小于當前Sk(k=4)的最小興趣度10.05，因此更新Sc，將它們刪除.

3.5 非樹模式挖掘非樹模式挖掘，即后向擴展，是在當前模式的基礎上繼續增添新的邊.算法2 展示了后向擴展的具體細節.

編碼樹T構建完成后，ItrMiner 調用函數BackSearch 來挖掘非樹模式.具體地，Back-Search 首先初始化一個整型參數h=1，然后迭代地生成非樹模式，模式生成過程遵循自頂向下的方式，從位于T頂層的編碼樹開始.每一輪迭代中，算法2 第4～7 行，BackSearch 在T的h層優先選擇支持度最大的模式Qhi，并利用BwTreeGen生成一組候選模式L.這個過程中會優先比較Sup(Qhi，G)與minItr的大小，如果Sup(Qhi，G)＜minItr，則終止當層循環.值得注意的是，BwTreeGen 的工作原理類似FwTreeGen，但僅通過后向擴展方式來擴展Qhi.算法2 第9～12 行對L中的每個候選模式Qe進行驗證，如果是未被擴展出的模式并且其興趣度大于等于minItr，則將Qe加入Sk并更新minItr.

例9當樹模式識別完成之后，BackSearch調用函數BwTreeGen 后向擴展編碼樹T上的模式來不斷地生成候選模式，從而實現非樹模式的挖掘.具體地，由于編碼樹的頂層節點都是單邊模式，不能進行后向擴展，故BackSearch 直接從第二層開始遍歷.如圖3 所示，Q11，Q41和Q42都是第二層模式，Q11的支持度最高，因此首先擴展Q11，通過函數BwTreeGen 擴展得出環形模式Q11-1，BackSearch 計算其支持度和興趣度，將其分別插入Sk(k=4)和Sc，再繼續擴展Q41和Q42.由于其擴展結果與Q11-1相同，因此當前Sk存放的即為最終結果，BackSearch 將其返回.

3.6 模式擴展約束規則為了解決傳統的使用頻繁單邊進行擴展的方法在Top-Rank-K 模式挖掘中產生大量低興趣度模式的問題，提出模式擴展約束規則，要求每個模式都有一個擴展約束支持度Q.cst，并在單邊e對模式進行擴展時需要滿足Q.cst≤sup(Qe，G)，即單邊對應的模式支持度大于等于被擴展模式的約束支持度.值得注意的是，“種子”模式的擴展約束支持度為其支持度本身，而子模式繼承了父模式的擴展約束支持度.

命題2有約束的模式擴展不會錯過任何一個模式的生成.

證明給定圖G的所有單邊模式e1，e2，…，en，其中，sup(e1，G)≥sup(e2，G)≥…≥sup(en，G).給定任意模式Q=(V，E(ei，ej，…，ek)，f)，i＜j＜k.由于模式擴展的約束，模式Q無法由單邊模式ei，ej擴展而得，但其總能被擴展約束的最小的ek擴展出來.因此，有約束的模式擴展不會錯過任何一個模式的生成.

例10如圖3 所示，Sc隊首元素Q6出隊，通過模式擴展約束規則可知Q6.cst=20.由于沒有其余單邊模式的支持度大于等于20，因此Q6無法進行擴展.緊接著Q1出隊，因為Q1.cst＜sup(Q6，G)，所以Q1通過Q6擴展生成模式Q11.圖4 所示為無約束的模式擴展編碼樹.與有約束的模式擴展相比，在結果相同的情況下，無約束的模式擴展產生了25 個冗余模式.最后經過檢驗，這些模式均被證實為不頻繁（其模式興趣度小于當前Sk的最小興趣度）.

圖4 未帶約束的模式擴展編碼樹Fig.4 Pattern expansion coding tree without constraints

上述例子表明，在結果相同的情況下，采用帶有約束的模式擴展策略，搜索空間會更小，算法的執行效率更高.下文將詳細探討這種優化對算法性能的影響.

4 實驗

為了全面評估ItrMiner 算法的性能進行了實驗研究，并與基線算法進行比較.實驗涵蓋了真實圖數據和合成圖數據，考察算法的運行時間、內存消耗和可擴展性.每個實驗重復五次，并對結果進行平均處理.

測試環境為一臺配備2.5 GHz 48 核CPU 和192 GB RAM 的服務器，操作系統為CentOS Linux release 7.8，實驗代碼均用java 編寫.

4.1 實驗數據使用如表3 所示的六個真實數據集.

表3 實驗使用的數據集Table 3 Datasets used in experiments

（1）Amazon［29］是產品聯合采購網絡，包含0.41×106個點和3.35×106條邊.當兩個商品a和b被客戶同時購買的頻次達到一定數量時，就會形成邊(a，b).

（2）MiCo［16］是由微軟合作作者信息構建的網絡，包含0.1×106個點和1.08×106條邊.每個節點代表作者，每條邊代表兩位作者之間的合作關系.

（3）YouTube［30］是由來自YouTube 平臺的視頻及其相關視頻構建的網絡，包含0.15×106個點和1.05×106條邊.每個節點代表一個用戶或頻道，每條邊代表兩個節點之間的關系.

（4）Twitter［31］是來自Twitter 平臺的社交網絡，包含八萬多個點和1.76×106條邊.每個節點代表一個Twitter 用戶，每條邊代表兩個用戶的關注.由于原始圖數據沒有標簽，因此隨機地對節點添加標簽，標簽分布服從高斯分布.

（5）CiteSeer［16］是計算科學領域的引文網絡，包含三千個點和四千條邊.每個節點代表一篇學術論文，每條邊代表兩篇論文之間的引用關系.

（6）PDB［32］是來自PDB 的一個蛋白質結構網絡，包含兩萬多個點和八萬多條邊.每個節點代表一個原子，每條邊表示分子之間的化學鍵.

4.2 實驗設置使用4.1 的六種真實圖數據集和通過圖生成器生成的10 種不同大小規模的人工合成圖數據集.

使用Java 實現ItrMiner 和以下算法.

（1）TKG.通過實現TKG 算法［25］并對其加入支持單個大圖中的支持度和興趣度的計算，使其能在單個大圖中挖掘Top-Rank-K 頻繁模式.

（2）Grami.是一種改良版的Grami 算法［16］，在Grami 的基礎上引入本文提出的興趣度計算來挖掘Top-Rank-K 頻繁模式.具體地，首先挖掘得到所有的頻繁模式，隨后計算其興趣度，經排序后返回前k名的所有模式.值得一提的是：①由于Grami 依賴支持度閾值進行剪枝，因此，算法利用啟發式方法來估算支持度閾值；②Grami 在挖掘過程中僅對候選模式進行支持度的判別，即是否達到支持度閾值，沒有精確計算對模式的支持度，故本文采用模式支持度下界，即將支持度閾值作為模式的支持度來進行興趣度值的計算.

（3）ItrMinernopt.是ItrMiner 無模式擴展約束的版本，與ItrMiner 相比，ItrMinernopt除了在模式擴展中沒有實現擴展約束以外，其余基本一致.

4.3 實驗結果

4.3.1 實驗一：k 對算法的影響首先，固定系數α=2.0，在六個真實數據集上，以50 為增量，k從100 增加到300.圖5 展示了六個真實數據集上所有算法的執行時間.

圖5 在六個數據集上k 對各算法執行時間的的影響Fig.5 The execution time of each algorithm with different k on six datasets

（1）隨著k的增加，所有算法的執行時間均變長，因為需要驗證的候選模式以及匹配增加了.需要注意的是，CiteSeer 的執行時間基本不變，這是因為預設的k已經大于需要驗證的所有候選模式的興趣度的數量.

（2）與TKG 和ItrMinernopt相比，ItrMiner 的效率更高，在六個真實數據集上，ItrMiner 平均花費的時間分別為TKG 的51.9%，39.2%，43.9%，18.7%，76.5%和94.4%.同時，ItrMiner 的模式擴展約束對提升執行效率有顯著作用，在六個真實數據集上，加入模式擴展約束后，ItrMiner 平均花費的時間是ItrMinernopt的45.4%，32.3%，40.4%，14.1%，74.7%和78.0%.此外，ItrMiner在稠密的數據集上的表現尤為出色.以Twitter數據集為例，當k=250 時，ItrMiner 和ItrMinernopt相比，最高效率可提升9.5 倍.同時，和TKG 相比，ItrMiner 僅需花費其13.2%的時間.

圖6 展示了各算法在六個真實數據集上的內存消耗.由圖可見，隨著k的增大，ItrMiner，ItrMinernopt和TKG 的內存消耗也相應增加，這是因為k越大，算法的搜索空間也越大.進一步觀察發 現，初 始k=100 時，ItrMiner，ItrMinernopt和TKG 的內存消耗都略高，這是因為它們沒有設置初始支持度閾值，算法開始的搜索空間較大.然而，在實際應用中，內存是一個重要的限制因素，這方面ItrMiner 表現最佳，它在大多數數據集上的內存消耗最小.相比之下，ItrMinernopt和TKG的內存消耗略高，但總體上它們的內存成本仍然是可以接受的，并且沒有一個算法在內存方面顯著劣于其他算法.

圖6 在六個數據集上k 對各算法內存消耗的的影響Fig.5 The memory consumption of each algorithm with different k on six datasets

4.3.2 實驗二：ItrMiner 與Grami 的比較比較ItrMiner 與Grami 的性能，以評估使用ItrMiner進行前k頻繁模式挖掘是否達到或超過傳統設定支持度閾值的頻繁模式挖掘算法的性能.

需要注意，與ItrMiner 在挖掘過程中動態維護興趣度排名在前k的模式方式不同，Grami 的運行流程主要分三部分：（1）輸入支持度閾值；（2）挖掘滿足支持度閾值的模式；（3）從模式中選取興趣度排名在前k的所有模式.為了保證結果的一致性，將不同k的ItrMiner 運行得到的模式集合中的最小支持度作為Grami 的支持度閾值輸入.

固定系數α=2.0，在六個真實數據集上，以50 為增量，k從100 增加到300.表4 和表5 分別展示了Grami 和ItrMiner 在六個真實數據集上的實驗結果，表中黑體字表示結果最優.

表4 Grami 和ItrMiner 算法在六個數據集上的執行時間（單位：s）Table 4 Execution time (unit：s) of Grami and ItrMiner on six datasets

表5 Grami 和ItrMiner 算法在六個數據集上的內存消耗(單位：GB)Table 5 Memory consumption (unit：GB) of Grami and ItrMiner on six datasets

由表4 可知，在六個真實數據集上，ItrMiner的執行時間比Grami 更短，尤其在YouTube 數據集上，k=300 時Grami 的執行時間接近ItrMiner的四倍.進一步觀察，隨著k的增大，ItrMiner 的優勢更明顯.例如，在Amazon 數據集上，k=100時Grami 的執行時間約為ItrMiner 的1.5 倍，而k=300 時，這個比例擴大到3 倍，因為較大的k會導致發現更多的模式，降低模式集合中的最小支持度，這會增大Grami 的搜索空間.而ItrMiner 采用基于興趣度優先的樹模式識別方法，并受到模式擴展約束規則的限制，避免了大量冗余模式的生成，提升了運行效率.然而，在MiCo 和Twitter數據集上，發現ItrMiner 的執行時間比Grami 更長.分析發現，ItrMiner 以動態的方式將潛在的高興趣度模式擴展出來，在擴展過程中ItrMiner 始終維護前k名的模式，并利用它們產生大量的候選模式，這一過程在特定的數據集上可能會消耗過長的時間.相反，Grami 在開始時就已指定最小支持度閾值，避免生成冗余的低支持度模式.綜上，Top-Rank-K 頻繁模式挖掘可以在無須設定支持度閾值的情況下更加高效地進行運算.

由表5 可知，除了PDB 和Twitter 數據集外，ItrMiner 在其余數據集上的內存消耗比Grami 更低.這是因為ItrMiner 采用模式擴展約束策略，可以避免生成大量的冗余模式和實例檢驗，有效地減小了算法的搜索空間.但在PDB 和Twitter 數據集上，ItrMiner 消耗的內存高于Grami，因為ItrMiner 需要同時維護兩個隊列Sk和Sc，Sk用 于動態存儲當前興趣度排名在前k的模式，Sc用于存儲需要通過動態搜索擴展的模式.

實際應用中，用戶通常難以確定適當的支持度閾值（參考例1）.為此，本文在不同數據集上，對支持度閾值進行調整，并計算k不同時的挖掘任務耗時.表6 展示了運行結果，表中黑體字表示性能最優.由表可見，ItrMiner 在所有數據集上的執行時間均比Grami 更短，并且，隨著k的增加，兩者之間的差距越大，表明支持度閾值的設定直接影響算法的執行效率.因此，在實際應用中，進行Top-Rank-K 挖掘更加便捷.

表6 Grami 和ItrMiner 算法在六個數據集上的執行時間（單位：s）Table 6 Execution time (unit：s) of Grami and ItrMiner on six datasets

在不同數據集上比較這兩種算法的性能表現，驗證了ItrMiner 的可行性和實用性，為實際應用中的用戶提供更多選擇和靈活性，更高效地進行模式挖掘分析.因此，可以將ItrMiner 視為傳統頻繁模式挖掘的一種有價值的替代方案.

4.3.3 實驗三：算法的可擴展性首先，固定系數α=2.0，k=600，將圖G=(V，E，L)的規模從(0.1 M，1 M)增長至(1 M，10 M)，其中頂點的增量為0.1 M，邊的增量為1 M，比較ItrMiner，ItrMinernopt和TKG 的性能，實驗結果如圖7 所示.由圖可見：（1）如前預期，隨著圖規模的增大，所有算法的執行時間和內存消耗也增加，但由于具體圖結構的不同，可能會出現局部下降；（2）與ItrMinernopt和TKG 相 比，ItrMiner 在不同規模的數據集上表現出更短的執行時間和更低的內存消耗.此外，ItrMiner 的執行時間對圖規模的敏感度更低，即當圖的規模從(0.1 M，1 M)增長至(1 M，10 M)，ItrMiner，ItrMinernopt和TKG 的執行時間分別增加了478，885 和705 s.因此，ItrMiner表現了更好的可擴展性.

圖7 算法的可擴展性Fig.6 Scalability of the algorithms

4.3.4 實驗四：α 對算法的影響首先，固定k=200，在六個真實數據集上，α以0.2 的步長從1.6增長至2.6，測試其對ItrMiner 的影響，實驗結果如圖8 所示.

圖8 六個數據集上α 對ItrMiner 算法的影響Fig.8 Impact of α of ItrMiner on six datasets

由圖可見：（1）隨著α的增大，ItrMiner 的執行時間和內存消耗呈下降趨勢，因為α越大，興趣度在支持度上的收益越大，算法會偏向于挖掘支持度更高的模式，從而更快地提高全局的支持度，加快搜索速度；（2）雖然不明顯，但是α的增大會使Top-Rank-K 模式的最大模式呈下降趨勢.原因同前，基于模式反單調性的特性，子模式的支持度必定不大于父模式，越小的模式支持度一般越高.為了獲取更高質量的模式，需要在模式大小和支持度之間尋找平衡，選擇合適的α.

5 結論

針對頻繁模式挖掘支持度閾值難以設定的問題，本文研究了Top-Rank-K 的頻繁模式挖掘問題.首先設計了一項同時考慮模式大小和模式支持度的興趣度指標，并基于該指標提出一種無須設置初始支持度閾值，直接挖掘排名前k的Top-Rank-K 頻繁模式挖掘算法ItrMiner.針對沒有初始支持度閾值作為輸入、算法剪枝困難的問題，ItrMiner 采用興趣度優先的樹模式識別來快速提升支持度閾值.同時，本文還提出一種新穎的模式擴展約束策略來有效地減少不必要模式的生成，縮短算法的執行時間，降低算法的內存消耗.使用真實圖和人工合成圖數據集來驗證ItrMiner的性能，結果表明，與無擴展約束ItrMinernopt和基線算法TKG 相比，ItrMiner 的執行時間更短，內存消耗更低，在稠密數據集上的優勢更顯著.另外，通過與帶有支持度閾值的Grami 算法的比較，驗證了ItrMiner 的可行性和實用性.在人工合成數據集上的實驗也證明ItrMiner 具有更好的擴展性.綜上，本文提出的ItrMiner 算法，耗時更短，內存消耗更低，還能高效地挖掘興趣度排名在前k的頻繁模式.

未來將致力于解決更大規模圖數據的頻繁模式挖掘問題，并嘗試通過并行計算的方法進一步提高ItrMiner 算法的執行效率.