文章名称
【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框架。
方法细节
图对比学习
图神经网络表示学习方法是指，在给定一系列图，并且图
是从图空间的分布中独立同分布采样来的，期望学习到一个映射函数
，进而得到图的向量表示，以应用到下游任务。下游任务的标签
是从条件分布中采样得到，即
。基于标签和上述表示函数
（一个GNN）可以学习得到下游分类模型
（可能是一个GNN，也可能是MLP）。文章中，作者采用message passing GNN作为图表示学习的函数。
对比学习的核心之一是对比损失。大多数GCL基于InfoMax[39]，其形式化表示如下图所示。背后的核心思想是让学习的表示和原始图信息尽可能的一致（也有的是构造两个相同的表示，也就是图增广）。
作者提到，由于GNN不能保证图结构到隐向量空间的一一映射关系，因此给GCL带来了更大的挑战。
如上所述，一些GCL采用Graph Data-Augmentation的思路来扰动图数据，减少不必要的噪声期望扰动后的视图保留了核心信息，并利用InfoMax通过拉近扰动后向量表示的距离，来学习这种信息，其具体形式如下图所示。其中，分别表示采用的图增广方法和增广方法的全集。
可以看出，为了保证增广后的向量表示彼此是真的相近，换句话说，真的只去掉了redundant信息，而没有引入额外的错误或噪声，需要大量的验证（trial and error）和领域知识。
AD-GCL
为解决上述问题，作者提出了AD-GCL框架，该框架基于graph information bottleneck（GIB）。原有方法[47, 48]采用的GIB目标函数如下图所示。其中，表示两个随机变量的互信息。
是上述GNN，用来得到图的向量表示。
可以看出，GIB和InfoMax相反。InfoMax要求最大化原始图与其向量表示的互信息，而GIB要求尽量减少该互信息。但同时GIB同时要求最大化与下游任务（标签）相关的互信息，因此GIB删除（与下有任务无关的）冗余信息。因此，GIB自然避免了上述提到的，GNN学习到冗余信息造成在下游任务上效果变差的问题。此外，去除冗余信息也会使GNN抵抗对抗向攻击，并且学习到可转移的知识。
但是，GIB要求有下游任务的标签信息，这在图自监督学习阶段是不能获得的。因此，作者提出利用如下图所示的目标函数，来学习最小的、可用于区分图特质（比如节点标签、图标签等）的信息。
其中，表示图增广方法集合（文章重点关注的是可参数化的一类图增广方法，而不是所有不同类的方法，或者说作者更关注的是参数优化吧）。AD-GCL的min-max优化旨在训练GNN，使得即使在使用非常激进的 GDA（即因为随便扰动，破坏了原始信息，导致
与
非常不同），GNN仍然可以最大化扰动图与原始图之间的互信息。与GDA-GCL中采用两个不同的GDA不同，AD-GCL将原始图
视为锚点，目标函数中最小化的部分，寻找
使得
尽可能远离锚点（也就是上述最激进的情况，这种方式增加对抗的能力，同时去掉了无用的信息，当然不是随便去掉，还是要能区分图的特质的）。
接下来是一大段理论推导，对细节感兴趣的同学可以参考论文原文和附录。结论见（前边的定义部分，如前所述，是因为GNN不能做到1对1映射，所以作者够早了近似等价1-WL test的quotient space）。
粗暴的直接阐述结论，
的第一个式子的意思是，AD-GCL的最优解可以确保GNN中encode的，与下游任务无关的信息小于一个上界（也就是最大不会超过），
。因为，这个界限和GIB在
的情况下相关，因此可以保证和下游任务的相关性（具体地说，
，具体的还需要参阅论文附录）。
选择的足够好，即要求
，且
不要太小（这个在具体实现的时候会做约束来保证）。作者提到这类似于对
啊？虽然作者说论证里可以没有
本节介绍了作者的研究背景和AD-GCL的框架，下节继续介绍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的。
理论和实际应用
个人感觉，文中对理论过渡到讲解并不详细，并且理论分析中是假设有的，但是没有的时候具体会不会影响或者影响有多少正文里没有讨论，只是说可以没有。也许需要细致的读一下附录。
文章引用
[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 infor�mation 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.
