Lin Z, Kang Z. Graph Filter-based Multi-view Attributed Graph Clustering[C]//IJCAI. 2021: 2723-2729.
摘要导读
由于图数据的快速发展，图聚类在整个研究领域受到了很大的关注。然而现有的图聚类方法存在两个缺陷：1）大部分方法无法同时利用属性信息和图结构信息。2）大部分方法都无法处理包含多个图和多个属性信息的多视图数据集。本文提出了一个简单又高效的多视图属性图聚类模型（MvAGC）。首先，图滤波用于得到特征的平滑表示；其次，采用一种新颖的策略选择少量的锚点来代替全样本的计算，也降低运算的复杂度；最后，设计了一种新的正则方式来获取挖掘高阶近邻信息。实验结果证明了模型的有效性。
数据集定义
给定一个无向图
，其中
是
个节点的集合，
表示在
-th 视图中，节点
和
之间的关系，
表示-th视图的属性矩阵。
中包含的结构信息可以记录为
个邻接矩阵
, 
，如果节点和之间有边存在则
，否则为0。基于每个图的度矩阵
，对称的正则化亲和度矩阵
定义为D_v%5E%7B-%5Cfrac%7B1%7D%7B2%7D%7D)
，图拉普拉斯矩阵为
。
方法浅析
该方法其实在思路上分为三个阶段。
为记录简单，首先介绍单视图的场景。
- 对数据进行预处理
图滤波在表示学习中一种经典的信号处理过程，可以得到平滑的信号表示。将数据点中的
个维度看作个图信号，可以将
阶图滤波作用在数据属性矩阵
上：得到的
是平滑过的数据表示。
- 自表示学习以及正则项得改进
不同于现有做法直接将用于谱聚类获得聚类结果，本文对平滑后的又做了一次自表示学习，即每个样本可以表示为其他样本的线性组合形式，而这个组合系数矩阵表示了任意两个点之间的相似性，即要学习的相似性图矩阵。这种做法减轻了手工制作的相似度指标所带来的偏差（Robust graph learning from noisy data-2020）。该过程可以形式化为：其中，
是trade-off系数，
是相似性图矩阵。第一项是重构误差，第二项是用于避免平凡解的正则项如核范数或
范数。但是在上面的式子种并未利用到原始的拓扑结构信息。
因此为了挖掘
种所包含的结构信息，本文设计了一个正则项。考虑到仅包含了样本的一阶近邻信息，作者引入了随机游走的
阶近似值为了同时考虑不同阶的结构信息，定义了关于的不同阶近邻信息%3DA%2BA%5E2%2B%5Ccdots%2BA%5EP)
。此时，有理由认为，最佳的
可能是由)
经过一个小转化得来的。由此，原有得优化目标可以写成：
- 通过使用锚点来减少计算得复杂度
从原始样本中选择了
个具有代表性得样本点（ 远小于 ），![B=[b_1, \cdots, b_m] \in \mathcal{R}^{d \times m}](https://math.jianshu.com/math?formula=B%3D%5Bb_1%2C%20%5Ccdots%2C%20b_m%5D%20%5Cin%20%5Cmathcal%7BR%7D%5E%7Bd%20%5Ctimes%20m%7D)
。建模得目标是生成其对应得相似性图矩阵
来揭示个节点和个锚点之间得相似性信息。根据选取得锚点得索引，可以从中抽取出复杂得结构信息
。此时，单视图得优化目标可以转化为：对于多视图数据，所有的视图都共享相同的
，以确保唯一一个独特的聚类模式。并且引入一个加权机制来解决不同视图得不同权重。因此，MvAGC得优化目标可以表示为如下：
是视图得权重参数，
是平滑参数，
是视图的锚点矩阵，对应的
来自。
锚点的选取策略
经典的锚点选取策略一般是使用k-means或者随机选择。这类方法认为每个节点在图中的重要性是同等的，这与图本身的性质是相矛盾的。因此，本文设计了一种基于节点重要性选取锚点的方式，给出了如下的重要性度量映射
。具体来说，给定节点，其重要性可以表示为如下：并将其在整个节点集合中进行归一化，得到重要性概率，并由此选出
中的第一个锚点：其中，
会使得该分布尖锐而
则使得分布较为平滑。对其进行
次不放回抽样，具体来说，每个剩余节点应满足
\ ，即其概率的计算为：直到中包含个节点。
- 优化策略
因为权重参数和的更新是耦合的，所以采用交替优化的方式进行参数更新：
（1）给定，将MvAGC的优化目标写成关于的函数，然后令其一阶导数为
求得
（2）给定求
- 聚类结果
为计算简便，本文对得到的进行了SVD分解得到相关的特征向量，具体流程如下：
一步一步娓娓道来，见招拆招。妙！
