文章名称
【AAAI-2022】【KAIST】Augmentation-Free Self-Supervised Learning on Graphs
核心要点
文章旨在解决现有图自监督学习方法严重依赖数据增广方式和增广参数设置的问题，提出了不需要设计增广方法的图自监督学习框架AFGRL。作者通过挖掘图中共享局部结构信息和全局语义的节点对来构造对比学习的正、负样本，实现对比学习，得到可迁移的节点表示。
研究背景
自监督学习在各领域取得了成功，主要依赖数据增广和对比损失两个核心要素。但是，作者认为如果不精心设计数据增广方法，在图数据上自监督的效果会比较差（所有有许多方法都采用大量实践来设计图增广方法，或者有些采用adaptive的方法自适应的学习增广策略。
如果照搬图像数据上的数据增广方法，图数据上的数据增广方法更容易在不经意间就改变了原始图上的语义信息（个人理解，可以认为图上的信息冗余比图像上的输入冗余更少，或者说信息要素的分布更分散，例如，图上的信息可能大部分集中在图片中央，有很强的位置不变形，也许也是平移不变性的一种体现）。
对比学习的目标是学习节点嵌入可以很好地推广到各种下游任务，而不使用任何类信息。受到BYOL[Grill et al. 2020]和BGRL[Thakoor et al. 2021]的启发，作者期望提出一种完全不需要图增广的方法（BGRL还是有增广的）。
方法细节
BYOL
由于作者的方法主要基于BYOL，因此简要介绍一下其流程，大致可以分为2个方面，
结构和流程方面。给定样本（BYOL原文里是图像）
，可以利用数据增广方法得到两个增广后的样本
。其中
是从所有可能的增广方法中选择的，两种不同的数据增广方式。随后，利用两个不同的encoder，online encoder和target encoder，
（括号内的一组变换函数或者说神经网络代表了一个encoder），得到变换后的样本向量
（我这里符号有一点不严谨，应该用粗体表示向量，意会吧:)）。由于是同一个样本扰动出来的，
作者期望两者的最小化两者之间的差异（采用
距离表示）。但是为了不坍缩到平凡解，作者采用了非对称的trick，在计算
加了一层模型，
，具体的损失如下图所示。其中，
表示normalize之后的结果。
asymmetric L2 distance但是，本身拉近距离应该是不具有方向性的，所以还得矫正回来，因此作者又构造了
，这个损失只是把
对调而已。
total loss优化方面。有了上述损失，可以对参数
进行优化。由于没有没有负样本，作者采用了不同的更新节奏，来分别更新
是每次都更新，而
是采用
分别是学习率和衰减权重。
updating parameters
BYOL on GCL
AFGRL
作者提出AFGRL框架，引入图结构数据中的关系归纳偏差和图的全局语义信息，来学习可以迁移到下游任务的向量表示。具体的说，作者利用online和target network中节点表示的 两两相似性 来构造正样本对，相似性的计算方法如下图所示。其中，分别代表online和target network中的节点表示。利用节点间的相似性分数，可以对目标节点
（作者称之为query node）选取k近邻的节点
作为正样本对集合。
尽管这样做简单有效，但是仍然存在2个问题，
是noisy的，因为没有采用下游标签信息，无法保证集合中的节点与query node是具有相同语义标签的（即最终的分类标签）。
- 由于只采用了向量空间的相似性，这种正样本对可能忽略了局部结构信息和全局语义信息。
因此，作者采用如下2种方法，过滤其中的noise，同时还捕获局部结构信息和全局语义信息，
Capturing Local Structural Information。由上述问题引申出来一些思考，什么样的近邻节点才是我们需要的？作者从服务下游任务的角度考虑，期望近邻节点与query node具有相同的class（也就是相同的标签）。因此，作者对上述提出的k近邻方法做了数据分析。分析结果如下图所示。
analysis of k nearest neighbor strategy其中，节点的embeding是通过随机初始化的2层GNN得到的（黑色原点与红色星星），横轴表示
取交（win-win联合的感觉）进行去噪。得到的所谓local positive集合的标签一致率用红色星星线代表，结果表示这种策略可以实现标签一致率的提升（直接用原始特征的黑色三角，只有30%，这符合预期，因为毕竟太稀疏了，很难计算相似和重合）。作者表示，之所以提升是因为GNN可以学到一些结构同态信息（即便只用了随机初始化），而近邻的平滑则帮助去掉了噪声，相当于利用了局部结构信息。
Capturing Global Semantics。除了利用局部结构信息外，作者还利用聚类方法引入了全局语义信息。具体的说，作者利用target network得到的节点向量
，作为特征进行K-means聚类，并与query node属于同一个类别的节点视为相似节点候选集
。再与k近邻方法得到的集合取交,得到所谓的global positive集合。值得注意的是，K-means对聚类中心初始化比较敏感。因此，作者采用
次K-means聚类，并对聚类结果取并集，得到一个类别的聚类结果（怎么确定跟谁对齐呢？并且是否有重复？参见
心得体会的讨论）。 作者表示，这样的方法能够将那些相隔较远，且语义类似（比如学术网络中，从事统一topic研究的作者）节点聚集为positive pair。
最终，作者通过对local positive和global positive取并集，得到所谓的real positive
，并以此为正样本集合，进行对比学习，具体目标函数如下图所示。
其中，表示从online network的预测头得到的节点
的embeding。**值得注意的是，作者也进行了损失对称，也就是把其他节点
当做query node传入online target（其实就是每个positive pair都要对调再过一遍，不然不对称）。
敬阅读的同学
这篇文章是在探索如何避免进行图增广，同SimGRACE一样，都受到了BGRL的影响，不同的是，AFGRL保留了EMA的特性，同时引入了类似PGCL的聚类方法来捕获全局信息，可以理解为是对样本进行了一些筛选。读了这些paper，基本上改进分为3个部分，
- 增广的选取，手动 or 自动 or 隐式（向量空间）。
- 正样本对或样本信息的筛选、提纯，例如使用聚类方法，或者启发式的方法。
- 利用不同的对比损失或者预测损失（扰动encoder）进行模型的学习。
混合这些trick，就派生了不同的方法。并且，大部分策略还是源于对比学习和自监督学习的基本技术的发展，也许可以多看看图像层面的自监督借鉴经验。
欢迎批评指正以及对写作方法提出意见（比如，分成几个部分写之类的），有其他喜欢的主题也欢迎留言。感谢大家阅读到这里！期待你的 点赞 喜欢 和 收藏！
心得体会
EMA
感觉值得注意的是，更新时用的是
的EMA，也就是说，是在模仿
。其实，这种快慢更新方式（嗯，这里说的不是快慢指针）也并不罕见（想起了DDQN没有？），一般是为了保证存在一个所谓的“伪目标”（不知道是不是可以称之为伪不动点）。这也许就是作者称之为target encoder的由来。
作者在做k近邻数据分析的时候采用随机初始化的2层GNN得到节点向量表示。这与最初说的k近邻相似度计算的向量分别来自online和target network不同。个人理解，最初设计这个k近邻是希望用两个view下的向量来寻找正样本对。然而，分析的时候用了一个随机（或者是2个）GNN来得到embeding能够反映真实模型的结果么？
此外，如果训练的比较好的模型做k近邻，应该能够学习到较丰富的结构和语义信息（毕竟GNN就是为了干这个的，但问题是没有监督），那么还有必要构造所谓的global positive么？ 个人感觉合理的解释是，因为没有标签，只能“自举”。
此外，个人理解是可以通过交替迭代的方式来实现收敛，一方面利用online和target network来计算embeding，一方面利用这个embeding来构造正样本对指导embeding学习。但是，这种类似boostrap的方法，已经体现在了online和target网络的更新中，再引入样本boostrap，会不会不稳定，也确实需要分析。
K-means对齐
个人感觉，作者采用K-means节点标号的方法对齐聚类结果，并取并集可能存在风险。因为，每次聚类的标号和聚类中心在空间中的位置不是完全对应的。也就是说，1号中心第一次可能在图的左上角，2号第一次在右下。第二次，可能正好对调（虽然几率不大，但有可能，和初始化的方法相关）。因此，两次结果取并集，可能扩大很多不必要的噪声。
个人认为，更合理的做法是，按照聚类中心的位置对齐。多次聚类都找和自己位置相对接近的聚类中心，两两合并。
无论怎样，都会有一个节点属于多个类别的可能。作者似乎没有明确解释这个问题。个人柑橘问题可能不大，因为毕竟比随机选取的扰动要噪声小很多。
为什么没有negative也能work？
个人感觉，由于target的更新是用EMA，感觉有点类似一些采用上一个batch的正样本，作为当前batch的负样本的方法[*1]虽然相似，但是不相同。（不过没太明白的是，那些方法是显示的推远了这种负样本，为什么这里拉近也有效果呢？）BYOL应该有答案。
文章引用
[Grill et al. 2020] Grill, J.-B.; Strub, F.; Altche, F.; Tallec, C.; Richemond, P. H.; ´ Buchatskaya, E.; Doersch, C.; Pires, B. A.; Guo, Z. D.; Azar, M. G.; et al. 2020. Bootstrap your own latent: A new approach to selfsupervised learning. arXiv preprint arXiv:2006.07733.
[Thakoor et al. 2021] Thakoor, S.; Tallec, C.; Azar, M. G.; Munos, R.; Velickovi ˇ c, P.; and ´ Valko, M. 2021. Bootstrapped representation learning on graphs. arXiv preprint arXiv:2102.06514.
[Zhu, Ghahramani, and Lafferty 2003] Zhu, X.; Ghahramani, Z.; and Lafferty, J. D. 2003. Semisupervised learning using gaussian fields and harmonic functions.
In ICML, 912–919.
[*1] Wang, Jinpeng, Jieming Zhu and Xiuqiang He. “Cross-Batch Negative Sampling for Training Two-Tower Recommenders.” Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval (2021): n. pag.
