图神经网络自监督学习 之 AD
文章名称
【NeurIPS-2021】【Purdue University/Georgia Tech/Microsoft Research】Adversarial Graph Augmentation to Improve Graph Contrastive Learning
核心要点
文章旨在解决现有图对比学习方法因随机（或者说没有针对性的）图增广，而造成学习到一些冗余的、不可靠的内在联系，进而导致学习得到的GNN在下游任务上效果不佳。作者提出了AD-GCL框架，利用对抗的方法学习图增广策略，并从理论上证明了这一方法的可行性。并基于此框架，对抗的学习edge-dropping图增广方法。
研究背景
图神经网络对比学习通过拉近经过不同图增广后的图（节点）表示来利用无标注数据进行自监督学习。采用适当的自监督学习任务至关重要（其实作者这里更偏重于损失函数的选取），不同的自监督学习任务会促使GNN从图数据中捕获不同的信息，任务的类型和参数选择严重影响学习到的向量表示在下游任务的表现。然而，现有的基于InfoMax的自监督方法容易学习到一些冗余的、不鲁邦的信息，导致GNN的效果并不是最优的[40]。而Information Bottleneck则能迫使GNN学习下游任务所需的最小的信息[41]。同时图增广方法是图自监督学习的重要组成部分，如何在训练时自适应的调整图增广方法，也是图（自动）自监督学习任务的核心目标之一。基于此，作者提出了AD-GCL框架。
方法细节
图对比学习
图神经网络表示学习方法是指，在给定一系列图{G }^{}_{i} \in \mathcal{ G }, i = 1, 2, \ldots, n，并且图{G}^{}_{i} \sim \mathbb{P}^{}_{\mathcal{ G }}是从图空间的分布中独立同分布采样来的，期望学习到一个映射函数{f}^{}_{}({G}^{}_{i})，进而得到图的向量表示，以应用到下游任务。下游任务的标签{y}^{}_{i} \in \mathcal{Y}^{}_{}是从条件分布中采样得到，即{y}^{}_{i} \sim \mathbb{P}^{}_{\mathcal{Y}^{}_{}}。基于标签和上述表示函数f（一个GNN）可以学习得到下游分类模型q（可能是一个GNN，也可能是MLP）。文章中，作者采用message passing GNN作为图表示学习的函数。
对比学习的核心之一是对比损失。大多数GCL基于InfoMax[39]，其形式化表示如下图所示。背后的核心思想是让学习的表示和原始图信息尽可能的一致（也有的是构造两个相同的表示，也就是图增广）。
作者提到，由于GNN不能保证图结构到隐向量空间的一一映射关系，因此给GCL带来了更大的挑战。
如上所述，一些GCL采用Graph Data-Augmentation的思路来扰动图数据，减少「不必要的噪声」期望扰动后的视图保留了核心信息，并利用InfoMax通过拉近扰动后向量表示的距离，来学习这种信息，其具体形式如下图所示。其中，{t}^{}_{i}, {T}^{}_{i}分别表示采用的图增广方法和增广方法的全集。
可以看出，为了保证增广后的向量表示彼此是「真的」相近，换句话说，真的只去掉了redundant信息，而没有引入额外的错误或噪声，需要大量的验证（trial and error）和领域知识。
AD-GCL
为解决上述问题，作者提出了AD-GCL框架，该框架基于graph information bottleneck（GIB）。原有方法[47, 48]采用的GIB目标函数如下图所示。其中，I表示两个随机变量的互信息。f是上述GNN，用来得到图的向量表示。
可以看出，GIB和InfoMax相反。InfoMax要求最大化原始图与其向量表示的互信息，而GIB要求尽量减少该互信息。但同时GIB同时要求最大化与下游任务（标签）相关的互信息，因此GIB删除（与下有任务无关的）冗余信息。因此，GIB自然避免了上述提到的，GNN学习到冗余信息造成在下游任务上效果变差的问题。此外，去除冗余信息也会使GNN抵抗对抗向攻击，并且学习到可转移的知识。
但是，GIB要求有下游任务的标签信息，这在图自监督学习阶段是不能获得的。因此，作者提出利用如下图所示的目标函数，来学习「最小的、可用于区分图特质（比如节点标签、图标签等）的信息」。
其中，\mathcal{T}^{}_{}表示图增广方法集合（文章重点关注的是可参数化的一类图增广方法，而不是所有不同类的方法，或者说作者更关注的是参数优化吧）。AD-GCL的min-max优化旨在训练GNN，使得即使在使用非常激进的 GDA（即因为随便扰动，破坏了原始信息，导致t(G)与G非常不同），GNN仍然可以最大化扰动图与原始图之间的互信息。与GDA-GCL中采用两个不同的GDA不同，AD-GCL将原始图G视为锚点，目标函数中最小化的部分，寻找T使得T(G)尽可能远离锚点（也就是上述最激进的情况，这种方式增加对抗的能力，同时去掉了无用的信息，当然不是随便去掉，还是要能区分图的特质的）。
接下来是一大段理论推导，对细节感兴趣的同学可以参考论文原文和附录。结论见Theorem\ 1（前边的定义部分，如前所述，是因为GNN不能做到1对1映射，所以作者够早了近似等价1-WL test的quotient space）。
粗暴的直接阐述结论，
Theorem\ 1的第一个式子的意思是，AD-GCL的最优解可以确保GNN中encode的，与下游任务无关的信息小于一个上界（也就是最大不会超过），{min}^{}_{T \in \mathcal{T }}{{I}({{t}^{\prime}_{}}({G}^{\prime}_{}); {G}^{\prime}_{}) - {I}({{t}^{\prime*}_{}}({G}^{\prime}_{}); Y)}。因为，这个界限和GIB在\beta = 1的情况下相关，因此可以保证和下游任务的相关性（具体地说，{min}^{}_{T \in \mathcal{T }}{{I}({{t}^{\prime}_{}}({G}^{\prime}_{}); {G}^{\prime}_{}) - {I}({{t}^{\prime*}_{}}({G}^{\prime}_{}); Y)} \ge {min}^{}_{f}[{I}({{f}^{}_{}}({G}^{}_{}); {G}^{}_{}) - {I}({{f}^{}_{}}({G}^{}_{}); Y)]，具体的还需要参阅论文附录）。
Theorem\ 1的第二个式子的意思是，AD-GCL的最优解确保学习到的向量表示和下游任务的互信息大于某一个下界，只要GDA \mathcal{ T }选择的足够好，即要求{I}({{t}^{\prime*}_{}}({G}^{\prime}_{}); Y) \ge min_{T \in \mathcal{ T}}{{I}({{t}^{\prime}_{}}({G}^{\prime}_{}); Y)}，且{I}({{f}^{*}_{}}({G}^{}_{}); Y)不要太小（这个在具体实现的时候会做约束来保证）。「作者提到这类似于对\mathcal{ T }做了正则化」。(疑问，我们没有Y啊？虽然作者说论证里可以没有Y)
❞
AD-GCL edge dropping
如上所述，AD-GCL的max部分，期望学习到的GNN {f}^{}_{\Theta}能够最大化原始图G和其扰动图{t}(G)的互信息，而min部分则不断地调整{T}^{}_{\Phi}，并从这个参数化的GDA中采样t，使得上述互信息最小。
作者采用参数化的edge-dropping增广方法作为{T}^{}_{\Phi}。作者强调，AD-GCL可以同样应用于其他GDA，比如node-dropping等，只不过，如上所述，AD-GCL的结论2要求尽可能的和下游任务保持足够的互信息，并且很多下游任务（分子节点分类）都只需要结构信息，而edge-dropping对结构信息的噪声最小，所以作者选择这个增广方法。但其他的任务同样可以。
并且作者还强调，这个这种利用下游任务的一些信息来选择大的方向并不意味着利用领域知识来设计GDA，因为{T}^{}_{\Phi}仍然很宽泛，而且具体GDA（参数）还需要优化。此外，实验表明AD-GCL with edge-dropping在社交网络分类和分子属性回归方面的效果也非常好（看到这里时，刚想吐槽，这不是用了下游任务么，就被作者怼回来了，总之就是没用下游信息）。
作者提出的AD-GCL of edge-dropping的整体框架如下图所示，其中包含2个GNN模型{f}^{}_{\Theta}，GNN-augmenter，以及两个MLP模型{MLP}^{}_{w_e}, g，并且GNN-augmenter和{MLP}^{}_{w_e}共同组成了{T}^{}_{\Phi}。
而对于{T}^{}_{\Phi}，有包括2个重要的建模步骤，
Parameterizing {T}^{}_{\Phi}。如上所述，包括GNN-augmenter和{MLP}^{}_{w_e}两部分，GNN-augmenter是GNN模型，与f_\Theta一样用来学习图的向量表示。不同的是，该模型得到的向量表示将交给{MLP}^{}_{w_e}得到edge-dropping的权重{w}^{}_{e}，该权重用来模拟伯努利分布，也就是drop某一条边e的概率。具体流程如下图所示。
Regularizing {T}^{}_{\Phi}。由于没有下游的标签，不能直接GIB。但是，从上述理论1中可以理解，本质就是要求与下游任务具有更多的互信息呗。而尽可能的少drop掉边可以保留更多的与下游任务相关的信息。因此，作者加入了drop边的比例的正则项，即\sum_{e \in E}^{}{\frac{{w}^{}_{e}}{|E|}}{}。因此，整个min-max的目标函数如下图所示。
❞
这里作者采用InfoNCE[40, 59, 62]来进行对比学习，采用in-batch negative sampling。具体公式如下图所示。
代码实现
AD-GCL的伪代码如下图所示。
心得体会
GDA-GCL的核心
个人感觉，GDA-GCL的核心是如何找到合适的增广方法，「确保能够去掉作者提到的redundant information，并且不会引入误差或损失有用信息。」 但似乎，现在的GCL方法并没有深入讨论方法是否会引入噪声，虽然有点方法会利用某种方式自动调节图增广，算是指导增广方法不要引入过多噪声，但是并没有形式化的界定和讨论，都需要靠大量的试验和专业知识来保证可靠。
下游信息和GDA Family
作者表示，GDA是参数化的，所以有个GDA Family的概念，下游任务的一些信息可以被用来选择这个Family（个人理解是个GDA的大方向），但是参数还需要人工优化，调整或实践。所以AD-GCL是自动化的，没有利用下游任务信息的。
个人理解，这里可能的局限是，不论怎么调参GDA Family是确定的，没法像等方法那样，在多个GDA Family上做组合。
不过，问题在于，AD-GCL的理论是完备的，并且详细的论证了与下游任务互信息的关系，以及如何确保不引入过多的冗余信息。因此，在单独一个GDA Family上是更优的。
或者可以理解为两类方法的侧重点不同。「作者也在附录里对比了AD-GCL和JOAO[70]，效果还是优于JOAO的。」
理论和实际应用
个人感觉，文中对理论过渡到讲解并不详细，并且理论分析中Y是假设有的，但是没有的时候具体会不会影响或者影响有多少正文里没有讨论，只是说可以没有。也许需要细致的读一下附录。
敬阅读的同学
「个人觉得，这篇AD-GCL仍然延续了自动图对比学习的思路，不同的是采用了GIB和对抗的思路。但本质上还是一个min max game，只是有比较扎实的理论推导，没太看明白的是结论和最终实践时的转换过程，也许可以参考附录了解更多信息。并且可以结合其他自动对比学习方法来看。
欢迎批评指正以及对写作方法提出意见（比如，分成几个部分写之类的），有其他喜欢的主题也欢迎留言。感谢大家阅读到这里！期待你的 点赞 喜欢 和 收藏 ！」
为方便查找原文引用，文章引用部分保持和原文对齐。个人引用的文章以星号开头。
文章引用
[39] R. Linsker, “Self-organization in a perceptual network,” Computer, vol. 21, no. 3, pp. 105–117, 1988.
[40] M. Tschannen, J. Djolonga, P. K. Rubenstein, S. Gelly, and M. Lucic, “On mutual information maximization for representation learning,” in International Conference on Learning Representations, 2020.
[47] T. Wu, H. Ren, P. Li, and J. Leskovec, “Graph information bottleneck,” in Advances in Neural Information Processing Systems, 2020.
[48] J. Yu, T. Xu, Y. Rong, Y. Bian, J. Huang, and R. He, “Recognizing predictive substructures with subgraph information bottleneck,” International Conference on Learning Representations, 2021.
[59] A. v. d. Oord, Y. Li, and O. Vinyals, “Representation learning with contrastive predictive coding,” arXiv preprint arXiv:1807.03748, 2018.
[62] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton, “A simple framework for contrastive learning of visual representations,” in International Conference on Machine Learning. PMLR, 2020, pp. 1597–1607.