论文解读(AGC)《Attributed Graph Clustering via Adaptive

论文信息

论文标题:Attributed Graph Clustering via Adaptive Graph Convolution
论文作者:Xiaotong Zhang, Han Liu, Qimai Li, Xiao-Ming Wu
论文来源:2019, IJCAI
论文地址:download 
论文代码:download 

1 Introduction

  关于GNN 是低通滤波器的好文。

2 Method

2.1 Graph Convolution

2.1.1 Basic idea

  为正式定义图卷积,首先引入图信号和图滤波器的概念。

  图信号可以表示为一个向量 $\boldsymbol{f}= \left[f\left(v_{1}\right), \cdots, f\left(v_{n}\right)\right]^{\top}$,其中 $f: \mathcal{V} \rightarrow \mathbb{R}$ 是一个实值函数。

    • 邻接矩阵 $A$
    • 度矩阵 $D=\operatorname{diag}\left(d_{1}, \cdots, d_{n}\right)$
    • 对称标准化图拉普拉斯矩阵 $L_{s}=I-D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$

  $L_{s}$ 可特征分解:$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]$ 是对应的正交特征向量。

  图滤波器 可表示为 $G= U p(\Lambda) U^{-1} \in \mathbb{R}^{n \times n}$,其中 $p(\Lambda)=\operatorname{diag}\left(p\left(\lambda_{1}\right), \cdots, p\left(\lambda_{n}\right)\right)$ 被称为 频率响应函数

  图卷积 被定义为 图信号 图滤波器 $G$ 的乘法:

    $\overline{\boldsymbol{f}}=G \boldsymbol{f} \quad\quad\quad(1)$

  其中,$\overline{\boldsymbol{f}}$ 为滤波后的图信号。

  特征矩阵 $X$ 的 每一列 可看作是一个图信号。在图信号处理中,特征值 $\left(\lambda_{q}\right)_{1 \leq q \leq n}$ 可以作为 频率,相关的特征向量 $\left(\boldsymbol{u}_{q}\right)_{1 \leq q \leq n}$ 可以作为图的傅里叶基。一个图信号 $f$ 可以被分解为一个特征向量的线性组合,即,

    $\boldsymbol{f}=U \boldsymbol{z}=\sum\limits_{q=1}^{n} z_{q} \boldsymbol{u}_{q} \quad\quad\quad(2)$

  式中,$\boldsymbol{z}=\left[z_{1}, \cdots, z_{n}\right]^{\top}$ 和 $z_{q}$ 为 $\boldsymbol{u}_{q}$ 的系数。系数 $\left|z_{q}\right|$ 的大小表示 $\boldsymbol{f}$ 中表示的基信号 $\boldsymbol{u}_{q}$ 的强度。

  如果图上附近的节点具有相似的特征表示,则图信号是平滑的。基信号 $\boldsymbol{u}_{q}$ 的平滑度可以用 拉普拉斯-贝尔特拉米算子 $\Omega(\cdot)$ 来测量,即,

    $\begin{aligned}\Omega\left(\boldsymbol{u}_{q}\right) &=\frac{1}{2} \sum\limits_{\left(v_{i}, v_{j}\right) \in \mathcal{E}} a_{i j}\left\|\frac{\boldsymbol{u}_{q}(i)}{\sqrt{d_{i}}}-\frac{\boldsymbol{u}_{q}(j)}{\sqrt{d_{j}}}\right\|_{2}^{2} \\&=\boldsymbol{u}_{q}^{\top} L_{s} \boldsymbol{u}_{q}=\lambda_{q}\end{aligned}\quad\quad\quad(3)$

  其中,$\boldsymbol{u}_{q}(i)$ 表示向量 $\boldsymbol{u}_{q}$ 的第 $i$ 个元素。

  $Eq.3$ 表示与较低频(较小特征值)相关的基信号更平滑,即平滑的图信号 $f$ 应该比高频图信号包含更多的低频基信号。这可通过与低通图滤波器 $G$ 进行图卷积来实现,如下所示。

  通过 $Eq.2$,图卷积可以写成

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

  在滤波后的信号 $\overline{\boldsymbol{f}}$ 中,基信号 $\boldsymbol{u}_{q}$ 的系数 $z_{q}$ 按 $p\left(\lambda_{q}\right)$ 进行缩放。为保持低频基信号和去除 $f$ 中的高频信号,图滤波器 $G$ 应该是低通的,即 频率响应函数 $p(\cdot)$ 应该是 减小 的和 非负 

  低通图滤波器可以有多种形式。在这里,本文设计了一个具有频率响应函数的低通图滤波器

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

  如 Figure 1(a) 中的红线所示,可以看到 $Eq.5$ 中的 $p(\cdot)$ 在 $[0,2]$ 上呈递减趋势,且为非负值。

  

  注意,对称归一化图拉普拉斯l的所有特征值 $\lambda_{q}$ 都属于区间 $[0,2]$,这表明 $Eq.5$ 中的  $p(\cdot)$ 是低通的。在 $Eq.5$ 中以 $p(\cdot)$ 为频率响应函数的图滤波器 $G$ 可以写成

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

  通过对特征矩阵 $X$ 进行图卷积,得到滤波后的特征矩阵:

    $\bar{X}=G X\quad\quad\quad(7)$

  其中,$\bar{X}=\left[\overline{\boldsymbol{x}}_{1}, \overline{\boldsymbol{x}}_{2}, \cdots, \overline{\boldsymbol{x}}_{n}\right]^{\top} \in \mathbb{R}^{n \times d}$ 是图卷积后过滤后的节点特征。在特征矩阵上应用这样种低通图滤波器,使相邻节点在每个维上具有相似的特征值,即图信号是平滑的。

  请注意,在 $Eq.6$ 中提出的图滤波器不同于在 GCN 中使用的图滤波器。GCN 中的图滤波器是 $G=   I-L_{s}$,频率响应函数 $p\left(\lambda_{q}\right)=1-\lambda_{q}$,这显然不是低通,因为它在 $\lambda_{q} \in(1,2]$ 为负。

 GCN 的滤波器

    $\begin{aligned}\tilde{D}^{-1 / 2} \tilde{A} \tilde{D}^{-1 / 2} &=\tilde{D}^{-1 / 2}(\tilde{D}-L) \tilde{D}^{-1 / 2} \\&=I-\tilde{D}^{-1 / 2} L \tilde{D}^{-1 / 2} \\&=I-\tilde{L}_{s}\end{aligned}$

  由于 $\tilde{L}_{s}$ 可以被正交对角化,设 $\tilde{L}_{s}=V \tilde{\Lambda} V^{\mathrm{T}}$ , $\tilde{\lambda}_{i}$ 是 $\tilde{L}_{s}$ 的特征值,可以证明 $\tilde{\lambda}_{i} \in[0,2)$。
  因此上式变为:

    $I-V \tilde{\Lambda} V^{T}=V(1-\tilde{\Lambda}) V^{\mathrm{T}}$

  显然,其频率响应函数为  $p(\lambda)=1-\tilde{\lambda}_{i} \in[-1,1)$ 。

2.1.2 k-Order Graph Convolution

  为了便于聚类,希望同一类的节点在经过图过滤后应该具有相似的特征表示。然而,$Eq.7$ 中的一阶图卷积可能不足以实现这一点,特别是对于大型稀疏图,因为它只通过一个节点的聚合来更新每个节点 $v_i$,而不考虑长距离邻域关系。为了捕获全局图的结构并便于聚类,建议使用 $k$ 阶图的卷积。

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

  其中 $k$ 为正整数,对应的图滤波器为

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

  在 $Eq.9$ 中,$G$ 的频率响应函数为

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

  如 Figure 1(a) 所示,随着 $k$ 的增加,$Eq.10$ 中的 $p\left(\lambda_{q}\right)$ 变得更低通,说明滤波后的节点特征 $\bar{X}$ 将更平滑。

  $k$ 阶图卷积的迭代计算公式为

    $\begin{array}{l} \overline{\boldsymbol{x}}_{i}^{(0)}=\boldsymbol{x}_{i}\\ \overline{\boldsymbol{x}}_{i}^{(1)}=\frac{1}{2}\left(\overline{\boldsymbol{x}}_{i}^{(0)}+\sum\limits_{\left(v_{i}, v_{j}\right) \in \mathcal{E}} \frac{a_{i j}}{\sqrt{d_{i} d_{j}}} \overline{\boldsymbol{x}}_{j}^{(0)}\right)\\\vdots \\\overline{\boldsymbol{x}}_{i}^{(k)}=\frac{1}{2}\left(\overline{\boldsymbol{x}}_{i}^{(k-1)}+\sum\limits_{\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)\end{array} \quad\quad\quad(11)$

  最终的 $\overline{\boldsymbol{x}}_{i}$ 是 $\overline{\boldsymbol{x}}_{i}^{(k)}$。

Note

  因为:

    ${\large \bar{X}=\left(I-\frac{1}{2} L_{s}\right) X=\frac{1}{2}\left(I+D^{-\frac{1}{2}} A D^{-\frac{1}{2}}\right) X} $

  所以:

    ${\large \overline{x_{i}}=\frac{1}{2}\left(x_{i}+\sum\limits_{\left(v_{i}, v_{j}\right) \in e} \frac{a_{i j}}{\sqrt{d_{i} d_{j}}} x_{j}\right)} $

Theoretical Analysis

  随着 $k$ 增加,$k$ 阶图卷积将使节点特征在每个维度上更平滑。下面,我们使用 $Eq.3$ 中定义的拉普拉斯-贝尔特拉米算子 $\Omega(\cdot)$ 来证明这一点。用 $f$ 表示特征矩阵 $X$ 的一列,可以分解为 $\boldsymbol{f}=U \boldsymbol{z}$。请注意, $\Omega(\beta \boldsymbol{f})=\beta^{2} \Omega(\boldsymbol{f})$,其中 $\beta$ 是一个标量。因此,为了比较不同的图信号的平滑性,我们需要把它们放在一个共同的尺度上。接下来,我们考虑一个归一化信号 $\frac{f}{\|f\|_{2}}$ 的平滑性,即,

    $\Omega\left(\frac{\boldsymbol{f}}{\|\boldsymbol{f}\|_{2}}\right)=\frac{\boldsymbol{f}^{\top} L_{s} \boldsymbol{f}}{\|\boldsymbol{f}\|_{2}^{2}}=\frac{\boldsymbol{z}^{\top} \Lambda \boldsymbol{z}}{\|\boldsymbol{z}\|_{2}^{2}}=\frac{\sum\limits_{i=1}^{n} \lambda_{i} z_{i}^{2}}{\sum\limits_{i=1}^{n} z_{i}^{2}} \quad\quad\quad(12)$

证明:

  

  我们现在可以用这个引理来证明 Theorem 1。为方便起见,我们将 $L_{s}$ 的特征值 $\lambda_{i}$ 按递增顺序排列为 $0 \leq \lambda_{1} \leq \cdots \leq \lambda_{n}$。由于 $p(\lambda)$ 是非增加的和非负的,所以 $p\left(\lambda_{1}\right) \geq \cdots \geq p\left(\lambda_{n}\right) \geq 0$。可以用上述引理来证明Theorem 1 ,通过设置 :

    $T_{i}=\lambda_{i}, \quad b_{i}=z_{i}^{2}, \quad c_{i}=p^{2}\left(\lambda_{i}\right) z_{i}^{2} \quad\quad\quad(16)$

  假设 $\boldsymbol{f}$ 和 $\overline{\boldsymbol{f}}$ 分别由 $(k−1)$ 阶和 $k$ 阶图卷积得到,我们可以立即从 Theorem 1 中推断出 $\overline{\boldsymbol{f}}$ 比 $\boldsymbol{f}$ 更平滑。换句话说,$k$ 阶图卷积会随着 $k$ 的增加而产生更平滑的特征。由于同一集群中的节点倾向于紧密连接,它们可能具有更多具有大 $k$ 的相似特征表示,这有利于聚类。

2.2 Clustering via Adaptive Graph Convolution

  算法如下:

  

  为了自适应地选择 $k$ 阶,我们使用聚类性能度量-仅基于数据的内在信息的内部标准。在这里,我们考虑 intra-cluster distance(对于给定的簇 $\mathcal{C}$),它表示 $\mathcal{C}$ 的紧致性:

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

  需要注意的是,在具有固定数据特征的情况下,簇间距离也可以用来度量聚类性能,良好的簇类划分应该具有较大的簇间距离和较小的簇内距离。然而,根据 Theorem 1,随着 $k$ 的增加,节点特征变得更平滑,这可以显著减少簇内和簇间的距离。因此,簇间的距离可能不是衡量集群性能的可靠度量指标因此,我们建议观察选择 $k$ 的簇内距离的变化。

  所以,最后的选择簇分配为 $\mathcal{C}^{(t-1)}$。这种选择策略的好处是有两方面的。首先,它确保为 $\text{intra }  (\mathcal{C})$ 找到一个局部最小值,这可能表明一个良好的簇分配,并避免过度平滑。其次,停止在 $\text{intra }  (\mathcal{C})$  内的第一个局部最小值是时间有效的。

3 Experiments

Datasets

  

节点聚类

  

4 Conclusion

  本文提出了一

原文链接:,转发请注明来源!