论文笔记 – 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

发表评论