文章名称
【ICLR-2022】【Michigan State University/Snap】Automated Self-Supervised Learning for Graphs
核心要点
文章旨在解决图神经网络上，不同预训练任务对下游任务的影响不同，需要精选预训练任务的问题。作者利用现实世界的网络具有所谓”同性相吸“的特性，自动的选取预训练任务，并从理论上证明了这一特性。基于此，作者提出AUTOSSL框架来自动寻去各种自监督任务（组合）提升模型预训练的效果（以下游任务结果为评估指标）。
研究背景
图神经网络的自监督学习方法带来的好处就不啰嗦了。但是作者发现（图神经网络上）不同的自监督任务在不同下有任务上表现差异较大，对比结果如下图所示（没有一个任务是一直排序比较理想的），对比方法包括s DGI [13]，PAR/CLU [14]， MVGRL [15]，PAIRDIS [16]以及PAIRSIM [11, 17]。
因此，作者认为选择SSL任务至关重要，需要有效的方法来自动组合各种图自监督任务，以便学习更好的节点表示。然而，在无监督（不利用下游任务信息的情况下）自动结合多个不同的 SSL 任务来是非常困难的（有点既要也要还要的意思了）。同时，如上图子图c所示，不同自监督任务的权重会极大影响下游任务的性能（作者表示CV领域通常是等权重[18–20]，但是不一定能超越单个预训练任务）。那么如何利用无监督信息构造一个伪评价指标指导自监督任务和权重的选取呢？作者利用图数据（包括社交网络、学术网络）了”同性相吸“或者说”连接的节点通常共享相同的标签“的特性，并且这个特性与下游任务是强相关的。因此，作者用相连的节点的embedding的相近（向量空间的距离）性来评估节点embedding学习的好坏。并且，作者证明，利用这个最大化伪同质的特性可以帮助最大化伪标签和下游标签之间互信息的上限。
方法细节
AutoSSL的目的是，在给定图，GNN
和
个自监督任务（损失）
的前提下，寻找合适的权重
，达到如下图所示的目标，其中
表示下游的评价指标。
该目标的意思是，模型能够学习到对下游任务”有益处的“节点表示。如前所述，SSL假设没有下游任务的数据，即得不到。
Pseudo-Homophily
为了量化“物以类聚”，作者借鉴图的同质性[39]，其形式定义如下图所示，本质是计算具有相同类别标签端点的连边占整个图中边的比例，或者称之为”类内边“占比。
又要说，我们没有下游任务的类标签。因此作者利用DeepCluster[40]根据聚类得到伪标签，计算同质性得到伪同质性。具体的，作者k-means聚类，将聚类结果作为伪标签来计算基于同质性的。
值得注意的是，作者从理论角度证明，最大化伪同质的特性可以帮助最大化伪标签和下游标签之间互信息的上限。其结论如下图所示，具体证明过程请参见原文附录。
上述定理表明在具有高同质性的图数据上，节点表示得到的伪同质性与真实同质性的差异越大，学习得到的伪标签（或者叫预测标签吧）与真实标签的互信息上界越小。所以最大化同质性，相当于最大化伪标签（或者叫预测标签吧）与真实标签的互信息上界（个人感觉这很直觉，因为同质性高的图就是靠这些同质性，甚至是标签传播在提升预测能力。那是不是直接标签传播不就行了？看似也不是，因为毕竟还需要不同的自监督任务来适应下游任务）。
Search Algorithms
基于上述Pseudo-Homophily，可以把前述公式1中（评分函数）替换成 negative pseudo-homophily。
解决了损失函数中评分函数的的问题，还需要解决约束中带有最优化问题的挑战。显然，不能直接用简单的梯度下降求解。因此，作者提出了（相对）两种高效求解的方法，
AUTOSSL-ES。该方法采用自适应协方差矩阵遗传算法CMA-ES[43]来迭代的寻找最优自监督任务组合权重
。具体的，在每次迭代中，CMA-ES从多元正态分布中采样一组候选解（8个）（即一组
评估神经网络模型学习的嵌入表示。基于评估结果，CMA-ES调整正态分布，使得更好的权重有更高的被选择的概率（这里其实也是交替的思想，只不过每次调整权重的维分布来控制
AUTOSSL-DS。上述基于遗传的方法在每一步迭代中都需要对神经网络模型进行优化，搜索空间大时仍然有很大开销（虽然只有8个解，8个候选解肯定也影响收敛速度）。因此，作者提出基于meta-gradient的优化方法来加速优化过程。**然而，由于k-means是“硬”聚类，上述pseudo-homophily不支持直接进行梯度回传。所以，作者先进行“软”聚类，再进行meta-gradient。
Soft Clustering。对k-means的“硬”转“软”的常规操作是利用GMM，假设聚类中心为
，每一个正态分布具有相同的采样方差
。可以的得到如下图所示的后验概率，
posterior probability随后，利用贝叶斯法则，并假设各个聚类的出现概率
（这里其实可以商榷，但是根据最大熵原理，也是合理的）。则可以得到给定节点embedding
后该节点属于某个类别的概率。
probability of a feature vector
作者表示，从上述概率公式可以看出，节点embedding是否属于某个类别，取决于的距离（显然的，重点在后面）。因此，判断两个节点是不是Homophily，直接看两个节点的距离就好了。作者引入了距离函数
，可以得到如下图所示的所谓“soft pseudo-homophily”，
soft pseudo-homophilyMeta Gradient Descent。在回头看公式1，如果两个部分的参数互相关联（
和
，那么就可以直接交替优化内外层。但是
和
meta-optimization
这里是指元学习中的内层优化（优化
值得注意的是，作者提到，这样的优化策略，并不是在寻找可以固定下来的最优
代码实现
AUTOSSL-ES和AUTOSSL-DS的伪代码如下图所示。
心得体会
不一定所有图都高度同质
其实这里说的同质和异质图、同质图分类的定义是不一样的。或者说那个应该叫同构图和异构图。也许很多同学也怀疑，是否所有图都满足high Homophily的假设？答案是否定的，作者在原文也提到，有heterophily graphs [39, 41]，并且作者把这类图当做未来的工作。
没有标签
因为没有标签所以需要构造伪标签，同时伪标签和模型实现共同收敛，是deep clustering的重要思想，有点类似bootstrap。
预训练
文章的目标是对一张图高效的寻找不同的，自监督任务以适应不同的下游任务。不同于其他预训练场景，比如说NLP的场景，利用大量的训练数据（类比到图这里就是大量的图数据）来训练同一个模型。因此，都是预训练，但其实还是有差别的。
假设
作者假设，这些聚类中心出现的概率一致。什么叫出现概率一致呢？个人理解，就是有就等可能的有
或其他中心，那聚类中心出不出现的概率谁决定呢？由是否有节点属于这个中心决定。那就是，不管怎么样，这些中心至少有一个节点的概率相等。看似合理，不过有点牵强。
类似DARTS的online updating
个人感觉，这个部分可以理解为，训练一个GNN模型，需要更新，在每次训练的时候，就问一下：“当前我应该怎么组合自监督任务啊（找当前看似最优的
）”，然后，不断迭代，最终得到的是一个最优的GNN。但是，这个
是不是能一直固定从头到尾训练一个SOTA GNN，答案是，不一定或者说大概率差点意思。
文章引用
[11] Wei Jin, Tyler Derr, Haochen Liu, Yiqi Wang, Suhang Wang, Zitao Liu, and Jiliang Tang. Self-supervised learning on graphs: Deep insights and new direction. arXiv preprint arXiv:2006.10141, 2020.
[12] Yaochen Xie, Zhao Xu, Jingtun Zhang, Zhengyang Wang, and Shuiwang Ji. Self-supervised learning of graph neural networks: A unified review. arXiv preprint arXiv:2102.10757, 2021.
[13] Petar Velickovi ˇ c, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep Graph Infomax. In International Conference on Learning Representations, 2019.
[14] Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. When does self-supervision help graph convolutional networks? ICML, 2020.
[15] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International Conference on Machine Learning, 2020.
[16] Zhen Peng, Yixiang Dong, Minnan Luo, Xiao-Ming Wu, and Qinghua Zheng. Self-supervised graph representation learning via global context prediction. arXiv preprint arXiv:2003.01604, 2020.
[17] Wei Jin, Tyler Derr, Yiqi Wang, Yao Ma, Zitao Liu, and Jiliang Tang. Node similarity preserving graph convolutional networks. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining. ACM, 2021.
[18] Carl Doersch and Andrew Zisserman. Multi-task self-supervised visual learning. In Proceedings of the IEEE International Conference on Computer Vision, pages 2051–2060, 2017.
[19] Zhongzheng Ren and Yong Jae Lee. Cross-domain self-supervised multi-task feature learning using synthetic imagery. In Proceedings of the IEEE onference on Computer Vision and Pattern Recognition, pages 762–771, 2018.
[20] Amir R Zamir, Alexander Sax, William Shen, Leonidas J Guibas, Jitendra Malik, and Silvio Savarese. Taskonomy: Disentangling task transfer learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3712–3722, 2018.
[32] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv:1806.09055, 2018.
[39] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020.
[40] Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsupervised learning of visual features. In Proceedings of the European Conference on Computer Vision (ECCV), pages 132–149, 2018.
[41] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gcn: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020.
[43] Nikolaus Hansen, Sibylle D Müller, and Petros Koumoutsakos. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (cma-es). Evolutionary computation, 11(1):1–18, 2003.
