论文解读（GCC）《Efficient Graph Convolution for Joint Node RepresentationLearning and Clustering》

论文信息

论文标题：Efficient Graph Convolution for Joint Node RepresentationLearning and Clustering
论文作者：Chakib Fettal, Lazhar Labiod,Mohamed Nadif
论文来源：2021, WSDM
论文地址：download
论文代码：download

1 Introduction

 　　一个统一的框架中解决了节点嵌入和聚类问题。

2 Method

　　整体框架：

　　

2.1 Joint Graph Representation Learning and Clustering

　　将同时进行的节点嵌入和聚类问题表述如下

　　　　 min θ1,θ2,G,F‖decθ2(encθ1(agg(A,X)))−agg(A,X)‖2⏟reconstruction term +α‖encθ1(agg(A,X))−GF‖2⏟clustering regularization term  s.t. G∈{0,1}n×k,G1k=1n(1) min θ1,θ2,G,F s.t. ∥decθ2(encθ1(agg(A,X)))−agg(A,X)∥2reconstruction term +α∥encθ1(agg(A,X))−GF∥2clustering regularization term G∈{0,1}n×k,G1k=1n(1)

　　其中：

• • G∈{0,1}n×kG∈{0,1}n×k 是二值分类矩阵；
  • F∈Rk×dF∈Rk×d 在嵌入空间中发挥质心的作用；
  • αα 是调节寻求重构和聚类之间权衡的系数；

　　注意，聚类正则化器是编码观测值上的均值聚类损失[25]。它惩罚不导致聚类友好表示的变换。

2.2 Linear Graph Embedding

　　Encoder 类似 Linear graph autoencoders (LGAE) [33] ，本文提出：

　　　　Z=enc(agg(A,X);W1)=agg(A,X)W1Z=enc(agg(A,X);W1)=agg(A,X)W1

　　Decoder 即一个简单的线性变换：

　　　　dec(Z;W2)=ZW2dec(Z;W2)=ZW2

2.3 Normalized Simple Graph Convolution

　　本文的聚合函数受到 SGC [42] 中提出的简单图卷积的启发。设为：

　　　　agg(A,X)=TpXagg(A,X)=TpX

　　其中，TT 不是添加了自环的对称标准化邻接矩阵，本文 TT  定义为 ：

　　　　T=D−1T(I+˜S)T=D−1T(I+S~)

　　其中：

• • ˜S=˜D−1/2˜A˜D−1/2S~=D~−1/2A~D~−1/2；
  • ˜A=A+IA~=A+I；
  • ˜DD~ 是从 ˜AA~ 得出的度矩阵；
  • DTDT 是从 I+˜SI+S~ 得出的度矩阵；

　　GCN 的频率响应函数 p(λ)=1−˜λi∈[−1,1)p(λ)=1−λ~i∈[−1,1)。

　　SGC 的传播矩阵为 I−˜S=I−˜D−1/2(I−˜L)˜D−1/2I−S~=I−D~−1/2(I−L~)D~−1/2，其频率响应函数为 h(˜λl)=1−˜λlh(λ~l)=1−λ~l，该滤波器在 [0,1][0,1] 上是低通的，而不是 [0,1.5][0,1.5]。然后，本文建议进一步添加自循环和行规范化矩阵 ˜SS~。这将产生以下影响

• • 从谱域的角度来看：所提出的归一化进一步缩小了矩阵的谱域到 [0,1][0,1] 中，如图2所示，这使得滤波器真正的低通；
  • 从空间域的角度来看：每个转换后的顶点成为邻居的加权平均值，这更直观，但它也考虑了列度信息，不像直接随机游走邻接归一化；

　　本文的问题变成：

　　　　min G,F,W1,W2‖TpX−TpXW1W2‖2+α‖TpXW1−GF‖2 s.t. G∈{0,1}n×k,G1k=1nmin G,F,W1,W2 s.t. ∥TpX−TpXW1W2∥2+α∥TpXW1−GF∥2G∈{0,1}n×k,G1k=1n

　　前项代表自编码器重构作用，后项代表嵌入空间聚类的作用。本文对于权重系数取相等（α=1α=1）。

2.5 Graph Convolutional Clustering

　　为使得嵌入空间信息和聚类信息相互补充，本文设置 W=W1=W⊤2W=W1=W⊤2，并添加一个正交性约束，所以 Eq.4Eq.4 变为：

　　　　min G,F,W‖TpX−TpXWW⊤‖2+‖TpXW−GF‖2 s.t. G∈{0,1}n×k,G1k=1n,W⊤W=Ik(5)min G,F,W s.t. ∥∥TpX−TpXWW⊤∥∥2+∥TpXW−GF∥2G∈{0,1}n×k,G1k=1n,W⊤W=Ik(5)

　　与 [43] 类似，该问题等价于

　　　　min G,F,W‖TpX−GFW⊤‖2 s.t. G∈{0,1}n×k,G1k=1n,W⊤W=Ik(6)min G,F,W s.t. ∥∥TpX−GFW⊤∥∥2G∈{0,1}n×k,G1k=1n,W⊤W=Ik(6)

证明：

　　首先分解重构项：

　　　　‖TpX−TpXWW⊤‖2=‖TpX‖2+‖TpXWW⊤‖2−2‖TpXW‖2=‖TpX‖2−‖TpXW‖2 due to W⊤W=Ik∥∥TpX−TpXWW⊤∥∥2=∥TpX∥2+∥∥TpXWW⊤∥∥2−2∥TpXW∥2=∥TpX∥2−∥TpXW∥2 due to W⊤W=Ik

　　其次，聚类正则化项分解为：

　　　　‖TpXW−GF‖2=‖TpXW‖2+‖GF‖2−2Tr((TpXW)⊤GF)∥TpXW−GF∥2=∥TpXW∥2+∥GF∥2−2Tr((TpXW)⊤GF)

　　上述两个结果表达式求和：

　　　　‖TpX‖2+‖GF‖2−2Tr((TpXW)⊤GF)=‖TpX−GFW⊤‖2 due to ‖GFW⊤‖=‖GF‖∥TpX∥2+∥GF∥2−2Tr((TpXW)⊤GF)=∥∥TpX−GFW⊤∥∥2 due to ∥∥GFW⊤∥∥=∥GF∥

　　因此，优化 Eq.5Eq.5 等价于优化 Eq.6Eq.6。

3 Optimization and algorithm

　　该算法交替固定 FF、GG 和 WW 中两个矩阵 ，并求解第三个矩阵。

3.1 Optimization Procedure

Initialization

　　对 TpXTpX 应用主成分分析(PCA) 得到的前 ff 个分量来初始化 WW。然后在 TpXTpX 上应用 k-means 得到 FF 和 GG。

Update Rule for FF

　　通过固定 GG 和 WW 并求解 FF，我们得到了一个线性最小二乘问题。通过将导数设为零，得到了对给定问题的最优解的正态方程。然后是更新规则

　　　　F=(G⊤G)−1G⊤TpXW(7)F=(G⊤G)−1G⊤TpXW(7)

　　直观地说，每个行向量 fifi 被设置为分配给集群 ii 的嵌入 XWXW 的平均值。并通过 K-means 更新质心矩阵。

Update Rule for WW

　　固定 Eq.6Eq.6 中的 FF 和 GG，所以更新规则如下：

　　　　W=UV⊤ s.t. [U,Σ,V]=SVD((TpX)⊤GF)W=UV⊤ s.t. [U,Σ,V]=SVD((TpX)⊤GF)

　　其中，

• • Σ=(σii)Σ=(σii)　　
  • UU 和 VV 分别代表 (TpX)⊤GF(TpX)⊤GF 的特征值和左、右特征向量；

　　固定 FF 和 GG 产生如下问题：

　　　　min W‖TpX−GFW⊤‖2 s.t. W⊤W=Ik.min W∥∥TpX−GFW⊤∥∥2 s.t. W⊤W=Ik.

　　因为：‖TpX−GFW⊤‖2=‖TpX‖2+‖GFW⊤‖2−2Tr(WF⊤G⊤TpX)∥∥TpX−GFW⊤∥∥2=∥TpX∥2+∥∥GFW⊤∥∥2−2Tr(WF⊤G⊤TpX) 和 ‖GFW⊤‖2=‖GF‖2∥∥GFW⊤∥∥2=∥GF∥2，所以 Eq.9Eq.9 等价于

　　　　maxWTr(WF⊤G⊤TpX) s.t. W⊤W=Ik.maxWTr(WF⊤G⊤TpX) s.t. W⊤W=Ik.

　　由于 [U,Σ,V]=SVD(F⊤G⊤TpX)[U,Σ,V]=SVD(F⊤G⊤TpX)，所以有

　　　　Tr(WF⊤G⊤TpX)=Tr(WUΣV⊤)=f∑i=1σii<w′iU,v′i>≤f∑i=1σii‖w′iU‖×‖v′i‖=f∑i=1σii=Tr(Σ)Tr(WF⊤G⊤TpX)=Tr(WUΣV⊤)=∑i=1fσii<w′iU,v′i>≤∑i=1fσii∥∥w′iU∥∥×∥∥v′i∥∥=∑i=1fσii=Tr(Σ)

　　这意味着当 Tr(WUΣV⊤)=Tr(Σ)Tr(WUΣV⊤)=Tr(Σ) 或当 V⊤WU=IV⊤WU=I 时达到了 Eq.9Eq.9 的上界，即在 W=VU⊤W=VU⊤ 时达到了最大值。

Update Rule for G

　　通过固定 FF 和 WW 并求解 FF，我们得到了一个可以通过 k-means 算法的分配步骤进行优化的问题。那么，更新规则定为

　　　　gij∗←{1 if j∗=argminj‖(TpXW)i−fj‖20 otherwise. (10)

3.2 The GCC Algorithm

　　算法步骤如 Algorithm 1 所示：

　　

　　传播阶 p 的选择对算法的整体性能非常重要。较小的 p 可能意味着传播的邻域信息不足，而较大的 p  可能导致图信号的过度平滑。Figure 3 显示了使用 t-SNE 算法[39]对不同 p 值的 Cora 数据集的投影。

　　

　　对于 p 的选择如 Algorithm 2 所示：

　　

4 Experiments

数据集

　　

聚类结果

　　

运行时间

　　

5 Conclusion

　　在本文中，我们利用图卷积网络的简单公式，得到了一个有效的模型，在一个统一的框架中解决了节点嵌入和聚类问题。首先，我们提供了一个归一化，使GCN编码器在严格意义上充当低通滤波器。其次，我们提出了一种新的方法，其中需要优化的目标函数利用了来自GCN嵌入重建损失和这些嵌入的簇结构的信息。第三，我们推导了复杂性被严格研究的GCC。在此过程中，我们展示了GCC如何以更有效的方式比其他图聚类算法获得更好的性能。请注意，所有比较的方法在本质上都是无监督的，以便与我们的模型进行公平的比较。我们的实验证明了我们的方法的兴趣。我们还展示了GCC是如何与其他方法相关的，包括一些GCN变体。

　　该模型是一种灵活的模型，可以从多个方向进行扩展，为今后的研究提供了机会。例如，在我们的方法中，我们假设调节寻求重建和聚类之间的权衡的 α 系数等于1，研究这个值的选择将是很有趣的。另一方面，虽然我们这项工作的重点是聚类，但值得将问题扩展到这样的，例如，协同聚类，这在文档聚类等许多现实场景中是有用的。

修改历史

2022-06-27 创建文章

论文解读目录

• 论文信息
• 1 Introduction
• 2 Method
•     2.1 Joint Graph Representation Learning and Clustering
•     2.2 Linear Graph Embedding
•     2.3 Normalized Simple Graph Convolution
•     2.5 Graph Convolutional Clustering
• 3 Optimization and algorithm
•     3.1 Optimization Procedure
•     3.2 The GCC Algorithm
• 4 Experiments
• 5 Conclusion
• 修改历史

__EOF__