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

2022-09-17 本文已影响0人掉了西红柿皮_Kee

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

摘要导读

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

数据集定义

给定一个无向图 $G=\{\mathcal{V}, E_1, \cdots, E_V, X^1, \cdots, X^V\}$ ，其中 $\mathcal{V}$ 是 $n$ 个节点的集合， $e_{i,j}^v \in E_v$ 表示在 $v$ -th 视图中，节点 $i$ 和 $j$ 之间的关系， $X^v=\{x_1^v, x_2^v, \cdots, x_n^v\}^T \in \mathcal{R}^{n \times d_v}$ 表示 $v$ -th视图的属性矩阵。 $G$ 中包含的结构信息可以记录为 $V$ 个邻接矩阵 $\{\tilde{A}_v\}_{v=1}^V$ , $\tilde{A}_v = \{\tilde{a}_{ij}^v\} \in \mathcal{R}^{n \times n}$ ，如果节点 $i$ 和 $j$ 之间有边存在则 $\tilde{a}_{ij}^v=1$ ，否则为0。基于每个图的度矩阵 $D_v$ ，对称的正则化亲和度矩阵 $A_v$ 定义为 $D_v^{-\frac{1}{2}}(\tilde{A}_v+I)D_v^{-\frac{1}{2}}$ ，图拉普拉斯矩阵为 $L_v=D_v-A_v$ 。

方法浅析

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

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

一步一步娓娓道来，见招拆招。妙！

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

摘要导读

数据集定义

方法浅析

猜你喜欢

热点阅读