https://arxiv.org/pdf/2204.04874

Augmentation-Free Graph Contrastive Learning with Performance Guarantee，2022，arxiv preprint

总结：本文提出了一种新的无需增强的图对比学习模型AF-GCL。数据增强的目的是让我们能够选取正负样本对，以此为自监督信号学习节点表示，那么无须增强的AF-GCL是怎样选取正负样本对的呢？AF-GCL的方案很简单，根据节点嵌入选择正负样本对。具体来说，对于query节点，从它T-hop邻居节点集合中，选择相似度最高的K个节点作为正样本，其余节点作为负样本。作者从理论上分析并证明了AF-GCL可以同时适用于同构和异构图，并且能有很不错的表现，而现有的GCL方法在异构图上通常表现较差。

总的来说，这篇文章还是挺好的，虽然提出的模型比较简单粗暴，但是实验效果还不错，并且文章中给了很多理论分析和证明。看了眼，最近两年，关于GNN的频域研究似乎挺火的，看到了好几篇相关的顶会文章，作者应该是基于现有的一些研究，迁移到对比学习中来了。这篇文章目前还没投出去，盲猜作者投了一手ICML2022。

1. 简介

1.1 摘要

Graph contrastive learning (GCL) is the most representative and prevalent self-supervised learning approach for graph-structured data. Despite its remarkable success, existing GCL methods highly rely on an augmentation scheme to learn the representations invariant across different augmentation views. In this work, we revisit such a convention in GCL through examining the effect of augmentation techniques on graph data via the lens of spectral theory. We found that graph augmentations preserve the low-frequency components and perturb the middle-and high-frequency components of the graph, which contributes to the success of GCL algorithms on homophilic graphs but hinder its application on heterophilic graphs, due to the high-frequency preference of heterophilic data. Motivated by this, we propose a novel, theoretically-principled, and augmentation-free GCL method, named AF-GCL, that (1) leverages the features aggregated by Graph Neural Network to construct the self-supervision signal instead of augmentations and therefore (2) is less sensitive to the graph homophily degree. Theoretically, We present the performance guarantee for AF-GCL as well as an analysis for understanding the efficacy of AF-GCL. Extensive experiments on 14 benchmark datasets with varying degrees of heterophily show that AF-GCL presents competitive or better performance on homophilic graphs and outperforms all existing state-of-the-art GCL methods on heterophilic graphs with significantly less computational overhead.

图对比学习是最具代表性和最流行的用于图结构数据的自监督学习方法。虽然GCL取得了很大成功，但是GCL方法高度依赖增强策略，从不同增强视角中学习表示不变量。本文，我们基于“lens of spectral theory”来验证增强技术在图数据上的作用，探究GCL方法中数据增强这一惯例。我们发现图增强保留了图的低频部分，对图的高频和中频部分进行扰动，这有助于将GCL应用到同构图上的，但是阻碍了它在异构图上的应用。因为异构图中高频部分太多了（这里不太懂是啥意思）。受此启发，我们提出了一种新的、有理论基础的、无须增强的GCL方法，称之为AF-GCL：（1）利用GNN聚合的特征来构建自监督信号，而不是增强策略，因此对图的同构程度不敏感；（2）作者进行了理论证明，保证AF-GCL具有优秀的性能。14个异构程度不同的标准数据集上的大量实验表明，和SOTA方法相比，在同构图上AF-GCL性能具有竞争力，在异构图上其性能优于所有其他GCL方法，同时计算代价更低。

1.2 本文工作

背景： 对比学习作为一种自监督学习方法被广泛应用于各个领域。对比学习的本质是学习数据增强下的表示不变性，这在视觉数据中被广泛研究。利用相同的模式，GCL鼓励representations在训练过程中尽可能少地保留关于inputs转换方式的信息，即对于手动转换的不变性。近几年，人们为GCL中设计了多种手动增强策略，比如node dropping、edge perturbation等。虽然大量实验证明了GCL方法的有效性，但是这些研究通常都是关于同构图的。

动机： 和同构图不同，在异构图中，相似的节点经常距离很远，这促使我们研究可以同时用于同构和异构图的GCL方法。（1）作者首先分析了在图数据增强过程中，哪些信息被保留了，哪些数据总是被扰动。从频域的角度俩分析图结构和特征，作者发现图增强主要保留了低频信息，扰动中频和高频信息。通过最大化原始图不同视角之间的一致性来学习这种扰动下的表示不变性，最终学习到的表示只保留了低频信息。根据现有研究，低频信息对同构图很重要。对于异构图，只有低频信息不足以学习有效的节点表示。（2）基于这一发现，作者提出疑问： is it possible to design a generic graph contrastive learning method effective on both homophilic and heterophilic graphs?

啥是频域？低频、中频、高频信息是啥？

可以参考这个回答。低频信息可以理解成某个节点和周围邻居节点信号差值比较小，也就是比较平滑；高频则是信号插值比较大。

本文工作： （1）作者提出了一种新的无需增强的GCL方法，AF-GCL，可以同时适用于同构和异构图。和现有GCL模型不同，AF-GCL基于聚合后的节点嵌入构建正负样本对，并直接在高维空间优化表示之间的距离。由于AF-GCL无需增强，因此更容易扩展到大型图上。（2）作者从理论上解释和证明了AF-GCL的有效性。

2. 方法

2.1 AF-GCL

为了设计一种通用的自监督信号，作者关注于聚合节点特征$\mathbf Z$在同构和异构图中的共同特性。即不管同构程度如何，相同类别的节点（应该是聚合后的节点特征）距离总是更近。利用这一特性，作者提出了一种无须增强的GCL方法AF-GCL。

2.1.1 Aggregated Features理论分析

作者首先对节点特征进行了一些假设，并从假设中引出关于节点特征的一个结论。然后在此假设下，提出了一条引理，并给出了证明。

1. 假设

   作者假设节点特征服从Gaussian mixture model。为了方便起见，以二分类问题为例。对于一个标签$y$的节点和一个潜在向量$\mu \sim \mathcal{N}\left(\mathbf{0}, \mathbf{I}_F / F\right)$，其中$\mathbf{I}_F \in \mathbb{R}^{F \times F}$是单位矩阵。节点特征的计算方式如下：

   $\mathbf{x}_i=y_i \mu+\frac{\mathbf{q}_i}{\sqrt{F}}$

   其中随机变量$\mathbf{q}_i \in \mathbb{R}^F$具有独立的“standard normal entries”（不太懂啥意思）。$y_i\in\{-1,1\}$为标签类别。这样所有类别为$y_i$的节点的特征都服从依赖于$y_i$的分布，$\mathbf{x}_i \sim P_{y_i}(\mathrm{x})$（因为上面公式中只有$y_i$一个输入）。

   基于以上分析，作者进一步假设：对于节点$i$，其邻居节点的标签是从$P(y_i)$中独立采样得到的。

2. 结论

   上述假设说明了一个结论：“ The neighbor’s label is generated from a distribution only dependent on the label of the central node, which contains both cases of homophily and heterophily. ”。

3. 引理

   关于引理的证明可以自己看原文。

2.1.1 模型设计

上一小节中的理论分析表明：通过邻域聚合得到的嵌入会向该类别的嵌入期望集中（大白话应该就是相同类别的节点的嵌入倾向于聚集到一起，应该就是类似聚类那种）。受此发现的启发，作者在AF-GCL中基于节点相似度来选取正负样本对。如下图2所示：

AF-GCL首先用一个图编码器对输入图进行编码，得到节点嵌入$\mathbf{H}=f_\theta(\mathbf{X}, \mathbf{A})$。然后使用一个带有L2范式的MLP映射头$g_w$，将节点嵌入映射到隐藏空间，得到$\mathbf Z=g_w(\mathbf H)$。每轮迭代过程中，从节点集合$S$中随机采样$b$个节点以及这些节点的T-hop邻居，构成节点集合$P$。对于任意节点$v_i\in S$，从$P$中选取$top-K_{pos}$个相似度的节点作为该节点的正样本集合，表示为$S_{\text {pos }}^i=\left\{v_i, v_i^1, v_i^2, \ldots, v_i^{K_{p o s}}\right\}$，计算方式如下：

$v_i^1, v_i^2, \ldots, v_i^{K_{p o s}}=\underset{v_j \in P}{\arg \max }\left(\mathbf{Z}_i^{\top} \mathbf{Z}_j, K_{p o s}\right)$

其中$\arg \max \left(\cdot, K_{p o s}\right)$表示选择top K个。由于hidden representation $\mathbf Z$已经正则化过了，因此内积就等价于余弦相似度。整个模型的对比损失定义如下：

$\mathcal{L}_{g c l}=-2 \mathbb{E} \underset{\substack{v_i \sim Uni(\mathcal V) \\ v_{i^+} \sim\left(Uni\left(\mathcal{S}_{p o s}^i\right)\right.}}{ }\left[\mathbf{Z}_i^{\top} \mathbf{Z}_{i^{+}}\right]+\underset{\substack{v_j \sim U n i(\mathcal{V}) \\ v_k \sim U n i(\mathcal{V})}}{\mathbb{E}_j}\left[\left(\mathbf{Z}_j^{\top} \mathbf{Z}_k\right)^2\right]$

这里其实是把$\mathcal V$中所有其他节点看作负样本了，目标函数其实就是正样本对相似度的期望减去负样本对相似度的期望。为啥第一项前面有个2？因为后一项中不仅有负样本对，还包含了正样本对。

AF-GCL 伪代码如下图所示：

2.2 理论支撑

作者从理论上证明并解释了AF-GCL的有效性。这块不太懂，感兴趣的可以自己看原文。

3. 实验

1. 基础对比

   

2. 计算代价

   

3. 嵌入维度