论文信息
论文标题：Graph Communal Contrastive Learning
论文作者：Bolian Li, Baoyu Jing, Hanghang Tong
论文来源：2022, WWW
论文地址：download
论文代码：download
1 Introduction
出发点：GCL 中节点级对比损失会有一定概率将同一社区中的节点视为负对，这是不合理的。
首先提出一种基于图结构信息学习社区划分的 Dense Community Aggregation（𝐷𝑒𝐶𝐴）算法。接下来，引入一种新的 Reweighted Self-supervised Cross-contrastive（𝑅𝑒𝑆𝐶）训练方案，将同一社区中的节点在表示空间中拉得更近。
本文框架：多视图对比。
2 Preliminaries
2.1 Similarity Measurement
Exponent cosine similarity:
$delta_{c}left(x_{1}, x_{2}right)=exp left{frac{x_{1}^{T} x_{2} / tau}{left|x_{1}right| cdotleft|x_{2}right|}right} quadquadquad(1)$
$delta_{e}left(x_{1}, x_{2}right)=exp left{-left|x_{1}-x_{2}right|^{2} / tau^{2}right} quadquadquad(2)$
2.2 Community Detection
Modularity. 社区划分中常用的模块度 [42]：
$ m=frac{1}{2 M} sumlimits _{i, j}left[A[i, j]-frac{d_{i} d_{j}}{2 M}right] r(i, j) quadquadquad(3)$
其中，$r(i, j)$ 代表着节点 $i$ 和 节点 $j$ 是否属于同一个社区，模块度测量了每条边对局部边缘密度（local edge density $left(d_{i} d_{j} / 2 Mright)$）的影响。
Edge count function.我们定义了邻接矩阵上的边计数函数（edge count function）：
$E(C)=sumlimits _{i, j} mathbb{1}left{A^{C}[i, j] neq 0right} quadquadquad(4)$
其中 $A^{C}$ 是社区 $C$ 的邻接矩阵。
Edge density function.边密度函数将真实边计数与给定社区 $C_{k}$ 中的最大可能边数进行比较：
${large d(k)=frac{Eleft(C_{k}right)}{left|C_{k}right|left(left|C_{k}right|-1right)} } quadquadquad(5)$
2.3 Attributed Multiplex Graph
Multiplex graphs 也被称为 multi-dimensional graphs [39]或 multi-view graphs[12,23,55]，它由多个单视图图组成，具有共享的节点和属性，但具有不同的图结构（通常具有不同类型的链接）[6]。
3 Method
3.1 Dense Community Aggregation
节点级GCL方法容易出现将结构相近的节点作为负样本配对的问题。本文的方法受到图中的模块化[42]的启发，它测量了社区中的 local edge density 。然而，模块化很容易受到边[36]的变化的干扰，这限制了其在检测社区时的鲁棒性（边缘在每个时代都会动态变化）。
因此，我们的目标是增强模块化的鲁棒性，并通过最大化每个社区的边缘密度来进一步扩展模块化，同时最小化不同社区之间的边缘密度。DeCA 通过端到端训练进行，如 Fig. 3 所示。
我们通过以端到端方式训练一个随机初始化的质心矩阵 $Phi$ 来学习社区划分，其中每个 $Phi[k,:]$ 代表第 $k$ 个社区的中心。
首先，我们将图中的每个节点以一定的概率分配给社区质心(通过相似度函数 $text{Eq.1}$ 、$text{Eq.2}$)。具体地说，我们定义了一个社区分配矩阵 $boldsymbol{R}$，其中每个 $boldsymbol{R}[i,:]$ 都是一个标准化的相似度向量，度量第 $i$ 个节点和所有社区质心之间的距离。在形式上，$boldsymbol{R}$ 是由
$boldsymbol{R}=text { normalize }left(deltaleft(f_{theta}(boldsymbol{X}, boldsymbol{A}), boldsymbol{Phi}right)right) quadquadquad(6)$
其中，$delta(cdot)$ 为 2.1 中定义的相似度函数。$f_{theta}(cdot)$ 是参数为 $theta$ 的图编码器，$normalize (cdot)$ 通过将每个社区的概率除以所有概率之和来归一化，并保持每个 $i$ 的 $sum_{j} R[i, j]=1$。
其次，我们采用了两个目标来训练社区划分：社区内密度 （intra-community density）：
$D_{text {intra }}=frac{1}{N} sumlimits _{i, j} sumlimits_{k}[A[i, j]-d(k)] R[i, k] R[j, k]quadquadquad(7)$
社区间密度（inter-community density ）：
$D_{text {inter }}=frac{1}{N(N-1)} sumlimits_{i, j} sumlimits_{k_{1} neq k_{2}} A[i, j] Rleft[i, k_{1}right] Rleft[j, k_{2}right] quadquadquad(8)$
这两个目标测量了每条边对 community edge density 的影响（而不是在模块化[42]中使用的局部边缘密度）。具体来说，在 $Eq. 7$ 和 $Eq. 8$ 中、$A[i, j]-d(k)$ 和 $A[i, j]-0$ 表示真实局部密度 $(A[i, j])$ 和预期密度（$d(k)$，intercommunity 为 $0$）之间的差距。通过最小化联合目标，将更新质心矩阵 $Phi$，以达到合理的社区划分：
$l_{D e C A}(R)=lambda_{w} D_{text {inter }}-D_{text {intra }} quadquadquad(9)$
其中 $lambda_{w}$ 是系数。此外，为了提高计算效率，我们在实际实现中稍微修改了 $l_{D e C A}$ 的形式(如附录C所示)。最后，我们结合了两个图视图的 $l_{D e C A}$ 目标，并同时对它们进行密集的社区聚合：
$L_{D e C A}=frac{1}{2}left[l_{D e C A}left(R^{1}right)+l_{D e C A}left(R^{2}right)right] quadquadquad(10)$
3.2 Reweighted Self-supervised Cross-contrastive Training
在本节中，我们提出了重加权自监督交叉对比（$ReSC$ ）训练方案。我们首先应用图数据增强来生成两个图视图，然后同时应用节点对比和社区对比来考虑节点级和社区级的信息。我们引入 node-community 对作为额外的负样本，以解决与负样本在相同的社区中配对节点的问题。
3.2.1 Graph augmentation
属性掩藏
$widetilde{X}=[X[1,:] odot boldsymbol{m} ; boldsymbol{X}[2,:] odot boldsymbol{m} ; ldots ldots ; boldsymbol{X}[N,:] odot boldsymbol{m}]^{prime} quadquadquad(11)$
其中，$m[i] sim text { Bernoulli }left(1-p_{v}right)$，$odot $ 代表着 Hadamard product 。
边丢弃
我们通过有概率地从原始边集 $E$ 中随机删除边来生成增广边集 $widetilde{E}$。
$Pleft{left(v_{1}, v_{2}right) in widetilde{E}right}=1-p_{e}, forallleft(v_{1}, v_{2}right) in E quadquadquad(12)$
上述两种数据增强，本文分别定义为 $t^{1}, t^{2} sim T$。
使用上述两种数据增强生成两个视图：$left(X^{1}, A^{1}right)=t^{1}(X, A)$、$left(X^{2}, A^{2}right)=t^{2}(X, A)$。让后通过 GCN 编码器获得他们的表示：$Z^{1}=f_{theta}left(X^{1}, A^{1}right) $ 和 $Z^{2}=f_{theta}left(X^{2}, A^{2}right)$。
3.2.2 Node contrast
在生成两个图视图后，我们同时使用节点对比和社区对比来学习节点表示。我们引入了一个基于InfoNCE[43]的对比损失来对 比节点-节点对：
$I_{N C E}left(Z^{1} ; Z^{2}right)=-log sumlimits_{i} frac{deltaleft(Z^{1}[i,:], Z^{2}[i,:]right)}{sum_{j} deltaleft(Z^{1}[i,:], Z^{2}[j,:]right)} quadquadquad(13)$
我们对这两个图的视图对称地应用节点对比度：
$L_{n o d e}=frac{1}{2}left[I_{N C E}left(Z^{1} ; Z^{2}right)+I_{N C E}left(Z^{2} ; Z^{1}right)right]quadquadquad(14)$
它在两个视图中区分负对，并强制最大化正对[35]之间的一致性。
3.2.3 Community contrast
Community contrast 基于 3.1 DeCA，
首先，我们用 $Eq.10$ 训练随机初始化的社区质心矩阵 $Phi$，得到社区中心。其次，我们采用一个重新加权的交叉对比目标，将一个视图的节点表示与另一个视图的社区质心进行对比（一种交叉对比的方式）。我们受到[4]中的交叉预测方案的启发，并在InfoNCE目标[43]中引入交叉对比，以最大化两个视图之间的社区一致性，强制使一个社区中的节点表示接近另一个视图中对应社区的节点表示。在形式上，社区对比是由
${large begin{array}{l}l_{text {com }}(Z, Phi)=-log sum_{i} frac{deltaleft(Z[i,:], Phileft[k_{i},:right]right)}{deltaleft(Z[i,:], Phileft[k_{i},:right]right)+sum_{k_{i} neq k} w(i, k) cdot delta(Z[i,:], Phi[k,:])}end{array}} quadquadquad(15)$
其中，第 $i$ 个节点被分配给第 $k_{i}$ 个社区。这里的， $w(i, k)=exp left{-gamma|Z[i,:]-Phi[k,:]|^{2}right}$ 是RBF的权值函数(与 $Eq. 2$ 中的高斯RBF相似度略有不同)，这更关注更相似的社区对。在这一目标中，相同社区内的节点表示的相似性最大化，因为它们与相同的质心呈正对比，而在不同的社区中，节点表示被负对比分开。同样，我们对称地计算了生成的两个图视图的对比目标：
$L_{text {com }}=frac{1}{2}left[l_{text {com }}left(Z^{1}, Phi^{2}right)+l_{text {com }}left(Z^{2}, Phi^{1}right)right]quadquadquad(16)$
其中，$Z^{1}$ 和 $Phi^{2}$ 分别为视图1和视图2的节点表示矩阵。
3.2.4 Joint objective
我们提出用 $alpha$-衰减系数将 $L_{n o d e}$, $L_{D e C A}$ 和 $L_{text {com }}$ 结合成一个联合目标：
$L=L_{text {node }}+alpha(t) L_{D e C A}+[1-alpha(t)] L_{text {com }}quadquadquad(17)$
其中，系数 $alpha(t)=exp {-t / eta}$ 会随着训练的进行而顺利衰减($t$ 为epoch)。我们观察到，通过 $DeCA$ 训练，社区分区将稳定在几百个 epoch内，而 $g CooL$ 模型的训练通常需要数千个epoch。为此，我们首先将 $alpha$-衰减主要应用于训练社区划分，并逐步将重点转移到学习节点表示上。
综上所述，$ReSC$ 的训练过程如 Algorithm 1 所示。
3.3 Adaptation to Multiplex graphs
所提出的 $gCooL$ 框架可以很自然地适应于多重图，并对训练和推理过程进行了一些修改。我们在不同的图视图之间应用对比训练，并考虑了它们之间的依赖性。
3.3.1 Training
在多重图中，我们不再需要通过图增强来生成图视图，因为多重图中的不同视图自然是多重查看的数据。我们建议在每对视图上检测社区（𝐷𝑒𝐶𝐴）和学习节点表示（𝑅𝑒𝑆𝐶）。改进后的训练过程如 Algorithm 2 所示。
