CommDGI: Community detection oriented deep graph infomax 2020 CIKM

目录

• CommDGI: Community detection oriented deep graph infomax
• • Graph Infomax Layer
  • Trainable Clustering Layer and Community-oriented Objectives
  • Disentangled Learning
  • Joint Optimization
• DEEP GRAPH INFOMAX 2019 ICLR

CommDGI: Community detection oriented deep graph infomax

问题：网络中存在一些无监督的、与结构相关的任务，如社区检测，这是网络分析中的一个基本问题。在这些特殊问题中，一般性的网络仍然很难学到所需要的结构信息。

为了克服通用图表示学习方法的缺点(如两步法，先表示再用如K-means等简单的聚类方法进行社区发现，但聚类步骤很难优化节点的嵌入学习)，提出了社区深度图信息网络(Community Deep graph Infomax, CommDGI)，这是一种用于处理社区检测问题的图神经网络。

受深度图信息在自监督图学习中的成功启发，设计了一种新的互信息机制来捕获图中的邻域和社区信息，采用可训练的集群层以端到端方式学习社区划分。

• 深度社团图信息网络(CommDGI)。该模型结合DGI图互信息最大化的思想，能够以自监督的方式对节点属性进行有效编码。
• 在图神经网络中加入了一个可训练的聚类层。我们采用模块化目标，在属性图上设计了一个新的社区检测目标——社区互信息，以帮助学习社区相关节点表示。
• 在聚类层中采用解纠缠表示法进行节点信息的训练和挖掘，提高了整个模型的可解释性。
• 该模型可以直接学习社区分区，利用多目标优化节点表示。 同时对聚类步和节点表示学习步进行优化。

上图说明了一般的图神经网络社区发现的两步方法的缺点。在一般意义上的图形神经网络中，社区检测是按顺序执行的，因此编码器倾向于将邻居节点转换到更紧密的向量空间(上图的B与C)。然而，社区检测问题需要更高阶的结构信息，一个社区中没有直接边连接的节点可能比邻居节点更相似(上图的A与B)。在面向社区检测的图形神经网络中，需要解决这些社区检测问题。

Graph Infomax Layer

这一层的思想类似于 DGI，即我们在图级表示和节点级表示之间最大化图 MI。

编码器 e 是一个图卷积网络(GCN)模型：

我们在这里应用对比方法来帮助促进学习的节点表示，以更好地捕获在属性图中不同节点的结构相似性。负采样邻接矩阵 A ~ \tilde{A} A~与原始邻接矩阵A相同，原始特征 x 随机排列得到负采样特征 x ~ \tilde{x} x~,我们可以学习负的采样节点表示 H ~ = E ( X ~ , A ~ ) \tilde{H} = \mathcal{E}(\tilde{X}, \tilde{A}) H~=E(X~,A~)

为了获得图级表示，定义一个Readout函数，R:R𝑛×𝑑′→ R𝑑′。

我们使用一个鉴别器来帮助最大化局部互信息，D: R𝑑’ × R𝑑’→R，D(ℎ𝑖，𝑆)代表分配给这个patch-summary对的概率分数(对于包含在summary中的patch，应该更高)。具体来说，我们用两个向量的点积加上一个sigmoid函数来实现鉴别器D。

图 MI 目标使用噪声对比型目标，标准二进制交叉熵(BCE)损失在联合样本(正样本)和边际乘积(负样本)之间。我们提出以下图表 MI 损失:
N,M分别代表正负样本数目。
社区深度图信息系统(CommDGI)的概念框架。给定一个属性图，CommDGI通过深度图信息编码器学习一个隐藏节点表示，并使用可训练的聚类层对其进行 *** 作，该聚类层与图编码器一起优化，并在训练时进行聚类分配。我们从节点级(图MI)、社区级(社区MI)和图级(模块度)三个尺度中选择目标。

Trainable Clustering Layer and Community-oriented Objectives

在这个集群层中，实现了一个可微 K平均算法，它将节点和嵌入空间的集群中心进行软分配。

对于节点 v i v_i vi​及其嵌入表示 h i h_i hi​， u k u_k uk​表示聚类k的聚类中心，$ R={r_{ik}} $表示软K-means的分配矩阵（隶属矩阵），对应的值代表分配的程度。具体地说，我们使用软最小值分配来根据距离将每个点分配到聚类中心。我们使用范数∥·∥作为负余弦相似度，因为它有较强的经验性能。𝛿是一个逆温度超参数，它定义了使用集群过程的硬度。我们可以通过类似于典型的K-means更新的迭代过程来优化聚类中心，交替设置:
这些迭代收敛到一个不动的点，在连续的更新之间𝜇保持不变。在不展开整个迭代轨迹[30]的情况下，可以有效地逼近该层的向后传递。

在得到聚类分配 r 和聚类参数 μ 的可微性方式后，我们需要一种方法来可微地将聚类解释为优化问题的软解，并根据这种解来区分图的目标值的松弛最佳化问题。在这个框架中，提出了一个面向社区的多元智能模型。社区多元智能可以促进表征在图学习中对节点的社区特征进行编码。

CommDGI 中的社区 MI 采用节点表示作为本地信息，集群中心作为社区级信息。我们在这里仍然使用鉴别器 D来表示分配给每个patch-summary对的概率得分。

类似于图 MI 最大化的意图，社区 MI 最大化估计鼓励框架在更新时学习每个节点的更多社区级信息，从而使得 CommDGI 的学习嵌入可以面向社区检测，不同于一般意图神经网络。

模块化是社区检测优化中的一个经典目标，它用于评估社区中网络分区的质量。我们可以将模块化目标应用到我们的聚类层中:
这是根据分配𝑅抽样的分区的期望值。

Disentangled Learning

现有的图形神经网络一般采用整体表示学习的方法: 节点学习的表示方法将节点的邻域描述为一个感知的整体。因此，邻域的不同部分之间的细微差别被忽略。然而，图的形成往往表现出一种社区结构，表明现实世界网络中的节点通常由于各种原因(例如，公司、兴趣、家庭)而与其他节点联系在一起，因而具有由若干不同组成部分组成的邻域。

关于解纠缠可以查看这篇论文《Independence Promoted Graph Disentangled Networks》

在社区检测问题中，一个解纠缠的表示可以更容易解释。

我们可以很自然地假设同一社区中的节点在特定方面具有相似的表示形式。不同群体的表征决定方面也是多种多样的。一个节点可以根据它在一个特定组件上的特性被分配一个特定的社区(在本文中我们称之为一个特殊的通道)。

我们将节点𝑣𝑖的表示定义为ℎ𝑖={ℎ𝑖1，ℎ𝑖2，…，ℎ𝑖𝐾}其中ℎ𝑖∈R𝑑’和ℎ𝑖𝑘∈R{𝑑’/𝐾}表示与社区𝑘相关的第k个通道上的表示。节点𝑣𝑖，ℎ𝑖的表示是{ℎ𝑖1，ℎ𝑖2，…ℎ𝑖𝐾}的连接结果。

通道的数量由图学习前社区的数量决定。在应用解缠 *** 作后，我们重写了聚类层的节点分配公式:
其中𝜇𝑘𝑘是社区𝑘的集群中心的第k个通道表示。𝜇𝑘的其余通道由每个节点表示的平均值定义。换句话说，我们只是将与社区𝑘相关的信息聚合到社区中心嵌入中。

通过这种分离的表示聚合，模型的社区MI可以以不同的方式更新，CommDGI可以学习节点和社区的分离信息，能够捕获比传统学习模式更具体的社区相关特性。

算法伪代码：

Joint Optimization

我们联合优化图表示学习和聚类层，并定义我们的总目标函数为:
我们可以直接从最后一个优化结果中得到我们的社区检测结果，并且得到的节点 i 的估计标签为:
这是最后一个软 K-means隶属分布 r 中最有可能的赋值。

这个方法的主要特点可以总结为无监督、面向聚类、解纠缠、端到端。

DEEP GRAPH INFOMAX 2019 ICLR

提出了深度图信息(DGI)，这是一种以无监督方式在图结构数据中学习节点表示的通用方法。

DGI 的作用在于最大化邻近表示（patch representation）与对应的高阶图摘要（high-level summaries of graphs）之间的互信息（MI）——它们都是使用已建立的图卷积网络体系结构推导出来的。

学习过的ptch表示以感兴趣的节点为中心总结子图(基于此点表示了全局信息)，因此可以在下流节点学习任务中重用。与大多数之前使用GCNs进行的无监督学习的方法相比，DGI不依赖于随机游走目标，并且很容易适用于直推式和归纳学习设置。

随机游走的问题是目标被认为过分强调邻近信息，以牺牲结构信息为代价，性能高度依赖于超参数选择

通过互信息神经估计(MINE) ，可伸缩的互信息估计变得可能和实用，它依赖于训练一个统计网络作为来自两个随机变量及其边际乘积的样本的分类器。在 MINE 之后，Hjelm 等人(2018)引入了用于学习高维数据表示的 Deep InfoMax (DIM)。DIM 训练了一个编码器模型，以最大化高级“全局”表示和输入的“局部”部分(如图像的补丁)之间的相互信息。这鼓励编码器携带出现在所有位置(因此是全局相关的)的信息类型，例如类标签的情况。

将DIM的思想应用到图域，可以认为图域具有比卷积神经网络捕获的结构更一般的类型。

DGI可以看作是对比学习。

DGI METHODOLOGY

学习编码器 ε ( X , A ) = H = h 1 , h 2 , . . . , h N \varepsilon(X,A) = H = {h_1,h_2,...,h_N} ε(X,A)=H=h1​,h2​,...,hN​输出为每个节点的高阶表示。这个编码器就是GCNs，因为卷积能把邻近节点的信息传递到这个点上，所以本文称这个点的表示 h i h_i hi​为patch representation。

局部-全局 互信息最大化：

编码器学习需要一个目标函数，这个目标函数的目的是最大化互信息：每个节点的局部表示（也就是 h i h_i hi​）与整个图的全局信息内容（表示为向量 s ）；这样的话每个节点的表示就能用一定的全局信息在里面了。

s用一个函数 R \mathcal R R 直接映射出来， s = R ( ε ( X , A ) ) , s ∈ R F s = \mathcal R(\boldsymbol{\varepsilon}(X,A)),s\in R^F s=R(ε(X,A)),s∈RF,表示一个图级别的摘要。

还需要一个判别器D ，拿来用： D ( h i , s ) D(h_i,s) D(hi​,s)表示分配给这对patch-summary对的概率分数；注意 h i h_i hi​是一个点的嵌入表示，s是整个图的摘要，因此每一个点都要与s做计算；

负样本用在判别器上，负样来来源于一个假图 ( X ˉ , A ˉ ) (\bar X,\bar A) (Xˉ,Aˉ)上生成的 h ˉ i \bar h_i hˉi​结合上面的s 来作为负样本；这样的话，这是一个二分类的判别器（二元交叉熵(BCE)损失）：

通过上式可以有效地最大化 h i ⃗ \vec{h_i} hi​ ​和 s ⃗ \vec{s} s 之间的互信息。

由于所有导出的patch representations都是为了保存与全局图总结的互信息，这允许在patch级别上发现和保存相似性——例如，具有相似结构的远距离节点（众所周知，这对于许多节点分类任务来说是一个强大的预测因素）。

OVERVIEW OF DGI

1. 输入(X,A),总结Deep Graph Infomax过程的步骤:
2. 使用损坏函数(corruption function)取样一个反例： ( X ~ , A ~ ) ∼ C ( X , A ) (\widetilde{X},\widetilde{A}) \sim C(X,A) (X ,A )∼C(X,A).
3. 通过编码器获得输入图的补丁表示(patch representations) h ˉ i : H = ε ( X , A ) = { h ˉ 1 , h ˉ 2 , . . . , h ˉ N } \bar h_i:H = \varepsilon{(X,A)} = \{\bar h_1,\bar h_2,...,\bar h_N\} hˉi​:H=ε(X,A)={hˉ1​,hˉ2​,...,hˉN​}.
4. 通过编码器获得负样本的patch representations h ~ j ⃗ \vec{\widetilde{h}_j} h j​ ​: H ~ = E ( X ~ , A ~ ) = { h ~ 1 ⃗ , h ~ 2 ⃗ , . . . , h ~ M ⃗ } \widetilde{\pmb{H}}=\mathcal{E}(\widetilde{\pmb{X}},\widetilde{\pmb{A}})=\{ \vec{\widetilde{h}_1},\vec{\widetilde{h}_2},..., \vec{\widetilde{h}_M}\} HHH =E(XXX ,AAA )={h 1​ ​,h 2​ ​,...,h M​ ​}.
5. 通过 Readout 函数传递输入图的patch representations来得到图级别的summary vector： s ⃗ = R ( H ) \vec{s}=\mathcal{R}(\pmb{H}) s =R(HHH).
6. 通过梯度下降法最小化目标函数式（1），更新参数 E 、 R 、 D \mathcal{E}、\mathcal{R}、\mathcal{D} E、R、D.
   
   直推式学习

编码器是一层图卷积网络(GCN)模型，具有以下传播规则：
其中， A ^ = A + I N \hat{A}=A+I_N A^=A+IN​代表加上自环的邻接矩阵， D ^ \hat{D} D^代表相应的度矩阵，满 D ^ i i = ∑ j A ^ i j \hat{D}_{ii}=\sum_j\hat{A}_{ij} D^ii​=∑j​A^ij​。对于非线性激活函数 σ \sigma σ，选择PReLU。 Θ ∈ R F × F ′ \Theta∈R^{F×F'} Θ∈RF×F′ 是应用于每个节点的可学习线性变换。 对于损坏函数C ，直接采用 A ~ = A \widetilde{A} = A A =A，但是 X ~ \widetilde{X} X 是由原本的特征矩阵X经过随机变换得到的。也就是说，损坏的图由与原始图完全相同的节点组成，但它们位于图中的不同位置，因此将得到不同的邻近表示。

大图上的归纳式学习

对于归纳学习，不再在编码器中使用GCN更新规则（因为学习的滤波器依赖于固定的和已知的邻接矩阵）；相反，我们应用平均池（ mean-pooling）传播规则，GraphSAGE-GCN：
D − 1 D ^ −1 D−1实际上执行的是标准化的和(因此是 mean-pooling)。尽管式（4）明确指定了邻接矩阵和度矩阵，但并不需要它们：因为 Const-GAT 模型中使用的持续关注机制可以观察到相同的归纳行为。 对于Reddit数据库，DGI 的编码器是一个带有跳过连接的三层均值池模型：
为了在此设置中定义破坏函数，DGI 使用与在直推式学习中类似的方法，但将每个次采样的patch作为一个单独的要破坏的图(即在次采样的patch中按行随机打乱特征矩阵)。这很可能导致中心节点的特征被替换为抽样邻居的特征，进一步鼓励负样本的多样性。然后将在中心节点中获得的patch表示提交给鉴别器。

多图上的归纳式学习 例如 PPI 数据集，编码器是一个带有密集跳过连接的三层均值池模型
其中， W s k i p W_{skip} Wskip​ 是一个可学习的投影矩阵。

在这个多图设置中，DGI 选择使用随机抽样的训练图作为负样本(即，DGI 的破坏函数只是从训练集中抽样一个不同的图)。

Readout，鉴别器的细节

在所有三个实验设置中，作者使用了相同的readout函数和discriminator体系结构。

对于 Readout Function，作者使用所有节点特征的简单平均值：

作者通过应用一个简单的双线性评分函数对图级别的summarize-patch representation对进行评分：
其中，W 是一个可学习的评分权重参数， σ \sigma σ是逻辑Sigmoid非线性，用于将分数转换为 ( h i ⃗ , s ⃗ ) (\vec{h_i},\vec{s}) (hi​ ​,s )为正对的概率。