屬性異構信息網絡的半監督協同聚類

劉嘎瓊, 韓 斌, 王東升, 嚴 熙, 李會格

(江蘇科技大學 計算機學院, 江蘇 鎮江 212100)

異構信息網絡(heterogeneous information networks, HINs)由多個節點及其之間的關系組成, 用于對復雜數據集進行建模[1]. 與傳統的節點和邊都屬于單一類型的同構網絡相比, HINs能有效地融合更多的結構信息, 具有更豐富的語義[2]. 因此, 如何建立高效的HINs對于數據挖掘至關重要[3].

目前, 元路徑被廣泛用于提取HINs節點間異構連接的結構語義. 熊菊霞等[4]提出了獲取不同類型節點語義的元路徑, 并提出了評價HINs中相同類型節點相似度的路徑模型. 考慮到不同元路徑的影響, 張文凱等[5]提出了將多條元路徑的相似性度量相結合. 但這些方法都是主要利用HINs的結構信息, 忽略了節點的屬性, 因此導致隱藏信息未得到充分挖掘. 為描述HINs中的順序屬性和分類屬性, 一種有效的方法是將節點的屬性視為向量, 其中每個維度表示一個屬性. 史加榮等[6]通過將不同元路徑的節點相似性與權重相結合, 設計了一種無監督的負矩陣分解算法; 朱超平等[7]通過分別構造鏈接圖和屬性圖整合結構信息和屬性信息. 但目前的研究主要集中在對同一類型節點的相似性搜索上, 而未對HINs中不同類型節點的聚類進行聯合分析. 實際上, 由于不同類型節點之間潛在的相關性(相似性), 不同類型的聚類通常是相互關聯的.

與傳統聚類方法不同, 協同聚類利用特征和樣本之間的對偶性, 實現特征和樣本的同時聚類. 此外, 協同聚類方法能在不同節點類型的聚類之間獲得潛在的對應關系, 從而使得到的聚類更具可解釋性. 董立巖等[8]將文檔視為一個二部譜圖, 然后根據圖尋找最小割點劃分對文檔和單詞進行聯合聚類; 夏菁等[9]提出了同時對基于元路徑的相似度矩陣進行因子分解, 實現了不同類型節點的聯合聚類; 周慧等[10]提出通過測量紋理視圖和顏色視圖等視圖中節點的相關性對多視圖數據進行聯合聚類. 但這些模型在處理屬性HINs時, 由于存在基于結構和屬性的多個相關度量, 無法對HINs進行聚類.

為解決上述問題, 本文提出一種基于屬性異構信息網絡的半監督協同聚類框架(SCCAIN). 該方法利用多條元路徑和可學習的權值對結構進行度量關聯性和不同空間屬性的參數化屬性關聯度量. 在3個數據集上的實驗驗證了本文方法的有效性.

1 預備知識

定義1異構信息網絡(HINs)表示為G={V,ε,T,R}, 其中V是節點集,ε是鏈接集,T是節點類型集,R是關系或鏈接類型集. 在HINs上有兩個映射函數, 一個是節點類型映射φ:V→T, 以獲取節點類型, 另一個是鏈接類型映射ψ:ε→R, 以獲取鏈接類型. 其中|T|+|R|>2.

定義2屬性HINs是一種特殊類型的HINs, 其形式為G={V,ε,F}. 與傳統的HINs相比, 屬性HINs具有豐富的屬性信息, 即F={fv}, 其中fv是節點v的屬性向量.

異構節點的屬性向量可能具有不同大小和含義. 以圖1為例, 有3種類型的節點, 即T={A,P,C}, 2種類型的鏈接. 此外, 作者和會議都包含向量形式的幾個屬性. 由于作者和會議的屬性表示不同的含義, 因此分別使用平行四邊形和正方形區分.

設A,P,C分別表示作者、論文和會議, 作者的屬性是他們感興趣的研究領域, 包括網絡嵌入、異常檢測、非負矩陣分解(NMF)和共聚類, 而會議的屬性是諸如聚類、主題建模和推薦系統等主題.

圖1 屬性化異構信息網絡示例Fig.1 Example of attributive heterogeneous information networks

如圖1所示, 元路徑A-P-C的源節點和目標節點是作者和會議. 此外, 不同的元路徑將捕獲不同的語義, 有助于聚類. 例如,A4和C3可以通過A-P-C或A-P-A-P-C連接, 第一個元路徑表示發布, 而第二個元路徑是通過共同作者捕獲作者和會議的相關性.

屬性HINs的半監督協同聚類問題： 給定一個屬性HIN, 其形式為G={V,ε,F}, 一些連接源節點Vs和目標節點Vt的元路徑, 以及一些節點之間的必須鏈接Mss,Mst,Mtt和不能鏈接Css,Cst,Ctt約束, 目標是同時考慮結構及屬性信息, 并生成具有整體相關性矩陣X的Vs和Vt的聚類. 特別地,Vs和Vt分別表示X的行實例和列實例. 此外,M/C的下標表示約束的類型. 例如,Mst是Vs和Vt之間必須連接的約束.

2 方法設計

2.1 總體框架

圖2為SCCAIN的總體框架. 在該框架中, 首先, 分別設計基于元路徑Λ重要性的結構相關性度量和基于潛在參數A的屬性相關性度量, 考慮到這兩種相關性, 本文將它們組合成一個整體相關性度量; 其次, 設計一個基于非負矩陣三因子分解(ONMTF)的半監督協同聚類模型, 該模型將相關性矩陣分解為S和T這兩個聚類分布, 以及一個輔助矩陣W. 此外, 由于相關性度量和協同聚類的性能相互影響, 因此將這兩部分整合到一個聯合的框架中, 并對其進行優化, 從而得到最終的異構節點聚類結果.

圖2 SCCAIN的總體框架Fig.2 Overall framework of SCCAIN

2.2 屬性HINs的相關性度量

2.2.1 結構相關性

采用異構網絡中相關性度量的通用框架(HeteSim)度量第i個s型節點與第j個t型節點之間的相關性, 表示為

(1)

其中vs,i和vt,j分別表示第i個源節點和第j個目標節點,HS(vs,i,vt,j|R1°…°Rl)為元路徑R1°R2°…°Rl上vs,i和vt,j之間的HeteSim值,O(vs,i|R1)為基于關系R1的vs,i的外鄰域,I(vt,j|Rl)為基于關系Rl的vt,j的內鄰域. 如果vs,i′=vt,j′, 則HS(vs,i′,vt,j′|R(l+1)/2)=1, 否則為0. 與傳統的只計算同構節點相似度基于元路徑的相似度算法(PathSim)或相關性不對稱的路徑約束隨機游走模型(PCRW)不同, HeteSim可以度量不同類型節點的相關性.

考慮到存在多個元路徑, 每個元路徑表示一種形式的結構相關性, 如圖2所示, 這里將元路徑重要性權重λP分配給具體的相關性HS(vs,i,vt,j|P), 然后計算結構相關性, 即

(2)

2.2.2 屬性相關性

給定第i個源節點的特征fs,i和第j個目標節點的特征ft,j, 不可能直接度量fs,i和ft,j的相關性. 通過將不同空間中的屬性映射到同一空間中, 進一步計算vs,i和vt,j的屬性相關性度量：

(3)

其中XA是屬性相關性矩陣,A∈RDs×Dt是不同空間的屬性向量的相關參數,σ(·)是激活函數, 采用ReLU函數保持屬性相關性為正.

2.2.3 整體相關性

SCCAIN綜合考慮了結構信息和屬性信息, 根據兩個節點的結構相關性和屬性相關性對節點的整體相關性進行評估. 通過設置一個平衡參數α∈[0,1],vs,i與vt,j的整體相關性定義為

X(vs,i,vt,j)=αXA(vs,i,vt,j)+(1-α)XL(vs,i,vt,j|Λ).

(4)

為更有效地學習參數, 本文利用附加約束指導優化, 相應的帶約束損失函數表示為

(5)

其中m表示標簽的數量,MCi,j表示不同類型節點的約束. 根據給定的必須鏈接集Ms,t和不能鏈接集Cs,t, 當Mst,i,j=1時,MCi,j=1； 當Cst,i,j=1時,MCi,j=0,Xi,j=X(vs,i,vt,j). 這些約束以及對同一類型節點的約束, 也可以用于指導協同聚類.

2.3 半監督協同聚類

本文設計了具有正交限制的半監督非負矩陣三因子分解, 以同時對不同類型的節點進行聚類:

(6)

2.4 聯合優化

給定不同類型的節點Vs和Vt, 目標是利用結構信息和屬性信息以及一些約束同時對Vs和Vt進行聚類. 為在該模型中同時優化協同聚類和相關性度量, 本文設計一個聯合模型學習相應的參數, 包括元路徑的權重Λ以及聚類分布S和T.即將相關性矩陣X視為一個與參數Θ={Λ,A}有關的變量X(Θ), 損失函數表示為

L=L1(Θ)+L2(Θ)+γ(‖Θ‖2).

(7)

在SCCAIN中, 使用迭代更新方法學習參數Θ和(S,W,T), 并且每次迭代均由以下兩個步驟組成.

1) 用固定的Θ更新S,W,T.給定Θ, 該步驟的主要目標是選擇半監督協同聚類模型的解(S,W,T). 有固定的X, 則L可表示為

(8)

在這個函數中有3個參數帶有約束, 分別固定其中兩個參數優化另一個參數:

(9)

(10)

(11)

為獲得準確的S,W,T, 迭代更新這3個參數, 直到它們穩定為止. 在更新過程完成后, 固定S,W,T以優化相關性度量.

2) 用固定的S,W,T更新Θ.對于固定的S,W,T,L是Θ={Λ,A}的函數, 全局損失函數等價于

Lrele=‖X(Θ)-SWTT‖2+γ(‖Θ‖2),

(12)

其中X(Θ)由式(4)和參數Θ計算得出,SWTT為固定值. 此外, 考慮到Λ≥0, 本文用max{0,λP}更新λP.

最后, 分別從優化后的S和T獲得源節點Gs的聚類和目標節點Gt的聚類. 其中,

相應的算法描述如下.

算法1

輸入： 不同類型的節點Vs和Vt;

輸出： 元路徑的權重Λ以及聚類分布S和T;

步驟1) 初始化相應參數γ

步驟2) do

步驟3) 固定Θ更新S,W,T

步驟4) 根據式(7)計算損失函數

步驟5) until收斂

步驟6) do

步驟7) 固定S更新Θ,W,T

步驟8) 根據式(7)計算損失函數

步驟9) until收斂

步驟10) do

步驟11) 固定W更新S,Θ,T

步驟12) 根據式(7)計算損失函數

步驟13) until收斂

步驟14) do

步驟15) 固定T更新S,W,Θ

步驟16) 根據式(7)計算損失函數

步驟17) until收斂

步驟18) 從優化后的S和T獲得源節點Gs的聚類和目標節點Gt的聚類.

3 實 驗

3.1 數據集和指標

表1列出了3個公共數據集的信息, 即Aminer,DBLP和一個Alibaba推薦數據集.

表1 數據集信息

1) Aminer數據集是一個公共基準數據集, 由作者(A)、論文(P)和會議(C)三種類型的節點組成, 相應的關系包括“發布”(P-C)、“參與”(A-C)和“寫”(A-P). 有5個主要研究領域: 數據挖掘、醫學信息學、理論、可視化和數據庫, 每個節點都被分配到一個特定的領域. 這里專注于同時對作者和會議進行聚類, 基于A-P-C,A-P-A-P-C和A-P-C-P-A-P-C三個元路徑計算結構相關性. 作者和會議的屬性都是相關的論文摘要, 利用doc2vec將文本建模為密集向量.

2) DBLP數據集是一個公共子網絡, 涉及4個研究領域的主要會議： 數據庫、數據挖掘、人工智能和信息檢索. 有4種類型的節點: 作者(A)、論文(P)、會議(C)和主題(T). 在該網絡中, 也關注作者和會議的協同聚類. 基于A-P-C,A-P-T-P-C和A-P-A-P-C三個元路徑計算結構相關性. 這里將在20個會議上由作者撰寫的論文數量設置為作者的屬性, 并將通過元路徑C-P-A-P-C的鏈接數量設置為會議的屬性.

3.2 實驗設置

首先將SCCAIN與其他三種協同聚類方法和兩種圖嵌入方法進行比較； 然后通過比較SCCAIN及其改進版本SCCAIN(L)和SCCAIN(A)分析屬性和結構的貢獻, 其中前者專注于屬性, 而后者專注于結構[12].

DNMTF是一種矩陣三因子分解方法, 可在協同聚類時同時優化矩陣因子分解和圖對偶正則化. 為公平比較, 將節點的k最近鄰和成對約束都設置為對偶正則化. 這里利用屬性HINs中的鏈接作為輸入矩陣. CPSSCC是一種半監督協同聚類方法, 該方法同時利用行約束投影和列約束投影在低維空間中引導聚類源節點和目標節點. ONMTF(HS)是一個非負矩陣三因子分解, 與文獻[13]中提出的傳統ONMTF不同, 本文利用多個元路徑的平均相關性作為相似度矩陣, 并在訓練過程中結合成對約束討論學習相關性度量的有效性. GCN(K)是一種流行的屬性圖嵌入學習方法, 該方法聚合圖信息以重建節點嵌入, 利用監督信息生成節點的基本嵌入, 并采用K均值方法分別對每種類型的節點進行聚類. H2V(K)是一種具有K均值的異構圖嵌入模型, H2V根據異構邊緣對鄰居進行采樣, 并學習節點和邊緣的嵌入. 在該模型中, 將成對約束整合到圖中以進行公平比較[14].

對于SCCAIN, 將學習率設為0.001, 最大迭代次數設為200,γ設為0.01. 利用Adam最小化L1的損失. 由于必須鏈接和不能鏈接對是作為監督信息提供的, 因此可通過交叉驗證調整α. 對于Aminer,DBLP和Alibaba數據集, 本文分別生成固定數量的必須鏈接和不能鏈接的鄰居作為總約束, 然后采樣2.5%,5%,7.5%,10%的約束進行學習. 基線和SCCAIN都運行10次, 并將平均值報告為性能. 采用標準化互信息NMI∈[0,1]和純度Purity∈[0,1]作為度量指標, NMI或Purity值越大, 表示性能越好.

3.3 對比分析

表2列出了3個不同尺度數據集上的NMI和Purity值. 對于DBLP和Aminer, 源節點和目標節點分別表示作者和會議; 對于阿里巴巴, 源節點和目標節點分別表示用戶和項目. 本文比較了所提出方法在源節點和目標節點聚類上的性能. 圖3為協同聚類可視化, 用于描述檢測異構集群之間潛在關聯的性能.

3.3.1 協同聚類的性能

由表2可見, SCCAIN對于3個數據集均達到最佳性能. 與DNMTF,CPSSCC,ONMTF(HS)相比, 本文主要的改進為可學習的整體相關性； 與GCN(K)和H2V(K)相比, 本文方法是一個同時考慮屬性和結構的HINs統一模型. 此外, 由于該網絡的稀疏性, DNMTF和CPSSCC在Alibaba數據集上的表現較差.

表2 3個不同尺度數據集上的NMI和Purity值

在半監督的情況下, 即存在約束率條件下, SCCAIN在源節點的聚類和目標節點的聚類性能比多數方法有明顯優勢, 表明SCCAIN在沒有太多約束的情況下能極大提升聚類效果. 但其他一些模型, 如GCN(K)和DNMTF, 其性能在很大程度上依賴于監督信息的規模, 且其增長速度慢于SCCAIN. 與采用靜態相關性的ONMTF(HS)相比, SCCAIN由于采用了自適應總體相關性度量, 因此其在半監督條件下即可得到良好的聚類性能.

3.3.2 協同聚類可視化

本文模型是同時聚類不同類型的節點, 可通過設置Aminer數據集上的協同聚類作為例子分析這些聚類的相關性. 由圖3可見, 根據作者的聚類和會議的聚類, 重新排列了DNMTF,ONMTF(HS),SSCAIN的關聯矩陣, 然后顯示相應的矩陣可視化, 色塊越深表示聚類的相關性越高. 通過比較圖3(A)～圖3(C)中的塊可見, SCCAIN由于明顯的塊而具有更好的檢測不同類型聚類相關性的能力, 這有助于將這些信息用于推薦系統和其他一些有價值的任務.

圖3 具有10%約束的Aminer數據集上協同聚類的相關性Fig.3 Correlation of collaborative clustering on Aminer data set with 10% constraint

3.4 模型分析

3.4.1 消融性

本文將SCCAIN與SCCAIN(L)和SCCAIN(A)的性能進行比較, 結果如圖4所示. 由圖4可見, 與SCCAIN(A)和SCCAIN(L)相比, 本文模型在這3個數據集上的表現都更好. 在Aminer數據集和DBLP數據集上, SCCAIN(L)的性能優于SCCAIN(A), 但SCCAIN(A)在Alibaba數據集上更好. 實驗結果表明了整合屬性信息和結構信息進行協同聚類的有效性. 此外, 盡管SCCAIN具有相似的結構, 但由于其具有自學習元路徑權值, 因此比ONMTF(HS)更好.

圖4 SCCAIN(A),SCCAIN(L),SCCAIN在協同聚類上的NMI性能Fig.4 NMI performance of SCCAIN(A),SCCAIN(L) and SCCAIN in collaborative clustering

3.4.2 收斂性和參數分析

為分析SCCAIN的收斂性, 本文將最大迭代次數從0增加到200, 并通過不同的監督信息展示SCCAIN的NMI值, 結果如圖5所示. 由圖5可見, 隨著3個數據集上監督信息的增加, SCCAIN可更快地收斂, 這驗證了監督信息以及優化框架的有效性.

為分析平衡參數α的影響, 將其從0調整為1, SCCAIN的NMI值的變化如圖6所示. 由圖6可見, 通過比較每個數據集的性能, 發現合適的α可以提高聚類的NMI值. 通過比較不同數據集上的性能趨勢, 可觀察到α在Aminer數據集上更敏感. 這是因為Aminer數據集上作者和會議的屬性是相關抽象向量的平均值. 此外, 若屬性相關性過強(即α≥0.5), 則可能很難區分作者或會議. 一方面, 一個會議的論文通常屬于多個領域, 因此它們屬性向量的平均值在許多不同會議中可能很相似； 另一方面, 由于語料庫較小, 因此在建模抽象文本的表示時可能會存在噪聲信息. 在DBLP和Alibaba 數據集上, 穩定的性能表明可以更容易地學習節點屬性的相關性, 以幫助進行協同聚類.

圖5 不同迭代次數的DBLP,Aminer,Alibaba數據集上SCCAIN的NMI值Fig.5 NMI values of SCCAIN on DBLP,Aminer,Alibaba data sets with different iterations

圖6 不同α的DBLP,Aminer,Alibaba數據集上SCCAIN的NMI值Fig.6 NMI values of SCCAIN on DBLP,Aminer,Alibaba data sets with different α

綜上所述, 為了同時利用屬性信息和結構信息實現更精確的協同聚類, 本文提出了一種基于屬性異構信息網絡的半監督協同聚類框架. 通過分析數據集實驗結果表明： 該方法在沒有太多約束的情況下能極大提升聚類效果, 實現良好的信息挖掘； 由于采用了自適應總體相關性度量, 且能同時利用屬性信息和結構信息, 因此其在半監督條件下即可得到良好的聚類性能； 自學習元路徑權值的引入能使本文方法在不同的約束率條件下保持較好的聚類效果, 監督信息的增加可加快收斂速度.