论文信息
论文标题：Attributed Graph Clustering: A Deep Attentional Embedding Approach
论文作者：Chun Wang, Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Chengqi Zhang
论文来源：2019, IJCAI
论文地址：download
论文代码：download
1 Introduction
研究现状：目前的图表示学习方法都是两阶段方法，且融合结构和属性信息的机制并不完美。
本文模型与传统的 two-step 方法的比较如 Figure 1 所示：
- 本文模型是将 节点表示 和 聚类 放在一个统一的框架中学习。
- Two-step 方法则是先学习 node embedding，然后进行聚类。
2 Method
总体框架：
组成部分：
-
- Graph Attentional Autoencoder
- Self-training Clustering
2.1 Graph Attentional Autoencoder
2.1.1 GAT encoder
首先：衡量 node i 的邻居 Ni 对于节点 i 的影响，采用图注意力机制：
zl+1i=σ(∑j∈NiαijWzlj)(1)
其中：αij is the attention coefficient that indicates the importance of neighbor node j to node i ；
对于注意力系数 αij 主要参考两个方面：
- 属性值（attribute values） ；
- 拓扑距离（ topological distance ）；
Aspact 1：属性值
注意力系数 αij 可以表示为 由 xi 和 xj 拼接形成的单层前馈神经网络：
cij=→aT[Wxi‖Wxj](2)
其中：
-
- →a∈R2m′ 是权重向量；
Aspact 2：拓扑距离
考虑节点高阶邻居信息（指 t-order 邻居），得到 proximity matrix ：
M=(B+B2+⋯+Bt)/t(3)
其中：
-
- B 是转移矩阵（transition matrix），当 eij∈E 有边相连，那么 Bij=1/di ，否则 Bij=0 。
- Mij 表示 node i 和 node j 的 t 阶内的拓扑相关性。如果 node i 和 node j 存在邻居关系（t 阶之内），那么 Mij>0。
对节点 i 的领域做标准化，采用 softmax function ：
αij=softmaxj(cij)=exp(cij)∑r∈Niexp(cir)(4)
将 Eq.2 中 cij 及 Eq.3 中的 Mij 带入 Eq.4，那么 attention 系数可以表示为：
αij=exp(δMij(→aT[Wxi‖Wxj]))∑r∈Niexp(δMir(→aT[Wxi‖Wxr]))(5)
其中，激活函数 δ 采用 LeakyReLU ；
本文堆叠 2 个 graph attention layers ：
z(1)i=σ(∑j∈NiαijW(0)xj)(6)
z(2)i=σ(∑j∈NiαijW(1)z(1)j)(7)
通过上述图注意力编码器，得到最终的 zi=z(2)i 。
2.1.2 Inner product decoder
解码器为 Inner product decoder ，用于重构图：
其中：
-
- ˆA 是重建后的图结构矩阵；
2.1.3 Reconstruction loss
最小化 A 和 ˆA 的重构错误：
Lr=n∑i=1loss(Ai,j,ˆAij)(9)
2.2 Self-optimizing Embedding
除优化重构误差外，还将 隐表示 输入一个自优化聚类模块，该模块最小化以下目标：
Lc=KL(P‖Q)=∑i∑upiulogpiuqiu(10)
其中：
-
- qiu度量隐表示 zi 和聚类中心 μu 之间的相似性，本文通过 Student's t-distribution 度量；
- piu 代表目标分布；
qiu=(1+‖zi−μu‖2)−1∑k(1+‖zi−μk‖2)−1（11）
piu=q2iu/∑iqiu∑k(q2ik/∑iqik)(12)
聚类损失迫使当前分布 Q 接近目标分布 P。
算法概述
-
- 首先使用没有用 selfoptimize clustering part 的自编码器获得初始 embedding ；
- 其次为计算 Eq.11 ，先使用 k−means 获得初始聚类中心 μ
- 然后根据 Lc 使用 SGD 进行优化更新 μ 和 z 。
需要注意的是 ：P 每 5 个 iteration 更新一次，Q 每个 iteration 更新一次。
算法步骤：
2.3 Joint Embedding and Clustering Optimization
联合优化 自编码器的重构损失 和 聚类损失，总目标函数为：
L=Lr+γLc(13)
其中：
-
- Lr 代表着重构损失；
- Lc 代表着聚类损失 ；
最终 vi 的 软标签 通过 Q 获得：
si=argmaxuqiu(14)
3 Experiments
4 Conclusion
贡献：
- 使用考虑了长距离结构信息图注意力网络的编码器；
- 采用内积重构邻接矩阵做；
修改历史
2022-02-19 创建文章
2022-06-09 修订文章
__EOF__
