圖正則化非負矩陣分解的異質網社區發現

劉家驥，包崇明，周麗華，王崇云，孔 兵

1.云南大學 信息學院，昆明 650091

2.云南大學 軟件學院，昆明 650091

3.云南大學 生態學與環境學院，昆明 650091

1 引言

現實世界中，許多復雜的系統都可以抽象成網絡的形式，對于復雜網絡的研究能夠加深對于不同系統性質的了解。目前，針對同質節點網絡有比較深入的研究，如社區發現[1]、影響最大化[2]和網絡傳播[3]等。然而，現實世界網絡往往由多種不同類型的異質節點構成，異質節點間的交互往往代表不同的連接關系。在實際網絡中，多種類型的節點由多種類型的鏈路連接，從而形成異質信息網絡（Heterogeneous Information Networks，HIN）[4]。例如，從論文合作網絡[5]中提取的數據包含作者、論文、關鍵詞和會議等多類型對象。這些不同類型的對象之間形成了不同類型的連接關系。

異質網絡數據挖掘的關鍵研究問題之一是社區發現[1]（community detection）。社區發現即根據網絡包含的鏈接、內容等大量屬性信息，對網絡中具有共同屬性的潛在結構進行挖掘。挖掘異質網絡中有用的、具有穩定性的社區，同樣具有重要的研究價值。同質網絡[6]將社區定義為：網絡中具有某種相似特性的節點集合，社區內部節點聯系緊密而社區間聯系相對稀疏。推廣到異質網絡，可以認為：社區內部各種相同或不同類型節點間的連接緊密，而社區間的各種相同或不同類型節點間的連接則比較稀疏。但在異質網絡社區發現中，異質網絡中的異構性導致以下兩個問題[7]：（1）異質網絡中互動噪聲很多，引起算法的性能降低。網絡中節點的屬性可以看作是連接到節點的所有邊相互作用和疊加的結果，一些不重要的信息往往能夠給聚類帶來很大影響，這就是異質網絡中大量存在的噪音。（2）各個異質節點關系錯綜復雜，難以在同一維度中有效整合網絡中的異質信息，挖掘出符合實際的社區結構。將多維的異質網絡轉換成同質網絡是當前針對異質網絡聚類的主流方法，但是在降維的過程中如何最大限度保留異質信息以及在同一維度有效整合異質信息，是當前所面臨的一大挑戰。

針對異質網絡社區發現存在的難點，研究人員進行了很多嘗試。主題模型是對網絡中蘊藏的語義信息進行統一建模的方法，代表性的有潛在語義分析（LSA）[8]、概率潛在語義分析（PLSA）[9]和潛在狄利克雷分配（LDA）[10]等模型，它們能夠有效地對異質網絡中的社區結構進行挖掘。Deng等人[11]提出TMGP算法，將異質網絡中的不同節點信息集成到主題模型中，初步完成對社區的有效劃分，不過多數的主題模型，都僅僅單純地利用了文本集中的語義信息，而語義信息在一定程度上并不能很好地代表社區結構的特征，且必須滿足異質節點相互獨立的條件，有一定的局限性。

最近研究發現，將排序算法和聚類算法組合到一起，能產生一定的“化學反應”，從而達到令人較為滿意的研究結果。RankClus[12]是基于排序的經典聚類方法，先對目標對象進行排序，由排序結果決定聚類對象向量，通過迭代對目標對象類別進行調整，可以得到較為準確的聚類效果。基于排序和聚類相結合的方法雖然充分考慮了異質鏈接關系的信息，但是都沒有考慮同類型節點之間的交互關系。

異質網絡中節點復雜多樣，呈高維態勢，因此通過降維完成異質網絡到同質網絡或者二分網絡的轉換也是目前一種常用而有效的方法。常用的降維方法包括主成分分析（PCA）[13]、線性降維分析（LDA）[14]、非負矩陣分解（NMF）[15]等。當前大部分相關算法并不能很好地去除異質節點之間噪聲，在網絡轉化過程中會丟失大量網絡信息，同時無法在同一維度對網絡信息進行有效整合[16]。而非負矩陣分解已經被證明了能夠很好地保持網絡原始信息，且方法簡單明了、解釋性強、效率高。如何將NMF 應用于異質網絡社區發現，是本文研究的重點。

本文以異質網絡中的星型網絡作為研究對象，提出了一種融合各個子網絡異構信息和各個子網絡內部拓撲信息的聯合優化算法，即基于圖正則化非負矩陣分解的異質網社區發現方法。為了將異質信息在同一維度進行有效整合，該算法首先對反映了不同子網絡共有潛在結構的共識矩陣進行學習，使用共識矩陣中每個行向量作為中心類型節點在每個社區當中的隸屬度分布，通過不斷迭代優化系數矩陣和共識矩陣，對兩個反映不同類型節點的子空間進行優化，在降維過程中也較大限度地保留了異質信息的完整性。同時，在考慮了不同子網絡之間異質關系的基礎上，算法結合多重子空間的流形約束，利用圖正則化，將中心類型子空間和屬性類型子空間的連接關系（即各個子網絡內蘊的拓撲結構信息）作為約束項，引入到正則化聯合優化算法之中。通過優化法則不斷迭代系數矩陣，找到高維數據在低維空間的緊致嵌入，成功消除了異質節點之間的部分噪聲。

2 算法思想

非負矩陣分解（NMF）算法具有簡便、可解釋性強和存儲空間少等優點，能夠在降維過程中較好地保持信息的完整性。在對異質網絡進行聚類時，它最關鍵的作用是能夠有效地揭示異質網絡中多維數據潛在的結構特征[17-18]。同時，由于NMF算法中分解得到的矩陣元素都必須滿足非負條件，因此該模型幾乎滿足了所有現實數據的物理屬性，可解釋性強。與大多數最先進的無監督算法相比，NMF 顯然擁有更加具有競爭力的性能。然而，當前鮮有將NMF運用于異質網絡聚類的算法，因為直接將NMF 應用于異質網絡聚類，需要向其分解因子矩陣U和V同時施加非負正交的約束，約束太強會使矩陣分解的逼近程度大大降低，從而限制了異質網絡的聚類性能。另一方面，當前算法無法有效解決去噪問題，也難以在同一維度整合異質信息。本文提出的HINGMF算法，優勢主要有以下幾個方面：（1）在非負矩陣分解中，通過引入共識矩陣V*，找到不同類型節點之間有意義且具有可比性的因式分解，從而充分利用了異質信息，讓其在同一維度得到有效整合；（2）通過圖正則化，將中心類型子空間和屬性類型子空間的內部連接關系作為約束項引入非負矩陣分解，結合多重子空間的流形約束，有效利用子網絡拓撲結構信息，達到去噪效果。

在實際生活中，許多的網絡都有一類中心節點，所有的屬性節點都通過中心節點相連接。在異質網絡中，存在著大量的星型結構網絡[18]，多種類型的節點通過同一種中心類型節點聯系在一起。圖1 所示的論文發表網絡即為一種具有星型模式的網絡，由關于研究論文的多種信息組成。每篇論文由一組作者撰寫，使用一組關鍵字，并在會議中發布。這樣的書目網絡由四種類型的對象組成：作者、會議、關鍵字和論文。論文和作者之間存在“被撰寫”和“撰寫”之間的關系，論文和術語之間存在“包含”和“被包含”的關系，而論文和會議則存在“被發表”和“發表”的關系。從圖1 可看出，書目信息網絡呈星形網絡模式，其中論文屬于中心類型，并且所有其他通過論文鏈接的對象，都稱為屬性類型。在書目信息網絡中，存在三個子網絡，分別是：論文-會議網絡、論文-作者網絡、論文-會議網絡。

圖1 星型網絡模型

假設有一個由中心類型和T種屬性類型之間的二分網絡組成的異質網絡，用{X(1),…,X(t),…,X(T)}表示所有子圖的鄰接矩陣，其中X(t)的每一列表示一個中心類型節點而每一行表示一個屬性類型節點。對于每一個子網絡X(t)∈RM(t)×N，希望找到滿足X(t)≈U(t)(V(t))T的低秩因式分解U(t)∈RM(t)×K和V(t)∈RN×K。在這里M(t)是屬性類型t的節點個數，N表示中心類型的節點個數，K代表希望發現的聚類個數。HINGMF 將通過U和V共同揭示異質網絡中隱藏的社區結構。

3 基于圖正則項非負矩陣分解的異質網絡聚類方法

和NMF 算法類似，異質網絡每個子網絡的目標函數為：

||·||F即F范數，U(t)≥0,V(t)≥0 代表對矩陣中每個元素都非負的限制。但是，這種表述假設每個子網都是獨立的，并且無法以統一的方式對異質網絡建模。通過將從子網絡中學到的系數矩陣V(t)與共識矩陣V*之間的差異結合起來，改變目標函數為：

對角矩陣Q(t)定義如下：

在計算誤差之前，將V(t)乘以Q(t)，以確保從不同子網中學習的V(t)具有可比性，在這里||X(t)||1= 1。另外，使用α作為固定參數來調整V(t)和共識矩陣V*差異的權重，文獻[19]表明該參數不太敏感，因此在整個實驗中將其設置為0.1。

文獻[20]表明，重視低維流形的幾何信息可以提高聚類質量。根據流形假設[21]，異質網絡數據經非負矩陣分解后，同類節點間的局部鄰域結構在低維特征空間中能夠得以保持，則當高維空間中距離較近的向量Xi·，Xj·映射到對應的低維流形上Vi·，Vj·時，距離依然較小。從而定義基于用戶子空間的正則項（平滑度懲罰項）為：

tr(·)表示矩陣的跡，W表示正則項權重矩陣，而矩陣D是滿足稱為拉普拉斯矩陣。結合之前的模型得到了一個新的模型：

到目前為止，將整個異質網絡的所有二分子網絡視為同等重要。考慮到不同子網絡的相對權重，通過將一組參數β(t)引入方程來開發自動權重學習策略。采用以指數形式表示的相對權重的原因是為了避免完全有利于具有最小誤差的子網絡，目標函數變為：

RE(t)表示與屬性類型t相關的子網絡的重建誤差：

為了解決上述優化問題，提出了一種迭代優化算法，分為以下三個步驟：（1）初始化，（2）固定V*，更新U和V，（3）固定U和V，更新V*。迭代（2）和（3），直到公式（6）收斂。算法1總結了這個兩步過程。算法流程圖如圖2所示。

圖2 算法流程圖

3.1 初始化

基矩陣U(t)和系數矩陣V(t)的合理初始化在HGNMF算法的整體性能中起重要作用。文中使用各個子網絡中的幾何信息來初始化特定基矩陣和系數矩陣。為實現此目的，每個子網單獨進行NMF聚類，單個子網絡的優化問題可以簡寫為：

文獻[22]提出，可以使用乘法更新過程最小化單獨對子網內部的系數矩陣和基矩陣進行優化。注意，此步驟是針對每個子網絡獨立執行的。則可得到基矩陣和系數矩陣的迭代公式。

圖正則項權重矩陣W可定義為：

其中，N(i)為節點i的k-最近鄰集合，并采用0-1 加權方式創建k-近鄰圖的權重矩陣：如果節點i是節點j的k-近鄰節點，或者節點j是節點i的k-近鄰節點時，Wi,j=1；否則Wi,j=0。

若已知節點i和節點j或節點j和節點i屬于同一類，則Wi,j=1，否則Wi,j=0。

得到U和V后，根據之后推導得到的公式（22）初始化V*。

3.2 固定V*，優化U 和V

一旦V*被固定，則每個子網絡就可以獨立進行優化。對于每個子網絡，將損失函數簡寫如下：

接下來，推導出可用于最小化公式（12）中的優化問題的更新規則。

3.2.1 固定V*和V ，更新U

設ψ為滿足限制條件U≥0 的拉格朗日乘子矩陣，則拉格朗日函數L(U,V)=O(U,V)+tr(ψU)。只考慮包含U的項，可以把L(U,V)重新寫成：

結合式（3）：

R對U進行求導可得：

運用KKT（Karush-Kuhn-Tucker）條件可得：

結合以上條件，可得出以下U迭代公式：

3.2.2 固定V*和U ，更新V

為確保從不同子網中學習的V(t)具有可比性，首先對U的列向量用Q進行正則化：

設Φ為滿足限制條件V≥0 的拉格朗日乘子矩陣，則拉格朗日函數：

和之前的步驟一樣，可以得到V的迭代公式：

3.3 固定U 和V ，優化V*

損失函數O對V*求導：

可以得到V*的迭代式為：

算法1基于圖正則項非負矩陣分解的異質網絡聚類方法

INPUT：HIN{X(1),…,X(t),…,X(T)}，parameters α，number of clusters K

OUTPUT：Clustering on both center type and attribute types

1.Normalize each subnetX(t)such that ||X(t)||1=1

2.InitializeU(t),V(t),V*andβ(t)(1 ≤t≤T)

3.while Eq.6 not converges do

4.for t=1 to T do

5.while Eq.12 not converges do

6.FixingV*,β(t)andV(t),updateU(t)by Eq.17

7.ComputeQ(t)as in Eq.3

8.NormalizeU(t)andV(t)as in Eq.18

9.FixingV*,β(t)andU(t),updateV(t)by Eq.20

10.end while

11.end for

12.FixingU(t)andV(t)(1 ≤t≤T), updateV*andβ(t)by Eqs.22 and 7.

13.end while

14.Cluster nodes of center type indicated by arg maxkVj*,k

15.For each attribute type t，cluster nodes of this type indicated by

3.4 時間復雜度分析

對于每個子網絡，內循環的算術運算并不復雜，這與公式（1）中單個子網絡NMF 的乘法更新規則非常相似。設M為中心類型節點個數，N為屬性節點個數，K為分類個數，T為子網絡個數。分步分析算法的復雜度，更新U的時間復雜度為O(MNK+(M+N)K2+(2N+3)K) ，更新V的時間復雜度為O(MNK+(M+N)K2+2NK)，更新共識矩陣V*時間復雜度為O(TMN)，算法的總復雜度為O(TMNK)。

4 實驗

4.1 實驗數據集

DBLP[5]是計算機領域的英文文獻數據庫，收錄了國際期刊和會議等公開發表的論文。它包含4 023 位作者，20個會議和11 771個關鍵詞，涵蓋了人工智能、信息檢索、數據挖掘和數據庫四個領域。其滿足星型結構，可分為三個子網絡：論文-會議子網絡、論文-作者子網絡、論文-會議子網絡，中心類型節點為論文節點。

Digg[23]數據集是集合了新聞信息和社交信息的網站，用戶可以在該網站上發布、評論新聞，也可以在網站上進行交友活動。Digg 數據集由9 583 個用戶，44 005條新聞和8 596個關鍵字組成，共包含4個興趣小組：游戲小組、政治小組、體育小組和商業小組。在實驗中取其40 000 條數據。其滿足星型結構，可分為兩個子網絡：新聞-用戶子網絡、新聞-關鍵字子網絡，中心類型節點為新聞節點。

Cora[24]論文引用數據集，該數據集由30 714篇學術論文、20 224 位作者以及17 265 個關鍵字組成，共包含7個研究領域：案例學習、遺傳算法、神經網絡、概率方法、增強學習、規則學習、理論研究。數據集中有關鍵字、作者和論文這三種節點，實驗選擇論文作為中心類型節點，兩個子網絡為論文-作者網絡和論文-關鍵字網絡。三個網絡的主要特征如表1所示。

表1 三個數據集的特征

4.2 度量標準

由于實驗選擇的數據集社區結構已知，這里采用兩種通用的評價指標來衡量各種聚類算法的聚類質量：

聚類準確度（AC）[25]：將預測結果與實際標簽做對比。可定義為：

其中，AC為聚類準確率，ci和ci分別為數據點xi的標簽與實際標簽；δ(i,j) 為 delta 函數，如果i=j，δ(i,j)=1，否則δ(i,j)=0 ；map(·) 為最優映射函數。聚類準確率越高，表明聚類算法的聚類質量越好。

標準互信息（NMI）[26]：為了評價社區發現的有效性，引入標準互信息（NMI）指標。通過對比網絡社區結構與算法發現的網絡社區結構的相似性驗證算法的有效性。NMI 的取值范圍為[0，1]，值越大表示劃分得到的社區越接近真實網絡中的社區結構。NMI定義為：

其中，Ni表示聚類標簽與實際標簽集中第i類樣本的數目 (1 ≤i≤k)，Ni,j為第i個類簇中屬于實際的第j類的樣本數目。NMI值越大，這說明算法的社區劃分質量越好。

4.3 實驗結果與分析

為了驗證本文提出的 HINGMF 算法的有效性，本文分別在三個常用的異質網絡數據集：DBLP 網絡、Digg網絡、Cora網絡上進行了驗證，度量標準有聚類準確度和標準互信息，它們都能一定程度地反映算法聚類的效果。之后將其結果與其他三種經典算法進行比較。實驗結果表明，HINGMF算法具有較高的精度和效率，聚類效果要明顯好于其他常用算法。

4.3.1 圖正則項參數λ 的選擇

為了分析圖正則項參數λ對HINGMF 算法聚類質量的影響，從0至0.3選取9個點，調整參數λ的值，對三個數據集進行測試，分析AC和NMI值的變化情況。結果如圖3所示。

從圖3中可以看出，當沒有任何子網絡內部連接信息時，即λ接近0時，算法變為HINMF算法，聚類效果較差。隨著λ的增大，各個子網絡內部拓撲信息被加入，聚類效果逐漸變好。當λ超過0.1 后，不論在DBLP 數據集、Digg 數據集，還是在Cora 數據集上，由于加入過量的子網絡內部連接信息，降低了作為連接所有屬性類型節點的中心類型節點在網絡結構中的重要性，算法的聚類效果開始下降。所以在后續實驗中，圖正則項參數λ均設為0.1。

4.3.2 實驗結果

為了證明所提方法聚類性能的有效性，與以下算法進行了比較。

NetClus[27]：針對異質網絡中大量存在的星型結構網絡，進行了排序迭代聚類，利用排序提高聚類的效果，并且劃分出具有相同星型結構的社區集合。它是目前針對星型網絡比較有效且常用的聚類方法。

NMF-LSE[22]：該算法在非負矩陣分解的基礎上，結合空間流形約束加入了圖正則項，同樣將先驗信息融入圖正則項權重矩陣，將先驗信息與拓撲信息相結合，有效平衡了兩者的關系，提高了聚類的性能。

HINMF[28]：異質網絡非負矩陣分解算法。該算法針對異質網絡中的星型網絡，通過實現各個子網中中心類型節點最小化來平衡不同子網絡之間的差異，但是沒有考慮各個子網內部的拓撲結構，不過依然能夠達到比較好的聚類效果。

表2 記錄了四種方法在不同數據集中的聚類效果。可以看到，HINGMF 的表現要優于其他算法，因為它通過對不同子網絡共有潛在結構的共識矩陣進行學習，充分挖掘并利用了各個子網絡之間的關聯信息，又引入了圖正則項，將中心類型子空間和屬性類型子空間的內部連接關系作為約束項，引進到算法中，有效地利用了子網絡內部拓撲結構信息，成功整合了不同子網之間關聯信息和子網內部幾何信息，去除了部分噪聲，所以算法在數據集上的效果都比較好。而HINMF 算法，同樣考慮了各個子網之間的關聯信息，但是并沒有考慮各個子圖內部節點的幾何信息，從而算法精度較低。而NMF-LSE算法在針對同質網絡進行聚類時能夠有非常好的效果，但是沒有考慮星型結構網絡的各個子網之間的關聯性，所以效果一般。NetClus 算法先對屬性類型節點進行排序，再根據中心類型節點確定聚類對象向量，迭代調整中心類型節點類別，進而完成社區劃分，但是當數據較多時，排序過程耗費時間比較復雜，且排序并不能讓節點精確劃分，故其聚類效果與幾類算法相比不夠理想。

表2 真實數據集中四種算法的性能 %

圖3 參數λ 對實驗效果的影響

當圖正則項權重矩陣中加入先驗信息時，實驗結果如表3所示。可以看到，加入少許先驗信息加入權重矩陣效果要優于采用0-1 加權方式創建的k-近鄰圖權重矩陣，同時避免了計算k-近鄰圖，減少了計算量。當添加的先驗信息只有2%的時候，其聚類效果已經和權重矩陣為k-近鄰圖的原算法相當，之后，隨著先驗信息的增多，其效果遠大于原算法。

表3 加入不同比例先驗信息的聚類效果 %

四種算法的結果對比如圖4所示。可以明顯看到，提出的算法在精度和NMI值兩個指標上明顯要優于其他三個算法。

5 結束語

異質網絡中存在多種不同屬性的節點和關系信息，迫切需要新的方法應對這種需求。本文提出了一種新的異質網絡社區發現方法，該方法在遵循星型異質網絡中不同子網絡中的數據點將以高概率分配給相同聚類原則的基礎上，提出了一種可以融合各個子網絡異質信息的聯合優化算法，該算法對反映了不同子網絡共有潛在結構的共識矩陣進行學習，使用了共識矩陣中每個行向量作為中心類型節點的在每個社區當中的隸屬度分布，通過輪流固定系數矩陣和共識矩陣，迭代對兩個反映不同類型節點的子空間進行優化，從而成功解決了無法有效整合異質信息的問題。同時在降維過程中較大限度地保留了異質信息的完整性。其次，將正則項引入到優化算法之中，結合多重子空間的流形約束，有效利用了各個子網絡的拓撲結構，通過優化法則不斷迭代系數矩陣，找到了高維數據在低維空間的緊致嵌入，成功消除了異質節點之間的部分噪聲。如何優化算法，使算法適用于大規模網絡的分析是本文下一步的研究內容。

圖4 不同算法在不同數據集聚類效果對比