Metadata

摘要

图变换器已被证明是一种有效的图学习方法，因为它采用了注意力机制，能够从图的复杂拓扑和特征信息中捕获表达性表示。传统图变换器对每对节点执行密集注意力（或全局注意力）来学习节点表示向量，导致二次计算成本对于大规模图数据来说是无法负担的。因此，图变换器的小批量训练是一个有前途的方向，但每个小批量中的有限样本无法支持有效的密集注意力来编码信息丰富的表示。
面对这一瓶颈，(1)我们首先为每个节点分配一个通过个性化PageRank(PPR)采样的token列表，然后仅在这个列表上应用标准多头自注意力来计算其节点表示。这种PPR tokenization方法将模型训练与复杂的图拓扑信息解耦，并使繁重的特征工程离线且独立，从而通过批量加载每个节点的token列表，使得图变换器的小批量训练成为可能。我们进一步证明这种PPR tokenization可以作为具有固定多项式滤波器和跳跃知识的图卷积网络使用。然而，仅使用个性化PageRank可能会限制token列表携带的信息，无法支持模型训练的不同图归纳偏置。
为此，(2)我们通过基于结构和内容的超节点引入多种类型的虚拟连接来重连图，使PPR tokenization能够将局部和全局上下文、长程交互和异质性信息编码到每个节点的token列表中，并形式化我们的基于虚拟连接排序的图变换器（VCR-Graphormer）。总体而言，与先前工作的O(n³)复杂度相比，VCR-Graphormer的图tokenization复杂度为O(m+klogk)。代码已提供。

研究问题

1. 计算复杂度问题

传统的图Transformer需要对每对节点执行密集注意力（或全局注意力）来学习节点表示向量，这种密集注意力机制能够从图的复杂拓扑和特征信息中捕获有表现力的表示。然而，这种计算方式导致了二次方的计算复杂度(O(n²))，对于大规模图数据来说是不可承受的。
尽管许多研究工作已经开发出各种图Transformer架构，如GT (Dwivedi and Bresson, 2020)、Gophormer (Zhao et al., 2021)、Graphormer (Ying et al., 2021)等，但它们大多需要处理所有节点对之间的注意力，这使得它们难以扩展到大规模图数据。

2. 小批量训练的局限性

小批量训练为图Transformer提供了一个有前景的方向，因为每次只处理图中的一部分节点。然而，每个小批次中的少量节点样本无法支持有效的密集注意力来编码充分的信息，特别是对于具有复杂拓扑和特征信息的大规模图数据。
现有的小批量图Transformer方法如NAGphormer (Chen et al., 2023)，虽然采用了自注意力机制，但仍存在以下问题：

  • 跳聚合方法可能无法很好地处理全局、长程交互和异构信息
  • 依赖于耗时的特征分解来进行位置编码
  • 计算复杂度仍然较高(O(n³))，限制了其在真正大规模图上的应用

解决方案需求

因此，亟需一种能够：

  1. 将模型训练与复杂的图拓扑信息解耦
  2. 允许离线和独立的特征工程
  3. 通过小批量方式有效训练
  4. 在保持高效的同时捕获足够的图信息
  5. 支持不同的图归纳偏置
    这些需求推动了VCR-Graphormer的发展，它通过个性化PageRank令牌化和虚拟连接机制，实现了高效的小批量图Transformer训练，同时能够编码局部和全局上下文、长程交互和异构信息。

方法

模型核心思想

VCR-Graphormer的核心思想是通过个性化PageRank(PPR)进行图分词化(tokenization)，并通过引入虚拟连接(virtual connections)增强令牌列表的信息表达能力。这一方法使模型能够在小批次训练中有效捕获图的局部和全局信息。

主要组件与数学公式

1. PPR分词化

首先使用个性化PageRank为每个目标节点u生成令牌列表Tu。个性化PageRank定义为（即PPR值）：

其中：

  • 是转移矩阵（可计算为或）（为邻接矩阵，为度矩阵）
  • 是目标节点（即当前节点）对应的one-hot随机向量
  • 是随机游走的平稳分布（个性化PageRank向量）
  • 是阻尼常数因子（通常设为0.85）

最终的PPR值通过迭代直到收敛或波动小于某个常量。
令牌列表有两种数学表示形式：
聚集形式:

离散形式:

其中是特征矩阵，表示第步随机游走。

2. 良好令牌列表的四项原则

作者提出好的令牌列表应满足：

  1. 反映输入图的局部和全局拓扑结构
  2. 支持长距离交互
  3. 处理异质性(heterophily)信息
  4. 实现高效计算

3. 虚拟连接与VCR-Graphormer

为满足上述原则，VCR-Graphormer引入了虚拟连接概念，通过重连图将全局信息编码到令牌列表中。目标节点的令牌列表包含四个组件：

其中：

  • 第一项：目标节点自身特征
  • 第二项：局部拓扑信息，基于步随机游走，较近邻居权重更高
  • 第三项：结构感知的虚拟连接信息，
  • 第四项：内容感知的虚拟连接信息，
    注意：一个对应的是一个节点

虚拟连接实现方法

  1. 结构感知虚拟连接：如图1(a)
    • 将图分区为个簇（使用METIS分区）
    • 为每个簇分配超级节点，连接簇内所有成员
    • 重构邻接矩阵：
    • 计算新的转移矩阵和个性化PageRank向量
  2. 内容感知虚拟连接：如图1(b)
    • 为每种标签分配超级节点，连接所有具相同标签的节点
    • 重构邻接矩阵：
    • 计算转移矩阵和个性化PageRank向量

模型架构

将令牌列表堆叠成矩阵作为transformer输入：

对于第t层：

其中，LN是层归一化，FFN是前馈神经网络，MHA是多头自注意力机制。最终通过读出函数（如均值、求和）获得节点表示。

计算复杂度

VCR-Graphormer的图分词化复杂度为，其中是图中的边数，是每个节点选择的邻居数（远小于或）。这比传统图变换器的以及NAGphormer的复杂度要低得多。

实验结果

作者在13个公开数据集上进行了实验，包括：

  • 9个节点分类基准数据集（如PubMed、CoraFull等）
  • 3个小型异质图数据集（如Squirrel、Actor等）
  • 1个大规模异质图数据集（arXiv-Year）
    实验结果表明，VCR-Graphormer在各种规模的数据集上取得了与基线模型相当或更好的性能，特别是在处理异质性图时表现优异。此外，消融研究验证了结构感知和内容感知邻居对模型的贡献。
    总之，VCR-Graphormer通过结合PPR分词化和虚拟连接技术，有效地解决了图变换器在大规模图上的训练效率问题，同时保持了模型对图全局信息捕捉的能力。

附录

1.VCR-Graphormer中Tu维度计算的推导

基本符号说明

  • ：节点特征矩阵，包含d$$维特征
  • ：随机游走的步数
  • $$k$̄$：从结构感知虚拟连接中采样的邻居数量
  • $$k$̂$：从内容感知虚拟连接中采样的邻居数量

四个组件的维度推导

组件1：

  • ：节点的特征向量
  • ：将标量1连接到特征向量
  • 维度：，即

组件2：

  • ：节点在第步随机游走后的特征向量
  • ：一个标量权重
  • 维度：，即
  • 注意：对于，此组件共有个向量

组件3：

  • ：节点的特征向量
  • ：u节点在结构感知虚拟连接下节点的PPR值
  • 维度：，即
  • 注意：对于，此组件共有个向量

组件4：

  • ：节点的特征向量
  • ：节点在内容感知虚拟连接下节点的PPR值
  • 维度：，即
  • 注意：对于，此组件共有个向量

Tu的最终维度

将这四个组件的向量堆叠为矩阵：

总行数 =
每行维数 =
因此，Tu的最终维度为：，表示为：

这个推导表明，Tu矩阵的维度取决于节点特征维度d、随机游走步数L和两种虚拟连接采样的邻居数量和。

References

  1. NAGphormer:A Tokenized Graph Transformer For Node Classification In Large Graphs
  2. Page Rank Algorithm