Attributed Graph Clustering via Adaptive Graph Convolution

介绍

pass

方法

问题形式

无向图G = (V,E,X)

• \(X\)为特征矩阵：\(X = [x_1, x_2, \cdots, x_n]\)

• 目标是把G分成m个聚类:\(C = \{C_1, C_2, \cdots, C_m\}\)

• 如果\(v_j\)能通过遍历k条边到达\(v_i\)，我们称\(v_j\)为\(v_i\)的k跳邻居

图卷积

为了正式定义图卷积，引入图信号和图滤波器；

其中，图信号：

图滤波器：

• \(P(\Lambda)\)称为响频函数，且\(P(\Lambda) = diag(p(\lambda_1), p(\lambda_2), \cdots, p(\lambda_n))\)，\(U = (u_1, u_2, \cdots, u_n)\)为正交的特征向量矩阵

其中，U求得由：

• \(\Lambda\)和\(D\)分别为邻接矩阵与度矩阵

• \(\Lambda = diag(\lambda_1, \lambda_2, \cdots, \lambda_n)\)为特征值矩阵

最后，图卷积被定义为：

特征阵X的每一个列向量可视为一个图信号，\(\lambda_q\)为频率，\(u_q\)傅里叶基，\(f\)可以拆成基相量的线性组合：

• 系数\(z_q\)表示\(u_q\)在\(f\)中的强弱程度

基信号\(u_q\)的平滑程度可以由Laplacian-Beltrami运算符求得：

• 符号：\(|| \ ||\)为范数符号
• 即一个平滑的信号\(f\)应包含尽可能多的低频，或尽可能少的高频

因此，我们可以通过图卷积过滤，达到这个效果，即G应该是一个低通滤波器。而一个低通滤波器的设计有许多种形式，作者选择其中一种：

则滤波器G可写作：

因此把G应用到X上得：

这使图信号更加平滑，有利于下游的聚类任务

k阶图卷积

为了减轻聚类任务，通过图卷积之后，同类节点应有相似的特征表征。然而，对于大型稀疏图，基于以上的图卷积仍是不够的，因为它只更新了1跳节点邻居。因此，为了更好地把握图结构和简化聚类任务，我们决定使用k阶图卷积

k阶图卷积被定义为：

对应的滤波器G和响频函数p分别为：

• 由Figure 1(a)可知k越大，平滑效果越好

k阶图卷积的迭代公式为：

可以看出，k阶图卷积通过迭代聚合k跳邻居的特征来更新来更新每个节点\(v_i\)的特征。

由于k阶图卷积考虑了远程数据关系，它可以捕获全局图结构，并提高聚类性能。

理论分析

pass

自适应k选择

作者为了采用经典的谱聚类方法，先得到核函数\(K\)，获得节点间的成对相似度：

从而得到对称且非负的相似度矩阵\(W\)：

• | |表示对每一个值取绝对值

最后，对W应用谱聚类方法，计算与\(W\)的m个最大特征值相关联的特征向量，并对特征向量应用k-means算法来获得聚类划分，从而获得聚类结果。

一个好的聚类应该有较大的簇间距离和较小的簇间距离，而根据Figure 1(b-e)以及理论1知随着k的增大，簇间距离和簇内距离都会减小。因此，作者决定通过观察不同的k取值下的簇内距离变化，并找到其局部最小值

簇内距离为：

逐渐增加k, 当簇内距离开始变大时,停止搜索

算法流程和时间复杂度

pass

实验