林隆龍
博士、副教授
目前任職于西南大學計算機與資訊科學學院 軟體學院。2022年6月于華中科技大學計算機科學與技術學院獲博士學位。目前主要研究興趣包括(時序)社群挖掘、局部聚類、Personalized PageRank計算、圖神經網絡的可擴充算法設計等領域。目前發表論文于AAAI,TSMC, ICDCS, TBD, DASFAA, JCST等頂級期刊/會議論文
01
内容簡介
圖聚類是一個重要的算法基礎，它被廣泛地應用在圖像分割、社群發現、機器學習等領域。一般地，圖聚類旨在将一個完整的圖劃分為幾個互不重疊的簇，使得每個簇的内部有較稠密的邊，而簇之間有較稀疏的邊。許多圖聚類的模型被提出，比如，子產品度、結構聚類以及稠密子圖。其中，基于Conductance的圖聚類是當今最為主流的一種方式，它有很好的結構性質以及堅固的理論基礎。然而，目前的基于Conductance的圖聚類算法面臨可擴充性低和品質差的困境。為了更好地解決上述困境，我們提出了一種基于Peeling的貪婪計算架構，它能囊括現存方法的計算範式。基于該架構，我們提出了一個高效率的啟發式算法PCon_core和一個高效率和高品質的近似算法PCon_de。其中，PCon_de具有線性的時間複雜度和近似線性的近似比。
02
Problem Definition & Applications
Background
圖聚類是一個非常重要的理論和實際問題，它旨在将一個圖劃分為不同的簇，使得簇内部的聯系或者邊較簇之間的聯系更多。用通俗的話解釋就是：物以類聚、人以群分。
基于這種直覺，學者們提出了大量的模型，主要包括兩大類。第一類是圖論模型，包括Clique、Quasi-Clique、K-truss、K-core、Densest subgraph和K-ECC等。第二類是統計實體模型，包括Betweenness Centrality、Modularity、Conductance、Graph Partitioning等。而這裡我們主要關注的是Conductance，這是因為Conductance能更好地符合圖聚類的直覺，并且它有很好的理論保證，與圖代數中的譜圖理論也有較多的聯系。
Problem Definition:
Conductance-based Graph Clustering
Conductance：給出一個無向圖G，基于Conductance的圖聚類旨在找到具有最小Conductance的頂點集C。Conductance的定義是一個比值的關系，即
式中，分子是基于edge cut來定義的，分母的取值是頂點集C中結點度數和與補集度數和內插補點的最小值。我們最終的研究目的是希望Conductance的值最小，即分子最小（與外部聯系最少），分母最大（C内部結點度數最多）。
Applications
Conductance也有很多應用。比較經典的應用是圖像分割、社群發現、機器學習。
03
Existing Solutions
現存的基于Conductance的圖聚類方法主要分為三類。第一類是基于費德勒向量（Fidler Vector）的圖聚類；第二類是基于擴散的局部聚類，主要目的是得到查詢結點與其餘結點之間的關系，比較經典的三種方式分别是Truncated Random Walk、Personalized PageRank、Heat Kernel PageRank；第三類是除了上述兩類方法以外的方式，代表性的有SDP、LP、Flow-based等。
Fiedler vector-based spectral clustering
該方法主要分為三個步驟：(1)計算歸一化拉普拉斯矩陣（D-1/2(D-A)D-1/2）的第二小特征值對應的特征向量x，其中x稱為費德勒向量。(2)對x中的所有項按照遞增的方式進行排序，使得xv1≤xv2≤…≤xvn。(3)輸出S=arg minφ(Si)，其中Si={xv1，xv2，…，xvi}。
該方法的優勢在于通過順序的學習将指數的組合轉化成線性的組合，缺點是第一步中計算第二小特征值的過程較慢，時間複雜度為O(n3)。
Diffusion-based local clustering
為了解決上述方法存在的問題，研究者們提出了基于擴散的局部聚類方法。該方法的主要步驟為：(1)給定一個種子節點q，它們通過一些圖擴散的方式（比如：Truncated Random Walk、Personalized PageRank、Heat Kernel PageRank）計算一個機率分布π (w.r.t q)，令y= π/D，其中D為對角度矩陣。(2)對y中所有非零項進行排序，使yv1≥yv2≥…≥ysup(y)，其中sup(y)是y中非零項的個數。(3)輸出S=arg minφ(Si)，其中Si={yv1，yv2，…，yvi}。這種方式在效率上會提升很多，但是聚類品質不高。
Deficiencies of Existing Solutions
該表顯示了現有解決方案的不足，有兩種基于特征向量的方法，即SC和ASC。有三種基于擴散的方法。從表中可以看出，基于特征向量的算法具有較高的時間和空間複雜度。基于擴散的方法沒有全局Conductance保證的啟發式方法。
04
Proposed Solutions: PCon_core & Pcon_de
Our Solution——Framework
由于之前工作的不足，我們提出了一個三階段計算架構，它包含了大多數現有方法的計算範式。即現有的解決方案可以被歸納為以下三個階段：(1)我們根據相應的應用為每個頂點給出一個預先定義的得分函數。簡單來說，我們用s(u)表示頂點u的分數。(2)我們疊代地删除分數最小的頂點。這樣的疊代删除過程被稱為Peeling過程。(3)我們輸出Peeling過程中Conductance最小的結果。但如何設計一個有效的得分函數并能有效地得到是該架構的一個重大挑戰！
Degeneracy Ordering
給定一個無向圖G，在G的所有頂點上的一個排列(u1，u2，…，un)，如果每個頂點ui在G的子圖中由ui, ui+1，…，un所構成的子圖中度數最小，這樣的排序稱之為Degeneracy Ordering。
PCon_core
在上述架構的基礎上，我們首先利用著名的Degeneracy Ordering提出了一種簡單的算法PCon_core。該算法的輸入為無向圖，輸出為聚類S。我們使用簡并排序來計算出Degeneracy Ordering，并配置設定頂點u的分數s(u)。顯然，Pcon_core具有線性的時間和空間複雜度，但在品質方面它是啟發式的，沒有全局的Conductance保證。
那麼如何在不犧牲效率的前提下提高聚類品質?我們嘗試将Conductance進行一個轉換，證明在vol(S)小于m的情況下，g(S)的值最大。那麼進一步能夠證明最優的Conductance的頂點集的頂點有
的結論，進而我們将其做出形式化的定義——度比，即u在S内部的度數與u在整個原始圖度數的比值，這其實也是對頂點u賦予一個分數值。
PCon_de
于是，我們設計了一種稱為PCon de的線性時間貪婪算法——PCon_de。該算法首先将目前搜尋空間S初始化為V，候選結果為V，并且根據定義，每個頂點u∈S的度比為DrS(u)。随後，它在每一輪中執行貪心去除過程以提高目标簇的品質。具體來說，在每一輪中，它都會獲得一個度數比最小的頂點u。第5-11行中更新目前搜尋空間S、候選結果（如果有）和DrS(v)。一旦目前搜尋空間為空，疊代就會終止。最後，傳回作為近似解。
05
Experiments
Datasets
我們在六個現實生活中的公開資料集上評估了我們提出的解決方案，這些資料集是基于Conductance的圖聚類的廣泛使用的基準。實驗中使用了這些資料集的最大連通分量。我們還使用五個人造圖LFR、WS、PLC、ER和BA。以下六個競争對手被實施以進行比較：基于特征向量的方法：SC和ASC；Diffusion-based methods: NIBBLE PPR、HK Relax；Flow-based methods: SimpleLocal、CRD。
Results on real-world graphs
由下表可以看出：(1) PCon_core和P Con_de在大多數圖上始終比其他方法更快，尤其是對于較大的圖。特别是，它們在DBLP、Youtube、LJ和Twitter上分别實作了SC的5、14、42和17倍的加速。(2) PCon_core比PCon de稍快，但PCon_core的Conductance值較差。(3) PCon_de傳回的聚類品質在六個資料集中的五個上優于其他方法。是以，這些結果清楚地表明，與基線相比，所提出的算法可以實作顯著地加速和高聚類品質。
從圖4中，我們可以看到PCon_core和PCon_de的記憶體開銷在所有資料集上始終小于SC。特别地，與SC相比，它們節省了1.4∼7.8倍的記憶體開銷。這是因為PCon_core和PCon_de隻需要線性空間複雜度來計算每個頂點的分數。然而，SC采用矩陣的特征向量來計算每個頂點的得分，是以在最壞情況下需要平方空間複雜度。這些結果表明PCon_core和PCon_de的記憶體消耗更低。
Results on synthetic graphs
我們進一步使用人造網絡來評估我們提出的解決方案的可擴充性和有效性。特别地，我們隻展示了圖5(a)中頂點數量不同的ER的可擴充性，但所有其他合成圖都有類似的趨勢。可以看出，PCon_core和PCon_de 相對于圖的大小接近線性。然而，SC的可擴充性較差，因為它的時間成本随着圖大小的增加而波動很大。這些結果表明我們提出的算法可以處理大量圖，而SC不能。
我們使用四個合成圖LFR、WS、PLC和BA來評估我們提出方案的可擴充性，圖6顯示了結果。可以看出，PCon_core和PCon_de 相對于圖的大小接近線性。是以，這些結果表明我們提出的算法可以處理大規模圖。
06
Summary
(1)我們引入了PCon，這是一種新穎的基于Peeling的圖聚類架構，它可以包含大多數最先進的算法。
(2)在PCon上，我們開發了兩種新穎且高效的算法，具有線性時間和空間複雜度。一種是旨在優化效率的啟發式算法，另一種是可以獲得可證明聚類品質的近似算法。
(3)在真實和人造資料集上的結果表明，我們的算法可以在保證高聚類精度的情況下實作5~42倍的加速，而使用的記憶體比基線算法少1.4~7.8倍。