论文笔记 – Label Efficient Semi-Supervised Learning via Graph Filtering

Qimai Li, et al., “Label Efficient Semi-Supervised Learning via Graph Filtering”, CVPR 2019

1 简介

• 姓名：IGCN
• 机构：香港理工
• 任务：图的半监督节点分类、0-shot 图像分类
• 流派：GCN
• 动机：GCN 不够 label-efficient（NN 参数太多，需要大量数据）
• 方法：这篇文章贡献有二
  • 从 label propagation 角度理解 GCN，提出 Generalized label propagation 框架，并以此解释 GCN normalized laplacian 和 renormalization trick 的用处
  • 设计了新的频率响应函数 $(1-\tilde{\lambda})^k$ 作为可以控制低通通多少的滤波器，并用多项式逼近（不用分解拉普拉斯矩阵了）
• 性能：又快又强，具体性能略（任务不太了解）
• 短评：“低通”和“平滑”这二者的关系，感觉是天然存在的？低通保留的低频分量，不就是更平滑的分量嘛。不过，本文是在标签传播的角度，写出目标函数，其闭式解直接就和 GCN 的低通 filter 有惊人的相似。这种数学上的理解真不错。

2 方法

2.1 label propagation 角度理解 GCN

LP 的目的是找到一个 embedding 矩阵 $Z\in\mathbb{R}^{n\times l}$，与标签矩阵 $Y$ 比较一致的同时，还在图上有平滑的信号（即邻居的 embedding 是差不多的）：

$$Z = \arg\min_Z \big\{\|Z-Y\|^2 + \alpha \text{Tr}(Z^TLZ)\big\}$$

前一项就是最小二乘法来拟合标签矩阵，后一项是拉普拉斯正则，让 embedding 具有平滑性。这个目标函数可以直接求导。令 $\{\}$ 中部分为 $f$，则有：

$$\frac{\partial f}{\partial Z} = 2(Z-Y) + \alpha Z (L + L^T) = 0$$

因此得到闭式解：

$$Z = (I+\alpha L)^{-1} Y$$

因此，（我理解）$(I+\alpha L)^{-1}$ 就直接可以看做一个“平滑算子”，因为他的用处就是让标签矩阵 $Y$ 更平滑嘛！把它转换到频域，有

$$p_{ar}(L) = (I+\alpha L)^{-1} = \Phi(1 + \alpha\Lambda)^{-1}\Phi^{-1}$$

频域 filter 的表示的函数（频率响应函数）即为 $p_{ar}(\lambda_i) = \frac{1}{1 + \alpha \lambda_i}$，画出来，就是左边图 a 的形式：

显然，这是一个低通滤波器。$\alpha$ 越大，越低通。我们知道，GCN 的 filter 是 $1-\lambda$，画出来就是右边图 b 的橘黄色的线，发现也算是一个低通，只不过在高频部分有了负的增益。而 renormalization trick 就对对此有了很大的改善：

如图所示，$\tilde{\lambda}$ 是拉普拉斯矩阵加自环之后的特征值。原先最大特征值是 $\lambda_m$（一般的拉普拉斯矩阵，就大约是 2），加入自环后，最大特征值就是 $\frac{d_m}{d_m+1}\lambda_m$（$d_m$ 是所有顶点最大的度，一般的拉普拉斯矩阵，就大约是 1.5）。因此引入自环后，频响函数就变为 b，在高频的很大一部分就消失了。下面 cd 画出了二阶的频响函数，是因为二阶的才都是正的值，一阶的负的增益，现在在理论上还不好解释。（4.6）

另外，将 $L$ normalize 为 $D^{-\frac{1}{2}} L D^{-\frac{1}{2}}$，是因为原先 $L$ 特征值的范围是 $[0,\infty]$，归一化之后特征值范围来到了 $[0,2]$，大大减小了高频的通过的量（对 $[2,\infty]$ 部分就完全没有增益了）（4.4）

以上就是整篇文章中对于 GCN 的新理解，我是从各个地方挑出来的，与原文的写作顺序完全不同。

2.2 Generalized Label Propagation Methods(GLP)

作者提出了 GLP 框架，并说，不带 ReLU 的多层 GCN 其实也属于 GLP 的一个例子。这部分我感觉没啥用，就直接把他原文中的框架复制一下：

• Signal: Use the feature matrix $X$ instead of the label matrix $Y$ as input signals.
• Filter: The filter $G$ can be any low-pass graph convolutional filter.
• Classifier: The classifier can be any classifer trained on the embeddings of labeled vertices.

因此 GLP 就是两步，先平滑，再分类。

2.3 Improve Graph Convolutional Networks(IGCN)

原先 GCN 的 filter 是 $1-\tilde{\lambda}$，作者给改成 $p_{rnm} = (1-\tilde{\lambda})^k$。

这样一来，就可以通过调参 $k$，控制 filter 的低通程度。就如同第一张图 b 画的，k 越大越低通。作者就觉得，在标签非常少的时候（就是半监督学习，有标签占比的数据很少，图中标签稀疏），就用更低通的，这样远距离的有标签点，也能参与到信息的聚合来；当标签比较多的时候，就让 filter 不要太低通，这样可以更好地区分不同类。（4.5）

上面说的是第一种改进的 renormalized(RMN) filter $p_{rnm}$，另一种改进就是用前面 label propagation 说的 Auto-Regressive (AR) filter $p_{ar}$ 作为 filter。

$p_{ar}$ 要求逆，作者用迭代来简化计算：

$$X^{i+1} = X + \frac{\alpha}{1+\alpha}WX^i$$ 

k 阶就算 k 次，这样就得到通过一层 IGCN 的结果。

$p_{rnm}(\tilde{L}) = (1-\tilde{L})^k$，计算时也不用矩阵分解，就直接对矩阵 $X$ 左乘 $k$ 次 $(1-\tilde{L})$ 就好了。

3 实验

又快又好，略

4 思考

1. 看这篇文章，似乎 label propagation 的方法好像完全不能适用于我的任务，我这 RE 重要的就是 embedding，图的结构其实都是虚的……
2. 他这个 label propagation 的做法，似乎是只适用于半监督的方法，即所有数据都放在一张图里，用有标签的控制 embedding 生成，让图上的 embedding 尽量光滑，这样无标签的节点，自然就生成了一个 embedding（应该是这样？）这就又激发了我用大图做 DocRE 的想法：做大图的时候，直接就把 train test 都放进图里来，test 作为“半监督”的数据。这样不才是图表示学习的主流做法嘛！像其它 DocRE 文章里那样，都是一篇文章一个图，真是太小了，性能上也不好看。
3. 文中说了，a low-pass filter G is applied on the feature matrix X to obtain a smooth feature matrix，我不能同意更多。
4. normalized laplacian 就能 有这么大的低通滤波能力，这个我还是不太理解。我还是觉得，这只是把特征值放缩了一个系数呀？为什么会额外产生低通的能力？难道不只是原来 $\infty$ 对应的频率，现在用 2 来代表了吗？
5. 这里 k 可不可以不当做超参？可不可以把 k 搞成一个与“标签稀疏程度”相关的函数？（不过好像也没什么使用场景）
6. 在 GCN 的实验上看来，奇数层 GCN 和偶数层 GCN 的结果也没什么本质的区别，所以负增益和正增益有什么区别呢？另外，如果说 GCN 是带阻滤波器，那么本文的 RNM 就是完全的低通了，所以效果好了很多？是因为这个吗？

5 TODO