论文笔记 – Beyond Low-frequency Information in Graph Convolutional Networks

2021-01-30

Deyu Bo, et al., “Beyond Low-frequency Information in Graph Convolutional Networks”, AAAI 2021

目录 展开

1 简介

  • 姓名：FAGCN
  • 机构：北邮，石川组
  • 任务：图上的节点分类
  • 流派：空间域 GCN，但是却有谱域方法的可解释性
  • 动机：非同配图中，高频信号也很重要，别家的 GNN 都只用低频信号做信息聚合。咱家在同类节点之间，用低频信号做信息聚合，在不同类节点之间，用高频信号做信息的“差分”
  • 方法：高低频分别有一个卷积核，这俩最后通过 $\alpha^G$，神奇的就转化成一个 attention score！就变成了 general GAT！
  • 性能：SOTA，彻底（?）解决了过平滑问题
  • 短评：感觉是一篇神作（也可能是我在机器学习领域见识太浅），可以作为一个很强的 baseline

2 方法

人家有自己的论文笔记：https://mp.weixin.qq.com/s/23oEhMPMSgEtQeZbnxDmxw，我也不细写了，我比较菜，就写一下对入门者友好的一些理解，也方便自己回忆。

2.1 GCN 基础

卷积的表示：$$y = f*_Gx = U((U^Tf)\odot(U^Tx)) = Ug_\theta U^Tx = U \cdot diag([\hat{h}(\lambda_1), \hat{h}(\lambda_2), …\hat{h}(\lambda_N)]) \cdot U^Tx$$ $f$ 是卷积核，$x$ 是信号。第二个 = 是卷积定理，空间域的卷积等价于频域相乘。具体来讲，即 $f$ 与 $x$ 的卷积 $f*_Gx$ 等于他俩先通过傅里叶变换 $U^T$ 得到谱域的信号 $U^Tf, U^Tx$，然后再相乘，再做傅里叶逆变换回到空间域。第三个 = 就是把前面的式子简化，从右到左看，就是信号 $x$ 先变换到谱域，得到信号 $U^Tx$，然后再做卷积，得到 $g_\theta U^Tx$，再回到空间域。其中 $g_\theta$ 是谱域的卷积核。(关于最后一个 = 证明，详见 [GCN中的等式证明 – superbrother的文章 – 知乎](https://zhuanlan.zhihu.com/p/121090537))

之前的工作都是在简化卷积核 $g_\theta$：

2.1.1 Spectral CNN

$$\begin{aligned}\quad g_\theta &= diag(\{\theta_i\}_{i=1}^n) \\\quad y &= U \cdot diag(\{\theta_i\}_{i=1}^n) \cdot U^Tx \\&= (\theta_1u_1u_1^T + \theta_2u_2u_2^T + … + \theta_nu_nu_n^T)x \\\end{aligned}$$

这里可以参考谱聚类和 PCA 的理解，图拉普拉斯矩阵的每个特征向量就对应一个维度，最小特征值对应的特征向量，就是谱聚类选择切一刀的维度，即下图的实线。在这个维度的两边，样本区别最大，那沿着这个维度，样本点就很难区分，于是这个维度上样本就是都很相似的，相似就是变化不大，样本变化不大，那这些样本拟合出来的曲线就也是变化不大的，就是低频的信号（推导详见 谱聚类 这篇博客）。

反之，最大特征值对应的特征向量，就是 PCA 方差最大的方向，在这个维度上样本最能区分，因此最大特征值也就对应高频的信号。因此图拉普拉斯的特征向量这一组基，也就能看做是图信号在谱域不同频率的一组基，低频的基对应小特征值，高频的基对应大特征值。

Spectral CNN 的想法比较朴素，设计卷积核，那就每个频率分量搞一个参数，把 $\hat{h}(\lambda_i)$ 换成 $\theta_i$。

2.1.2 ChebyNet

$$\quad g_\theta = \sum_{k=0}^{K-1}\theta_k\Lambda^k$$ $$\quad y \approx U \cdot \sum_{k=0}^{K-1}\theta_k\Lambda^k \cdot U^Tx= \sum_{k=0}^{K-1}\theta_k (U \Lambda^k U^T)x= \sum_{k=0}^{K-1}\theta_k (U \Lambda U^T)^kx= \sum_{k=0}^{K-1}\theta_k L^kx$$

这里 $L = U\Lambda U^T, \Lambda = diag([\lambda_1, \lambda_2, …, \lambda_n])$

这样还不够简单，ChebyNet 又在这个基础上，用切比雪夫多项式展开对卷积核做近似。具体不写了，打算过几天认真看一下原文，到时候再写这个。争取解开我的几个疑惑：怎么就能用多项式近似？多项式有什么意义？多项式的每一项还代表不同频率分量吗？

2.1.3 GCN

$$\begin{aligned}\quad g_\theta &= I-\Lambda\\\quad y &= \theta(I-L)x \\\end{aligned}$$

GCN 的卷积核就是对 ChebyNet 的一阶近似：只保留零阶一阶分量，两个 $\theta$ 搞成一个。

2.2 FAGCN

作者在文中第 2 部分发现，非同配图（不同类型的节点有更大概率相连）中，只使用低通滤波器，就会让信息在不同类节点之间沿着边传递，这就使得不同类节点之间的信息也被搞得相似了，分类的性能就不好。作者希望，在同类节点之间的边，用低通滤波器传递同类的信息，做信息聚合，不同类节点之间的边，用高通滤波器传递“我们不一样”的信息，让两个节点分的更开。

于是作者设计了两个卷积核：低频 $\mathcal{F}_L$，高频 $\mathcal{F}_H$$$\mathcal{F}_L = \varepsilon I + D^{-1/2}AD^{-1/2} = (\varepsilon + 1)I-L$$ $$\mathcal{F}_H = \varepsilon I – D^{-1/2}AD^{-1/2} = (\varepsilon – 1)I+L$$

为什么这样设计？我搞不懂，可能是为了凑出 3.1 的“高通滤波让节点更能区别开来”？

作者还画了二阶高低通滤波器的图，相比于 GCN 的 filter，本文的 $\mathcal{F}_L$ 和 $\mathcal{F}_H$的确幅频响应函数表现更好，$\mathcal{F}_L$ 低通更多高通更低了。不过，我还是不太明白，这俩在二阶不都还是低频和高频都更通了吗？滤波器的响应函数直接求平方，这代表什么？作者做这部分图想告诉我们什么？

然后作者又搞了一个骚操作。

每个 layer 的信息聚合是两个滤波器信号加权求和：$$\begin{aligned}\tilde{h} &= \alpha_{ij}^L(\mathcal{F}_L\cdot H)_i + \alpha_{ij}^H(\mathcal{F}_H\cdot H)_i \\&= \alpha_{ij}^L((\varepsilon H + H – LH)_i + \alpha_{ij}^H(\varepsilon H – H + LH)_i \\&= (\alpha_{ij}^L + \alpha_{ij}^H)\varepsilon h_i + (\alpha_{ij}^L – \alpha_{ij}^H)(I-L)H\end{aligned}$$

然后作者令 $\alpha_{ij}^L + \alpha_{ij}^H = 1, \alpha_{ij}^L – \alpha_{ij}^H = \alpha_{ij}^G$，就得到$$\tilde{h} = \varepsilon h_i + \sum_{j\in\mathcal{N}}\frac{\alpha_{ij}^G}{\sqrt{d_id_j}}h_j$$

这里 $\alpha_{ij}^G$ 是可以学习的参数，$\alpha_{ij}^G = \text{tanh}(g^T[h_i\|h_j])$，$\alpha_{ij}^G > 0$ 表示这两个点之间更多的是低通信号，也就是说，这条边更可能同配（？）$\alpha_{ij}^G < 0$ 就是高频信号为主。

除了修改卷积核，作者还将卷积核特征变换的操作进行解耦，即中间各层不做特征变换，只卷积：$$\begin{aligned}h_i^{(0)} = \phi(W_1h_i) \\h_i^{(l)} = \varepsilon h_i^{(0)} + \sum_{j\in\mathcal{N}}\frac{\alpha_{ij}^G}{\sqrt{d_id_j}}h_j^{(l-1)} \\h_{out} = W_2h_i^{(L)}\end{aligned}$$

3 实验

3.1 FAGCN 的表达能力

作者计算了节点 $u,v$ 之间的距离、他俩低频信号的距离、他俩高频信号的距离：$$\mathcal{D} = \|h_u – h_v\|_2$$ $$\mathcal{D}_L = \|(\varepsilon h_u + h_v) – (\varepsilon h_v + h_u)\|_2 = |1-\varepsilon|\mathcal{D}$$ $$\mathcal{D}_H = \|(\varepsilon h_u – h_v) – (\varepsilon h_v – h_u)\|_2 = |1+\varepsilon|\mathcal{D}$$

发现 $\mathcal{D}_H > \mathcal{D} > \mathcal{D}_L$，即低通滤波让节点更相似，高通滤波让节点更能区别开来。

GCN 的 filter 是一个低通滤波器：$$\mathcal{D}_G = \|(\frac{1}{d_u}h_u + h_v) – (\frac{1}{d_v}h_v + h_u)\| \approx |1-\frac{1}{d}|\mathcal{D} < \mathcal{D}$$

3.2 实验

  1. 同配数据集 Cora, Citeseer, Pubmed SOTA
  2. 非同配数据集 Chameleon, Squirrel, Actor SOTA
  3. 性能几乎不会随模型深度增加而降低，解决了过平滑问题
  4. 统计每条边的 $\alpha_G$，发现确实，同配数据集里都是 $\alpha_{ij}^G > 0$ 的边，非同配数据集里正负都有

4 思考与疑问

  1. 不太明白，他最后用的是一阶的卷积核，那他中间搞个平方，画四张图，是为了干啥？
  2. 他解决了过平滑的问题，是因为设计了高通的卷积核，还是因为把卷积和特征变换解耦呢？感觉这俩都对过平滑问题有缓解。
  3. 既然有 $\alpha_{ij}^G > 0$ 低频，那么 $\alpha_{ij}^G $ 是不是可以做边的分类？当然，这里只能区分边是不是链接同类的节点，更复杂的边的分类（比如 EoG）还得想想。另外，是不是可以加个 loss，用“边的两个节点是否同类”来监督 $\alpha_{ij}^G$？
  4. DocRE 构建的图是完全非同配的！但不是节点分类，而是 entity pair 分类，这就导致，可能完全不适用本文的方法，因为如果是给 entity pair 分类，那么在不同 entity type 之间的边上做信息的平滑，说不定还是好事呢。如果要直接用他的方法，就得 entity pair 作为 node，这是完全不合理的。另外，他统计边对应的 $\alpha_{ij}^G$ 的方法也不能用在 RE。
  5. 两个不同类 entity 之间，传递什么信息好呢？这样一想，是不是传递 topic 信息，才是最有助于得到好的 entity pair 表示呢？
  6. 看完本文，我对“低频”的物理意义又有了新的理解。本文的低频信号，是指同类节点之间的相似，低频滤波，是让同类节点平均一下；高频信号是指不同类节点之间的差异，高通滤波，是让不同类节点分开一点。这是从“样本之间的关系”角度看待高低频的。（低频信息表示“同配边”连接的邻居间的相似之处，高频信息表示“非同配边”邻居之间的差异；低通滤波器表示求同，高通滤波器表示存异。）BERT-prism 的低频信号，是整体文本中变化频率低的信息，即 topic 信息，低通滤波，是提取出 topic 信息；高频信号是文本中变化频率高的信息，即 pos 信息，高通滤波，是提取出 pos 信息。这是从“样本内部分量”角度看待高低频的。唉，幻想破灭了，这俩可能根本不是一回事
  7. 感觉本文和 BERT-prism 还有另一层关系： 本文的视角，是相当于就摆出来，低频就是相似，高频就是相异；而 BERT-prism 却认为，全都是相异，只不过在低频，是 topic 相异，中频 dialog act 相异，低频 pos 相异。这样对比，二者还是挺有意思的。

5 TODO

  1. ChebyNet
  2. Simplifying GCN, graph filtering, AMGCN

6 Ref

[1] 图卷积网络(GCN)原理解析

发表评论