从图谱视角再谈图对比学习

作者: 酷酷的群 | 来源:发表于2023-02-06 08:50 被阅读0次

论文标题：Revisiting Graph Contrastive Learning from the Perspective of Graph Spectrum
论文链接：https://arxiv.org/abs/2210.02330
论文来源：NeurIPS 2022
代码链接：https://github.com/liun-online/SpCo

一、概述

传统图对比学习主要包括三个模块：图增强、通过encoder学习图表示、对比损失，框架图如下图所示。本质上图对比学习旨在最大化不同增强视图之间的一致性来学习不变性表示。经典的图对比学习方法致力于设计不同的图增强策略。举例来说，如启发式方法包括node or edge dropping、feature masking和diffusion，基于学习的方法包括InfoMin、disentanglement和对抗训练。虽然有很多图增强策略被提出，但是基础的增强机制并没有被很好地理解。本文将回答以下问题：
①在一个增强图中什么信息应该保留或丢弃？
②不同图增强策略之间有没有一些通用的规则？
③如何使用这些通用的规则来验证和改进当前的图对比学习方法？

框架

从本质上来讲，增强图通过改变原图中的一些部分来获得，从而也改变了图谱中频率的强度。本文通过实验来验证图对比学习中的低频信息和高频信息的重要性，结果表明低频信息和高频信息都很重要。保留更多的高频信息对提高图对比学习的性能尤其有帮助，不过如上图(b)所示，处理两个对比图 $V_1$ 和 $V_2$ 中高频信息的方法应该是不同的。这一点可以总结为本文提出的general graph augmentation (GAME)规则：两个对比视图的高频信息的振幅差异应该比低频信息的振幅差异更大。

为了解释GAME规则，我们需要理解图对比学习学习到的表示编码了什么信息。本文提出了对比不变性（contrastive invariance）理论，即定理1。同时通过上图(b)可知，两个增强图的低频信息振幅的差异要比高频信息振幅的差异小，所以最低频的的信息就是两个增强图的近似不变模式（approximately invariant pattern），因此本文认为图对比学习主要学习到的是低频信息。这一理论不仅解释了图对比学习为什么有效，也为评价哪种增强策略更好提供了标准。

本文称满足GAME规则的两个增强为最优对比对（optimal contrastive pair）。本文也提出了一个新的通用的图对比学习框架，能够使用最优对比对来增强现有的图对比学习方法，称为spectral graph contrastive learning(SpCo)。具体的，为了确保学习到的增强图是原图邻接矩阵的最优对比对，我们需要使得其高频信息的振幅上升，同时保持低频信息与原图相同。众所周知图对比学习设计的两个增强视图应该要尽可能地保持原图的本质特征，改变不重要的特征。本文的意义就在于其解释了这些本质特征实际上是图在频域的低频信息，而那些需要了改变的不重要的特征为高频信息，因此SpCo设计的总之就是保留低频信息与原图相同，而提升高频信息的振幅以使得两个视图的高频信息不同。

二、预备知识

在本文中使用 $\mathcal{G}=(\mathcal{V},\mathcal{E})$ 来表示一个无向图， $\mathcal{V}$ 是 $N$ 个节点的集合， $\mathcal{E}\subseteq \mathcal{V}\times \mathcal{V}$ 是边的集合。 $A\in \left \{0,1\right \}^{N\times N}$ 是邻接矩阵， $D=diag(d_{1},\cdots ,d_{N})$ 是节点度矩阵。 $\mathcal{G}$ ， $X=[x_{1},\cdots ,x_{N}]\in \mathbb{R}^{N\times d}$ 是特征向量矩阵。另外我们用 $\mathcal{L}=D-A$ 作为 $\mathcal{G}$ 未标准化的拉普拉斯矩阵，用 $\hat{\mathcal{L}}=I_{N}-\hat{A}=D^{-1/2}(D-A)D^{-1/2}$ 表示对称标准化的图拉普拉斯矩阵。

$\hat{\mathcal{L}}$ 的特征分解（谱分解）为 $U\Lambda U^{T}$ ，这里 $\Lambda =diag(\lambda _{1},\cdots ,\lambda _{N})$ ， $U=[u_{1}^{T},\cdots ,u_{N}^{T}]\in \mathbb{R}^{N\times N}$ 分别为 $\hat{\mathcal{L}}$ 的特征值与特征向量。不失一般性，在本文中假设 $0\leq \lambda _{1}\leq \cdots \leq \lambda _{N}< 2$ ，这里按照GCN（第三代图卷积网络：使用图卷积网络进行半监督分类）的做法近似 $\lambda _{N}\approx 2$ 。另外用 $\mathcal{F}_{L}=\left \{\lambda _{1},\cdots ,\lambda _{\left \lfloor N/2\right \rfloor}\right \}$ 和 $\mathcal{F}_{H}=\left \{\lambda _{\left \lfloor N/2\right \rfloor+1},\cdots ,\lambda _{N}\right \}$ 分别表示频率中的低频部分和高频部分。图谱被定义为这些不同频率的振幅，用 $\phi (\lambda )$ 来表示，表示对应的频率被增强还是减弱。除此之外，在本文中重写特征分解为 $\hat{\mathcal{L}}=\lambda _{1}\cdot u_{1}u_{1}^{T}+\cdots +\lambda _{N}\cdot u_{N}u_{N}^{T}$ ，这里我们定义 $u_{i}u_{i}^{T}\in \mathbb{R}^{N\times N}$ 为 $\lambda _{i}$ 相关的特征空间，记作 $S_{i}$ 。

三、图增强的影响：实验研究

在本节中，我们旨在从图谱的角度探讨在两种对比增强中应该考虑哪些信息。我们设计了一种简单图对比学习框架，如下图所示。将邻接矩阵 $A$ 和增强视图 $V$ 两个视图输入到一个共享的GCN中来获取节点表示 $H_{A}$ 和 $H_{V}$ ，然后使用InfoNCE损失来训练。

框架

我们通过从原始图中提取不同频率的信息来构造增广图，以此来分析不同信息的影响，这个过程如下图所示。具体的，我们将 $\mathcal{L}$ 的频率分为 $\mathcal{F}_{L}$ 和 $\mathcal{F}_{H}$ 两部分，并且分别在这两部分上进行实验。以 $\mathcal{F}_{L}$ 的增强为例，我们保持高频部分为 $u_{N/2}u_{N/2}^{T}+\cdots +u_{N}u_{N}^{T}$ 。然后，我们逐渐将 $\mathcal{F}_{L}$ 中的特征空间按照 $\left [20\%,40\%,60\%,80\%\right ]$ 的比例逐渐加回来，从最低的频率开始。因此，增强 $\mathcal{F}_{L}$ 中 $20\%$ 的特征空间的 $V$ 为 $u_{1}u_{1}^{T}+\cdots +u_{0.2*N/2}u_{0.2*N/2}^{T}+u_{N/2}u_{N/2}^{T}+\cdots +u_{N}u_{N}^{T}$ 。类似的增强 $\mathcal{F}_{H}$ 中 $20\%$ 的特征空间的 $V$ 为 $u_{1}u_{1}^{T}+\cdots +u_{N/2}u_{N/2}^{T}+u_{(N+1)/2}u_{(N+1)/2}^{T}+\cdots +u_{0.7*N}u_{0.7*N}^{T}$ 。需要注意我们将 $V$ 的图谱设置为 $\phi _{V}(\lambda )=1,\forall \lambda \in [0,2]$ ，这是因为我们只想要测试不同的 $u_{i}u_{i}^{T}$ 的作用，避免特征值 $\lambda$ 的影响。

增强视图的生成过程

按照上面的设置，本文在Cora, Citeseer, BlogCatalog, Flickr共4个数据集上进行节点分类，实验结果如下图所示。

实验

对于每个数据集，在 $V$ 中：
①当频率的最低频部分被保留时，模型达到了最高性能；
②当越来越多的 $\mathcal{F}_{H}$ 中的频率部分被加进来时，模型的性能逐渐提升。

下图展示了 $A$ 和 $V$ 的图谱，我们可以看到在生成的 $V$ 中：
①当频率的最低频部分被保留时， $A$ 和 $V$ 在 $\mathcal{F}_{L}$ 中频率的振幅差异会变小；
②当 $\mathcal{F}_{H}$ 中更多的频率被加入进来以后， $A$ 和 $V$ 在 $\mathcal{F}_{H}$ 中频率的振幅差异会变大。

图谱

根据上面的结果和分析，本文提出了图增强的GAME规则：

给定两个随机增强 $V_1$ 和 $V_2$ ，其图谱分别为 $\phi _{V_{1}}(\lambda )$ 和 $\phi _{V_{2}}(\lambda )$ ，接着对于 $\forall \lambda _{m}\in [1,2]$ 和 $\forall \lambda _{n}\in [0,1]$ ，当满足以下条件时 $V_1$ 和 $V_2$ 是一个有效的增强对：
$|\phi _{V_{1}}(\lambda _{m})-\phi _{V_{2}}(\lambda _{m})|> |\phi _{V_{1}}(\lambda _{n})-\phi _{V_{2}}(\lambda _{n})|$
我们称这样的两个增强 $V_1$ 和 $V_2$ 是一个最优对比对。

虽然这一规则是从 $A$ 和 $V$ 的对比中衍生出来的，但这些视图的选择并没有限制GAME规则的普遍性。考虑到大多数增广都是从原始邻接矩阵 $A$ 中获得的，因此两个视图一个是邻接矩阵 $A$ 另一个是增强视图 $V$ 这样的设置是很自然的。

四、GAME规则的分析

在本节中，我们旨在通过实验和理论分析验证GAME规则的正确性，即两个满足GAME规则的对比增强是否能在下游任务中表现得更好。我们用一些现有方法（MVGRL、GCA、GraphCL）所使用的数据增强来替换 $V$ 。具体的，MVGRL提出了PPR matrix、heat diffusion matrix和pair-wise distance matrix；GCA根据节点度中心性、特征向量中心性、PageRank中心性来随机丢弃边；GraphCL采用随机node dropping、edge perturbation和subgraph sampling。这三个方法一共九种增强方式基本上覆盖了目前的主流图数据增强方法。为了准确地描述某些 $\lambda _{i}$ 在这些增强后的振幅变化，我们采用矩阵摄动理论（matrix perturbation theory）：

$\Delta \lambda _{i}=\lambda _{i}^{'}-\lambda _{i}=u_{i}^{T}\Delta Au_{i}-\lambda _{i}u_{i}^{T}\Delta Du_{i}+O(\left \|\Delta A\right \|)$

$\lambda _{i}^{'}$ 是改变后的特征值， $\Delta A=A^{'}-A$ 代表图增强修改的边， $\Delta D$ 是度矩阵相应的变化。我们利用上式来计算每种增强的特征值，并且在下图中绘制了它们对应的振幅。这里没有用特征分解来获取 $A^{'}-$ 的特征值，这是因为这样得到的特征值是未经排序的，因此我们不知道得到的特征值与 $A$ 的特征值的对应关系，所以无法得到 $\Delta \lambda _{i}$ 。

图谱

实验在Cora数据集上进行，我们使用上面采用的简单图对比学习框架来对比 $A$ 和这些增强，实验结果如下表所示。实验结果显示PPR matrix、heat diffusion matrix和pair-wise distance matrix这些更符合GAME规则的增强方法取得了更好的性能，它们在低频信息振幅上有较小的差异，在高频信息振幅上有较大的差异。

实验

本文还提出了下面的定理来解释图对比学习的学习过程：

定理1（对比不变性）
给定一个邻接矩阵 $A$ 和生成的增强图 $V$ ， $A$ 和 $V$ 的第 $i$ 个频率分别为 $\lambda _{i}$ 和 $\gamma _{i}$ ，在优化InfoNCE损失函数时， $\mathcal{L}_{InfoNCE}$ 遵循以下上界：
$\mathcal{L}_{InfoNCE}\leq \frac{1+N}{2}\sum _{i}\theta _{i}[2-(\lambda _{i}-\gamma _{i})^{2}]$
这里 $\theta _{i}$ 是第 $i$ 项的自适应权重。

定理1表明了图对比学习损失函数的上界，最大化对比损失等同于最大化上界。这意味着更大的 $\theta _{i}$ 将匹配更小的 $(\lambda _{i}-\gamma _{i})^{2}$ 或者 $\lambda _{i}\approx \gamma _{i}$ 。同时，如果满足 $\lambda _{i}\approx \gamma _{i}$ ，这意味着这两个对比增强被认为在第 $i$ 个频率处具有不变性。因此图对比学习会促使encoder学习到两个增强视图在频域上的不变性。GAME规则主张两个增强在 $\mathcal{F}_{L}$ 上的差异要小，因此在GAME规则的指导下，图对比学习能够捕获两个增强共同的低频信息。

五、谱图对比学习（SpCo）

基于GAME规则，本文提出了一个通用的图对比学习框架SpCo，能够作为现有图对比学习方法的插件来增强其性能。SpCo能够学习一个变换 $\Delta A$ 来获得一个增强视图 $A_{\_}$ （ $\Delta A=A_{\_}-A$ ），是的 $A$ 和 $A_{\_}$ 成为最优对比对。然而，将他们应用在现有的图对比学习方法 $\Phi$ 中，该过程如下图所示。

SpCo

首先，我们划分 $\Delta A=\Delta _{A_{+}}-\Delta _{A_{-}}$ ，这里的 $\Delta _{A_{+}}$ 与 $\Delta _{A_{-}}$ 分别表示哪些边会被增加或删除。接下来阐述如何学习 $\Delta _{A_{+}}$ ， $\Delta _{A_{-}}$ 也类似。SpCo需要最大化下列损失函数来学习 $\Delta _{A_{+}}$ ：

$\mathcal{J}=\underset{Matching\; Term}{\underbrace{<\mathcal{C},\Delta _{A_{+}}>^{2}}}+\underset{Entropy\; Reg.}{\underbrace{\epsilon H(\Delta _{A_{+}})}}+\underset{Lagrange\; Constraint\; Conditions}{\underbrace{<f,\Delta _{A_{+}}1_{N}-a>+<g,\Delta _{A_{+}}^{T}1_{N}-b>}}$

这个损失函数包括三个部分：
①匹配项。 $\forall P,Q\in \mathbb{R}^{N\times N},<P,Q>=\sum _{ij}P_{ij}Q_{ij}$ ，为了最大化 $<\mathcal{C},\Delta _{A_{+}}>^{2}$ ， $\Delta _{A_{+}}$ 应该学习匹配 $\mathcal{C}$ ，也就是要尽可能地与 $\mathcal{C}$ 相似。我们定义 $\mathcal{C}=Ug(\lambda )U^{T}$ ，这里的 $U$ 和 $g(\lambda )$ 是 $A$ 的特征矩阵以及特征值上的某个函数。根据GAME规则，我们定义 $\phi _{\Delta }(\lambda )=|\phi _{A}(\lambda )-\phi _{A_{\_}}(\lambda )|$ ，我们需要对于 $\forall \lambda _{m}\in [1,2]$ 和 $\forall \lambda _{n}\in [0,1]$ 满足 $\phi _{\Delta }(\lambda _{m})> \phi _{\Delta }(\lambda _{n})$ ，因此 $\phi _{\Delta }(\lambda )$ 应该是一个单调递增函数。由于 $\mathcal{C}$ 指导 $\Delta _{A_{+}}$ 去捕获图谱的变化（ $\phi _{\Delta }(\lambda )$ ），因此很自然地我们将 $g(\lambda )$ 设置为一个单调递增函数。更进一步来讲，我们注意到上面的图6中，拉普拉斯矩阵 $\mathcal{L}$ 的图谱是单调递增的，因此符合我们的要求，所以我们简单地设置 $\mathcal{C}=\Theta \mathcal{L}$ ， $\Theta$ 是一个在训练中更新的参数。
②熵正则项。这里 $H(P)=-\sum _{ij}P_{ij}(log(P_{ij})-1)$ ， $\epsilon$ 是这一项的权重，这一正则项的目的在于增加学习到的 $\Delta _{A_{+}}$ 的不确定性，这将促使更多的边参与到优化过程中。
③拉格朗日限制条件。 $f\in \mathbb{R}^{N\times 1}$ 和 $g\in \mathbb{R}^{N\times 1}$ 是拉格朗日乘子， $a$ 和 $b$ 是两个分布，在本文中都采用节点度分布。这一项的目的在于限制 $\Delta _{A_{+}}$ 的行数和列数。

SpCo按照梯度上升的方式优化 $\mathcal{J}$ 来得到 $\Delta _{A_{+}}$ ， $\Delta _{A_{-}}$ 也类似，这个过程的算法如下（推导过程参看原文）：

算法

得到 $\Delta A$ 后按照以下方式来获取 $A_{\_}$ ：

$A_{\_}=A+\eta \cdot S*\Delta A$

上式中 $*$ 表示了两个矩阵的element-wise乘积， $\eta$ 是组合系数。为了让 $\Delta A$ 稀疏化，我们利用范围矩阵 $S$ 来限制关注的范围，例如只关注one-hop邻居的拓扑改变。

SpCo的整个流程算法如下：

算法

六、实验

节点分类

我们将基线模型中的 GCL 方法根据 loss 分为三类：BCE loss（DGI, MVGRL）、InfoNCE loss（GRACE, GCA, GraphCL）以及 CCA loss（CCA-SSG）。从这三类方法中分别选出一个（DGI, GRACE, CCA-SSG）与 SpCo 相结合，以此来验证插件 SpCo 的有效性和通用性，结果如下表所示。

节点分类

可视化

下图可视化了应用SpCo 的三种方法后的图谱。实验说明应用SpCo后两个视图成了最优对比对。

可视化

$\mathcal{C}$ 的其他选择

$\mathcal{C}$ 除了 $\Theta \mathcal{L}$ 还可以有其他的选择。

其他选择

超参数敏感性

测试了参数 $\epsilon$ 的敏感性。

超参数敏感性

从图谱视角再谈图对比学习

一、概述

二、预备知识

三、图增强的影响：实验研究

四、GAME规则的分析

五、谱图对比学习（SpCo）

六、实验

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

人工智能