AGC：基于自适应图卷积的属性图聚类模型

论文标题｜ Attributed Graph Clustering via Adaptive Graph Convolution
论文来源｜ IJCAI 2019
论文链接｜ https://arxiv.org/abs/1906.01210
源码链接｜ https://github.com/karenlatong/AGC-master

TL;DR

这篇论文针对属性图聚类问题提出了自适应的图卷积方法 AGC，主要想法是运用高阶图卷积来捕获图的全局簇结构特征，并且可以对不同的图来自适应地选择合适的阶数。实验部分在不同的基准网络数据集中验证了 AGC 的效果优于当前的 baseline。

Problem Formulation

给定无向图 $\mathcal{G}=(\mathcal{V}, \mathcal{E}, X)$ ，其中 $\mathcal{V}, \mathcal{E}$ 分别表示节点集合 $\left\{v_{1}, v_{2}, \ldots, v_{n}\right\}$ 和边集合， $X$ 表示所有节点的特征矩阵 $X=\left[\boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \cdots, \boldsymbol{x}_{n}\right]^{\top} \in \mathbb{R}^{n \times d}$ ， $A$ 表示邻接矩阵 $\left\{a_{i j}\right\} \in \mathbb{R}^{n \times n}$ 。属性图聚类的目标是将图 $\mathcal{G}$ 中的节点划分到 $m$ 个不同的簇中 $\mathcal{C}=\left\{C_{1}, C_{2}, \cdots, C_{m}\right\}$ 。

论文的整体工作就是利用 GCN 在属性图中进行社团检测，貌似解决了之前我在学校想解决但是没有解决的问题，这也是看这篇文章的原因。

PS：哎看完之后好像还是没有解决看样子是期待太高了。

Algorithm/Model

Graph Convolution

GCN 的背景知识不再赘述，可以参考另一篇博客图卷积网络 GCN（三）详解三代图卷积网络理论，本文直接从作者对 GCN 的改进说起。

图卷积的公式可以表达为以下形式：

$\overline{\boldsymbol{f}}=G \boldsymbol{f}$

其中 $\boldsymbol{f}$ 表示图信号, $\overline{\boldsymbol{f}}$ 表示过滤后的图信号，可以理解为图节点特征矩阵 $X$ 的一列值； $G$ 表示基于拉普拉斯矩阵的一个线性的图滤波器 $G = U p(\Lambda) U^{-1} \in \mathbb{R}^{n \times n}$ ，其中值表示归一化的拉普拉斯矩阵特征分解矩阵 $L_{s}=U \Lambda U^{-1}$ ， $\Lambda=\operatorname{diag}\left(\lambda_{1}, \cdots, \lambda_{n}\right)$ ， $U=\left[\boldsymbol{u}_{1}, \cdots, \boldsymbol{u}_{n}\right]$ ， $p(\Lambda)=\operatorname{diag}\left(p\left(\lambda_{1}\right), \cdots, p\left(\lambda_{n}\right)\right)$ 表示傅里叶变换的频率响应函数。所以图信号可以使用拉普拉斯矩阵的特征向量为一组基进行表示。

$\boldsymbol{f}=U \boldsymbol{z}=\sum_{q=1}^{n} z_{q} \boldsymbol{u}_{q}$

其中 $\boldsymbol{z}=\left[z_{1}, \cdots, z_{n}\right]^{\top}$ 表示这组基的系数，因此图卷积公式可以重写成

$\overline{\boldsymbol{f}}=G \boldsymbol{f}=U p(\Lambda) U^{-1} \cdot U \boldsymbol{z}=\sum_{q=1}^{n} p\left(\lambda_{q}\right) z_{q} \boldsymbol{u}_{\boldsymbol{q}}$

为了过滤掉图中的高频信号并保留低频信号，所以频率响应函数 $p(\cdot)$ 应该是递减且非负的，作者就设计了一种图的低通滤波器，令 $p\left(\lambda_{q}\right)=1-\frac{1}{2} \lambda_{q}$ ，📢 注意：拉普拉斯矩阵的特征值范围为 [0,2] 所以才可以定义这种线性函数，所以图滤波器 $G$ 的形式变化为

$G=U p(\Lambda) U^{-1}=U\left(I-\frac{1}{2} \Lambda\right) U^{-1}=I-\frac{1}{2} L_{s}$

所以对于图中所有节点特征进行卷积的的计算公式可以表示为

$\bar{X}=G X = (I-\frac{1}{2} L_{s})X$

作者指出论文中提出的滤波器和三代图卷积 GCN 的不同点主要在于：GCN 的一阶近似滤波器 $G=I-L_s$ ，其中 $p\left(\lambda_{q}\right)=1- \lambda_{q}$ 不是低通滤波的，因为在 $(1,2]$ 特征值区间频率响应函数是负的！为什导致负数了呢，难道是近似计算太多导致最后结果都不是图谱卷积？ 🤔

思考：重新反思下论文中想法与传统 GCN 的不同点：

二代图卷积的思路是使用 $K$ 阶多项式来近似表示频率响应函数 $g_{\theta}(\Lambda) \approx \sum_{k=0}^{K-1} \theta_{k} \Lambda^{k}$ .
三代图卷积是直接使用一阶来近似卷积，然后通过训练和堆叠卷积层来达到多阶的效果。
传统的图卷积都是通过训练来学习卷积核参数，而论文中直接自定义了低通图滤波器 $G$ ，即图卷积核参数。

综上，那么最直观地导致结果是论文中提出的方法 node embedding 都不需要训练了，直接通过拉普拉斯矩阵进行 Smoothing 就可以得到 node embedding，厉害厉害 👏

k-Order Graph Convolution

剩下的就是如何使用多阶图卷积来捕获图全局的计算方法了。

根据上述的一阶图卷积，那么 $k$ 阶图卷积的计算公式如下

$\bar{X}=\left(I-\frac{1}{2} L_{s}\right)^{k} X$

对应的图滤波器和频率响应函数为

$G=\left(I-\frac{1}{2} L_{s}\right)^{k}=U\left(I-\frac{1}{2} \Lambda\right)^{k} U^{-1}$

$p\left(\lambda_{q}\right)=\left(1-\frac{1}{2} \lambda_{q}\right)^{k}$

节点特征的 $k$ 阶迭代的计算公式如下所示，

$\overline{\boldsymbol{x}}_{i}^{(0)}=\boldsymbol{x}_{i}\\ \overline{\boldsymbol{x}}_{i}^{(1)}=\frac{1}{2}\left(\overline{\boldsymbol{x}}_{i}^{(0)}+\sum_{\left(v_{i}, v_{j}\right) \in \mathcal{E}} \frac{a_{i j}}{\sqrt{d_{i} d_{j}}} \overline{\boldsymbol{x}}_{j}^{(0)}\right) \\ \cdots \\ \overline{\boldsymbol{x}}_{i}^{(k)}=\frac{1}{2}\left(\overline{\boldsymbol{x}}_{i}^{(k-1)}+\sum_{\left(v_{i}, v_{j}\right) \in \mathcal{E}} \frac{a_{i j}}{\sqrt{d_{i} d_{j}}} \overline{\boldsymbol{x}}_{j}^{(k-1)}\right)$

那么还剩下个问题，如何选择合适大小的 $k$ 值呢？在下一节就会讲到。

Clustering AGC

至于聚类方法，论文中采用的是谱聚类将过滤后的特征矩阵 $\bar{X}$ 划分为 $m$ 个簇。

首先通过特征矩阵来计算节点间的距离

$K=\bar{X} \bar{X}^{T}$

为了使距离矩阵是对称且非负的，因此将矩阵进行对称化

$W=\frac{1}{2}\left(|K|+\left|K^{\top}\right|\right)$

其中 $|\cdot|$ 表示将矩阵中的值求绝对值。

根据距离矩阵 $W$ 求解 $m$ 个最大的特征值然后使用 k-means 算法获得最终的划分结果。

对于论文中的 $k$ 阶图卷积还有个关键问题： 如何选择的 $k$ 值？，因为 $k$ 值太大会导致 over-smoothing 问题。

首先给出 cora 数据集中不同 $k$ 值的可视化结果，发现 $k=12$ 时分类效果较好。

为了选择合适的 $k$ ，论文中选用一个聚类性能指标 簇内距离 来判断，主要意义是可以表示不同聚类 $\mathcal{C}$ 的效果。计算公式如下图所示

$\operatorname{intra}(\mathcal{C})=\frac{1}{|\mathcal{C}|} \sum_{C \in \mathcal{C}} \frac{1}{|C|(|C|-1)} \sum_{v_{i}, v_{j} \in C, \atop v_{i} \neq v_{j}}\left\|\bar{x}_{i}-\bar{x}_{j}\right\|_{2}$