基于張量圖卷積的多視圖聚類①

劉 改,吳 峰,劉詩儀

(西安工程大學 計算機科學學院,西安 710699)

在現實生活中,數據往往可以從不同的來源收集或多個視圖觀察,不同來源獲取的數據形成了多視圖數據.在這些多視圖中,每一個獨立的視圖滿足特定數據分析任務的需求,然而不同的視圖之間往往包含著互補型的數據,此類互補的數據可以提供更加全面的特征信息[1].如何挖掘并利用多視圖數據引起廣泛的關注.數據挖掘常用的方法有分類,聚類等.由于數據獲取的來源增多,數據越發復雜,憑借個人經驗和一些專業知識已不能完成分類任務.因此聚類分析成為一種尋找沒有類別標記數據之間內在結構的關鍵技術[2].傳統聚類算法處理的數據是單視圖的,很難適用于多視圖數據的聚類分析.面對多視圖數據,學者們大致從以下方向進行研究,第一類以Elhamifar 等人[3]為代表的將多視圖數據直接拼接為單視圖數據,由于多視圖數據中含大量重復的數據,此類簡單將其拼接的方法,會帶來維度災難.為了解決上述問題,Kumar 等人[4]提出了只提取多視圖之間的互補性信息以及Brbi?等人[5]僅提取多視圖間的一致性信息來提升聚類效果的方法,然而隨著現有數據的日益復雜,這種單一的提取方法不能夠滿足數據處理的要求.基于此,一些學者提出能夠同時提取互補性和一致性的方法[6].傳統的多視圖聚類方法通常用線性模型和淺層模型揭示復雜多視圖數據之間關系,其學習能力有限.并且,圖形結構信息與數據內在特征無法有效地結合,對聚類效果產生一定的影響.

深層學習因其強大學習能力得到了廣泛的應用,特別是具有強大建模能力的卷積神經網絡.但傳統的卷積神經網絡因其卷積核固定只能處理具有平移不變性的歐氏空間的數據.而現實中,存在著各式各樣的非歐式圖,如社交網絡圖,生物分子結構圖等,此類圖形結構數據中每個節點的局部結構各不相同.圖神經網絡[7]旨在將深度神經網絡應用于結構化數據,由于圖的結構不是規則網格,傳統的卷積神經網絡不易推廣到圖結構數據,因此促使了圖卷積網絡的出現和發展.圖卷積網絡在提取圖的特征和拓撲信息方面是非常重要.Kipf 等人[8]結合深度學習和圖卷積,提出了圖自編碼器.它利用模型學習的結果重構了原始輸入圖的拓撲結構;Bo 等人[9]首次將圖神經網絡用在聚類上,將用于深度提取自身特征的自編碼器與擅長融合鄰居特征圖卷積神經網絡進行結合;Wang 等人[10]提出了一種深度聚類算法,通過圖神經網絡結合自訓練做圖聚類.圖卷積在單視圖的圖聚類得到了很大的發展,但在多視圖上,應用甚少.

針對上述問題,受到TGCN[11]的啟發,本文提出了一種基于張量圖卷積的多視圖聚類方法(TGCNMC).將張量圖卷積應用在多視圖聚類上,通過串聯多個視圖形成張量圖,利用圖內圖卷積分別學習到張量圖中每個圖形信息和數據內在特征,再利用圖間圖卷積,多視圖間進行互相學習,更好的提取圖數據的深層結構以及多視圖數據間的互補信息.此外引入了自監督聚類模型對聚類結果進行優化.

1 相關工作

本文所提算法涉及張量圖卷積神經網絡及多視圖聚類,此節中分別對其進行簡要介紹.

1.1 圖卷積神經網絡

圖卷積神經網絡將卷積網絡應用到實際生活中各式各樣的非歐式圖中,通過消息傳遞來合并圖形結構信息和節點(或邊緣)特征,并計算深度節點的表示.圖神經網絡是一個圖的特征學習的過程,要實現對于圖數據的端對端學習,學習系統必須能夠適配圖數據的內在模式.圖數據中同時包含著兩部分信息:圖中對象的固有性質與對象之間的性質.這種由關聯所產生的結構不僅對圖數據中節點的刻畫具有很大的幫助作用,而且對全圖的刻畫也起著關鍵作用,針對圖數據的學習系統,必須能夠做到對屬性信息和結構信息進行端對端的學習.圖卷積的研究從兩個方面展開,譜域卷積和空域卷積.譜方法是一種圖上的信號處理,把圖上的信號投影到譜域,再與卷積核相乘,最后利用傅里葉逆變換把信號變換到節點域[12].Gori 等人[13]首次提出了圖神經網絡;Bruna 等人[14]從卷積定理出發,定義了譜空間的卷積,由于該方法空間復雜度高;Defferrard 等人[15]提出了用切比雪夫多項式來近似卷積核,不需要做特征分解,將計算復雜度降低.在這兩種方法啟發下,Kipf 等人[7]通過堆疊多個卷積層建立了一個GCN 模型,他提出的圖卷積神經網絡可以看作是譜方法和空間方法的融合.此外,受傳統自動編碼器的啟發,Kipf等人[8]結合圖卷積神經網絡提出了圖自動編碼器(GAE),在編碼層利用圖卷積神經網絡作為編碼器將圖結構集成到節點特征中,學習節點嵌入.GAE 沒有像自編碼器一樣恢復輸入的特征,而是重建圖,因為節點的連接可以被視為弱監督信息[16].具體地說,解碼器計算任意兩個節點之間的內積,然后將它們映射到一個概率空間中,通過Sigmoid 函數來模擬相似性.隨著卷積算子的逐漸完善,多種多樣的圖特性成為人們的關注點.圖卷積也被應用到各個領域,例如,網絡分析[17],生物化學[18],自然語言處理[19]等.

1.2 多視圖聚類

給定一個標簽未知的多視圖數據集,多視圖聚類算法挖掘并利用不同視圖之間的一致性信息和互補性信息,構建并學習共識函數,融合不同視圖,最后將每個數據樣本劃分到相應的類中.多視圖聚類作為一個新興的研究領域,獲得了國內外學者的廣泛研究,Chao等人[20]對多視圖聚類的研究做了綜述性介紹;De Sa[21]率先研究了兩個視圖數據的譜聚類,基于最小化不一致性準則提出一種由二部圖構建的譜聚類算法;Zhou 等人[22]通過歸一化圖切割算法從單視圖聚類擴展到多視圖聚類;Cheng 等人[23]結合協同正則化技術提出一種多視圖的圖聚類算法;Zhan[24]將圖拉普拉斯矩陣融合的方法用于多視圖數據聚類.此類傳統多視圖聚類方法通常是線性模型和淺層模型,揭示復雜多視圖數據關系的能力有限.

2 模型與算法

在本節將詳細介紹本文提出的基于張量圖卷積的多視圖聚類網絡(TGCNMC).如圖1所示,網絡結構主要由兩個部分組成.基于張量圖卷積的圖自編碼器模塊和自監督圖聚類模塊.

圖1 基于張量圖卷積的多視圖聚類框架圖

2.1 張量圖自編碼器

為更加全面的學習多視圖數據的信息,本文提出了基于圖卷積設計了一個可全面融合多視圖信息的張量圖自編碼器.其中通過基于張量圖卷積的圖自編碼器學習共同的潛在表示.此外,設計了多視圖解碼器從學習表示中重建多視圖圖數據.

假設一個無向圖G=(V,E),其中|v|=n表示圖G中有n個節點,E表示邊的集合,對于每個節點i均有特征xi,用矩陣Xn×d表示,則將特征矩陣X和鄰接矩陣A構成GCN 的輸入.

本文中圖自編碼器編碼部分由兩層構成.第一層由傳統的圖卷積層,輸入多視圖數據和相應圖將多視圖串聯為一個張量圖進行圖內卷積,用于聚合圖中每個節點鄰居的信息.因此,套用式(2),可以得到式(3).

第二層做圖間圖卷積,是在張量圖中不同的圖間進行傳遞信息,使不同的圖的異構信息就可完整地融合成一個一致的信息.張量圖中的所有圖共享節點集,將張量圖中每張圖的同一個節點相互連接,最終,得到了n個虛圖,虛圖中的所有節點都相互連接,并且邊權值設置為1,使異構信息更有效地融合在一起.從而得到了一個新的圖鄰接張量圖間圖卷積如式(4)所示.

在完成圖間圖卷積后,對得到的圖進行平均池化,用來得到要聚類的文檔節點的最終表示.

為監督張量圖卷積編碼器學習的融合表示,采用多組圖解碼器從嵌入表達Z重建多視圖圖數據由于學習到的表示已經包含了內容和結構信息,因此采用特定的解碼器來預測節點之間的鏈接,如式(5).

其中,σ是邏輯符號函數.重構的鄰接矩陣的元素是通過做了一個非線性變換.其中Wm是第m個特定解碼器中學到的參數矩陣.在x較大的時候,采用φ(x)可以更好的逼近y=x,φ(x)函數更好地對節點對的內積進行映射.

2.2 自監督模型

圖聚類是一個無監督的任務,在訓練的過程中不了解學到的嵌入是否有好的優化.受到DEC[9]的啟發,本文使用一種自監督的嵌入算法作為監督優化.自監督模型就是對圖自編碼器所學習到的嵌入進行約束和整合,使其更適合于聚類任務.

給定初始簇質心μj,使用t分布作為核來衡量嵌入表示點zi和質心μj之間的相似性.

分配樣本i到集群j的概率為qij,也稱為軟分配分布.進一步的,聚類信息來實現聚類導向的節點表示.為實現類內距離最小,類間距離最大.因此,定義了如下的目標分布:

最后,通過計算兩個分布之間的交叉熵,來實現互相約束,也就是所謂的自監督:

本文TGCNMC 總損失由兩部分構成如下所示:

其中,Lr和Lc分別為重建損失和聚類損失,γ ≥0是一個控制兩者之間平衡的系數.

3 實驗分析

在公開的數據集上對本文提出的算法與經典的深度聚類算法進行對比實驗,來驗證本文所提出方法的有效性.

3.1 數據集

DBLP 是一個引用網絡數據集,此數據集來自于DBLP,ACM,MAG 和其他來源中提取的一個具有多重屬性圖的單視圖數據,按照在文獻[25]中的設置來構建多視圖數據集.分別利用同一篇論文中合作關系同一會議發表論文和兩位作者發表了相同術語的論文這3 種關系來構建3 個不同視圖.按此方法構建的多視圖數據集避免了在視圖收集中某個視圖的部分數據缺失問題.

ACM 數據集包含出版KDD,SIGMOD,SIGCOMM,MobiCOMM 和VLDB 和被分為3 類的論文.該數據集包含3 025 篇論文,5 835 名作者和56 個主題.分別利用兩篇論文由同一作者撰寫關系和兩篇論文包含相同的主題關系,構建了兩個視圖.

IMDB 是一個電影網絡數據集.利用電影由同一演員表演和電影由同一導演兩組關系來構建兩個視圖.對數據集的詳細描述見表1.

表1 本文所用數據集

3.2 參數及指標

算法運行環境:PyCharm 2020;加速環境:Cuda_10.2;操作系統:Windows 10;深度學習框架:TensorFlow 1.15.0;語言環境:Python 3.7.

本文訓練所有與自動編碼器相關的模型(GAE、O2MAC、DCNS、TGCNMC)進行1 000 次迭代,使用Adam 算法進行優化,學習率λ設置為0.001.所有嵌入方法的維數均為32.對于O2MAC,收斂閾值設置為δ=0.1%,更新間隔為T=20.對于其余的參數,采用了在相應的論文中所描述的設置.由于所有的聚類算法都依賴于初始化,本文使用隨機初始化重復所有的方法重復10 次,并報告平均性能.

評估指標:使用4 種評價指標來評判聚類效果:聚類準確性ACC,標準化互信息NMI,調整蘭德系數ARI和F值F1.一般來說,這4 種指標的值越高,就表示聚類效果更好.

3.3 對比試驗

實驗對比當前主流深度學習聚類算法,來對所本文提出算法性能進行驗證.GAE[8]將圖上的光譜卷積移植到自編碼器框架上的方法;SDCN[9]方法使用圖卷積神經網絡和自動編碼器共同構建聚類網絡.并提出自監督模塊對圖卷積模塊和自動編碼器模塊的參數進行更新.SwMC[26]為一種自加權多視圖圖聚類方法.通過引入自權重參數,學習一個拉普拉斯秩約束的相似圖;O2MAC[26]為一對多視圖自動編碼聚類方法,一對多視圖圖自編碼器能夠通過使用一個信息圖視圖和內容數據來重建多個圖視圖來學習節點嵌入.

3.4 實驗結果

所提出的算法在3 組數據集上與當前的一些聚類方法的性能對比見表2.實驗分析如下.

表2 不同數據集上聚類效果對比

與多視圖模型SwMC 對比分析.首先可以看出,本文提出的基于GCN 的方法比基于圖的淺層方法SwMC 的性能更好,證實了圖卷積網絡將相鄰信息與節點特征結合起來是有用的;其次,因為SwMC 是一種兩步融合方法,而且這種混合操作可能會引入噪聲.使用簡單的多視圖加權處理的SwMC 并不能提高結果.因此,本文提出的端到端融合的模型,可以更好的完成聚類任務.

O2MAC 模型使用挑選信息量最為豐富的視圖作為輸入,對視圖間互補性信息捕獲不佳.而本文為了更好地提取各個視圖結構,將所有視圖作為TGCNMC 的輸入,對3 種視圖數據進行串聯,各個視圖間分別進行圖內學習以及視圖間的互相學習,更加完整的揭示多視圖數據中的一致性與互補性信息.通過與O2MAC模型對比,可以看出本文提出的模型在ACC、NMI 等評價指標上有一定的提升,得到更好的聚類結果.驗證張量圖卷積的有效性.

此外本文通過相同數據集下與單視圖聚類模型GAE 及SDCN 進行實驗與O2MAC 及本文提出的方法TGCNMC 進行對比,可以看出多視圖聚類方法的性能優于具有最佳視圖結果的單一聚類方法

4 結論

本文研究了深度學習下的多視圖聚類,旨在通過圖神經網絡來挖據多視圖數據的互補性信息和一致性信息,更加全面的描述數據.因此,本文提出了一種基于張量圖卷積的多視圖聚類方法.此方法將多視圖串聯為張量圖,采用圖內圖卷積來聚合各個視圖中來自鄰居節點的信息,再利用圖間卷積來進行多個視圖間的信息的交換學習,有效地挖掘了多視圖的一致性及互補性信息.此外本文還引入了一個自監督聚類模型來優化聚類結果,使特征空間更適合聚類.通過將其實驗結果與幾種典型的算法進行了比較,驗證了該方法的有效性.