基于子圖分解的圖聚類神經(jīng)網(wǎng)絡(luò)

鄧祥　俞璐　姚昌華　朱瑾

摘? 要： 聚類是機(jī)器學(xué)習(xí)的核心任務(wù)之一，其主要目的是將無標(biāo)簽數(shù)據(jù)中的不同簇?cái)?shù)據(jù)進(jìn)行分離。深度聚類算法使用深度神經(jīng)網(wǎng)絡(luò)聯(lián)合優(yōu)化聚類目標(biāo)與特征提取，極大地提高了聚類性能。圖聚類是深度聚類領(lǐng)域近兩年研究的一個重要分支，其在處理圖結(jié)構(gòu)數(shù)據(jù)上有極大的優(yōu)勢。提出一種新的圖聚類方案：基于子圖分解的圖聚網(wǎng)絡(luò)，該模型在圖自編碼器的基礎(chǔ)上通過構(gòu)建多個子圖，并在子圖的嵌入空間中加以組稀疏約束達(dá)到最終的聚類目的。

關(guān)鍵詞： 模式識別; 圖神經(jīng)網(wǎng)絡(luò); 深度學(xué)習(xí); 深度聚類

中圖分類號：TP181? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ?文章編號：1006-8228（2022）05-06-05

Graph clustering neural network based on subgraph decomposition

Deng Xiang Yu Lu ?Yao Changhua ?Zhu Jin

Abstract： Clustering is one of the core tasks of machine learning. Its main purpose is to separate different cluster data from unlabeled data. Deep clustering algorithm uses deep neural network to jointly optimize clustering objectives and feature extraction， which greatly improves the clustering performance. Graph clustering is an important branch in the field of deep clustering in past two years. It has great advantages in processing graph structure data. In this paper， a new graph clustering scheme， graph clustering network based on subgraph decomposition， is proposed. Based on graph Auto-encoder， this model achieves the final clustering purpose by constructing multiple subgraphs and imposing group sparse constraints in the embedded space of subgraphs.

Key words： pattern recognition; graph neural network; deep learning; deep clustering

引言

聚類任務(wù)的主要目的是把相似的數(shù)據(jù)聚成一簇，其關(guān)鍵是如何有效地度量樣本之間的相似性。在人工數(shù)據(jù)集中由于數(shù)據(jù)沒有冗余信息、具有分離的數(shù)據(jù)結(jié)構(gòu)所以聚類難度較低。在大數(shù)據(jù)時代數(shù)據(jù)包含了大量的冗余信息且有高度復(fù)雜的結(jié)構(gòu)，極大地增加了聚類的難度，所以近些年的聚類算法更多的關(guān)注如何進(jìn)行特征提取，在保持有效特征的同時去除冗余噪聲的干擾以降低聚類的難度。

隨著近些年深度學(xué)習(xí)的發(fā)展，神經(jīng)網(wǎng)絡(luò)的表示學(xué)習(xí)能力越來越強(qiáng)，因此使用神經(jīng)網(wǎng)絡(luò)進(jìn)行特征處理是現(xiàn)如今聚類方案應(yīng)對復(fù)雜數(shù)據(jù)集的方法之一?；谏疃葘W(xué)習(xí)的聚類方案主要有兩種方式。其一是使用神經(jīng)網(wǎng)絡(luò)進(jìn)行無監(jiān)督特征學(xué)習(xí)，學(xué)得一個高維數(shù)據(jù)的低維嵌入，之后在這個低維嵌入特征上進(jìn)行傳統(tǒng)聚類。這類方法雖然在一定程度上去除了冗余噪聲，但是由于缺少全局的聚類聚目標(biāo)函數(shù)，導(dǎo)致提取的特征不是利于聚類的特征，并沒有充分地發(fā)揮神經(jīng)網(wǎng)絡(luò)的優(yōu)勢。其二是以聚類目標(biāo)為導(dǎo)向的深度聚類方案，讓聚類目標(biāo)指導(dǎo)神經(jīng)網(wǎng)絡(luò)的特征提取工作，使神經(jīng)網(wǎng)絡(luò)提取的特征是利于聚類的特征。這種方案可以更好地利用神經(jīng)網(wǎng)絡(luò)的表示學(xué)習(xí)能力和非線性逼近能力，可以很好地處理現(xiàn)如今越加復(fù)雜的數(shù)據(jù)集。

1 相關(guān)工作

1.1 相關(guān)理論

近年來隨著深度聚類不斷發(fā)展涌現(xiàn)出了大量杰出的算法，根據(jù)深度聚類算法所使用的神經(jīng)網(wǎng)絡(luò)不同，文獻(xiàn)[1，2]將現(xiàn)有的深度聚類方法劃分為基于不同神經(jīng)網(wǎng)絡(luò)的聚類方法，其大致可以分為以下幾個類別：基于自編碼器的聚類算法、基于生成對抗網(wǎng)絡(luò)的聚類算法、基于變分自編碼器的聚類算法等。發(fā)展這些基于不同神經(jīng)網(wǎng)絡(luò)的深度聚類算法的目的是為了應(yīng)對不同類型、不同應(yīng)用環(huán)境的復(fù)雜數(shù)據(jù)集。

以上這些深度聚類算法能夠處理大多數(shù)的結(jié)構(gòu)化數(shù)據(jù)，但面對非結(jié)構(gòu)化數(shù)據(jù)如圖數(shù)據(jù)集時卻無能為力。而近兩年，隨著圖神經(jīng)網(wǎng)絡(luò)的提出，非結(jié)構(gòu)化數(shù)據(jù)的處理不再是一個困擾性的問題，因此人們期望借助圖神經(jīng)網(wǎng)絡(luò)的能力來獲取無標(biāo)簽數(shù)據(jù)的簇結(jié)構(gòu)信息，以此來提取利于聚類的特征表示，達(dá)到提升聚類效果的目的。

基于圖神經(jīng)網(wǎng)絡(luò)的深度聚類模型中較成功的有Embedding Graph Auto-Encoder（EGAE）[3]，DeepAttentional Embedded GraphClustering（DAEGC）[4]，Structural Deep Clustering Network（SDCN）[5]，adaptive graph convolution （AGC）[6]，Adversarial Graph Auto-Encoders（AGAE）[7]等。其中AGAE的輸入是相似性矩陣，利用圖卷積神經(jīng)網(wǎng)絡(luò)處理相似性矩陣提取特征，并把它與特征先驗(yàn)分布中得到的特征一同進(jìn)行對抗性訓(xùn)練， 得到一個能完成聚類的概率分布。DAEGC將注意力機(jī)制引入圖神經(jīng)網(wǎng)絡(luò)，在圖自編碼器的圖結(jié)構(gòu)重構(gòu)過程中關(guān)注邊的權(quán)重變化，之后在這個圖神經(jīng)網(wǎng)絡(luò)提取的特征上進(jìn)行自訓(xùn)練聚類，其自訓(xùn)練聚類參考了DEC[8]模型，把特征與聚類中心的相似度轉(zhuǎn)化為概率分布p，對分布p進(jìn)行置信度加強(qiáng)形成分布q，最小化分布p，q的KL散度達(dá)到聚類目標(biāo)。SDCN模型則是在引入圖自編碼器的同時引入經(jīng)典自編碼器，使用雙重自監(jiān)督模塊使兩類自編碼器提取特征時能夠互相監(jiān)督，這里的雙重自監(jiān)督模塊與DAEGC模型一樣都借鑒了DEC模型提出的聚類分布，即求自編碼器中間特征與聚類中心相似度轉(zhuǎn)化的概率分布p與置信度加強(qiáng)分布q的KL散度。AGC模型與SDCN模型相似都使用了多層圖卷積神經(jīng)網(wǎng)絡(luò)來提取高階結(jié)構(gòu)信息，并通過逐漸增加K的方式來達(dá)到自適應(yīng)地選擇聚合信息的階數(shù)。EGAE模型同樣是在多層圖卷積神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)上設(shè)計(jì)的聚類模型，該模型在圖卷積神經(jīng)網(wǎng)絡(luò)提取的帶有結(jié)構(gòu)信息的特征上設(shè)計(jì)兩個類似于k-means聚類和譜聚類的損失項(xiàng)，通過這種聯(lián)合訓(xùn)練的方式來取得更好的聚類效果。

對上述基于圖卷積神經(jīng)網(wǎng)絡(luò)的聚類模型研究可以發(fā)現(xiàn)，圖神經(jīng)網(wǎng)絡(luò)聚類算法都需要在圖自編碼器網(wǎng)絡(luò)上設(shè)計(jì)的聚類損失函數(shù)，其主要原因是借助圖自編碼的結(jié)構(gòu)捕捉能力來獲取帶有簇結(jié)構(gòu)信息的低維嵌入特征，本文同樣選擇在圖自編碼器上開發(fā)聚類算法，不同于上述算法對中間特征設(shè)計(jì)聚類的損失項(xiàng)，本文算法從圖自編碼器的結(jié)構(gòu)重構(gòu)能力出發(fā)，將數(shù)據(jù)的圖結(jié)構(gòu)劃分為不同的子圖，這些子圖代表不同的聚類簇，利用圖自編碼器重構(gòu)出子圖結(jié)構(gòu)，以達(dá)到聚類的目的。本文主要貢獻(xiàn)：使用圖自編碼器神經(jīng)網(wǎng)絡(luò)探索聚類簇的子圖結(jié)構(gòu)。

1.2 圖卷積

結(jié)構(gòu)化數(shù)據(jù)可以用卷積操作來提取特征信息，而卷積操作并不能處理非結(jié)構(gòu)化數(shù)據(jù)，如社交網(wǎng)絡(luò)、知識圖譜、蛋白質(zhì)結(jié)構(gòu)、萬維網(wǎng)等，對于這些非結(jié)構(gòu)化數(shù)據(jù)，如何像卷積操作一樣提取有效的特征信息是一些應(yīng)用的關(guān)鍵。圖卷積[9]操作是在圖上進(jìn)行的卷積操作，能夠捕獲數(shù)據(jù)的結(jié)構(gòu)信息。圖卷積操作定義如下：給定一個圖G（V，E，X），V代表圖的頂點(diǎn)集合，E代表圖上存在的邊的集合，X代表節(jié)點(diǎn)的特征矩陣，由此可以得到圖的鄰接矩陣A，和鄰接矩陣的度矩陣D，該矩陣是一個對角矩陣，對角線上的值為對應(yīng)節(jié)點(diǎn)的度。如圖卷積操作表示中，[?（）]是激活函數(shù)，Z是圖卷積操作提取的特征信息。

⑴

在具體實(shí)現(xiàn)中，我們對圖卷積操作做如下處理：

⑵

其中[A=A+I]、[D]是（A+I）的度矩陣，其同樣是一個對角矩陣，對角線上的點(diǎn)是（A+I）節(jié)點(diǎn)的度。

1.3 圖自編碼器

圖自編碼器[10]利用多層圖卷積操作提取節(jié)點(diǎn)的特征信息，經(jīng)典自編碼器的目標(biāo)是重構(gòu)出原始樣本的信息，而圖自編碼器不同于經(jīng)典自編碼器，它的目標(biāo)是使用圖卷積操作提取的特征來重構(gòu)出原始的圖結(jié)構(gòu)，在保證圖結(jié)構(gòu)信息不變的情況下，捕獲帶有聚類簇結(jié)構(gòu)的節(jié)點(diǎn)信息。其定義如下：

⑶

其中[Zl]是第l層圖卷積的輸出，[Wl]是第l層的權(quán)重。這里輸入層圖卷積的[Zl]為節(jié)點(diǎn)的特征矩陣X，編碼器輸出層圖卷積的[Zl+1]為嵌入特征Z。

對編碼器的嵌入特征Z與Z的轉(zhuǎn)置，做矩陣運(yùn)算得到一個圖結(jié)構(gòu)矩陣[A]，使用這個矩陣重構(gòu)原圖，以達(dá)到圖結(jié)構(gòu)不變的目的。

⑷

⑸

2 基于子圖分解的圖聚類網(wǎng)絡(luò)

2.1 本文算法的聚類思想

譜聚類算法是最著名的圖聚類算法，對于非圖結(jié)構(gòu)的數(shù)據(jù)集，譜聚類通過k近鄰、全連接、[ε-]領(lǐng)域等方法將數(shù)據(jù)樣本之間的相似性轉(zhuǎn)化為圖的邊權(quán)重。再將構(gòu)建的圖結(jié)構(gòu)切割成不同的子圖，這些不同的子圖代表了不同的聚類簇結(jié)構(gòu)，譜聚類的核心聚類思想是讓切割之后的子圖間邊權(quán)重低，而子圖內(nèi)邊權(quán)重高。因此如何進(jìn)行子圖切割是譜聚類的關(guān)鍵。

本文受譜聚類的啟發(fā)使用神經(jīng)網(wǎng)絡(luò)進(jìn)行子圖切割，借助圖卷積神經(jīng)網(wǎng)絡(luò)提取不同子圖的嵌入特征，再使用不同的嵌入特征重構(gòu)出不同的子圖結(jié)構(gòu)，達(dá)到聚類的目的。

2.2 子圖劃分

本文算法借助圖卷積神經(jīng)網(wǎng)絡(luò)將數(shù)據(jù)集的圖結(jié)構(gòu)劃分為K個子圖，其具體的結(jié)構(gòu)如圖1所示，劃分的思想是將來自淺層圖卷積F的特征送入K個子圖網(wǎng)絡(luò)中，每個子圖網(wǎng)絡(luò)都將生成一個對應(yīng)的子圖。其中[ZlkN×d']是第k個子圖第l層的圖卷積輸出特征，[AkN×N]是第k個子圖的鄰接矩陣。

⑹

⑺

為了達(dá)到子圖劃分的目的，我們增加了一個判別網(wǎng)絡(luò)用來輸出樣本屬于各簇的概率[QN×K]，用這個概率向量對重構(gòu)的圖結(jié)構(gòu)進(jìn)行篩選，得到K個聚類簇的結(jié)構(gòu)圖。篩選的方法為：樣本屬于第i簇概率乘以第i個子網(wǎng)絡(luò)產(chǎn)生的特征[Zi]和子圖[Ai]。其具體的篩選步驟為如下兩種情況（其中[（x）p，q]是定義的維度擴(kuò)展操作將x擴(kuò)展到p、q維）：

⑴ 樣本j屬于第i簇則理想狀態(tài)[QN×Kj，i=1]，對[QN×Kj，i=1]進(jìn)行維度擴(kuò)展，將第二維擴(kuò)展到N維，得到[Q1=（QN×Kj，i=1）1×N]，將第二維擴(kuò)展到d'維得到[Q2=（QN×Kj，i=1）1×d']，再分別與[Aij：]和[Zij：]做點(diǎn)乘，從而將樣本j的嵌入特征和子圖結(jié)構(gòu)保留在第i簇。

⑵ 樣本j不屬于第i簇則理想狀態(tài)[QN×Kj，i=0]，對[QN×Kj，i=0]進(jìn)行維度擴(kuò)展，將第二維擴(kuò)展到N維得到[Q1=（QN×Kj，i=0）1×N]，將第二維擴(kuò)展到d'維得到[Q2=（QN×Kj，i=0）1×d']再分別與[Aij：]和[Zij：]進(jìn)行點(diǎn)乘，從而將樣本j的嵌入特征和子圖結(jié)構(gòu)從第i簇中去除。

以上這兩種情況可以統(tǒng)一為如下公式：

⑻

⑼

⑽

這里我們對判別網(wǎng)絡(luò)輸出的概率分布進(jìn)行一個加權(quán)指數(shù)的操作[QαN×K]，用來增加模型的自由度和靈活性。

2.3 先驗(yàn)知識

先驗(yàn)知識能夠輔助聚類，不同的先驗(yàn)知識對聚類算法的影響程度不同，在聚類算法中最常見的先驗(yàn)知識是聚類簇的數(shù)目K，根據(jù)聚類算法設(shè)計(jì)角度的不同，可能需要設(shè)置不同的先驗(yàn)知識。在本文中由于我們需要使用樣本屬于各簇的概率向量來篩選子圖，為了使樣本在篩選子圖時不陷入極端解（如預(yù)測為同一簇），我們假設(shè)模型預(yù)測樣本簇的概率分布的先驗(yàn)知識為均勻分布。模型預(yù)測的簇分布為q ，先驗(yàn)分布為均勻分布p，則本文算法的先驗(yàn)損失項(xiàng)為q和p的KL散度。

⑾

⑿

⒀

2.4 本文算法描述

前文中，我們生成了K個子圖，并引入了均勻分布作為聚類簇分布的先驗(yàn)知識，至此，我們完成了使用圖卷積神經(jīng)網(wǎng)絡(luò)定義聚類簇結(jié)構(gòu)，但仍然缺少關(guān)鍵的聚類引導(dǎo)項(xiàng)來保證不同簇的嵌入特征和子圖結(jié)構(gòu)向正確的方向劃分。這里我們使用圖自編碼器來完成這個工作，假設(shè)得到K個正確的子圖劃分，則這個K個子圖的合并將逼近原數(shù)據(jù)的圖結(jié)構(gòu)。

⒁

⒂

因此，本文提出的深度聚類算法的聚類引導(dǎo)項(xiàng)選擇使用圖自編碼器讓圖結(jié)構(gòu)[A]重構(gòu)出原數(shù)據(jù)的圖結(jié)構(gòu)A。在保證每個子圖都在原始圖結(jié)構(gòu)中時，使用圖卷積提取各自子圖的嵌入特征，同時選擇均勻分布保證了模型的解不至于陷入極端解，如把所有樣本劃分為同一簇。本文的算法描述如表1所示，由此可以得出本文聚類算法的損失公式：

⒃

3 實(shí)驗(yàn)及結(jié)果分析

3.1 數(shù)據(jù)集

本文選擇Cora數(shù)據(jù)集[11]用來驗(yàn)證本文提出的圖深度聚類算法，Cora數(shù)據(jù)集由七類深度學(xué)習(xí)論文組成，其中包含基于案例、遺傳算法、神經(jīng)網(wǎng)絡(luò)、概率網(wǎng)絡(luò)、強(qiáng)化學(xué)習(xí)、規(guī)則學(xué)習(xí)、理論這七方面的論文。整個數(shù)據(jù)語料庫中共包含2708篇論文，每篇論文至少被一篇論文引用，同時至少引用一篇論文。數(shù)據(jù)集包含了論文之間引用關(guān)系的索引，依據(jù)這些索引位置可以建立論文之間引用關(guān)系的鄰接矩陣。對每篇論文進(jìn)行詞干提取、去除詞尾，刪去詞頻小于10的詞等操作后保留了1433個特有的詞，對這些詞建立詞向量，形成了圖節(jié)點(diǎn)的特征矩陣X。

3.2 評估指標(biāo)

本文選用互信息（NMI）[12]指標(biāo)，來評估本文提出的深度聚類算法的聚類性能。NMI指標(biāo)能夠評估一個變量包含另一個變量的信息量。NMI 指標(biāo)的取值范圍是[0，1]，越接近1說明變量Y包含變量X的信息量越小，變量X確定性越大。

⒄

3.3 模型的實(shí)現(xiàn)

模型的具體實(shí)現(xiàn)圖卷積網(wǎng)絡(luò)F采用一層圖卷積操作。網(wǎng)絡(luò)G是七個并列的子網(wǎng)絡(luò)，每個網(wǎng)絡(luò)都是一層圖卷積操作，且其輸入是來自網(wǎng)絡(luò)F的淺層嵌入特征。網(wǎng)絡(luò)Q是四層線性網(wǎng)絡(luò)，其輸入是節(jié)點(diǎn)的特征矩陣X，輸出是樣本所屬簇的預(yù)測結(jié)果。聚類簇?cái)?shù)目設(shè)為7，迭代周期設(shè)置為10000，優(yōu)化函數(shù)選擇Adam[13]算法，學(xué)習(xí)率lr=0.01，加權(quán)指數(shù)[α=2]。

3.4 實(shí)驗(yàn)結(jié)果

表2展示了本文算法在Cora數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，該結(jié)果取自多次實(shí)驗(yàn)的最優(yōu)結(jié)果，圖2展示了算法的NMI指標(biāo)在模型訓(xùn)練過程中的變化情況。表2中我們選擇了三類作用在不同輸入上的聚類算法與本文提出的算法做比較。

觀察表2可以看出本文提出的圖神經(jīng)網(wǎng)絡(luò)聚類算法要明顯優(yōu)于只作用于數(shù)據(jù)特征上的聚類算法和只作用圖結(jié)構(gòu)上的聚類算法。這表明基于圖卷積神經(jīng)網(wǎng)絡(luò)的聚類算法有效地利用了數(shù)據(jù)集的圖結(jié)構(gòu)和節(jié)點(diǎn)的特征。

觀察圖2可以看出本文的算法在輪次為0的時候NMI指標(biāo)為0，此時不具備聚類能力，隨著訓(xùn)練地進(jìn)行在各損失項(xiàng)的相互約束下，逐漸具備聚類的能力，最終結(jié)果收斂在0.36附近。

圖2和表2的結(jié)果表明本文提出的基于子圖分解的圖聚類網(wǎng)絡(luò)具有聚類劃分的能力。

4 結(jié)束語

本文提出的基于子圖分解的圖聚類網(wǎng)絡(luò)在圖自編碼器的基礎(chǔ)上對原始數(shù)據(jù)集的圖結(jié)構(gòu)進(jìn)行子圖劃分，以不同的子圖結(jié)構(gòu)來區(qū)分?jǐn)?shù)據(jù)集中的不同簇結(jié)構(gòu)以達(dá)到聚類劃分的目的。該算法在Cora數(shù)據(jù)集上取得了較好的結(jié)果。本文算法的下一步工作是對劃分的子圖做進(jìn)一步的約束以期能夠達(dá)到更高的聚類效果。

參考文獻(xiàn)（References）：

[1] ALJALBOUT E.Clustering with deep learning： taxonomy

and new methods[J/OL].（2018-09-13） [2021-04-02].http：//export.arxiv.org/abs/1801.07648

[2] MINE.A survey of clustering with deep learning：from the

perspective of network architecture[J].IEEE Access，2018，6：39501-39514

[3] Li X， Zhang H， Zhang R. Embedding graph auto-encoder

with joint clustering via adjacency sharing[J].arXiv e-prints，2020： arXiv：2002.08643

[4] Wang C， Pan S， Hu R， et al. Attributed graph clustering：A

deep attentional embedding approach[J]. arXiv preprint arXiv：1906.06532，2019

[5] Bo D， Wang X， Shi C， et al. Structural deep clustering

network[C]//Proceedings of The Web Conference 2020，2020：1400-1410

[6] Zhang X， Liu H， Li Q， et al. Attributed graph clustering via

adaptive graph convolution[J]. arXiv preprint arXiv：1906.01210，2019

[7] TAO Z，LIU H，LI J，etal.Adversarial graph embedding for

ensemble clustering[C]//Twenty-Eighth International Joint Conference on Artificial Intelligence IJCAI-19，2019

[8] Xie J， Girshick R， Farhadi A. Unsupervised deep

embedding for clustering analysis[C]//International conference on machine learning. PMLR，2016：478-487

[9] Niepert M， Ahmed M， Kutzkov K. Learning convolutional

neural networks for graphs[C]//International conference on machine learning. PMLR，2016：2014-2023

[10] Kipf T N， Welling M. Variational graph auto-encoders[J].

arXiv preprint arXiv：1611.07308，2016

[11] Sen P， Namata G， Bilgic M， et al. Collective classification

in network data[J]. AI magazine，2008，29（3）：93-93

[12] P. A. Estévez， M. Tesmer， C. A. Perez， and J. M. Zurada，

“Normalized mutual information feature selection，” IEEE Trans. Neural Netw.，2009，20（2）：189-201

[13] DiederikKingma and Jimmy Ba. Adam： A method for

stochastic optimization. arXiv preprint arXiv：1412.6980，2014

收稿日期：2021-09-22

*基金項(xiàng)目：國家自然科學(xué)基金面上項(xiàng)目（No.61971439）; 江蘇省自然科學(xué)基金面上項(xiàng)目（No.BK20191329）; 中國博士后科學(xué)基金項(xiàng)目（No.2019T120987）; 南京信息工程大學(xué)人才啟動經(jīng)費(fèi)（No.2020r100）

作者簡介：鄧祥（1994-），男，安徽六安人，碩士研究生，主要研究方向：模式識別與深度學(xué)習(xí)。