孫艷豐， 杜鵬飛

(1.北京工業(yè)大學(xué)信息學(xué)部， 北京 100124； 2.北京工業(yè)大學(xué)多媒體與智能軟件技術(shù)北京市重點實驗室， 北京 100124)

聚類是數(shù)據(jù)分析的一項基本任務(wù)，將樣本按照相似性關(guān)系分到不同的類別中[1]. 最近，由于深度網(wǎng)絡(luò)所展現(xiàn)出的強大的數(shù)據(jù)表示學(xué)習(xí)能力，應(yīng)用深度網(wǎng)絡(luò)來解決聚類問題受到人們的關(guān)注. 目前，一些深度聚類算法已經(jīng)成功地在各種實際中進行應(yīng)用，例如文本聚類[2]、圖像聚類[3-4]等. 挖掘數(shù)據(jù)原始特征空間中的屬性信息以獲得有判別力的數(shù)據(jù)表示是深度聚類中的一個關(guān)鍵步驟，例如：Hinton等[5]通過自動編碼器(auto-encoder,AE)網(wǎng)絡(luò)驅(qū)動表征學(xué)習(xí)；Xie等[6]提出了深度編碼聚類(deep embedded clustering，DEC)方法，將原始數(shù)據(jù)空間經(jīng)過參數(shù)化非線性映射到低維特征空間，在低維特征空間優(yōu)化聚類目標來學(xué)習(xí)節(jié)點表示；Guo等[7]提出了改進的通過保持局部結(jié)構(gòu)進行聚類的網(wǎng)絡(luò)，該網(wǎng)絡(luò)引入了重構(gòu)損失、融合聚類損失和AE的重構(gòu)損失，從而學(xué)習(xí)到具有局部結(jié)構(gòu)約束的特征. 然而，這些模型只是針對結(jié)構(gòu)化的數(shù)據(jù)學(xué)習(xí)原始節(jié)點屬性信息，在處理非結(jié)構(gòu)化的圖關(guān)系數(shù)據(jù)聚類時表現(xiàn)不佳.

針對圖結(jié)構(gòu)數(shù)據(jù)的聚類問題，最近的研究工作集中于學(xué)習(xí)圖拓撲結(jié)構(gòu)的編碼表示，將圖拓撲結(jié)構(gòu)與原始節(jié)點屬性更好地結(jié)合. 新興的圖卷積網(wǎng)絡(luò)(graph convolutional network,GCN)[8]給這一工作帶來了巨大的突破. GCN基于圖的拓撲結(jié)構(gòu)和節(jié)點屬性信息，通過聚合來自相鄰節(jié)點的特征迭代更新節(jié)點編碼. 在此基礎(chǔ)上，Kipf 等[9]提出了圖自動編碼器(graph auto-encoder，GAE)和變分圖自動編碼器(variational graph auto-encoder，VGAE)，GAE利用GCN作為編碼器獲得節(jié)點的表示，VGAE使學(xué)習(xí)到的表示符合高斯先驗分布；Fatemi等[10]提出了一種利用高階圖卷積自適應(yīng)地捕獲全局結(jié)構(gòu)信息來學(xué)習(xí)節(jié)點表示的方法；Wang等[11]使用圖注意力融合網(wǎng)絡(luò)作為編碼器來融合圖結(jié)構(gòu)信息和節(jié)點屬性；Pan等[12]進一步提出了一種對抗性正則化圖自動編碼器(adversarially regularized graph auto-encoder，ARGA)用于學(xué)習(xí)潛在的節(jié)點表示；Bo等[13]提出了深度結(jié)構(gòu)化聚類網(wǎng)絡(luò)(structural deep clustering network，SDCN)，利用深度AE和GCN分別學(xué)習(xí)節(jié)點屬性信息和圖結(jié)構(gòu)信息表示，并通過自監(jiān)督機制將它們集成到一個統(tǒng)一的框架中. Peng等[14]提出了注意力驅(qū)動的圖聚類網(wǎng)絡(luò)(attention-driven graph clustering network，AGCN)，將圖結(jié)構(gòu)信息和節(jié)點屬性信息通過注意力機制進行融合以獲得更利于聚類的節(jié)點表示. 現(xiàn)有的方法都是從原始圖結(jié)構(gòu)和節(jié)點特征中學(xué)習(xí)優(yōu)質(zhì)的嵌入表示，然而，原始的圖結(jié)構(gòu)關(guān)系由于數(shù)據(jù)噪聲或度量的不準確可能導(dǎo)致關(guān)系描述不精確. 另外，有研究表明，GCN在從圖拓撲信息和節(jié)點屬性信息中學(xué)習(xí)嵌入表示時表現(xiàn)出來的性能并不是特別令人滿意[15]，因此，如何獲得更準確的嵌入表示是一個關(guān)鍵問題.

針對以上提出的不足之處，本文提出一種深度聚類網(wǎng)絡(luò)，即基于多通道圖卷積網(wǎng)絡(luò)(multi-channel graph convolutional network, McGCN)的節(jié)點聚類.

1 McGCN的節(jié)點聚類模型

1.1 符號定義及任務(wù)說明

首先介紹一些符號及概念，屬性圖可以表示為G={V,E,X},其中：V是節(jié)點集合；E是邊集合；X∈Rn×m是節(jié)點的屬性矩陣，n表示節(jié)點數(shù)，m表示特征的維數(shù).圖的鄰接矩陣表示為A∈Rn×n，如果Vi和Vj之間有邊，則Aij=1，否則為0.給定一個圖G和聚類數(shù)k，屬性圖聚類的目的是把圖G中的節(jié)點劃分到k個不相交的簇中.任務(wù)說明如圖1所示，黃色和藍色分別表示2種類別的節(jié)點，聚類模型根據(jù)拓撲信息和特征信息將它們分到2個簇中.

圖1 屬性圖聚類示例Fig.1 Example of attributed graph clustering

1.2 整體框架

對于圖數(shù)據(jù)集，本文把原始的拓撲圖結(jié)構(gòu)稱為拓撲圖，把基于節(jié)點特征相似度通過K-近鄰(K-nearest neighbor，KNN)算法構(gòu)建的圖結(jié)構(gòu)稱為特征圖.然后，使用AE提取節(jié)點特征的數(shù)據(jù)表示，使用GCN從拓撲圖和特征圖中提取圖的數(shù)據(jù)表示，以便在不同的空間學(xué)習(xí)嵌入表示.最后，通過一個自適應(yīng)融合模塊將3個通道得到的節(jié)點編碼進行融合.此外，采用了自監(jiān)督機制和編碼之間的差異性約束來監(jiān)督訓(xùn)練過程，模型整體框架如圖2所示.

圖2 多通道圖卷積聚類網(wǎng)絡(luò)結(jié)構(gòu)Fig.2 Structure of multi-channel graph convolution clustering network

1.2.1 節(jié)點特征的編碼模塊

不考慮節(jié)點之間的連接關(guān)系，只考慮節(jié)點的特征，將節(jié)點特征嵌入到低維空間有很多方法，如去噪自動編碼器(denoising auto-encoder，DAE)、稀疏自動編碼器(sparse auto-encoder, SAE)、變分自動編碼器(variational auto-encoder, VAE)等.本文使用最基本的AE，其主要由2個部分組成，即將輸入映射到中間層表示的編碼器以及將中間層映射到輸出的解碼器，通過最小化原始特征與重構(gòu)特征之間的重構(gòu)損失來學(xué)習(xí)編碼表示.它的編碼、解碼和重構(gòu)損失公式分別可以表示為

(1)

(2)

(3)

1.2.2 圖結(jié)構(gòu)的編碼模塊

GAE的目標是根據(jù)節(jié)點特征和圖鄰接關(guān)系學(xué)習(xí)圖的低維節(jié)點嵌入.近年來，GCN在處理圖數(shù)據(jù)上表現(xiàn)出來的性能得到了廣泛的認可，基本思想是根據(jù)鄰接關(guān)系聚合鄰居節(jié)點的特征信息，通過堆疊多層的圖網(wǎng)絡(luò)學(xué)習(xí)更深層次的表示.給定一個節(jié)點特征矩陣X和鄰接矩陣A，GCN通過A和X生成新的節(jié)點表示，第l層輸出可以表示為

(4)

對于圖數(shù)據(jù)，原始圖關(guān)系可能存在誤差，使得通過原始拓撲圖和節(jié)點特征得到的嵌入表示并不是令人滿意的，因此，使用節(jié)點之間的特征相似度構(gòu)建特征圖，拓撲圖和特征圖同時被用來提取圖數(shù)據(jù)的嵌入表示.這種方法可更充分地從特征空間中挖掘可靠信息.另外，為了使算法能夠適應(yīng)非圖數(shù)據(jù)，采用不同K值下KNN算法生成的鄰接關(guān)系來表示拓撲圖和特征圖.

1.2.3 融合模塊

如何融合這些來自不同通道的節(jié)點編碼是一個挑戰(zhàn)，常用的方法有加權(quán)求和、拼接和注意力機制等.為了充分融合由AE和GCN得到的嵌入表示，采用了一種基于注意力的動態(tài)融合機制，使得上述3個通道得到的節(jié)點表示充分交互.具體的圖示如圖2所示，首先將來自3個通道的嵌入表示(Zae，Zfg，Ztg)兩兩加權(quán)求和進行初步融合，得到3個新的嵌入表示(Zae-fg，Zae-tg，Zfg-tg)，融合規(guī)則用公式表示為

Zae-fg=α·Zae+(1-α)·Zfg
Zae-tg=β·Zae+(1-β)·Ztg
Zfg-tg=γ·Zfg+(1-γ)·Ztg

(5)

式中α、β、γ表示融合的超參數(shù).之后，對Zae-fg、Zae-tg、Zfg-tg應(yīng)用注意力機制以實現(xiàn)自適應(yīng)融合，通過全連接層挖掘不同表示之間的關(guān)系，使用tanh(·)激活函數(shù)，并且進行softmax歸一化，將得到的每個嵌入表示系數(shù)與對應(yīng)的嵌入表示加權(quán)求和，得到融合之后的嵌入表示.融合規(guī)則的公式為

Ztemp=[Zae-fg‖Zae-tg‖Zfg-tg]

(6)

ω=W2(tanh(W1·Ztemp+b))

(7)

(8)

式中：Ztemp∈Rn×3×d表示把待融合的嵌入表示(Zae-fg，Zae-tg，Zfg-tg)拼接到一起；W1、W2均為全連接層的權(quán)重；b為偏置；ω∈Rn×3×1表示嵌入表示的融合系數(shù)；θ∈Rn×3×1為對系數(shù)歸一化的結(jié)果.由此可以得到最終的融合表示，將融合后的表示通過softmax函數(shù)得到n個樣本屬于k個簇的概率分布Z∈Rn×k，這一過程用公式表述為

Z=softmax(θ1·Zae-fg+θ2·Zae-tg+θ3·Zfg-tg)

(9)

對網(wǎng)絡(luò)訓(xùn)練后，可以通過Z得到預(yù)測的簇標簽，公式為

yi=arg maxzi

(10)

式中：yi表示第i個樣本預(yù)測的簇標簽；zi表示Z的第i個樣本.

由于特征空間的圖結(jié)構(gòu)是通過KNN算法從原始節(jié)點屬性X生成的，為了充分挖掘特征空間的信息，應(yīng)訓(xùn)練編碼器在節(jié)點屬性空間和特征圖空間學(xué)習(xí)到有差異的嵌入表示，同時也約束節(jié)點屬性空間和拓撲圖空間的嵌入表示有差異性.為此，本文使用希爾伯特- 施密特獨立性準則(Hilbert-Schmidt independence criterion，HSIC)進行約束.HSIC是一種基于核的獨立性度量方法，主要功能是衡量2個變量的分布差異，其公式可以描述為

LHSIC(Zae,Zfg)=(n-1)-2tr(RKaeRKfg)

(11)

LHSIC(Zae,Ztg)=(n-1)-2tr(RKaeRKtg)

(12)

1.2.4 自監(jiān)督模塊

獲得融合的嵌入表示后，借鑒文獻[16]中的策略，對融合后的嵌入表示增加約束,以便更好地實現(xiàn)聚類任務(wù),這也成為現(xiàn)在許多深度聚類方法中實現(xiàn)聚類的最常用策略[17].其詳細過程如下：首先，使用Student-t分布作為核來度量由AE學(xué)習(xí)到的嵌入表示中第i個樣本和第j個聚類質(zhì)心之間的相似性，計算公式為

(13)

式中：qij表示樣本zae,i分配到聚類中心μj的概率；zae,i表示AE學(xué)習(xí)到的嵌入表示Zae的第i個樣本；μj是通過對Zae進行K-means計算得到的聚類中心；α表示自由度，是一個超參數(shù)，本文實驗中設(shè)置為1.對每個樣本進行計算，得到所有樣本分配分布，稱之為聚類軟分配分布Q.

為了增加聚類的內(nèi)聚力，使Q的數(shù)據(jù)表示更接近聚類中心，求得Q的歸一化分布P為

(14)

最后，為了使融合后的分布與融合前的分布相一致，在目標分布P的協(xié)助下通過優(yōu)化融合后的嵌入表示分布Z與AE學(xué)習(xí)到的嵌入表示分布Q之間的KL(Kullback-Leibler)散度達到這一目的，在此使用了2個約束項

(15)

(16)

式中LKL(PQ)、LKL(PZ)分別表示聚類軟分配分布Q和融合后嵌入表示分布Z與歸一化分布P之間的KL散度.

通過最小化式(15)(16)可以使融合后的分布Z和融合前的分布Q很好地對齊，由于P是通過Q生成的，而P又反過來監(jiān)督Q的更新，整個過程中沒有人為的引導(dǎo)，因此，稱為自監(jiān)督方式.P、Q和Z之間的約束正則項如圖2中紅色虛線標注所示.

本文通過這一監(jiān)督方法把AE和GCN整合到一個網(wǎng)絡(luò)中，實現(xiàn)端到端的訓(xùn)練.在對網(wǎng)絡(luò)進行訓(xùn)練之后，通過融合后的表示分布Z可以直接得到預(yù)測聚類結(jié)果，最終，整個網(wǎng)絡(luò)的損失函數(shù)設(shè)計為

L=λ1·LR+λ2·LKL(PQae)+λ3·LKL(PZ)+
λ4·LHSIC(Zae,Zfg)+λ5·LHSIC(Zae,Ztg)

(17)

式中：LR表示AE的重構(gòu)損失；LHSIC(Zae，Zfg)、LHSIC(Zae，Ztg)分別表示對節(jié)點屬性與特征圖和拓撲圖編碼得到的嵌入表示之間的差異性損失.

整個模型的算法步驟如下.

2 實驗

2.1 實驗數(shù)據(jù)

本文在6個常用的基準數(shù)據(jù)集上進行了實驗，包括1個圖像數(shù)據(jù)集USPS、1個人類活動識別記錄數(shù)據(jù)集HHAR、1個文本數(shù)據(jù)集Reuters和3個圖數(shù)據(jù)集ACM、DBLP、CiteSeer，數(shù)據(jù)集的簡要描述如表1所示.

表1 數(shù)據(jù)集描述

USPS數(shù)據(jù)集包括9 298個灰度手寫數(shù)字圖像，共10個類別(即0～9).

HHAR數(shù)據(jù)集包含智能手表的10 299條傳感器記錄. 樣本被劃分為6類人類活動(騎自行車、坐、站、走、上樓梯和下樓梯).

Reuters數(shù)據(jù)集包含大約81萬篇英語新聞故事，并按類別進行標記. 使用公司/工業(yè)、政府/社會、市場和經(jīng)濟作為標簽.

ACM數(shù)據(jù)集是來自ACM數(shù)字圖書館的一個論文網(wǎng)絡(luò)數(shù)據(jù)集，其中邊表示同一作者撰寫. 特征是關(guān)鍵詞的詞袋表示. 樣本按照研究領(lǐng)域分成3類(數(shù)據(jù)庫、無線通信、數(shù)據(jù)挖掘).

DBLP數(shù)據(jù)集是一個作者網(wǎng)絡(luò)數(shù)據(jù)集. 節(jié)點表示作者，邊表示作者合作完成的論文. 作者分為4個領(lǐng)域：數(shù)據(jù)庫、數(shù)據(jù)挖掘、機器學(xué)習(xí)和信息檢索.

CiteSeer數(shù)據(jù)集是一個引文網(wǎng)絡(luò)數(shù)據(jù)集，包含每個文檔的稀疏詞匯特征向量包和文檔之間的引文鏈接列表. 標簽包含6個領(lǐng)域：代理、人工智能、數(shù)據(jù)庫、信息檢索、機器語言和人機交互.

2.2 對比方法

本文將提出的方法與8種方法進行了對比，其中前3種是基于AE的非圖數(shù)據(jù)聚類方法，后5種是基于GCN的圖數(shù)據(jù)聚類方法.

1) AE方法：對AE從原始數(shù)據(jù)中學(xué)習(xí)到的嵌入表示執(zhí)行K-means聚類.

2) DEC方法：在上述AE方法基礎(chǔ)上加入約束項，將編碼器學(xué)習(xí)嵌入表示和聚類分配兩部分聯(lián)合后進行優(yōu)化，不再把兩部分割裂開，從而提高聚類.

3) IDEC方法：在DEC上增加了一個自編碼器的重構(gòu)損失以更好地學(xué)習(xí)嵌入表示，提高聚類效果.

4) GAE方法：結(jié)合GCN和AE設(shè)計，用于學(xué)習(xí)數(shù)據(jù)表示.

5) VGAE方法：在GAE的基礎(chǔ)上，從原始數(shù)據(jù)中學(xué)習(xí)到一個分布，從這個分布中采樣一組數(shù)據(jù)作為嵌入表示進行聚類.

6) DAEGC方法：使用GAT網(wǎng)絡(luò)來學(xué)習(xí)嵌入表示，并生成目標分布，使其指導(dǎo)嵌入表示進行更新.

7) SDCN方法：通過AE學(xué)習(xí)節(jié)點特征表示，并通過GCN學(xué)習(xí)圖結(jié)構(gòu)表示，把這兩部分的嵌入表示融合，進行聚類任務(wù).

8) AGCN方法：在SDCN的基礎(chǔ)上，在兩部分嵌入表示融合時使用了注意力機制，得到更利于聚類的節(jié)點表示.

9) McGCN方法：即本文提出的方法.

2.3 聚類結(jié)果

本文的方法和8種對比方法在6個基準數(shù)據(jù)集上的實驗結(jié)果如表2所示. 表中：ACC表示聚類結(jié)果的準確度；NMI表示聚類結(jié)果中正確聚類信息的數(shù)量；ARI表示類別劃分的重疊程度；F1是模型準確率和召回率的調(diào)和平均值.

根據(jù)表中數(shù)據(jù)可以觀察到：本文方法在6個數(shù)據(jù)集的比較中大部分指標都獲得了最好的聚類性能. 精度提升顯著的原因有3個方面：首先，文中的方法增加了一個新的圖結(jié)構(gòu)，提供了更豐富的信息；其次，加入差異性約束模塊后顯著地增加了節(jié)點表示的多樣性，使其從不同角度學(xué)習(xí)到有區(qū)別的嵌入表示；最后，基于注意力機制融合模塊，自適應(yīng)地融合了來自各個通道的嵌入表示，充分地利用了每個通道中的信息. 在ACM、DBLP數(shù)據(jù)集中，本文提出的方法性能改進不明顯. 通過對模型算法及實驗結(jié)果進行分析，認為這個數(shù)據(jù)集的拓撲圖與特征圖結(jié)構(gòu)比較一致，增加特征圖結(jié)構(gòu)并不能有效地提高聚類精度.

2.4 消融實驗

針對模型中的差異性約束HSIC，本文進行了消融實驗來檢驗它的作用，實驗結(jié)果如表3所示. 表中：McGCN表示本文提出的具有HSIC約束的模型；McGCN-HSIC表示去掉HSIC約束的模型. 可以發(fā)現(xiàn)，擁有HSIC約束的要明顯優(yōu)于沒有HSIC的模型. 這一觀察結(jié)果表明，HSIC約束能夠約束2個通道中的編碼器，使其學(xué)習(xí)不同的嵌入表示，從而利用更全面的信息來提高網(wǎng)絡(luò)的聚類性能.

表3 HSIC約束對模型的影響

2.5 訓(xùn)練過程分析

通過實驗對McGCN的訓(xùn)練過程進行了分析，并與之前的SDCN方法做比較，實驗結(jié)果見圖3.

圖3 正確率與訓(xùn)練次數(shù)的關(guān)系Fig.3 Relationship between accuracy and training times

在Reuters和HHAR的訓(xùn)練過程中存在一些波動，分析原因是3個通道學(xué)習(xí)到的嵌入表示差異性較大且沒有一個具有主導(dǎo)性的嵌入表示，導(dǎo)致在自適應(yīng)融合時權(quán)重分配多樣化，進而表現(xiàn)出正確率波動. 但是，隨著訓(xùn)練的進行，最終的聚類結(jié)果都趨于穩(wěn)定.

3 結(jié)論

1) 本文提出的McGCN方法基于AE和GCN在原始節(jié)點特征空間、拓撲圖空間和特征圖空間進行嵌入表示的學(xué)習(xí)，并且通過一個基于注意力機制的融合模塊將節(jié)點編碼融合，應(yīng)用Student-t分布得到樣本的軟分配分布，通過自監(jiān)督的方式優(yōu)化軟分配分布與目標分布之間的差異，執(zhí)行端到端的訓(xùn)練.

2) 在常用的基準數(shù)據(jù)集上對提出的方法進行評估，結(jié)果表明該方法有效地提高了聚類精度.

3) 雖然本文方法已經(jīng)取得了較好的性能，但由于圖結(jié)構(gòu)編碼采用的是GCN，它本質(zhì)上是平等地聚合鄰居節(jié)點信息，沒有更好地結(jié)合節(jié)點的結(jié)構(gòu)關(guān)系屬性，存在一定局限性，未來將探索更有效的圖結(jié)構(gòu)編碼方式.