论文解读(GMIM)《Deep Graph Clustering via Mutual Inform

论文信息

论文标题: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)$

破坏函数 corruption function :

  通过一个破坏函数 $\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

  本文介绍了一个用于节点嵌入的聚类促进目标。我们提出的方法利用对比学习来产生一个聚类友好的潜在空间,假设学习到的表示遵循一个高斯分布的混合。嵌入和聚类目标在一个统一的框架中进行优化,以相互受益。实验表明,结合聚类定向目标函数可以提高图对比学习的聚类能力。我们在真实数据集上评估了该方法的有效性,以证明其有效性,经验结果证明了我们的方法具有良好的性能。

 

原文链接:,转发请注明来源!