基于網絡嵌入的稀疏子圖發現算法

孫鶴立，何 亮，何 方，孫苗苗，賈曉琳*

（1.西安交通大學計算機科學與技術學院，西安 710049；2.西安交通大學新聞與新媒體學院，西安 710049）

（*通信作者電子郵箱xlinjia@mail.xjtu.edu.cn）

0 引言

隨著在線社交網絡（如新浪微博、微信）的廣泛流行，社團發現問題由于其廣泛的應用得到了長足的發展。然而現有的多數工作大多關注于網絡中的稠密子圖發現問題，很少有關于稀疏子圖（tenuous subgraph）的研究。所謂稀疏子圖，是指由具有較少的連接或者弱連接的節點組成的子圖結構。

稀疏子圖在實際生活中有許多的應用場景。例如，在科研論文的審稿時，組織者需要為論文分派審稿人。除了需要審稿人的研究領域與論文內容相關之外，也需要避免審稿人與論文作者、審稿人之間互相認識，從而避免審稿時可能出現的學術不端現象，保證審稿過程的公平公正。當前多數審稿系統都使用了論文作者合作關系、工作單位、國籍等信息來避免研究領域的偏差，但是很少考慮到論文作者與審稿人之間的社交關系的稀疏性。弱社交網絡中的好友推薦問題、患者治療小組組建問題［1］同樣與稀疏子圖有關。可見，稀疏子圖在現實生活中具有較為廣泛的應用前景。

患者治療小組組建：在精神康復治療領域，針對某些疾病，如酗酒、藥物依賴等，在對患者進行治療時，通常是將有針對性的治療和小組內患者之間的互助相結合的。這個治療小組成員的選擇不是隨意的，而是需要滿足一定的條件：盡可能保證治療小組中的成員互不認識且沒有共同的朋友，這樣可以將治療小組中共享的私人信息被傳播的可能性降到最低，從而避免他們因為害怕熟識的朋友知道自己的秘密而不吐露自己內心的真實想法；且治療小組的規模不宜過小，這樣可以確保小組里的每個成員都能得到他人的充分的幫助。

評審專家選擇：在審閱學術論文或項目立項評審時，均需指派專家。除了保證這些專家的研究方向與所評閱論文或項目的研究內容一致，還要盡可能避免審稿人和論文作者/項目申請人認識及審稿人之間互相認識，以確保評審過程的公平公正。

最近，稀疏子圖開始引起了一些研究者的興趣，研究者提出了一些用于稀疏子圖發現的方法［2-4］，這些方法均基于圖結構給出了稀疏子圖的定義，并進行了相關研究。與之前的方法不同，本文提出一種基于網絡嵌入的稀疏子圖發現（Tenuous subGraph Finding，TGF）方法，將圖結構轉化為向量表示，進而在歐氏空間中進行稀疏子圖的發現。通過這種方法能夠更高效地進行稀疏子圖的發現，并且可以很好地結合網絡結構和屬性信息。

1 相關研究

1.1 稀疏子圖發現

稀疏子圖相關的研究從2017 年才開始逐漸出現。Shen等［2］提出的MkTG（Minimumk-Triangle disconnected Group）問題是首個關于稀疏子圖發現問題的研究。MkTG 問題使用子圖中k-triangle 的個數來衡量子圖的稀疏性。k-triangle 定義為子圖中的一個三元組，其中任意兩個節點之間的最短路徑均小于k。MkTG 問題即為找到圖中最大的一個節點集合，使得其中的k-triangle 的數量盡可能地少，并且節點數量盡可能地多。盡管該方法可以找到稀疏子圖，但是k-triangle 在某些情況下不是一個很好的評估稀疏性的指標。另一方面，由于需要計算每個節點參與的k-triangle 的數量，導致該方法的時間復雜度較高，較難應用于大規模網絡上的稀疏子圖發現。在MkTG 問題的基礎上，Li 等［4］提出KLM（K-Line-Minimized）用于稀疏子圖發現。KLM 使用k-line衡量子圖的稀疏性。k-line定義為圖中最短路徑小于k的一個節點對。KLM 問題嘗試找到一個節點集合，使得其中k-line 的數量盡可能地少，同時節點的數量盡可能地多。

與前面兩個工作不同，Hsu 等［3］提出了 UTNA（Unfamiliarity-aware-Therapy group selection with Noah’s Ark principle）問題，利用稀疏子圖發現解決群體治療問題。群體治療是針對心理疾病進行治療的主要臨床手段之一，然而治療小組的組建是相當有挑戰性的。UTNA 旨在自動化地找出合理的治療群體成員。UTNA 問題即找到一個最大的子圖，使得其中連邊的數目盡可能地少，且節點滿足諾亞方舟準則（Noah’s Ark Principle）。

以上幾種方法均是基于圖結構尋找稀疏子圖，并且均提出各自不同的關于稀疏子圖的定義，然后基于這些定義設計了解決算法。然而，由于圖結構的復雜性，這些關于稀疏子圖的求解問題都是NP 難的，只能通過貪婪算法找到近似解，并且時間復雜度通常較高。隨著網絡嵌入方法在網絡分析領域的流行，本文考慮使用基于網絡嵌入的方法來尋找稀疏子圖。

1.2 網絡嵌入

網絡嵌入（network embedding）［5-7］又稱為網絡表示學習（network representation learning），旨在將網絡中的每個節點表示為低維向量，使原網絡的拓撲結構信息被高效地保存于學習到的向量中。傳統的網絡一般用稀疏的鄰接矩陣或拉普拉斯矩陣保存網絡結構特征信息，在網絡規模很大的情況下，這種表示會帶來維災難。網絡嵌入將鄰接矩陣映射成低維向量，很好地解決了維災難問題。

近年來，隨著深度學習的發展，越來越多的研究者開始采用深度學習中的技術解決網絡嵌入問題。DeepWalk算法［8］對網絡進行固定長度的隨機游走，得到節點序列，然后使用Skip-Gram 模型對這些節點序列進行學習，從而得到節點向量表示。Node2Vec方法［9］基于DeepWalk 方法，對隨機游走過程進行了改進，設計了一種有偏的隨機游走方法，在深度優先搜索和廣度優先搜索之間進行權衡。LINE（Large-scale Network Embedding）算法［10］則嘗試在網絡嵌入時保留網絡中的一階親密性和二階親密性，通過最小化鄰接矩陣和表示向量的KL（Kullback-Leibler）散度，可以在線性時間內高效地學習到節點向量表示。TADW（Text-Associated DeepWalk）算法［11］是一種針對文本屬性網絡的網絡嵌入方法，在DeeWalk 的基礎之上，加入了文本特征的學習，使用非負矩陣分解方法來進行優化。一些基于自編碼器［12-14］的網絡嵌入方法同樣也能很好地學習到網絡結構信息，如SDNE（Structural Deep Network Embedding）算法［12］、DNGR（Deep Neural Networks for Graph Representations）算法［13］等。

2 基于網絡嵌入的稀疏子圖發現算法

TGF 算法主要分為兩個步驟：節點網絡嵌入學習和稀疏子集發現。其中：節點網絡嵌入負責對網絡進行特征學習，在盡可能保持網絡信息的情況下，將每個節點映射成低維空間中的表示向量；稀疏子集發現通過對學習到的節點表示向量進行學習，找到其中的稀疏子結構。

2.1 節點網絡嵌入學習

本文主要基于Node2Vec 方法的思想進行網絡嵌入。Node2vec是對DeepWalk 算法的改進，借鑒了自然語言處理中的詞嵌入方法［15］。通過在網絡中進行隨機游走，得到節點序列，然后再使用skip-gram 方法即可學習到每個節點的表示向量。它的隨機游走方法是深度優先遍歷和廣度優先遍歷的一種權衡，通過設置參數控制游走在鄰域停留或者往遠處擴散。Node2vec 方法首先對網絡中的鄰域信息進行學習，然后對鄰域信息保持目標函數進行優化完成節點表示向量的學習過程。這個目標函數是靈活的，而且有偏的隨機游走方法使得該算法可以采樣到不同類型的鄰居結構。

Node2vec方法的優勢在于它可以靈活控制隨機游走的方式，很好地使原圖中的結構信息得以保留。在原圖中距離較遠的兩個節點，在低維向量表示空間中，它們的相對位置也會較遠。Node2vec 綜合考慮節點的DFS（Depth First Search）鄰域和BFS（Bread First Search）鄰域通過對深度優先遍歷和廣度優先遍歷進行權衡，既能學習到局部的鄰域結構信息，又能避免游走過遠導致較遠的兩個節點形成相似的表示向量，充分考慮節點的“同質性”和“同構性”。“同質性”表示距離相近節點的嵌入向量應該盡量接近，“同構性”表示結構上相似的節點的嵌入向量應該盡量接近。

如圖1所示，節點u和s1、s2、s3、s4之間聯系非常緊密，它們組成了一個社區，應該具有相似的向量表示。同樣地，節點v和s5、s6、s7、s8也應該具有相似的向量表示，它們也組成了一個社區。可以看出u和v分別是這兩個社區的中心節點，它們在社區中扮演同樣的角色，因此也應該具有相似的向量表示。Node2vec算法可以充分捕捉節點間的“同構性”。

圖1 網絡結構示意圖Fig.1 Schematic diagram of network structure

2.2 稀疏子集發現

稀疏子集是由稀疏子圖中的節點組成的集合，為了便于后續形式化描述，這里將稀疏子圖問題轉化為稀疏子集發現。在得到網絡的節點表示向量之后，將稀疏子圖發現問題從圖結構中轉移到了低維向量空間中。由于向量空間與圖結構完全不同，原先在圖結構上定義的k-line、k-triangle 等均無法使用，因此為了在向量空間中完成稀疏子集發現，需要重新定義向量空間中的稀疏子集發現問題。以下討論中本文假設網絡嵌入方法學習到的節點表示向量的維度為h。

首先需要考慮的是低維向量空間中稀疏性的度量方法。給定一個向量集合時，如何去評價它是否稀疏。本文可以通過計算樣本之間的距離來判斷兩個點相距較近還是較遠。對于一個向量集合，可以計算所有向量之間的距離，如果它們之間的距離都比較遠，那么可以認為這個向量集合比較稀疏。為了衡量向量集合的稀疏性，本文引入ε對的定義：

定義1ε對，ε-pair。給定兩個樣本點的向量表示x1、x2，如果它們滿足dis(x1，x2)＜ε，將其稱為一個ε對。有了ε對的定義之后，就可以衡量給定的向量集合的稀疏性。假設集合T中的ε對的數量為r，r越小，說明集合T越稀疏。

這里的樣本距離度量方式可以有多種，比如余弦距離、歐氏距離等。本文選用的距離度量為歐氏距離，即

下面給出向量空間中稀疏子集發現問題的定義：

定義2稀疏子集發現（tenuous subset finding）問題。給定歐氏空間Rh的散點集合，給定距離參數ε，從集合D中找到一個子集，使得T滿足以下條件：

a）?xi∈T，xj∈T，dis(xi，xj)＞ε；

b）??xm∈{xi|xi∈D，xi?T}。

其中：|T|表示集合中節點的個數；dis(xi，xj)為點xi與xj之間的距離。約束條件a）表明稀疏子集T中的任意兩個節點間的距離需大于ε，即對的數量為0，這表明T中的所有節點間的距離都比較遠，從而可以表明T比較稀疏；約束條件b）則表明稀疏子集中的樣本數目應盡可能多。

為了解決定義2 中的稀疏子集發現問題，本文提出了一種基于局部密度擴張的貪婪算法TGF。TGF 算法的思路為：計算所有節點的鄰居節點及鄰居數目，首先選取鄰居數目最少的節點u加到稀疏子集中，對于剩下的候選節點，在滿足dis(u，xi)＞ε的條件下優先將鄰居數目最少的節點加入到稀疏子集中。該算法在向稀疏子集中添加節點時總是選取當前狀態下的最優節點，整體來講是一種貪婪算法。

首先提出ε鄰居的概念，定義如下：

定義3ε鄰居（epsilon neighborhood）。對于點xi∈D，給定距離參數ε，則點xi的ε鄰居Nε(xi)定義為：

Nε(xi)={xi∈D|dis(xi，xj)≤ε}

這個集合的樣本個數記為|Nε(xi)|。可見，ε鄰居定義為與給定樣本點的距離小于ε的所有節點集合。對于給定樣本點xi，其ε鄰居中的樣本數量|Nε(xi)|越少，說明該樣本周圍的密度較小，則該節點越有可能被加入到稀疏子集中；反之，樣本點xi的ε鄰居中的樣本數量|Nε(xi)|越大，說明該樣本周圍的密度較大，則該節點應盡可能避免被加入到稀疏子集中。

為了確保找到的稀疏子集中不存在ε對，在選取樣本點加入到稀疏子集時，應該從候選集合中去掉該樣本ε鄰居中的所有樣本點。為了避免過多的樣本被刪除，應盡量選擇密度較小的樣本點加入到稀疏子集中。在刪除樣本點時，其鄰域內所有樣本點的ε鄰居都需要進行更新。

TGF算法的偽代碼如算法1所示。

其中：第1）～2）行定義了相關變量；第3）～5）行是預處理階段，負責計算出所有樣本的ε鄰居Nε(xi)以及ε鄰居數量|Nε(xi)|；第6）～18）行是算法的主體部分，負責尋找稀疏子集并且刪除不在稀疏子集中的樣本點，其中第8）行將樣本xt加入到稀疏子集中；第9）～14）行刪除xt的ε鄰居中的所有樣本點，15）～18）行從候選集中刪除樣本點xt。

圖2 為算法在二維空間上的稀疏子集發現過程。其中圖2（a）表示初始化階段，計算出每個樣本的ε鄰居和ε鄰居數量，每個樣本點旁邊標示的數字即為樣本的ε鄰居的數量。圖2（b）為TGF 算法最終找到的稀疏子集，所有的樣本點的ε鄰域數量都為0，可見所有的樣本點的ε鄰域內均沒有其他樣本點。

圖2 稀疏子集發現過程Fig.2 Process of tenuous subset finding

2.3 時間復雜度分析

對于網絡嵌入階段，本文采用的是基于Node2vec 的網絡嵌入方法，Node2vec 方法主要分為隨機游走和skip-gram 的訓練兩個步驟。隨機游走的時間復雜度為O(N)，skip-gram 的時間復雜度為O(logN)。對于ε鄰居的計算過程，采用kd-tree數據索引結構，時間復雜度為O(NlogN)。對于稀疏子集發現的計算過程，每次添加樣本點到稀疏子集中時，需要在未訪問的樣本中查找鄰居數目最少的樣本，采用線性查找的方法，時間復雜度為O(N)。刪除給定樣本的ε鄰居中的樣本這一步驟的時間復雜度為O(ρ2)，其中ρ表示平均每個樣本的ε鄰居個數。綜上，稀疏子集發現過程總的時間復雜度為O(l(N+ρ2))，其中l表示集合D中的稀疏子集的個數，通常l≤N，可以近似認為尋找稀疏子集算法的時間復雜度接近線性時間復雜度，即O(N)。

綜合以上分析，TGF 的算法時間復雜度為O(N+logN+NlogN+l(N+ρ2))，整理后即為O(NlogN+l(N+ρ2))。

3 實驗與結果分析

為了評估TGF 算法的準確率和有效性，在多個人工合成網絡和真實網絡數據集上進行實驗，并和已有的算法進行對比。本次實驗的電腦環境為Interl Core i5-4590 CPU @3.2 GHz 型號CPU 和8 GB 內存，操作系統為Ubuntu 16.04，TGF算法采用Python語言實現。

3.1 實驗數據集

本實驗中采用的數據集分為人工合成網絡數據集和真實網絡數據集。數據集的所有相關信息總結在表1中。

表1 數據集信息Tab.1 Dataset information

Polbooks 政治書籍網絡：政治書籍網絡是由亞馬遜銷售的政治書籍構成的網絡，其中節點表示由亞馬遜賣出的書籍，邊則表示兩本書經常被同時購買。每本書上都存在一個標簽，表明該書籍的政治傾向性，分別為“自由”（liberal）、“中立”（neutral）和“保守”（conservative）。

Football 橄欖球聯賽網絡：Football 美國大學橄欖球聯賽網絡是由美國大學的橄欖球比賽情況構成的一個網絡，其中的節點表示球隊，邊表示兩個球隊之間曾經打過比賽。該網絡中一共有115 個節點和613 條邊。網絡中的所有球隊被劃分成了11個聯盟和5支獨立隊伍。

Email_eu 研究機構郵件網絡：Email_eu 是由歐洲某研究結構的郵件往來信息組成的網絡。其中節點表示一個研究人員，邊表示兩個研究人員之間有過郵件往來。這些研究人員分屬42個不同的科研機構。

表1 中的以Synthetic 開頭的數據集表明它是一個人工合成數據集。人工合成數據集由Lancichinetti 等［16］開發的LFR benchmark 工具生成，在生成網絡時可以指定網絡的節點數目、平均度、混亂程度等。

3.2 對比算法和評估指標

為了評估TGF 算法的性能，本節選取兩個已有的稀疏子圖發現算法WK（Weight ofK-hop）和TERA（Triangle and Edge Reduction Algorithm）來進行對比。

在對實驗結果進行衡量時，本文采了k-line、k-triangle 以及k-density 作為評價指標。關于k-triangle 和k-line 的定義詳見1.1節。k-density的定義如下：

3.3 整體結果分析

本節主要分析各個算法在數據集上的整體表現。為了公平起見，設定在所有數據集上找到的稀疏子圖規模是一致的，并且設定找到的稀疏子圖的規模為原圖規模的1/10。針對ε優化，使得TGF算法能找到指定大小的稀疏子圖，且該稀疏子圖中的1-line、1-triangle 以及1-density 值都較小。由于TGF 的時間復雜度非常低，所有要找到合適的ε并不困難。對于WK算法和TERA，為了找到指定規模大小的稀疏子圖，需要多次嘗試選擇不同的k值。

表2 是WK、TERA、TGF 三個算法在人工合成數據集上的結果。其中：1-line 表示子圖中邊的數量；1-triangle 表示子圖中直接相連的三個節點組成的三角形的數量；1-density 表示對應的子圖密度；2-line 表示子圖中最短路徑長度不大于2 的節點對的數量；2-triangle 表示子圖中三個節點組成的兩兩之間距離不大于2的三元組的數量；2-density表示對應的子圖密度。從表2 中可以看到本文提出的TGF 算法在所有數據集上的1-line、1-triangle 和1-density 值都是最小的，找到的所有的稀疏子圖中都不存在直接連邊和三角形結構；然而TGF 算法在其他幾個數據集上的2-line、2-triangle 和2-density 值較大，產生這種結果的原因可能是WK 和TERA 的直接目標就是最小化稀疏子圖中的k-line數量和k-triangle的數量，而本文提出的TGF 算法并沒有直接針對2-line 或2-triangle 進行優化。不過TGF 與這些方法得到的結果差距都非常小，也能在一定程度上表明TGF算法具有良好的性能。

表2 各算法在人工合成數據集上的結果Tab.2 Results of different algorithms on synthetic datasets

表3展示的是三個算法在Polbooks、Football和Emai_eu三個真實數據集上的結果。從這兩個表上可以看出TGF算法在這三個數據集上的1-line、1-triangle 和1-density 值都是最小的。TGF 在Polblooks 數據集上得到的2-triangle 值也是最小的。

表3 各個算法在真實數據集上的結果Tab.3 Results of different algorithms on real datasets

綜合以上分析，可以看出TGF 算法通過網絡嵌入方法將網絡結構映射到低維向量空間中，然后采用基于密度的稀疏子圖發現方法來間接地完成稀疏子圖發現的方法是可行的。該算法在所有的數據集上都展示出了優秀的性能，尤其在1-line、1-triangle 和1-density 三個指標上的值都小于WK 和TERA 兩個對比算法。由于WK 和TERA 兩個算法是直接對2-line、2-trangle和2-density這三個指標做優化的，所以這兩個算法在這三個指標上的值相對較小，但是TGF 算法在這些指標上的值與WK 和TERA 的差距非常小，說明TGF 算法具有良好的性能。

3.4 參數敏感性分析

本文提出的TGF引入參數ε來度量向量之間的距離，ε對結果有較大的影響。為了分析TGF 算法的參數ε對性能的影響，本文在兩個人工合成數據集上進行了實驗，分析隨著參數ε從小到大的變化，對應找到的稀疏子圖中各項指標的變化情況。圖3 展示了TGF 算法在Synthetic_800 和Synthetic_2000、Synthetic_300000 三個數據集上的參數敏感性分析情況。

圖3 TGF算法在三個數據集上的參數敏感性情況Fig.3 Parameter sensitivity of TGF algorithm on three datasets

圖3 中：縱坐標表示算法得到的1-line、1-triangle 個數和找到的稀疏子圖節點數，即n_tenuous。從圖3中可以看出，隨著參數距離ε的增大，得到的1-line，1-triangle 個數均開始逐漸減小，并且呈現出快速下降的趨勢。這說明TGF 對參數ε較為敏感，如果ε過小，TGF 可能返回整個數據集作為稀疏子圖結果集。而隨著ε的增大，由于TGF會刪除選定點的ε鄰域內的所有節點，所以n_tenuous 的個數開始快速降低。從Synthetic_800 數據集上得到的結果可以看出：1）當ε＜2.2 時，TGF 會返回整個數據集作為稀疏子圖結果集；2）當ε在2.5～3.0 時，得到的1-line、1-triangle 和n_tenuous 個數開始快速下降；3）當ε=3.0時，是一個拐點，在ε＞3.0以后，得到的1-line、1-triangle 和n_tenuous 個數下降速度開始減慢；4）當ε＞4.0時，1-line、1-triangle 和n_tenuous 個數都變成了0。在Synthetic_2000 和Synthetic_300000 數據集上呈現出了類似的結果，當ε在2.5～3.0 時，算法得到的1-line，1-triangle 和n_tenuous 個數呈現出快速下降趨勢；在ε＞4.5 之后，1-line、1-triangle和n_tenuous個數都歸為0。

綜上可知，ε參數對得到的稀疏子圖的影響較大，選擇合適的ε能得到較好的結果（稀疏子圖規模較大且子圖較稀疏），而如果ε選得過小或者過大則有可能導致返回整個數據集作為稀疏子圖結果集或者稀疏子圖結果集為空。在多個實驗數據集上的結果表明，ε選擇在區間1.5～4.5 時，TGF 算法能取得較好的效果。

3.5 實例分析

為了更好地展現出TGF 算法尋找稀疏子圖的效果，本節選取Polbooks 數據集進行實例分析，展示TGF 算法在該數據集上的稀疏子圖發現結果。

圖4 是TGF 算法在Polbooks 網絡上找到的稀疏子圖的示意圖。其中較大的節點表示通過TGF 算法找到的10 個節點，它們共同組成了一個稀疏子圖，可以看到這個稀疏子圖中的節點均勻地分布在整個網絡中。在該稀疏子圖結構中，任意兩個節點之間都不存在連邊。由此可見，TGF 算法在真實網絡上的效果很好，能夠有效地找到網絡中的稀疏子圖結構，并且有足夠的稀疏性。當然，由于這里的ε參數取值為0.8，此時只找到了10 個節點。如果將ε參數取得更小，那么TGF 能找到規模更大的稀疏子圖；反之，將ε參數取得更大，那么找到的稀疏子圖規模就會更小。參數ε的選擇可以根據實際需要找到的稀疏子圖規模來決定。

圖4 Polbooks網絡上找到的稀疏子圖Fig.4 Tenuous subgraph found in Polbooks network

3.6 時間性能分析

本節主要比較TGF算法和其他對比算法的時間效率和可擴展性。表4 為WK、TERA 和TGF 算法在多個人工合成網絡數據集上的運行時間對比。這里分別采用了三個人工合成數據集。為了公平的進行比較，本文在對比WK、TERA 和TGF三個算法的運行時間時，設定在所有數據集上找到的稀疏子圖規模是一致的。

表4 各個算法在不同數據集上的運行時間 單位：sTab.4 Running time of different algorithms on different datasets unit：s

從表4 可以看出，相較于其他兩個算法，TGF 算法的時間效率是最高的，且隨著網絡規模的增大，TGF的優勢變得更為明顯。TGF算法的運行時間較低的原因有兩個方面：一方面，TGF 通過網絡嵌入方法將圖結構映射到低維向量空間中，在向量空間中的距離計算相對于圖中的最短路徑計算復雜度大降低；另一方面，TGF 采用了哈希表存儲所有節點的ε鄰居信息，因此查詢和刪除樣本的速度很快，得到稀疏子圖的時間幾乎是線性的。

4 結語

本文提出了基于網絡嵌入的稀疏子圖發現方法，將網絡結構映射到低維空間中。在Synthetic_100、Synthetic_1000、Synthetic_300000 三個人工生成數據集上的時間性能分析表明，TGF 算法展示出較好的效果，在Synthetic_1000 數據集上與TERA 和WK 算法相比，TGF 算法的搜索效率是TERA 的1 353 倍，是WK 算法的4 倍。同時通過在真實數據集和人工生成數據集上的實驗結果表明，本文方法在1-line、1-triangle、1-density 指標上的結果也較優。本文沒有考慮屬性圖上的稀疏子圖發現問題，網絡中節點的屬性信息也是非常重要的，比如性別屬性、年齡屬性、背景屬性等信息，后續會結合節點屬性展開相關研究。