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 实验
- 同配数据集 Cora, Citeseer, Pubmed SOTA
- 非同配数据集 Chameleon, Squirrel, Actor SOTA
- 性能几乎不会随模型深度增加而降低,解决了过平滑问题
- 统计每条边的 $\alpha_G$,发现确实,同配数据集里都是 $\alpha_{ij}^G > 0$ 的边,非同配数据集里正负都有
4 思考与疑问
- 不太明白,他最后用的是一阶的卷积核,那他中间搞个平方,画四张图,是为了干啥?
- 他解决了过平滑的问题,是因为设计了高通的卷积核,还是因为把卷积和特征变换解耦呢?感觉这俩都对过平滑问题有缓解。
- 既然有 $\alpha_{ij}^G > 0$ 低频,那么 $\alpha_{ij}^G $ 是不是可以做边的分类?当然,这里只能区分边是不是链接同类的节点,更复杂的边的分类(比如 EoG)还得想想。另外,是不是可以加个 loss,用“边的两个节点是否同类”来监督 $\alpha_{ij}^G$?
- DocRE 构建的图是完全非同配的!但不是节点分类,而是 entity pair 分类,这就导致,可能完全不适用本文的方法,因为如果是给 entity pair 分类,那么在不同 entity type 之间的边上做信息的平滑,说不定还是好事呢。如果要直接用他的方法,就得 entity pair 作为 node,这是完全不合理的。另外,他统计边对应的 $\alpha_{ij}^G$ 的方法也不能用在 RE。
- 两个不同类 entity 之间,传递什么信息好呢?这样一想,是不是传递 topic 信息,才是最有助于得到好的 entity pair 表示呢?
- 看完本文,我对“低频”的物理意义又有了新的理解。本文的低频信号,是指同类节点之间的相似,低频滤波,是让同类节点平均一下;高频信号是指不同类节点之间的差异,高通滤波,是让不同类节点分开一点。这是从“样本之间的关系”角度看待高低频的。(低频信息表示“同配边”连接的邻居间的相似之处,高频信息表示“非同配边”邻居之间的差异;低通滤波器表示求同,高通滤波器表示存异。)BERT-prism 的低频信号,是整体文本中变化频率低的信息,即 topic 信息,低通滤波,是提取出 topic 信息;高频信号是文本中变化频率高的信息,即 pos 信息,高通滤波,是提取出 pos 信息。这是从“样本内部分量”角度看待高低频的。唉,幻想破灭了,这俩可能根本不是一回事
- 感觉本文和 BERT-prism 还有另一层关系: 本文的视角,是相当于就摆出来,低频就是相似,高频就是相异;而 BERT-prism 却认为,全都是相异,只不过在低频,是 topic 相异,中频 dialog act 相异,低频 pos 相异。这样对比,二者还是挺有意思的。
5 TODO
- ChebyNet
- Simplifying GCN, graph filtering, AMGCN
6 Ref
[1] 图卷积网络(GCN)原理解析