注意力機制和圖卷積神經網絡引導的譜聚類方法

陳容珊，高淑萍，齊小剛

（西安電子科技大學 數學與統計學院, 陜西 西安 710071）

聚類是一種通過度量數據點之間的相似性對未標記數據點進行分類的方法。常用的度量數據點之間相似性的方法有歐幾里德距離、余弦距離及曼哈頓距離等。經典的聚類算法如K-均值聚類[1]、譜聚類[2]、分層聚類[3]等，近年來已廣泛應用于各個領域。然而，經典的聚類方法作用于高維數據時性能較差且計算復雜度較高[4-5]。受到深度學習中一些模型的啟發，學者們將深度學習與經典的聚類算法相結合提出了深度聚類的概念。

卷積神經網絡（convolutional neural network,CNNs）作為深度學習中一類重要的架構，由于其只能作用于傳統的歐幾里德數據，且在一般的圖結構中定義局部卷積濾波器和池運算符非常困難[6-10]，因此，針對卷積神經網絡CNNs 的局限性，研究者們提出了圖卷積神經網絡（GCNs)。圖卷積神經網絡(graph neural network, GCNs) 繼承了卷積神經網絡（CNNs）中的池化操作及卷積操作，可以結合局部特征信息，去除冗余信息[4,11-13]，并且將卷積運算擴展到更一般的圖結構，可以處理更一般的拓撲結構[5,14-17]。鑒于圖卷積神經網絡比卷積神經網絡更強大的優勢，基于圖卷積神經網絡的各類聚類算法成為研究熱點。

經典的譜聚類算法的原理是將樣本數據映射到與其拓撲結構相對應的圖拉普拉斯矩陣的特征空間，通過對圖拉普拉斯矩陣進行特征分解得到相應的聚類結果[18-21]。然而，當圖的結構足夠復雜時，與圖結構對應的圖拉普拉斯矩陣的維數會劇增，進行特征分解的代價過高，不適用于具有復雜結構的圖數據集和大數據集的聚類分析，因此，研究者們提出了基于深度學習的譜聚類算法并已證明在行為識別[22-23]、社區檢測[24]、圖像處理[25-27]等任務中體現了良好的性能。有研究者在2020 年提出了基于自編碼器的生物數據低秩譜集成聚類算法[28-29]，將深度自動編碼器同譜聚類算法結合應用于生物領域[30-31]。2019 年另有研究者提出了基于深度神經網絡的多視圖數據光譜聚類[32-33]，利用多個孿生網絡（siamese networks）同譜聚類算法結合并應用于多視圖數據[34-37]。還有研究者提出了基于圖神經網絡圖池的譜聚類算法，將圖拉普拉斯矩陣特征分解導致的高計算量問題轉化為目標函數的優化問題[38]，通過優化一個圖分割問題得到相應的聚類結果，在一定程度上取得了良好的效果[39-40]。然而上述研究成果仍存在局限性，如忽略了節點之間的關聯度信息，使得一些重要性較低的節點被劃分到同一簇中，導致聚類結果依然不夠準確；使用的網絡太淺，不適用于復雜的數據集；經典的圖卷積神經網絡(GCNs)架構中涉及的節點數量發生變化時，需要更新整張圖，導致較高昂的計算成本和存儲成本[38,41]。

近年來，注意力機制廣泛應用于各類聚類算法中。2021 年提出了基于注意力機制的深度子空間應用于多視圖數據的分類，將自注意力機制引入深度子空間聚類網絡，通過計算節點之間的注意力系數對不同的節點分配不同大小的權重從而給予不同的關注[28,33,42]。2021 年提出了具有雙重引導自監督的深度注意引導圖聚類，動態融合不同層的多尺度特征從而學習更高效的潛在表示[9,40,43]尺度自注意深度聚類方法，利用自注意力機制融合各模塊生成語義信息的互補特征表示應用于具有特征缺失的數據[44]。

在前人研究工作的基礎上，本文對基于圖神經網絡圖池的譜聚類算法進行改進，提出了一種將注意力機制與改進的圖卷積神經網絡相結合的譜聚類算法(graph attention spectral clustering，GATSC)。該算法首先利用注意力機制計算節點之間的注意力系數來提高聚類結果的準確性；對傳統的圖卷積神經網絡(GCNs)進行改進，即在神經網絡的每一層中圍繞每個節點選擇一定數量的鄰居。然后將聚合的鄰居信息與節點在上一層的表示連接起來，形成節點在該層的表示，從而降低經典的圖神經網絡的存儲成本。通過實驗表明，與其他譜聚類算法相比，本文提出的模型在圖像分類、圖像聚類及圖重構中具有顯著優勢。

本文主要貢獻如下：1）本文提出了將注意力機制與改進的GCNs 相結合的深度譜聚類算法。與現有的方法不同，本文提出的模型在進行聚類操作時需要計算節點之間的注意力系數，通過節點間的注意力系數來引導節點聚類從而提高聚類性能。2）本文模型在進行圖重構時，利用注意力機制和拓撲結構信息雙重引導重構操作。具體地，將節點之間的注意力信息和圖的拓撲結構信息分別作為權重添加在損失函數上，從而不僅在拓撲結構上進行局部保留，而且考慮節點之間的關聯度，從而使各部分的重構邊緣更加清晰。

1 相關理論知識

1.1 深度聚類

有研究者在2018 年發表了一篇關于深度聚類的綜述，包括深度聚類（deep clustering）被提出的原因、原理及經典的一些深度聚類模型[45]?，F實中的大多數數據集往往不具有標簽或者存在部分的標簽缺失，因此，對這類數據進行分類的難度系數較大。而深度聚類算法利用深度學習中的模型將數據進行降維嵌入至低維的特征空間，然后選擇適當的相似性度量函數并且制定合理的聚類損失函數，最終通過訓練模型最小化聚類損失從而對無標簽的數據進行分類。聚類思想見圖1，圖中每一種顏色代表一種數據類型。

圖1 理想狀態下的聚類效果Fig.1 Clustering diagram under ideal condition

1.2 圖卷積神經網絡

由于卷積神經網絡（CNNs）只能作用于歐幾里德域的數據，不適用于更一般的圖數據，在對圖數據進行處理時效果不佳，因此，有研究者于2019年在ICLR 中發表了關于圖卷積神經網絡（GCNs）的文章[46]。GCNs 繼承了卷積神經網絡的優勢，將卷積操作擴展到更一般的圖結構中，能夠更好地進行圖表示學習。具體地講，GCNs 將原始數據輸入圖卷積神經網絡后，圖神經網絡利用卷積核聚合一階鄰域內所有節點的特征信息作為中心節點的潛在特征、利用池化層的池化操作去掉冗余的特征信息，最終學習到節點的高效表示。

1.3 注意力機制

隨著神經網絡的發展，注意力機制已成為神經網絡中的一個重要概念，并在不同領域得到了應用和研究。近年來，注意力機制在語音處理、圖像處理等方面得到了越來越廣泛的應用。在許多基于序列的任務中，注意力機制已經具有極高的準確性。有研究者在2018 年提出了注意力機制并結合圖神經網絡驗證了其效果（注意力機制模型見圖2）[47]。

圖2 注意力機制模型Fig.2 Attention mechanism model

注意力機制的核心是計算不同節點之間注意力系數，首先利用卷積操作得到m個節點的特征表示，分別記為h1,h2,···,hm，然后利用下式計算節點i和節點j之間的注意力系數：

式中：a(·):RF′×RF′→R為一個映射函數，W是權重矩陣，表 示節點i及節點j之間的關聯度，及分別表示節點i及節點j進行正則化操作后的特征表示， αij利用Softmax 函數將節點i及節點j之間的關聯度eij作歸一化處理。

注意力機制將計算得到的節點之間的注意力信息視為權重，并通過權重最大的部分來幫助用戶做出決策。然而當輸入中不同數據點的尺寸不一致時，往往需要多種類型的卷積塊對不同尺寸的輸入進行處理，當卷積塊類型過多時需要訓練大量參數將導致高昂的計算成本。注意力機制不僅充分考慮節點內部的潛在關系，還能處理具有可變大小的輸入從而極大地降低了計算成本。當注意力機制被應用于計算一個序列的表示時,它通常被稱為自注意力（self-attention）或內部的關注, 當注意力機制與遞歸神經網絡(RNN)或其他卷積神經網絡相結合時，這種機制已被證明對機器閱讀等任務很有用[48]

2 本文提出的模型GATSC

現有的深度譜聚類算法存在一定的局限性如：忽略了節點之間的關聯度信息，使得一些重要性較低的節點被劃分到同一簇中，導致聚類結果依然不夠準確；使用的網絡太淺，不適用于復雜的數據集；經典的圖卷積神經網絡(GCNs)架構中涉及的節點數量發生變化時，需要更新整張圖將導致較高昂的計算成本和存儲成本。因此，本文提出了基于注意力機制和改進的圖卷積神經網絡結合的譜聚類算法，記為GATSC。該算法與原有的基于圖神經網絡圖池的譜聚類算法（graph neural networks spectral clustering，GNNSC）相比較，降低了迭代過程中的存儲成本，提高聚類準確性。算法流程見圖3。

圖3 本文提出的模型框架Fig.3 Model of the proposed algorithm

本文基于文獻[39]提出的基于圖神經網絡圖池的譜聚類算法，在原有的模型基礎上增加了注意力機制，改進了聚類損失函數和重構損失函數。給定一張圖記為G，將G定義為G={V,E}， 其中V表示圖G中所有節點構成的集合，且 |V|=N，V中的每一個節點都是一個F維的向量。E代表圖G中所有 邊 的 集 合。A是 圖G的 鄰 接 矩 陣，A∈RN×N。X是圖G中節點的特征矩陣，H∈RN×F，H中每一行都是圖G的一個節點。

本文提出的模型算法步驟如下：

1)數據預處理。將圖像數據進行分割，得到各個節點的特征信息。

2)學習節點的潛在表示。本文利用改進的圖卷積神經網絡，對于每個節點v∈V，聚合節點v固定數量的一階鄰居 {u|u∈N(v)}，利用一個聚合函數AGGl來進行聚合操作，將聚合后的結果同節點v在第l-1層 的潛在表示連接后得到節點v在第l層的潛在表示：

其中u∈N(v)。

需要說明的是， AGGl不是聚合拓撲結構意義下的一階鄰居，而是聚合對中心節點貢獻大的鄰居節點，即對中心節點重要性高的節點作為鄰居，其中重要性的大小通過注意力系數衡量。

3)計算節點之間的注意力信息。首先定義節點i的特征和節點j的特征的關聯度如下：

其中，f是共享Attention 機制，f:RF×RF→R，W是一個可訓練的權重矩陣。

為了更好地比較不同節點特征之間的相關性，并考慮到每一層的共享Attention 機制f是被一個權重向量參數W所量化的， β ∈R2F，本文對關聯度作歸一化處理如下。

（a）當節點j屬于節點i的一階鄰域時：

（b）當節點j不屬于節點i的一階鄰域時：

式中：V是所有節點特征組成的集合，Vl是節點l的一階鄰域的特征組成的集合，hi、hj及hk分別為節點i、 節點j及節點k的特征表示，W是權重矩陣，β是權重系數，LeaklyRELU 是激活函數。

4)利用本文提出的模型進行聚類。給出了式（7）的損失函數，通過訓練神經網絡得到每一次迭代后的最優聚類分配結果。

式中： | |·||F是Frobenius 范數；U是進行軟聚類分配時的分配矩陣，即uij∈[0,1]，U1K=1N，K為強連通分支的個數；為 正則化后的節點度矩陣；為正則化后的鄰接矩陣，其元素

其 中i≠j。

圖4 給出了模型GATSC 的池化層模型。

圖4 GATSC 的池化層模型Fig.4 Pooling layer model of GATSC

5) 根據聚類結果進行圖重構。利用注意力機制和拓撲信息雙重引導重構操作，既保留了局部信息，又能準確地勾勒出各部分的邊緣。首先利用每次迭代的聚類分配矩陣對節點特征矩陣和鄰接矩陣進行迭代操作。每次迭代的鄰接矩陣和節點特征矩陣計算如下：

式中：U為軟聚類分配的分配矩陣，H為圖的節點特征矩陣，為歸一化操作后圖的節點鄰接矩陣。使用GCNs 的自動編碼器進行重構操作如下：

用兩種方法定義解碼器的重構損失，如下所示：

或者

最后將節點之間的注意力系數和拓撲結構信息分別作為權重引入式（10）或（11），計算公式如下：

本段對提出的模型的計算復雜度進行分析。本文采用改進的GCNs 中的池化層計算聚類分配矩陣U，其中U∈RK×K。計算復雜度來源于聚類損失與正則化損失，由式(7)可知聚類損失主要由聚類分配矩陣松弛后的決策鄰接矩陣構成，正則化損失主要由聚類分配矩陣構成，因此，主要計算復雜度為O(NK(K+N))。由于圖中并非所有節點都高度相關，可以設置一定的閾值，在每一次迭代后，將低于閾值的節點之間的關聯度可視為0，即在模型的每次訓練過程中會丟棄掉一些相關度不高的節點之間的邊，從而對松弛后的節點鄰接矩陣進行降維，最終計算復雜度應小于O(NK(K+N))。

3 實驗與分析

在本節中，將本文提出的模型與無注意力引導的深度譜聚類模型GNNSC 進行比較。本實驗每個部分的具體實現建立在Spectral、Tensorflow、Pytorch 等架構上。

3.1 無監督聚類實驗及分析

3.1.1 引文網絡Cora、Citeseer 及Pubmed 上的聚類比較

首先考慮了在3 個引文網絡Cora、Citeseer 及Pubmed 上的聚類任務。這3 個引文網絡中的節點是各類文獻的特征向量構成的集合，這些特征向量包含文獻的年份、作者、科目等信息。節點之間的邊被定義為文獻之間引用或者被引用的關系，且這種關系利用二進制來表示，0 代表沒有引用關系，1 代表具有引用關系?？紤]到兩種文獻之間或許沒有直接的引用關系，但是可能存在間接的引用關系。本文利用注意力引導聚類可以關注到多跳節點之間的相關性。每個節點都被標記為文檔類型，對各個文檔類型進行聚類。利用NMI 及CS 兩種評價指標來評估聚類效果，其中表示正則化的互信息，表示完整性得分。

將本文GATSC 與GNNSC、譜聚類（SC）、基于可微分池化操作的深度譜聚類（DiffPool）進行對比（見表1）。由表1 可以看出，本文提出的模型在Cora、Citeseer 及Pubmed 3 個引文網絡上的NMI 得分優于SC 及DiffPool 兩個模型，表明本文選取的池化層類型更優。而本文提出的模型的NMI 得分優于GNNSC 模型表明了注意力機制的強大性。GNNSC 模型沒有充分考慮節點之間的注意力信息，僅利用節點的拓撲信息尋找強連通分支，進而將節點進行分類。圖5 及圖6 分別給出了本文提出的模型與GNNSC 的NMI 值隨著迭代次數的變化、三類損失函數隨著迭代次數的變化的曲線圖，顯示出本文提出的模型獲得了更加穩定的集群性能，且迭代收斂的速度更快。

表1 對不同的引文網絡節點聚類得到的NMI 值和CS 值Table 1 NMI value and CS value obtained by clustering different citation network nodes

圖5 本文提出的模型在Cora 數據集上的無監督損失及NMI 值Fig.5 Unsupervised loss of proposed model and NMI value on Cora dataset

圖6 GNNSC 在Cora 數據集上的無監督損失及NMI 值Fig.6 Unsupervised loss of GNNSC and NMI value on Cora dataset

3.1.2 圖像分割聚類比較

將本文提出的模型應用于圖像分割任務。首先對原圖像進行過分割操作，節點特征由過分割后的圖像的各個區域的平均值和不同顏色組成，設置聚類數量為4，實驗結果如圖7 所示。實驗結果顯示，GNNSC 總體效果良好，但是圖像中各個邊緣不夠清晰，存在一定的聚類誤差。本文提出的模型中由于節點之間的相似性不再純粹利用拓撲距離來衡量，因此圖像中每個部分的邊緣會被劃分地更清楚，同時也減少了一定的聚類錯誤。

圖7 圖像分割任務效果Fig.7 Results of image segmentation

3.2 圖重構實驗及分析

本文利用注意力機制計算節點之間的注意力系數，設計了基于注意力信息和拓撲信息雙重引導的自動編碼器，并通過最小化重構損失來重建原始輸入的節點特征矩陣及原始輸入的鄰接矩陣，保留25%的原始節點。本文GATSC 及GNNSC圖重構結果比較如圖8。

圖8 環形圖重構效果Fig.8 Results of ring graph reconstruction

由圖8 可以看出，本文提出的模型對于環形圖的重構效果更優。雖然GNNSC 對于環形的重構較好，但是在環形的邊緣重構效果較差。

本文提出的模型及GNNSC 應用于直方圖的重構（見圖9）。結果表明，本文提出的模型對于直方圖的重構效果更優。GNNSC 在重構直方圖時，內部節點重構較好，但是對于邊緣的節點重構效果不佳。

圖9 方形圖的重構效果Fig.9 Results of grid graph reconstruction

3.3 有監督的圖像分類實驗及分析

在本節實驗中，將本文提出的模型及其他模型應用于有監督的圖分類任務進行比較分析。本文考慮了WL、Dense、No-pool、Graclus、NDP、DiffPool、Top-K、SAGPool 及GNNSC 9 種模型，采用了Mutagenicity、Proteins、DD、COLLAB 及Reddit-Binary 5 種圖分類數據集，測試了10 種模型的分類精度。對于數據集中沒有特征的圖數據，借鑒GNNSC 模型中的實驗，將每個節點的度信息和聚類系數作為節點的特征，使用十折進行訓練分割或測試分割來評估模型性能，在每個圖像分割任務的每次折疊中使用訓練集的10%用于驗證模型的優劣性。使用10%的訓練集作為早期停止的驗證。為了公平比較實驗結果，本節中采用一致的網絡架構。將GATSC 與Graclus、NDP、Top-K、DiffPool 及SAGPool 進行分類效果比較時，只改變了池化層的選擇（結果見表2）。將WL、Dense、No-pool 與GATSC 模型進行對比，是為了比較有無池化操作是否對分類效果有影響（結果見表2）。

表2 無監督的圖分類精度Table 2 Unsupervised accuracy of graph classification

表2 給出了10 種模型對于有監督的圖分類任務的效果?？梢钥闯?，與其他方法相比，本文提出的模型在5 種圖分類數據集上總能取得良好的結果。同時我們也注意到幾個細節，有池化操作的模型不總是優于無池化操作的模型，因為池化操作選擇不當可能會適得其反；除此之外，GNNSC 在Reddit-Binary 數據集上也具有極好的分類精度。綜上，本文提出的模型在有監督和無監督任務中均具有良好的性能。

4 結束語

針對圖卷積神經網絡的譜聚類算法具有局限性，本文提出了基于注意力機制引導的譜聚類模型GATSC。與無注意力引導的譜聚類模型相比較，本文的模型克服了基于模型的池方法和無模型的拉普拉斯矩陣分解方法的缺點，利用注意力機制提高了聚類的準確性、利用改進的圖卷積神經網絡降低了存儲成本。與傳統的解碼器重構相比較，本文的重構模塊降低了重構錯誤，提高了重構準確性，緩解了原始重構效果中邊緣不清晰的缺陷。實驗結果表明，本文提出的模型在Cora、Citeseer、Pubmed 3 個引文網絡聚類、在環形圖和方形圖上重構、在Mutagenicity、Proteins、DD、COLLAB 及Reddit-Binary 5 種圖分類數據集上圖分類，均顯示出良好的性能。然而在進行有監督分類實驗時，本文提出的模型在Reddit-Binary 數據集上表現一般，且不適用于具有多樣性數據集的聚類，因此，下一步的工作是對多樣性數據集進行深度聚類研究。