論文解讀（GMIM）《Deep Graph Clustering via Mutual Information Maximization and Mixture Model》
論文信息
論文標題：Deep Graph Clustering via Mutual Information Maximization and Mixture Model
論文作者：Maedeh Ahmadi, Mehran Safayani, Abdolreza Mirzaei
論文來源：2022, arXiv
論文地址：download
論文代碼：download
1 Introduction
結合高斯混合模型+對比學習。
2 Method
總體框架
2.1 Node Embedding
Encoder ： $\mathcal{E}(X, A)=H=\left\{h_{1}, h_{2}, \ldots, h_{N}\right\} \in \mathbb{R}^{N \times F}$
本文選取的 Encoder 是單層的 GCN：
$\mathcal{E}(X, A)=\operatorname{PReLU}\left(\widehat{D}^{-\frac{1}{2}} \hat{A} \widehat{D}^{-\frac{1}{2}} X \Phi\right) \quad\quad\quad(3)$
通過一個破壞函數 $\tilde{G}=C(G)$ 打亂 $X$ 的行，生成負圖 $\tilde{G}$。
Readout function ：
獲得圖級表示：
$s=\mathcal{R}(H)=\sigma\left(1 / N \sum_{i=1}^{N} h_{i}\right)$
鑒別器（discriminator）：
$\mathcal{D}(h, s)=\sigma\left(h^{T} W s\right) \quad\quad\quad(1)$
為了使 $h_{i}$ 和和向量 $s$ 之間的互信息最大化，採用最小化下述交叉熵損失：
${\large \mathcal{L}_{M I}=-\frac{1}{2 N}\left(\sum\limits _{i=1}^{N} \mathbb{E}_{(X, A)}\left[\log \mathcal{D}\left(h_{i}, s\right)\right]+\sum\limits _{j=1}^{N} \mathbb{E}_{(\tilde{X}, \tilde{A})}\left[\log \left(1-\mathcal{D}\left(\tilde{h}_{j}, s\right)\right)\right]\right)} \quad\quad\quad(2)$
2.2 Graph Diffusion
消息傳遞的神經網絡在圖的直接節點之間傳遞消息。雖然他們試圖在深層聚合來自高階鄰居的消息，但由於過度平滑現象，他們大多數在 $2$ 層網絡中達到了最好的性能。只獲取一跳的鄰居信息是存在局限性的，一些方法試圖捕獲圖中的高階信息。其中一個成功的方法之一是圖擴散卷積(GDC)。它用一個擴散矩陣代替鄰接矩陣，並表示為
$S=\sum\limits _{k=0}^{\infty} \Theta_{k} T^{k} \quad\quad\quad(4)$
典型的圖擴散 Personalized PageRank (PPR)，PPR 擴散的封閉形式的解決方案如下：
$S^{\mathrm{PPR}}=\alpha\left(I_{n}-(1-\alpha) D^{-\frac{1}{2}} A D^{-\frac{1}{2}}\right)^{-1} \quad\quad\quad(5)$
其中，$T=A D^{-1}$ ，$ \Theta_{k}=\alpha(1-\alpha)^{k}$.
2.1.3 Gaussian Mixture Modeling for Community Detection
假設通過一個參數為 $\Psi $ 的節點嵌入模型，為圖中的每個節點計算了一個節點嵌入 $v_{i}$。本文認為每個節點都是由一個多元高斯分佈生成的。然後，圖中所有節點的高斯混合模型的似然值：
$p(V)=\prod_{i=1}^{|V|} \sum\limits _{K=1}^{K} p\left(c_{i}=k\right) p\left(v_{i} \mid c_{i}=k ; \Psi, \mu_{k}, \Sigma_{k}\right) \quad\quad\quad(6)$
這裡 $c_{i}$ 表示節點 $i$ 的軟社區分配，$p\left(c_{i}=k\right)$ 表示節點 $i$ 被分配給社區 $k$ 的概率。$p\left(v_{i} \mid c_{i}=k ; \Psi, \mu_{k}, \Sigma_{k}\right)$ 是一個多元高斯分佈如下：
$p\left(v_{i} \mid c_{i}=k ; \Psi, \mu_{k}, \Sigma_{k}\right)=N\left(h_{i} \mid \mu_{k}, \Sigma_{k}\right) \quad\quad\quad(7)$
為方便，將 $p\left(c_{i}=k\right) $ 表示為 $\pi_{i, k}$，其中 $\sum\limits _{k=1}^{K} \pi_{i, k}=1$。對於 $i=1, \ldots,|V|$ 和$k=1, \ldots, K$，高斯混合的參數是 $\Pi=\left\{\pi_{i, k}\right\}, M=\left\{\mu_{k}\right\}$ 和 $\sum\limits =\left\{\Sigma_{k}\right\}$ 。假設協方差矩陣 $\Sigma_{k}$ 是對角矩陣。
2.1.4 Clustering-friendly Node Embedding
我們提出了一個促進聚類的目標，它輸出一個適合聚類的潛在空間。我們假設學習到的潛在空間遵循一個MoG分佈。我們定義的目標函數有兩部分：嵌入和聚類。嵌入部分利用LMI的自學習目標進行節點表示學習，聚類模塊試圖強制執行這種表示，以遵循 MoG 分佈。後一個目標是通過最小化 MoG 分佈下的負對數似然(NLL)來實現的：
$L_{N L L}=-\sum\limits _{i=1}^{|V|} \log \sum\limits _{k=1}^{K} \pi_{i, k} \mathcal{N}\left(h_{i} \mid \mu_{k}, \Sigma_{k}\right) \quad\quad\quad(8)$
我們的總損失函數被定義為：
$\mathcal{L}=\omega \mathcal{L}_{M I}+\beta \mathcal{L}_{N L L} \quad\quad\quad(9)$
其中，$\mathcal{L}_{M I}$ 和 $\mathcal{L}_{N L L}$ 分別為互信息損失和負對數似然(NLL)。在優化了我們的目標之後，我們有了一個k-means友好的潛在空間，在這個空間上我們應用k-means算法來得到最終的節點簇。
2.1.5 Inference
總損失函數由兩組參數組成：節點嵌入參數（ $\Psi$ ）和MoG參數($\Pi$、$M$ 和 $\Sigma$)。為了優化這些參數，我們使用了一種迭代的方法，通過固定一個集合和優化另一個集合。我們通過使用 $\text{Eq.2}$ 作為損失函數來訓練模型來初始化 $\Psi$ 參數。為了初始化MoG參數，我們對 $\Psi $ 初始化實現的嵌入應用 K-means 算法。我們使用K-means算法的硬分配結果進行初始化( $\Pi$, $M$, $\Sigma$)。這種迭代方法的細節如下所述。
Fixing $\Psi$ Parameters and Optimizing $(\Pi, M, \Sigma)$
固定深度網絡參數，我們使用期望最大化算法進行優化$(\Pi, M, \Sigma)$。使用以下方程迭代更新這些參數：
$\pi_{i, k}=\frac{N_{k}}{|V|} \quad\quad\quad(10)$
$\mu_{k}=\frac{1}{N_{k}} \sum\limits _{i=1}^{|V|} \mathcal{V}_{i k} h_{i} \quad\quad\quad(11)$
$\Sigma_{k}=\frac{1}{N_{k}} \sum\limits _{i=1}^{|V|} \mathcal{V}_{i k}\left(h_{i}-\mu_{k}\right)\left(h_{i}-\mu_{k}\right)^{T} \quad\quad\quad(12)$
其中
$\mathcal{V}_{i k}=\frac{\pi_{i, k} \mathcal{N}\left(h_{i} \mid \mu_{k}, \Sigma_{k}\right)}{\sum\limits _{k^{\prime}=1}^{K} \pi_{i, k^{\prime}} \mathcal{N}\left(h_{i} \mid \mu_{k^{\prime}}, \Sigma_{k^{\prime}}\right)} \quad\quad\quad(13)$
$\mathcal{N}_{k}=\sum\limits _{i=1}^{|V|} \mathcal{V}_{i} k \quad 1 \leq k \leq K \quad\quad\quad(14)$
Fixing $(\Pi, M, \Sigma)$ and Updating $\Psi$ Parameters
在固定 MoG 參數後，我們使用隨機梯度下降(SGD)優化了相對於 $\Psi$ 參數的總損失函數 $\text{Eq.6}$。$\Psi$由的可學習評分矩陣$W$、編碼器參數 $\Phi $ 和的PReLU參數組成。Algorithm 1 總結了我們提出的方法。
3 Experiment
數據集
在我們的實驗中，我們使用了兩個廣泛使用的標準網絡數據集(Cora和Pubmed)來進行屬性圖社區檢測。
在Cora數據集上的聚類結果
在 Pubmed 數據集上的可視化結果
在 Pubmed 數據集上的聚類結果
消融實驗
4 Conclusion
本文介紹了一個用於節點嵌入的聚類促進目標。我們提出的方法利用對比學習來產生一個聚類友好的潛在空間，假設學習到的表示遵循一個高斯分佈的混合。嵌入和聚類目標在一個統一的框架中進行優化，以相互受益。實驗表明，結合聚類定向目標函數可以提高圖對比學習的聚類能力。我們在真實數據集上評估了該方法的有效性，以證明其有效性，經驗結果證明了我們的方法具有良好的性能。
