论文阅读“Graph Filter-based Multi-vi

Lin Z, Kang Z. Graph Filter-based Multi-view Attributed Graph Clustering[C]//IJCAI. 2021: 2723-2729.

摘要导读

由于图数据的快速发展，图聚类在整个研究领域受到了很大的关注。然而现有的图聚类方法存在两个缺陷：1）大部分方法无法同时利用属性信息和图结构信息。2）大部分方法都无法处理包含多个图和多个属性信息的多视图数据集。本文提出了一个简单又高效的多视图属性图聚类模型（MvAGC）。首先，图滤波用于得到特征的平滑表示；其次，采用一种新颖的策略选择少量的锚点来代替全样本的计算，也降低运算的复杂度；最后，设计了一种新的正则方式来获取挖掘高阶近邻信息。实验结果证明了模型的有效性。

数据集定义

给定一个无向图，其中是个节点的集合，表示在-th 视图中，节点和之间的关系，表示-th视图的属性矩阵。中包含的结构信息可以记录为个邻接矩阵, ，如果节点和之间有边存在则，否则为0。基于每个图的度矩阵，对称的正则化亲和度矩阵定义为，图拉普拉斯矩阵为。

方法浅析

该方法其实在思路上分为三个阶段。
为记录简单，首先介绍单视图的场景。

• 对数据进行预处理
  图滤波在表示学习中一种经典的信号处理过程，可以得到平滑的信号表示。将数据点中的个维度看作个图信号，可以将阶图滤波作用在数据属性矩阵上： 得到的是平滑过的数据表示。
• 自表示学习以及正则项得改进
  不同于现有做法直接将用于谱聚类获得聚类结果，本文对平滑后的又做了一次自表示学习，即每个样本可以表示为其他样本的线性组合形式，而这个组合系数矩阵表示了任意两个点之间的相似性，即要学习的相似性图矩阵。这种做法减轻了手工制作的相似度指标所带来的偏差（Robust graph learning from noisy data-2020）。该过程可以形式化为： 其中，是trade-off系数，是相似性图矩阵。第一项是重构误差，第二项是用于避免平凡解的正则项如核范数或范数。但是在上面的式子种并未利用到原始的拓扑结构信息。
  因此为了挖掘种所包含的结构信息，本文设计了一个正则项。考虑到仅包含了样本的一阶近邻信息，作者引入了随机游走的阶近似值 为了同时考虑不同阶的结构信息，定义了关于的不同阶近邻信息。此时，有理由认为，最佳的可能是由经过一个小转化得来的。由此，原有得优化目标可以写成：
• 通过使用锚点来减少计算得复杂度
  从原始样本中选择了个具有代表性得样本点（ 远小于 ），。建模得目标是生成其对应得相似性图矩阵来揭示个节点和个锚点之间得相似性信息。根据选取得锚点得索引，可以从中抽取出复杂得结构信息。此时，单视图得优化目标可以转化为： 对于多视图数据，所有的视图都共享相同的，以确保唯一一个独特的聚类模式。并且引入一个加权机制来解决不同视图得不同权重。因此，MvAGC得优化目标可以表示为如下： 是视图得权重参数，是平滑参数，是视图的锚点矩阵，对应的来自。
  锚点的选取策略
  经典的锚点选取策略一般是使用k-means或者随机选择。这类方法认为每个节点在图中的重要性是同等的，这与图本身的性质是相矛盾的。因此，本文设计了一种基于节点重要性选取锚点的方式，给出了如下的重要性度量映射。具体来说，给定节点，其重要性可以表示为如下： 并将其在整个节点集合中进行归一化，得到重要性概率，并由此选出中的第一个锚点： 其中，会使得该分布尖锐而则使得分布较为平滑。对其进行次不放回抽样，具体来说，每个剩余节点应满足 \ ，即其概率的计算为： 直到中包含个节点。
• 优化策略
  因为权重参数和的更新是耦合的，所以采用交替优化的方式进行参数更新：
  （1）给定，将MvAGC的优化目标写成关于的函数，然后令其一阶导数为求得
  （2）给定求
• 聚类结果
  为计算简便，本文对得到的进行了SVD分解得到相关的特征向量，具体流程如下：