圖神經網路時代的深度聚類

Introduction

聚類作為經典的無監督學習演算法在資料探勘/機器學習的發展歷史中留下了不可磨滅的印記。其中，經典的聚類演算法K-Means也被選為資料探勘十大經典演算法。隨著深度學習的興起，一些工作嘗試將深度學習技術（如Autoencoder）引入到傳統聚類演算法中，也取得了不錯的效果。

近些年，圖神經網路已經成為深度學習領域最熱門的方向之一，也在推薦/自然語言處理/計算機視覺等很多領域得到了廣泛的應用。

那麼，能不能利用圖神經網路強大的結構捕獲能力來提升聚類演算法的效果呢？本文梳理總結了圖神經網路賦能的深度聚類演算法，供大家參考。

Models

19IJCAI Attributed Graph Clustering: A Deep Attentional Embedding Approach

Motivation

本文認為之前的深度聚類演算法都是two-step的：首先學習資料的特徵表示embedding，然後基於特徵表示進行資料聚類。這樣所學習的資料embedding並不是任務導向的。那麼，如果能夠在學習embedding的過程中，針對聚類任務做一些針對性的設計，那麼學習到的embedding自然可以實現更好的聚類。

針對上述問題，本文提出了一種聚類導向的深度演算法Deep Attentional Embedded Graph Clustering （DAEGC）。 DAEGC一邊透過圖神經網路來學習節點表示，一邊透過一種自訓練的圖聚類增強同一簇節點之間的內聚性。

下圖清晰的展示two-step和本文所提出的DAEGC的差異。

Model

下圖展示了DAEGC的模型框架

可以看出，整個DAEGC主要包含兩大模組：帶有注意力機制的圖自編碼器+自訓練聚類。

帶有注意力機制的圖自編碼器

這裡就是經典的GAE架構：透過對鄰居的聚合來學習節點表示，然後利用節點對的內積來重構原始網路結構。比較有特色的部分就是結合注意力機制來學習鄰居的權重，這樣可以更好的學習節點表示。

下式展示了融合注意力機制的GAE是如何聚合鄰居資訊來更新節點表示的。本質上就是對鄰居的加權平均。

$z_{i}^{l+1}=\sigma\left(\sum_{j \in N_{i}} \alpha_{i j} W z_{j}^{l}\right) \\$

其中，

$z_{i}^{l},z_{i}^{l+1}$

分別是聚合鄰居資訊前後的節點

的表示，

$N_{i}$

代表節點

的鄰居集合，

$\alpha_{ij}$

表示了節點對

之間的注意力權重。

有了節點表示後， GAE可以透過計算節點對的內積來重構原始網路結構，進而實現無監督的節點表示學習。

$\hat{A}_{i j}=\operatorname{sigmoid}\left(z_{i}^{\top} z_{j}\right) \\$

其中，

$\hat{A}_{i j}$

可以理解為節點對

間存在邊的機率。最後，透過經典的AE重構損失

$L_{r}=\sum_{i=1}^{n} \operatorname{loss}\left(A_{i, j}, \hat{A}_{i j}\right)$

就可以對GAE進行訓練。

自訓練聚類

GAE所學習到的節點表示只是為了更好的重構網路結構，和聚類並沒有直接聯絡。自訓練聚類模組就是對GAE所學習到的embedding進行約束和整合，使其更適合於聚類任務。假定聚類中為

$\mu_{u}$

，那麼節點

屬於某個類別的機率

$q_{i u}$

，如下式所示：

$q_{i u}=\frac{\left(1+\left\|z_{i}-\mu_{u}\right\|^{2}\right)^{-1}}{\sum_{k}\left(1+\left\|z_{i}-\mu_{k}\right\|^{2}\right)^{-1}} \\$

這裡，

$q_{i u}$

可以看作是節點的分配的分佈。進一步的，為了引入聚類資訊來實現聚類導向的節點表示，我們需要迫使每個節點與相應的聚類中心更近一些，以實現所謂的類內距離最小，類間距離最大。因此，我們定義瞭如下的目標分佈：

$p_{i u}=\frac{q_{i u}^{2} / \sum_{i} q_{i u}}{\sum_{k}\left(q_{i k}^{2} / \sum_{i} q_{i k}\right)} \\$

在目標分佈中，透過二次方

$q_{i u}$

可以實現一種“強調”的效果（二次方後，分佈會變得更加尖銳，也更置信）。在訓練過程中，分佈

實際起到了一種標籤的效果。最後，透過計算兩個分佈之間的KL散度，來實現互相約束，也就是所謂的自訓練。

$L_{c}=K L(P \| Q)=\sum_{i} \sum_{u} p_{i u} \log \frac{p_{i u}}{q_{i u}} \\$

綜合起來，模型最終的損失函式為

$L=L_{r}+\gamma L_{c} \\$

節點

的所處於的簇

$\boldsymbol{s}_{i}$

（也可以理解為其標籤）可以透過下式計算：

$\boldsymbol{s}_{i}=\arg \max _{u} q_{i u} \\$

Experiment

作者在3個數據集上進行了實現， DAEGC在大部分情況下都取得了最好的效果。

20WWW Structural Deep Clustering Network

Motivation

深度自編碼器可以透過多層非線性編碼來提取特徵資訊，而圖神經網路可以聚合鄰居資訊來充分挖掘結構資訊。為了同時實現對特徵的降維抽取和對結構資訊的挖掘，本文提出了Structural Deep Clustering Network （SDCN）。透過堆疊多層GNN， SDCN實現了對高階結構資訊的捕獲。同時，受益於自編碼器和GNN的自監督，這裡的多層GNN並不會出現所謂的過平滑現象。過平滑現象指的是，隨著層數的增加，GNN所學習到的節點表示逐漸變得不可區分。

Model

在開始介紹模型之前，需要說明的是：如果資料集本身並沒有圖結構，作者將會透過計算節點之間的Top-K相似性利用KNN手動構建一張圖。下面是兩種相似性計算方法： Heat Kernel和Dotp roduct

$Heat\ Kernel:\mathbf{S}_{i j}=e^{-\frac{\left\|x_{i}-x_{j}\right\|^{2}}{t}} \\$

$Dot\ product: \mathbf{S}_{i j}=\mathbf{x}_{j}^{T} \mathbf{x}_{i} \\$

下圖展示了整個SDCN的模型架構圖。可以看出，整個模型主要包含3個部分： GCN模組，DNN模組和雙重自監督模組。

DNN模組

這裡是一個經典的自編碼器。編碼器將輸入

$\mathbf{X}$

（也就是

$\mathbf{H}^{(0)}$

）透過神經網路編碼為隱表示

$\mathbf{H}$

；解碼器將隱表示

$\mathbf{H}$

解碼為

$\hat{\mathbf{X}}$

（也就是

$\mathbf{H}^{(L)}$

）。

$\mathbf{H}^{(\ell)}=\phi\left(\mathbf{W}_{e}^{(\ell)} \mathbf{H}^{(\ell-1)}+\mathbf{b}_{e}^{(\ell)}\right) \\ \mathbf{H}^{(\ell)}=\phi\left(\mathbf{W}_{d}^{(\ell)} \mathbf{H}^{(\ell-1)}+\mathbf{b}_{d}^{(\ell)}\right)\\ \mathcal{L}_{r e s}=\frac{1}{2 N}\|\mathbf{X}-\hat{\mathbf{X}}\|_{F}^{2} \\$

可以看出，透過重構loss和多層非線性對映，

$\mathbf{H}^{(\ell)}$

可以較好的反映節點的特徵資訊。

GCN模組

另一方面， GCN可以聚合鄰居資訊來更新節點表示，其更新過程如下：

$\mathbf{Z}^{(\ell)}=\phi\left(\widetilde{\mathbf{D}}^{-\frac{1}{2}} \widetilde{\mathbf{A}} \widetilde{\mathbf{D}}^{-\frac{1}{2}} \mathbf{Z}^{(\ell-1)} \mathbf{W}^{(\ell-1)}\right) \\$

其中，

$\mathbf{Z}^{(\ell)}$

是第

$\ell$

層GCN學習到的表示，

$\widetilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}$

是帶有自聯的鄰接矩陣，

$\widetilde{\mathbf{D}}_{i i}=\sum_{j} \widetilde{\mathbf{A}}_{\mathbf{i j}}$

。

截止到目前為止都是一些常規的DNN和GCN。接下來就是SDCN的特色部分：第

$\ell$

層最終表示

$\widetilde{\mathbf{Z}}^{(\ell-1)}$

實際上混合了初始GCN表示

$\mathbf{Z}^{(\ell-1)}$

和DNN的編碼表示

$\mathbf{H}^{(\ell-1)}$

。

$\widetilde{\mathbf{Z}}^{(\ell-1)}=(1-\epsilon) \mathbf{Z}^{(\ell-1)}+\epsilon \mathbf{H}^{(\ell-1)} \\$

可以看出，在這一步，作者將GNN和DNN聯絡了起來。第L層的最終表示可以進一步對映為一個類別機率，

$Z=\operatorname{softmax}\left(\widetilde{\mathbf{D}}^{-\frac{1}{2}} \widetilde{\mathbf{A}} \widetilde{\mathbf{D}}^{-\frac{1}{2}} \mathbf{Z}^{(L)} \mathbf{W}^{(L)}\right) \\$

其中，

$z_{ij}\in Z$

可以看做是節點

屬於類別

的機率，

其實是一個指示了節點處於不同類別的機率分佈。

雙重自監督模組

最後是一個雙重自監督模組，其作用體現在兩個方面：（1）透過GCN部分和DNN部分的互相監督可以實現模型的無監督學習。（2）透過引入聚類資訊來更好的學習任務導向的節點表示。與上一篇19IJCAI Attributed Graph Clustering： A Deep Attentional Embedding Approach類似， SDCN也設計了兩個分佈。這裡不再贅述，詳見上一篇的解讀。

節點的類別分佈為：

$q_{i j}=\frac{\left(1+\left\|\mathbf{h}_{i}-\boldsymbol{\mu}_{j}\right\|^{2} / v\right)^{-\frac{v+1}{2}}}{\sum_{j^{\prime}}\left(1+\left\|\mathbf{h}_{i}-\boldsymbol{\mu}_{j^{\prime}}\right\|^{2} / v\right)^{-\frac{v+1}{2}}} \\$

目標分佈為：

$p_{i j}=\frac{q_{i j}^{2} / f_{j}}{\sum_{j^{\prime}} q_{i j^{\prime}}^{2} / f_{j^{\prime}}} \\$

同樣的，也是最小化兩個分佈之間的KL散度：

$\mathcal{L}_{c l u}=K L(P \| Q)=\sum_{i} \sum_{j} p_{i j} \log \frac{p_{i j}}{q_{i j}} \\$

這裡，我們可以將

$p_{i j}$

視為標籤來對GCN模組進行監督。

$\mathcal{L}_{g c n}=K L(P \| Z)=\sum_{i} \sum_{j} p_{i j} \log \frac{p_{i j}}{z_{i j}} \\$

總的來說，分佈

起到了一個橋接的作用，將DNN所學到的表示和GCN所學習到的表示進行約束。

模型完整損失函式如下：

$\mathcal{L}=\mathcal{L}_{r e s}+\alpha \mathcal{L}_{c l u}+\beta \mathcal{L}_{g c n} \\$

節點

的標籤可以透過下式計算：

$r_{i}=\underset{j}{\arg \max } z_{i j} \\$

Experiment

作者在6個數據集上做了大量的有效性實驗。可以看出， SDCN在所有資料集上都取得了大幅的提升。

比較有意思的實驗是模型層數實驗，如下圖所示。可以看出，隨著層數的增加，模型的效果會有大幅度的提升，並沒有出現過平滑現象。

除此之外，作者還測試了不同的混合係數

$\epsilon$

對模型效果的影響。

19IJCAI Attributed Graph Clustering via Adaptive Graph Convolution

Motivation

與上一篇SDCN相似，本文也利用了高階結構資訊（多層GNN）來提升聚類的效果。儘管這兩篇非常相似，它們也是有一些差異的：（1）本文所提出的AGC是從圖訊號處理譜圖理論的角度來理解GNN並增強了聚類效果；（2）本文所涉及的AGC可以自適應的選擇高階資訊的階數，而SDCN則需要手動指定超引數。

Model

譜域的圖卷積

這裡首先簡單回顧一下譜域的圖卷積：

$\overline{\boldsymbol{f}}=G \boldsymbol{f}=U p(\Lambda) U^{-1} \cdot U \boldsymbol{z}=\sum_{q=1}^{n} p\left(\lambda_{q}\right) z_{q} \boldsymbol{u}_{q} \\$

其中，

$p(\Lambda)$

是一個頻響函式，可以對

$\Lambda$

中的值（也就是特徵值）進行放縮，

$\overline{\boldsymbol{f}}, \boldsymbol{f}$

分別是經過圖濾波器

卷積前後的圖訊號。

$\boldsymbol{f}=U \boldsymbol{z}=\sum_{q=1}^{n} z_{q} \boldsymbol{u}_{q} \\$

這裡，

$\boldsymbol{f}$

可以看做一組基訊號的加權，而這組基是由拉普拉斯矩陣

分解得到的，

$L_s=U \Lambda U^{-1} \\$

其中，

$U=\left[\boldsymbol{u}_{1}, \cdots, \boldsymbol{u}_{n}\right]$

代表

個基向量，

$\Lambda=\operatorname{diag}\left(\lambda_{1}, \cdots, \lambda_{n}\right)$

是一個對角陣，

$\lambda_{q}$

的大小可以反映基向量

$\boldsymbol{u}_{q}$

的平滑程度。

$\begin{array}{l} \Omega\left(\boldsymbol{u}_{q}\right)=\frac{1}{2} \sum_{\left(v_{i}, v_{j}\right) \in \mathcal{E}} a_{i j}\left\|\frac{\boldsymbol{u}_{q}(i)}{\sqrt{d_{i}}}-\frac{\boldsymbol{u}_{q}(j)}{\sqrt{d_{j}}}\right\|_{2}^{2} \\ =\boldsymbol{u}_{q}^{\top} L_{s} \boldsymbol{u}_{q}=\lambda_{q}\end{array} \\$

為什麼這裡需要涉及到“平滑”這個概念呢？圖上的“平滑”程度反映了相鄰節點的相似程度。圖上的高頻意味著不平滑，特徵值大；圖上的低頻意味著平滑，特徵值小。

那麼在一組基中，相對平滑的圖訊號實際上是有利於聚類的。因為聚類的目的是把相似的節點放到一起。

如何實現對低頻訊號的篩選（也就是對高頻訊號的抑制）呢？其實很簡單，我們只要想辦法將較大特徵進行壓縮。回想上面的頻響函式

$p(\Lambda)$

的作用，我們可以設計恰當的

來實現我們的目的

$p\left(\lambda_{q}\right)=1-\frac{1}{2} \lambda_{q} \\$

很明顯，

$\lambda_q$

越大，

$p\left(\lambda_{q}\right)$

越小。相應的圖濾波

可以寫作：

$G=U p(\Lambda) U^{-1}=U\left(I-\frac{1}{2} \Lambda\right) U^{-1}=I-\frac{1}{2} L_{s} \\$

一階圖卷積可以寫作：

$\bar{X}=\left(I-\frac{1}{2} L_{s}\right) X \\$

那麼，k階圖卷積也呼之欲出，

$\bar{X}=\left(I-\frac{1}{2} L_{s}\right)^{k} X \\ p\left(\lambda_{q}\right)=\left(1-\frac{1}{2} \lambda_{q}\right)^{k} \\$

到這裡，也就可以聚合k階鄰居來學習節點表示了，也就是所謂的k階圖卷積。同時注意，卷積過程中抑制了高頻訊號，更多的低頻訊號（更符合聚類要求）被捕獲了。

自適應k選擇

現在還剩一個問題需要解決，圖卷積的k階該如何確定？

這裡作者用了一個啟發式的方法：逐漸增加k，當類內距離開始變小時，停止搜尋。內類距離如下所示

$i n t r a(\mathcal{C})=\frac{1}{|\mathcal{C}|} \sum_{C \in \mathcal{C}} \frac{1}{|C|(|C|-1)} \sum_{v_{i}, v_{j} \in C}\left\|\bar{x}_{i}-\bar{x}_{j}\right\|_{2} \\$

可以看出，這裡k的選擇也是比較符合聚類的要求（類內距離最小，類間距離最大）。

Experiment

作者在4個經典資料集上進行了實驗。總的來說，AGC的效果還是不錯的。

20ArXiv Embedding Graph Auto-Encoder with Joint Clustering via Adjacency Sharing

Motivation

本文與之前幾篇的類似，也是用GNN來學習適合於聚類任務的節點表示。比較特別的是，本文同時考慮了K-Mean聚類和譜聚類來實現更好的聚類。

Model

下圖展示了本文所提出的Embedding Graph Auto-Encoder with JOint Clustering via Adjacency Sharing （EGAE-JOCAS）的整體框架。

圖自編碼器

首先，作者利用圖卷積神經網路來學習節點的表示

，然後利用節點表示來嘗試重構原始圖結構。

$\hat{A}=\sigma\left(\phi\left(Z Z^{T}\right)\right) \\ \\$

略有不同的是，作者這裡對

$Z Z^{T}$

做了一個非線性變換。

$\phi(x)=x-\frac{1}{x} \\$

作者認為

$\phi(x)$

（函式曲線見下圖）可以更好的對節點對的內積進行對映。在

較大的時候，

$\phi(x)$

可以更好的逼近

。

聯合聚類

聯合聚類的公式如下圖所示，

$\min _{G^{T} G=I}\left\|X-F G^{T}\right\|_{F}^{2}+\gamma \operatorname{tr}\left(G^{T} L G\right) \\$

第一項是K-Mean聚類，其中

是一個指示器，實際上反映了節點屬於不同簇的機率。

第二項是譜聚類，直觀的理解就是，相近的節點應該屬於相同的簇。回顧上一篇的“平滑程度”，可以發現它們有異曲同工之妙。

$\begin{array}{l} \Omega\left(\boldsymbol{u}_{q}\right)=\boldsymbol{u}_{q}^{\top} L_{s} \boldsymbol{u}_{q}\end{array} \\$

聯合之前GAE的重構損失，EGAE-JOCAS最終的目標函式為：

$\min _{\hat{A}, Z, F, G^{T} G=I} J(\hat{A}, A)+\alpha\left(\left\|Z-F G^{T}\right\|_{F}^{2}+\gamma \operatorname{tr}\left(G^{T} L G\right)\right) \\$

Experiment

最後，作者在四個資料集上進行了實驗。總的來說，EGAE-JOCAS在所有資料集上都取得了明顯的提升。

Conclusion

聚類是機器學習/資料探勘的一個基礎性問題。從傳統聚類到深度聚類以及現在圖神經網路賦能的聚類，各種各樣的聚類算層出不窮，也在很多領域得到了廣泛的應用。考慮到圖神經網路對結構資訊的捕獲能力，在涉及到群體結構的聚類任務上，本文所介紹的聚類演算法應該會取得更大的提升。

小蜜蜂問答

小蜜蜂問答

圖神經網路時代的深度聚類

推薦文章

小蜜蜂問答

小蜜蜂問答

圖神經網路時代的深度聚類

相關文章

迷你世界如何找到二級傳送器？

馬上30歲了，自學會計晚嗎？

組織生活會內容要求？

豐都九重天溫度怎麼樣？

推薦文章