1. 论文基本信息

1.1. 标题

NAGphormer: 大型图节点分类的标记化图 Transformer (NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs)

1.2. 作者

Jinsong Chen, Kaiyuan Gao, Gaichao Li, Kun He 等。 作者主要来自华中科技大学 (Huazhong University of Science and Technology) 的人工智能与计算机科学与技术学院、以及霍普克罗夫特计算科学中心 (Hopcroft Center on Computing Science)。

1.3. 发表期刊/会议

该论文作为预印本 (preprint) 发表在 arXiv 上。虽然论文中引用了NeurIPS等会议，但本文的发布信息显示为 arXiv。在相关领域，Graph Transformer 和图神经网络 (GNNs) 是当前热门的研究方向，因此该工作具有较高的时效性和潜在影响力。

1.4. 发表年份

2022年

1.5. 摘要

图 Transformer (graph Transformer) 作为一种新型架构，在各种图挖掘任务中展现出卓越的性能。在本工作中，作者观察到现有的图 Transformer 将节点视为独立的词元 (token)，并构建由所有节点词元组成的单个长序列来训练 Transformer 模型，这导致自注意力 (self-attention) 计算的二次复杂度 (quadratic complexity) 使得其难以扩展到大型图。为此，作者提出了一种邻域聚合图 Transformer (Neighborhood Aggregation Graph Transformer, NAGphormer)。NAGphormer 将每个节点视为一个序列 (sequence)，该序列包含由作者提出的 Hop2Token 模块构建的一系列词元。对于每个节点，Hop2Token 将来自不同跳数 (hops) 的邻域特征聚合成不同的表示，从而生成一个词元向量序列作为输入。通过这种方式，NAGphormer 可以以小批量 (mini-batch) 方式进行训练，因此能够扩展到大型图。此外，作者从数学上证明，与一类先进的图神经网络（即解耦图卷积网络 (decoupled Graph Convolutional Network)）相比，NAGphormer 能够从多跳邻域 (multi-hop neighborhoods) 中学习到更具信息量的节点表示 (node representations)。在从小到大的基准数据集上进行的广泛实验表明，NAGphormer 始终优于现有图 Transformer 和主流 GNN。

1.6. 原文链接

https://arxiv.org/abs/2206.04910 PDF 链接: https://arxiv.org/pdf/2206.04910v4.pdf 发布状态: 预印本 (preprint)

2. 整体概括

2.1. 研究背景与动机

2.1.1. 论文试图解决的核心问题

论文主要关注的核心问题是如何让图 Transformer 模型能够有效且高效地应用于大型图 (large graphs) 上的节点分类 (node classification) 任务。

2.1.2. 为什么这个问题在当前领域是重要的？现有研究存在哪些具体的挑战或空白？

• 图结构数据的复杂性: 图作为一种强大的数据结构，广泛用于表示实体及其关系，但其复杂特性（如属性特征和拓扑特征）使得图挖掘任务极具挑战性。
• GNN 的局限性:
  • 图神经网络 (Graph Neural Networks, GNNs) 凭借其消息传递 (message passing) 机制在图挖掘任务中表现出色。
  • 然而，基于消息传递的 GNN 存在固有的局限性，如随着模型深度增加而出现的过平滑 (over-smoothing) 和过挤压 (over-squashing) 问题，这限制了它们学习深层结构信息的能力。
  • 大多数 GNN 在训练时需要完整的邻接矩阵 (adjacency matrix)，这使得它们难以扩展到包含数百万节点和边的超大型图。虽然有采样 (sampling) 和近似传播 (approximation propagation) 等可扩展 GNN 的策略，但这通常会带来信息损失。
• 传统 Transformer 的局限性:
  • Transformer 在欧几里得 (Euclidean) 结构数据（如自然语言和图像）上表现卓越，但图数据是非欧几里得的，具有复杂的结构拓扑和属性特征，无法直接编码为 Transformer 的词元。
  • 现有的图 Transformer 通常将所有节点视为独立的词元，构建一个包含所有节点词元的单一长序列作为输入。这种方法导致自注意力计算的复杂度与节点数量的平方成正比 ($O(N^2)$)，使得它们难以扩展到大型图。
  • 此外，针对 GNN 的可扩展策略（如节点采样和近似传播）不适用于图 Transformer，因为后者捕获的是所有节点对的全局注意力 (global attention)，而非消息传递机制。

2.1.3. 这篇论文的切入点或创新思路

本文的创新点在于改变了图 Transformer 的“词元化”方式。

• 传统图 Transformer: 将图中的每个节点作为一个独立的词元。

• NAGphormer 的思路: 将图中的每个节点视为一个序列，而这个序列由该节点不同跳数邻域聚合而成的词元组成。

  这种新颖的“词元化”策略带来了两个关键优势：

1. 可扩展性: 每个节点的输入变成一个固定长度的序列（由跳数 $K+1$ 决定），而不是整个图的节点数。这样一来，Transformer 可以在每个节点级别进行处理，从而能够以小批量 (mini-batch) 方式训练，极大地提高了模型处理大型图的能力。
2. 多跳邻域信息整合: 通过将不同跳数的邻域信息转化为不同的词元，NAGphormer 能够更好地捕获节点的多跳邻域语义关联和结构信息，并利用 Transformer 的自注意力机制学习这些词元之间的关系。

2.2. 核心贡献/主要发现

论文的主要贡献包括：

• 提出了 Hop2Token 模块: 一种新颖的邻域聚合方法，将每个跳数的邻域特征聚合成一个节点表示，从而为每个节点生成一个包含其不同跳数邻域信息的词元向量序列。这使得复杂的图数据中的每个节点可以被视为一个词元序列，类似于自然语言处理 (NLP) 和计算机视觉 (CV) 中的处理方式。
• 提出了 NAGphormer 模型: 一个用于节点分类任务的新型图 Transformer 模型。通过 Hop2Token 的输出，NAGphormer 可以以小批量方式训练，从而能够处理大型图。
• 开发了基于注意力的读出函数 (attention-based readout function): 该函数能够自适应地学习不同跳数邻域的重要性，进一步提升模型性能。
• 理论分析: 从自注意力机制的角度，数学上证明了所提出的 NAGphormer 与先进的解耦 GCN 相比，能够从多跳邻域中学习到更具表达能力的节点表示。
• 广泛实验验证: 在从小到大的基准数据集上进行的广泛实验表明，NAGphormer 始终优于现有图 Transformer 和主流 GNN。

3. 预备知识与相关工作

3.1. 基础概念

3.1.1. 图神经网络 (Graph Neural Networks, GNNs)

GNN 是一类专门处理图结构数据的深度学习模型。它们通过消息传递 (message passing) 机制工作，即每个节点聚合其邻居节点的信息来更新自己的表示。

• 消息传递机制 (Message Passing Mechanism):

  • 聚合 (Aggregation): 节点从其邻居收集信息。这通常通过对邻居特征进行求和、求平均或最大池化 (max pooling) 等操作实现。
  • 更新 (Update): 节点结合其自身当前状态和聚合到的邻居信息来更新其新的表示。
  • 这个过程通常迭代多层，使得节点能够学习到多跳邻域的信息。

• 图卷积网络 (Graph Convolutional Network, GCN): GCN 是一种典型的 GNN 模型，它将卷积操作推广到图数据上。GCN 层可以表示为： $$\mathbf{H}^{(l+1)} = \sigma(\hat{\mathbf{A}}\mathbf{H}^{(l)}\mathbf{W}^{(l)})$$ 其中：

  • $\mathbf{H}^{(l)} \in \mathbb{R}^{n \times d^{(l)}}$ 是第 $l$ 层的节点表示矩阵，其中 $n$ 是节点数，$d^{(l)}$ 是特征维度。
  • $\mathbf{W}^{(l)} \in \mathbb{R}^{d^{(l)} \times d^{(l+1)}}$ 是第 $l$ 层的可学习参数矩阵。
  • $\hat{\mathbf{A}}$ 是归一化 (normalized) 的邻接矩阵，通常是 $\tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2}$，其中 $\tilde{\mathbf{A}}$ 是带有自环 (self-loops) 的邻接矩阵，$\tilde{\mathbf{D}}$ 是对应的度矩阵 (degree matrix)。自环保证了节点在聚合邻居信息时也考虑到自身。
  • $\sigma(\cdot)$ 是非线性激活函数，如 ReLU。 GCN 的特点是将邻域聚合 (neighborhood aggregation) 和特征转换 (feature transformation) 耦合在同一层中。

• 过平滑 (Over-smoothing): GNN 模型的固有局限性。当 GNN 层数过多时，节点会不断聚合其越来越远的邻居信息，导致所有节点的表示趋于相似，区分度降低，最终失去图结构中的局部特性。

• 过挤压 (Over-squashing): GNN 模型的另一个局限性。当图的拓扑结构复杂或路径过长时，消息在传递过程中经过瓶颈节点 (bottleneck nodes) 时，信息量会急剧减少，导致远距离信息无法有效传播到目标节点。

3.1.2. 解耦图卷积网络 (Decoupled Graph Convolutional Network, Decoupled GCN)

为了解决 GCN 中邻域聚合和特征转换耦合导致的过平滑问题，解耦 GCN 将这两个操作分离。其一般形式如下： $$\mathbf{Z} = \sum_{k=0}^K \beta_k \mathbf{H}^{(k)}, \quad \mathbf{H}^{(k)} = \hat{\mathbf{A}}\mathbf{H}^{(k-1)}, \quad \mathbf{H}^{(0)} = f_{\boldsymbol{\theta}}(\mathbf{X})$$ 其中：

• $\mathbf{Z}$ 是最终的节点表示。
• $\mathbf{H}^{(k)}$ 是传播步骤 $k$ 时的隐藏表示。
• $\beta_k$ 是传播步骤 $k$ 的聚合系数。
• $\hat{\mathbf{A}}$ 是归一化邻接矩阵。
• $f_{\boldsymbol{\theta}}$ 是一个神经网络模块（通常是多层感知机 (MLP)）用于初始特征转换。
• $\mathbf{X}$ 是原始属性特征矩阵。 这种设计提高了计算效率，并能捕获更深的结构信息，因为它移除了 GNN 层间的非线性激活函数。

3.1.3. Transformer

Transformer 是一种基于注意力机制的深度学习架构，最初用于自然语言处理。

• 自注意力机制 (Self-attention Mechanism): Transformer 的核心组件，它允许模型在处理序列数据时，评估序列中不同位置的元素之间的相关性，从而为每个元素生成一个“加权和”表示。 对于输入 $\mathbf{H} \in \mathbb{R}^{n \times d}$（$n$ 是词元数，$d$ 是隐藏维度），自注意力模块首先将其投影到三个子空间：查询 (Query, Q)、键 (Key, K) 和值 (Value, V)： $$\mathbf{Q} = \mathbf{H}\mathbf{W}^Q, \quad \mathbf{K} = \mathbf{H}\mathbf{W}^K, \quad \mathbf{V} = \mathbf{H}\mathbf{W}^V$$ 其中 $\mathbf{W}^Q \in \mathbb{R}^{d \times d_K}$、$\mathbf{W}^K \in \mathbb{R}^{d \times d_K}$ 和 $\mathbf{W}^V \in \mathbb{R}^{d \times d_V}$ 是可学习的投影矩阵。$d_K$ 和 $d_V$ 分别是键/查询和值的维度。 然后，注意力矩阵通过计算 $\mathbf{Q}$ 和 $\mathbf{K}$ 的点积得到，并通过 softmax 进行归一化，再与 $\mathbf{V}$ 相乘得到输出 $\mathbf{H}'$: $$\mathbf{H}' = \mathrm{softmax}\left(\frac{\mathbf{Q}\mathbf{K}^\top}{\sqrt{d_K}}\right)\mathbf{V}$$ 其中，$\mathrm{softmax}\left(\frac{\mathbf{Q}\mathbf{K}^\top}{\sqrt{d_K}}\right)$ 是注意力矩阵，它捕获了序列中输入词元对之间的相似性。$\sqrt{d_K}$ 用于缩放点积，防止梯度过小。

• Transformer 编码器 (Transformer Encoder): 由多个 Transformer 层组成，每层包含一个多头自注意力 (Multi-Head Self-Attention, MSA) 模块和一个位置前馈网络 (Position-wise Feed-Forward Network, FFN)。层归一化 (LayerNorm, LN) 和残差连接 (residual connection) 也是其重要组成部分。

3.2. 前人工作

3.2.1. 图神经网络 (GNNs)

GNNs 已成为图结构数据建模的强大技术，例如 GCN (Kipf & Welling, 2017) 和 GAT (Velikovi et al., 2018)。它们通过不同的聚合策略学习邻居特征，在各种图挖掘任务中表现出竞争性。然而，这些典型的 GNNs 采用耦合设计，将聚合模块和特征转换模块绑定在每个 GNN 层中，导致在层数增加时出现过平滑和过挤压问题。

3.2.2. 可扩展 GNN (Scalable GNNs)

为了将 GNN 应用于大规模图，主要有两类策略：

1. 节点采样策略 (Node Sampling Strategy): 例如 GraphSAGE (Hamilton et al., 2017)、Cluster-GCN (Chiang et al., 2019)、GraphSAINT (Zeng et al., 2020) 等，通过从整个图中采样部分节点来减少模型训练的节点规模。
2. 近似传播策略 (Approximation Propagation): 例如 PPRGo (Bojchevski et al., 2020)、GRAND+ (Feng et al., 2022) 等，通过各种近似方法加速传播操作，如近似 PageRank。 尽管这些方法降低了训练成本，但通常会引入信息损失，并限制其在大型网络上的性能。

3.2.3. 图 Transformer (Graph Transformers)

近年来，Transformer 架构也被推广到图数据。主要有三种策略将图结构信息整合到 Transformer 中：

1. 从图结构中提取位置嵌入 (Positional Embedding): 例如利用 Laplacian 矩阵的特征向量 (Dwivedi & Bresson, 2020; Kreuzer et al., 2021) 或度相关特征向量 (Ying et al., 2021) 来捕获节点结构信息。
2. 结合 GNN 和 Transformer: 将 GNN 作为辅助模块来提取节点的固定局部结构信息，再将其输入到 Transformer 中学习长距离关系 (Jain et al., 2021; Rong et al., 2020)。也有混合层设计，包含 GNN 层和自注意力层，以捕获局部和全局信息 (Rampásek et al., 2022)。
3. 将图结构偏置集成到自注意力矩阵中 (Graph Structural Bias in Self-attention Matrix): 将各种图结构特征转换为注意力偏置，并集成到自注意力矩阵中。例如，基于最短路径距离建模节点对的结构相似性 (Ying et al., 2021)，或通过考虑不同邻域中节点对的关系来提出邻近性增强注意力矩阵 (Zhao et al., 2021)。

3.3. 技术演进

图表示学习领域从传统的图特征工程（如 PageRank、节点度等）发展到早期的谱图理论方法，再到以 GNNs 为代表的基于消息传递的深度学习方法。GNNs 解决了传统方法在处理复杂图结构上的局限性，但又面临过平滑、过挤压和大规模图扩展性的挑战。

与此同时，Transformer 在 NLP 和 CV 领域取得了巨大成功，促使研究人员探索如何将其强大的序列建模能力引入图领域。早期的图 Transformer 主要关注如何将图结构信息编码成适合 Transformer 输入的形式，例如位置编码或注意力偏置。然而，这些方法大多继承了 Transformer 在序列长度上的二次复杂度问题，导致在大型图上训练困难。

NAGphormer 正是处于这一技术演进的交叉点，旨在解决现有图 Transformer 在大规模图上的扩展性问题，同时保留 Transformer 强大的建模能力和对多跳邻域的有效学习。

3.4. 差异化分析

• 与传统 GNN 的区别:

  • NAGphormer 利用 Transformer 的自注意力机制来学习不同跳数邻域的语义相关性，这在大多数 GNN 中被忽略。
  • 虽然解耦 GCN 也聚合多跳信息，但其聚合权重通常是固定的。NAGphormer 通过自注意力机制和基于注意力的读出函数，能够自适应地学习节点与其不同跳数邻域之间的重要性。
  • NAGphormer 引入的 Transformer 结构使其能够更好地捕获长距离依赖关系，同时缓解 GNNs 的过平滑和过挤压问题。

• 与现有图 Transformer 的区别:

  • 核心差异：词元化策略。 现有图 Transformer 将所有节点作为独立词元构成一个长序列，导致自注意力计算复杂度为 $O(N^2)$（$N$ 为节点数）。NAGphormer 则将每个节点转换为一个由其多跳邻域聚合而成的固定长度的词元序列（长度为 $K+1$）。
  • 可扩展性： 这种节点级的词元化使得 NAGphormer 可以进行小批量训练，从而能够处理大规模图，而大多数现有图 Transformer（如 Graphormer, SAN, GraphGPS 在某些情况下）在大型图上会遇到内存溢出 (Out-Of-Memory, OOM) 问题。
  • 邻域信息编码： NAGphormer 的 Hop2Token 模块显式地编码了不同跳数邻域的信息，并将其作为独立的词元输入 Transformer，使得模型能够细致地学习多跳邻域的语义。

4. 方法论

4.1. 方法原理

NAGphormer 的核心思想是将每个节点视为一个由其多跳邻域信息构成的词元序列，而不是将整个图的所有节点作为单一长序列的词元。这样，图 Transformer 的自注意力机制可以在每个节点的局部邻域序列上操作，从而避免了全局节点间注意力计算带来的二次复杂度问题，实现了小批量训练和对大型图的可扩展性。同时，通过专门设计的 Hop2Token 模块，模型能够有效捕获节点的多跳邻域结构信息，并利用 Transformer 的强大建模能力学习这些多跳邻域之间的关系。

4.2. 核心方法详解

NAGphormer 的模型框架如原文 Figure 1 所示。主要包括以下几个步骤：

1. 结构编码 (Structural Encoding): 结合原始节点属性特征和 Laplacian 特征向量，形成结构感知特征。
2. Hop2Token 模块: 使用 Hop2Token 模块聚合不同跳数邻域的特征，为每个节点生成一个词元序列。
3. Transformer 编码器 (Transformer Encoder): 将生成的词元序列输入到 Transformer 编码器中，学习节点的高级表示。
4. 基于注意力的读出函数 (Attention-based Readout Function): 将 Transformer 的输出聚合为最终的节点表示。
5. MLP 分类器: 通过一个多层感知机 (MLP) 进行标签预测。

4.2.1. 结构编码 (Structural Encoding)

为了同时保留节点的属性信息和结构信息，NAGphormer 首先将原始的节点属性特征 $\mathbf{X} \in \mathbb{R}^{n \times d}$ 与 Laplacian 矩阵的特征向量 (eigenvectors of Laplacian matrix) 结合。具体来说，选择对应于 $s$ 个最小非平凡特征值 (smallest non-trivial eigenvalues) 的特征向量来构建结构矩阵 $\mathbf{U} \in \mathbb{R}^{n \times s}$。然后，通过拼接操作将两者融合： $$\mathbf{X}' = \mathbf{X} \| \mathbf{U}$$ 其中：

• $\mathbf{X} \in \mathbb{R}^{n \times d}$ 是原始的节点属性特征矩阵，$n$ 是节点数，$d$ 是特征维度。
• $\mathbf{U} \in \mathbb{R}^{n \times s}$ 是由 Laplacian 特征向量构成的结构矩阵，$s$ 是选择的特征向量数量。
• $\|$ 表示拼接 (concatenation) 操作。
• $\mathbf{X}' \in \mathbb{R}^{n \times (d+s)}$ 是融合后的结构感知特征矩阵，作为 Hop2Token 模块的输入。

4.2.2. Hop2Token 模块

Hop2Token 模块旨在聚合节点不同跳数邻域的特征，并将其转化为一个序列。 对于节点 $v$，其 $k$-跳邻域 (k-hop neighborhood) 定义为 $\mathcal{N}^k(v) = \{u \in V | d(v,u) \leq k\}$，其中 d(v,u) 是 $v$ 和 $u$ 之间的最短路径距离。特别地，$\mathcal{N}^{\bar{0}}(v) \dot{=} \{v\}$ 表示 0-跳邻域即节点本身。

Hop2Token 通过聚合操作 $\phi$ 将 $k$-跳邻域 $\mathcal{N}^k(v)$ 转换为一个邻域嵌入 $\mathbf{x}_v^k$: $$\mathbf{x}_v^k = \phi(\mathcal{N}^k(v))$$ 其中，$\mathbf{x}_v^k$ 是节点 $v$ 的 $k$-跳邻域表示。 通过为节点 $v$ 计算 $K+1$ 个跳数（从 0 到 $K$）的邻域嵌入，可以构建一个序列 $\mathcal{S}_v = (\mathbf{x}_v^0, \mathbf{x}_v^1, ..., \mathbf{x}_v^K)$ 来表示其邻域信息。

在实际实现中，Hop2Token 采用类似于解耦 GCN 的传播过程来获取 $k$-跳邻域信息。给定归一化邻接矩阵 $\hat{\mathbf{A}}$ (也称为转移矩阵 (transition matrix)) 和融合特征矩阵 $\mathbf{X}'$（上一步得到的），通过连续乘以 $\hat{\mathbf{A}}$ 来传播信息： $$\mathbf{X}_k = \hat{\mathbf{A}}^k \mathbf{X}'$$ 其中：

• $\mathbf{X}_k \in \mathbb{R}^{n \times (d+s)}$ 表示所有节点的 $k$-跳邻域特征矩阵。
• $\hat{\mathbf{A}}^k$ 表示归一化邻接矩阵 $\hat{\mathbf{A}}$ 的 $k$ 次幂。

算法 1: Hop2Token 算法

输入: 归一化邻接矩阵 $\hat{\mathbf{A}}$；特征矩阵 $\mathbf{X}'$；传播步数 $K$ 输出: 所有节点的序列 $\mathbf{X}_G$

1. 初始化 $\mathbf{X}_G$ 为一个 $n \times (K+1) \times (d+s)$ 的张量 (tensor)。

2. 对于 $k$ 从 0 到 $K$ 执行:

3.  对于 $i$ 从 `0` 到 `n-1` (节点索引) 执行:
   

4.      $\mathbf{X}_G[i, k] = \mathbf{X}'[i]$ (这一步实际上是保存当前传播步数下的节点特征，对应于 $\mathbf{X}_k$ 的节点行)
   

5.  $\mathbf{X}' = \hat{\mathbf{A}} \mathbf{X}'$ (更新 $\mathbf{X}'$ 为下一跳的聚合特征)
   

6. 结束循环

7. 返回 $\mathbf{X}_G$

   说明: 算法中的第 4 行可能存在歧义，原文的意图应是保存当前传播步骤 $k$ 得到的特征，即 $\mathbf{X}_G[:, k, :] = \mathbf{X}'$，其中 $\mathbf{X}'$ 在每次循环中被更新为 $\hat{\mathbf{A}} \mathbf{X}'$。因此，在 $k=0$ 时，$\mathbf{X}_G[:, 0, :]$ 存储的是原始特征 $\mathbf{X}'$；在 $k=1$ 时，$\mathbf{X}_G[:, 1, :]$ 存储的是 $\hat{\mathbf{A}} \mathbf{X}'$；以此类推，$\mathbf{X}_G[:, k, :]$ 存储的是 $\hat{\mathbf{A}}^k \mathbf{X}'$。这样，对于每个节点 $v$，其第 $k$ 维特征 $\mathbf{x}_v^k$ 就对应于 $\mathbf{X}_G[v, k, :]$。 Hop2Token 的优势在于它是非参数化的，可以在模型训练前离线 (offline) 执行，并且其输出支持小批量训练，从而使模型能够处理任意大小的图。

4.2.3. 词元序列投影与 Transformer 编码器

经过 Hop2Token 模块，对于每个节点 $v$，我们得到一个由 $K+1$ 个词元组成的序列 $\mathcal{S}_v = (\mathbf{x}_v^0, \mathbf{x}_v^1, ..., \mathbf{x}_v^K)$，其中每个词元 $\mathbf{x}_v^k \in \mathbb{R}^{d'}$ ($d'$ 是融合特征维度 $d+s$)。 这些词元序列首先通过一个可学习的线性投影 $\mathbf{E} \in \mathbb{R}^{d' \times d_m}$ 映射到 Transformer 的隐藏维度 $d_m$: $$\mathbf{Z}_v^{(0)} = [\mathbf{x}_v^0 \mathbf{E} ; \mathbf{x}_v^1 \mathbf{E} ; \dots ; \mathbf{x}_v^K \mathbf{E}]$$ 其中：

• $\mathbf{Z}_v^{(0)} \in \mathbb{R}^{(K+1) \times d_m}$ 是节点 $v$ 的初始词元嵌入序列，作为 Transformer 编码器的输入。

• $\mathbf{E}$ 是线性投影矩阵。

  然后，将 $\mathbf{Z}_v^{(0)}$ 输入到 Transformer 编码器。Transformer 编码器的构建块包括多头自注意力 (Multi-Head Self-Attention, MSA) 和位置前馈网络 (Feed-Forward Network, FFN)。NAGphormer 遵循标准的 Transformer 编码器实现，并在每个块之前应用层归一化 (LayerNorm, LN)。FFN 包含两个线性层和一个 GELU 非线性激活函数： $$\begin{align*} \mathbf{Z}_v^{\prime(\ell)} &= \operatorname{MSA}\left(\operatorname{LN}\left(\mathbf{Z}_v^{(\ell-1)}\right)\right) + \mathbf{Z}_v^{(\ell-1)} \\ \mathbf{Z}_v^{(\ell)} &= \operatorname{FFN}\left(\operatorname{LN}\left(\mathbf{Z}_v^{\prime(\ell)}\right)\right) + \mathbf{Z}_v^{\prime(\ell)} \end{align*}$$ 其中：

• $\ell = 1, \ldots, L$ 表示 Transformer 的第 $\ell$ 层。

• $\mathbf{Z}_v^{(\ell-1)}$ 是前一层的输出。

• $\operatorname{MSA}(\cdot)$ 是多头自注意力模块。

• $\operatorname{LN}(\cdot)$ 是层归一化。

• $\operatorname{FFN}(\cdot)$ 是前馈网络。

• 残差连接 (+) 确保了信息流的顺畅，避免了梯度消失。

  经过 $L$ 层 Transformer 编码器后，我们得到最终的词元序列 $\mathbf{Z}_v^{(L)} \in \mathbb{R}^{(K+1) \times d_m}$。

4.2.4. 基于注意力的读出函数 (Attention-based Readout Function)

Transformer 编码器的输出 $\mathbf{Z}_v^{(L)}$ 包含了节点 $v$ 所有邻域的嵌入。为了将其聚合成一个最终的节点表示，NAGphormer 采用了一种基于注意力的读出函数。 对于节点 $v$ 的输出矩阵 $\mathbf{Z} \in \mathbb{R}^{(K+1) \times d_m}$ (为简化符号，这里使用 $\mathbf{Z}$ 代替 $\mathbf{Z}_v^{(L)}$)，其中 $\mathbf{Z}_0$ 是节点自身的词元表示，$\mathbf{Z}_k$ 是其 $k$-跳邻域的词元表示。 该读出函数通过计算 0-跳邻域（即节点本身 $\mathbf{Z}_0$）与每个其他 $k$-跳邻域 $\mathbf{Z}_k$ 之间的注意力系数来学习不同跳数邻域的重要性： $$\alpha_k = \frac{\exp((\mathbf{Z}_0 \| \mathbf{Z}_k) \mathbf{W}_a^\top)}{\sum_{i=1}^K \exp((\mathbf{Z}_0 \| \mathbf{Z}_i) \mathbf{W}_a^\top)}$$ 其中：

• $\alpha_k$ 是第 $k$ 跳邻域的归一化注意力系数。
• $\mathbf{Z}_0 \| \mathbf{Z}_k$ 表示将 0-跳表示和 $k$-跳表示进行拼接。
• $\mathbf{W}_a \in \mathbb{R}^{1 \times 2d_m}$ 是可学习的投影向量，用于计算注意力得分。
• $i = 1, \ldots, K$ 表示对除 0-跳以外的所有跳数进行求和归一化。 最终的节点表示 $\mathbf{Z}_{out}$ 通过将 0-跳表示与加权聚合的 1 到 $K$ 跳邻域表示相加得到： $$\mathbf{Z}_{out} = \mathbf{Z}_0 + \sum_{k=1}^K \alpha_k \mathbf{Z}_k$$ 其中：
• $\mathbf{Z}_{out}$ 是节点 $v$ 的最终表示，用于后续的分类任务。
• 这种加权聚合方式考虑了每个邻域与节点自身的相关性，使得模型能够自适应地学习更具表达力的节点表示。

4.2.5. 理论分析 (Fact 1 证明)

NAGphormer 在理论上与解耦 GCN 进行了比较。作者提出了一个事实 (Fact 1)，并给出了详细证明，表明解耦 GCN 可以被视为在 Hop2Token 模块的输出上应用了一个具有固定注意力矩阵的自注意力机制。

Fact 1: 从 Hop2Token 输出的节点表示的角度来看，解耦 GCN 可以被视为应用了一个具有固定注意力矩阵 $\mathbf{S} \in \mathbb{R}^{(K+1) \times (K+1)}$ 的自注意力机制，其中 $\mathbf{S}_{K,k} = \beta_k$ 对于 $k \in \{0, ..., K\}$。

证明: 首先，Hop2Token 和解耦 GCN 都使用相同的传播过程来获取不同跳数邻域的信息。为了简洁，我们用 $\mathbf{H}_{i}^{(k)} \in \mathbb{R}^{1 \times d}$ 表示节点 $i$ 在传播步骤 $k$ 时的邻域信息。

对于任意节点 $i$，根据公式 (2) 解耦 GCN 学习到的输出表示 $\mathbf{Z}_i \in \mathbb{R}^{1 \times d}$ 的每个元素 $\mathbf{Z}_{i,m}$ （其中 $m \in \{1, ..., d\}$）计算如下： $$\mathbf{Z}_{i,m} = \sum_{k=0}^K \beta_k \mathbf{H}_{i,m}^{(k)}$$ 其中，$\beta_k$ 是聚合权重，$\mathbf{H}_{i,m}^{(k)}$ 是节点 $i$ 在传播步骤 $k$ 时，其 $m$ 维特征。

另一方面，Hop2Token 为节点 $i$ 生成的矩阵形式的输出 $\mathbf{X}_i \in \mathbb{R}^{(K+1) \times d}$ 表示为： $$\mathbf{X}_i = \begin{bmatrix} \mathbf{H}_{i,0}^{(0)} & \mathbf{H}_{i,1}^{(0)} & \cdots & \mathbf{H}_{i,d}^{(0)} \\ \mathbf{H}_{i,0}^{(1)} & \mathbf{H}_{i,1}^{(1)} & \cdots & \mathbf{H}_{i,d}^{(1)} \\ \vdots & \vdots & \ddots & \vdots \\ \mathbf{H}_{i,0}^{(K)} & \mathbf{H}_{i,1}^{(K)} & \cdots & \mathbf{H}_{i,d}^{(K)} \end{bmatrix}$$ 假设我们有一个如下所示的注意力矩阵 $\mathbf{S} \in \mathbb{R}^{(K+1) \times (K+1)}$： $$\mathbf{S} = \begin{bmatrix} 0 & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ \beta_0 & \beta_1 & \cdots & \beta_K \end{bmatrix}$$ 根据自注意力机制的公式 (4)，通过这个注意力矩阵 $\mathbf{S}$ 学习到的输出矩阵 $\mathbf{T} \in \mathbb{R}^{(K+1) \times d}$ 可以描述为： $$\mathbf{T} = \mathbf{S} \mathbf{X}_i = \begin{bmatrix} 0 & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ \gamma_0 & \gamma_1 & \cdots & \gamma_d \end{bmatrix}$$ 其中，对于 $m \in \{1, ..., d\}$，$\gamma_m$ 的计算为： $$\gamma_m = \sum_{k=0}^K \beta_k \mathbf{H}_{i,m}^{(k)}$$ 如果使用求和 (summation) 读出函数来获取节点 $i$ 的最终表示 $\mathbf{T}^{final} \in \mathbb{R}^{1 \times d}$ 的每个元素 $\mathbf{T}_m^{final}$ （其中 $m \in \{1, ..., d\}$）： $$\mathbf{T}_m^{final} = \sum_{k=0}^K \mathbf{T}_{k,m} = (0 + 0 + \cdots + \gamma_m) = \sum_{k=0}^K \beta_k \mathbf{H}_{i,m}^{(k)} = \mathbf{Z}_{i,m}$$ 最终，我们可以得到 Fact 1。

结论: 理论分析表明，解耦 GCN 仅仅通过一个固定的注意力矩阵（其最后一行是传播权重 $\beta_k$）来捕获多跳邻域的部分信息，并且这些固定系数限制了模型自适应地学习每个节点个体邻域信息的能力。相比之下，NAGphormer 使用完整的自注意力机制来学习不同跳数邻域之间的语义相关性，并通过基于注意力的读出函数自适应地学习节点表示，因此能够学习到更具信息量的节点表示。

4.2.6. 复杂度分析

NAGphormer 的时间复杂度和空间复杂度主要由 Transformer 的自注意力模块决定。

• 时间复杂度: 主要取决于自注意力模块。NAGphormer 的计算复杂度为 $O(n (K+1)^2 d)$。 其中：

  • $n$: 节点数量。
  • $K$: 传播步数，决定了每个节点序列的长度为 $K+1$。
  • $d$: 特征向量的维度。 相较于传统图 Transformer 的 $O(N^2 d)$（其中 $N$ 是图中总节点数），NAGphormer 的复杂度与单个节点的邻域序列长度有关，且 $n$ 可以通过小批量训练来管理。

• 空间复杂度: 主要包括模型参数和每层的输出。

  • 模型参数部分：主要来自 Transformer 层，为 $O(d^2 L)$。
  • 注意力矩阵和隐藏节点表示部分：为 $O(b(K+1)^2 + b(K+1)d)$。 其中：
  • $L$: Transformer 层数。
  • $b$: 批量大小 (batch size)。 因此，总空间复杂度为 $O(b(K+1)^2 + b(K+1)d + d^2 L)$。 由于采用了小批量训练，空间复杂度与批量大小 $b$ 相关，而非总节点数 $n$，使得其对内存的需求可控，从而能够处理大型图。

5. 实验设置

5.1. 数据集

实验使用了九个广泛使用的不同规模数据集，包括六个小规模数据集和三个大规模数据集。

• 小规模数据集:

  • Pubmed: 引用网络 (citation network)。节点代表论文，边代表引用关系。
  • CoraFull: 引用网络。节点代表论文，边代表引用关系。
  • Computer (Amazon Computers): 协同购买网络 (co-purchase network)。节点代表商品，边表示两个商品经常一起被购买。
  • Photo (Amazon Photo): 协同购买网络。节点代表商品，边表示两个商品经常一起被购买。
  • CS (Co-authorship network): 共同作者网络 (co-authorship network)。节点代表作者，边表示作者至少合著了一篇论文。
  • Physics (Co-authorship network): 共同作者网络。节点代表作者，边表示作者至少合著了一篇论文。 对于小规模数据集，采用 60%/20%/20% 的随机划分作为训练集/验证集/测试集 (train/val/test splits)。

• 大规模数据集:

  • AMiner-CS: 引用网络。
  • Reddit: 社交网络 (social network)。节点代表帖子，边表示同一用户评论了这两个帖子。
  • Amazon2M: 协同购买网络。 大规模数据集的划分遵循 Feng 等人 (2022) 的设置。

以下是原文 Table 4 的结果，展示了数据集的统计信息：

选择这些数据集是为了全面评估模型在不同规模（从小到大）、不同类型（引用网络、协同购买网络、社交网络、共同作者网络）和不同特征维度（几十到上千）的图上的性能和可扩展性。

5.2. 评估指标

论文中使用的评估指标是准确率 (Accuracy)。 准确率用于衡量分类模型正确预测样本比例的能力。

1. 概念定义: 准确率表示模型在所有预测中正确分类的样本数占总样本数的比例。它是一个直观且常用的分类任务评估指标，尤其适用于类别分布相对均衡的数据集。

2. 数学公式: $$\text{Accuracy} = \frac{\text{Number of Correct Predictions}}{\text{Total Number of Predictions}} = \frac{TP + TN}{TP + TN + FP + FN}$$

3. 符号解释:

   • $\text{TP}$ (True Positives): 真正例，模型正确地将正类别样本预测为正类别。
   • $\text{TN}$ (True Negatives): 真负例，模型正确地将负类别样本预测为负类别。
   • $\text{FP}$ (False Positives): 假正例，模型错误地将负类别样本预测为正类别。
   • $\text{FN}$ (False Negatives): 假负例，模型错误地将正类别样本预测为负类别。

5.3. 对比基线

论文将 NAGphormer 与十二个先进的基线模型进行了比较，这些基线涵盖了不同类型的图神经网络和图 Transformer。

• 全批次 GNN (Full-batch GNNs):

  • GCN (Kipf & Welling, 2017): 经典的图卷积网络。
  • GAT (Velikovi et al., 2018): 图注意力网络，利用注意力机制聚合邻居信息。
  • APPNP (Klicpera et al., 2019): 基于个性化 PageRank 的传播模型，解耦 GCN 的代表。
  • GPRGNN (Chien et al., 2021): 自适应通用 PageRank 图神经网络，解耦 GCN 的代表。 这些基线具有代表性，因为它们是图神经网络领域的里程碑式工作，并且 APPNP 和 GPRGNN 是解耦 GCN 的先进代表，与 NAGphormer 的理论分析有直接关联。

• 可扩展 GNN (Scalable GNNs):

  • GraphSAINT (Zeng et al., 2020): 基于图采样的归纳学习方法。
  • PPRGo (Bojchevski et al., 2020): 基于近似 PageRank 的可扩展 GNN。
  • $GRAND+$ (Feng et al., 2022): 可扩展图随机神经网络。 这些基线代表了处理大规模图的最新 GNN 技术，用于验证 NAGphormer 在可扩展性方面的优势。

• 图 Transformer (Graph Transformers):

  • GT (Dwivedi & Bresson, 2020): 将 Laplacian 特征向量引入 Transformer 作为位置编码。
  • SAN (Kreuzer et al., 2021): 利用 Laplacian 矩阵的完整谱信息学习位置编码。
  • Graphormer (Ying et al., 2021): 引入图结构偏置到注意力矩阵中。
  • GraphGPS (Rampásek et al., 2022): 混合层设计，包含 GNN 层和自注意力层。
  • Gophormer (Zhao et al., 2021): 采用 ego-graph 采样和 Transformer 进行节点分类。 这些基线是图 Transformer 领域的代表性工作，涵盖了不同的结构信息整合策略，用于直接比较 NAGphormer 与现有图 Transformer 的性能。部分图 Transformer 由于其 $O(N^2)$ 复杂度，在大图上可能出现内存溢出。

6. 实验结果与分析

6.1. 核心结果分析

6.1.1. 小规模数据集上的比较

原文 Table 1 报告了所有模型在小规模数据集上的平均准确率和标准差。 以下是原文 Table 1 的结果：

分析:

• NAGphormer 的优越性: NAGphormer 在所有六个小规模数据集上都持续优于所有基线模型，取得了最佳性能。这表明其在捕获节点局部信息和多跳邻域语义相关性方面的有效性。
• 与 GNNs 的比较: NAGphormer 甚至超越了 APPNP 和 GPRGNN 等解耦 GCN，这证实了其能够学习到更具信息量的节点表示，如理论分析所示。传统的 GNN 可能忽略了不同跳数邻居之间的语义关系。
• 与图 Transformer 的比较: NAGphormer 也优于其他图 Transformer 模型，这表明其独特的词元化策略（Hop2Token）和局部信息利用对节点分类任务有益。
• 内存溢出 (OOM) 问题: 值得注意的是，Graphormer、SAN 和 GraphGPS 即使在某些小规模图上也会出现内存溢出错误。这进一步强调了为大规模图设计可扩展图 Transformer 的必要性，也间接印证了 NAGphormer 词元化方法的优势。

6.1.2. 大规模数据集上的比较

原文 Table 2 报告了所有模型在大规模数据集上的平均准确率和标准差。由于现有图 Transformer 在大规模图上无法运行，这里只与可扩展 GNN 进行了比较。 以下是原文 Table 2 的结果：

分析:

• NAGphormer 的可扩展性与性能: NAGphormer 在所有三个大规模数据集上始终优于可扩展 GNN 基线。这验证了 NAGphormer 能够有效地处理大型图，并且能够更好地保留节点的局部信息，从而在大规模图上的节点分类任务中表现出色。
• 对大型图的适用性: 结果表明，NAGphormer 成功地将 Transformer 的强大能力扩展到此前难以处理的大型图上。

6.1.3. 与 Gophormer 的进一步比较

原文 Table 5 报告了 NAGphormer 和 Gophormer 在其他数据集上的准确率比较。 以下是原文 Table 5 的结果：

分析:

• NAGphormer 在大多数数据集（Cora, Pubmed, Blogcatalog, DBLP, Flickr）上表现优于 Gophormer，仅在 Citeseer 上略低于 Gophormer。这进一步证明了 NAGphormer 在节点分类任务上的强大能力。

6.2. 消融实验/参数分析

6.2.1. 结构编码 (Structural Encoding) 的有效性

原文 Table 3 比较了使用和不使用结构编码 (Structural Encoding, SE) 的准确率。 以下是原文 Table 3 的结果：

分析:

• 在所有数据集上，引入结构编码 (With-SE) 都带来了性能提升，尽管提升幅度在不同数据集上有所不同。
• 这表明节点的结构信息对于节点分类任务至关重要，并且通过 Laplacian 特征向量进行结构编码是有效的。
• 不同数据集增益的差异可能反映了不同图的拓扑结构多样性，以及结构信息在这些图中扮演的不同重要性。

6.2.2. 基于注意力的读出函数 (Attention-based Readout Function) 的有效性

图 2 展示了 NAGphormer 在不同读出函数下的性能。

分析:

• ATT. (基于注意力的读出函数，Equation 11) 在小规模数据集上始终优于 SIN. 和 SUM.。

  • SIN. (Self-Information) 仅使用节点自身的表示作为最终输出。
  • SUM. (Summation) 将所有跳数的邻域信息等权相加。

• 这表明自适应地聚合来自不同邻域的信息对于学习更具表达能力的节点表示非常有益，从而提升了节点分类的性能。

  图 4 展示了基于注意力的读出函数在大规模数据集上的性能。

  分析:

• 在大规模数据集上（AMiner-CS、Reddit、Amazon2M），ATT. 同样持续优于 SIN. 和 SUM.。

• 这进一步证实了基于注意力的读出函数在处理复杂和大规模图数据时，能够通过自适应加权不同跳数邻域信息，从而有效提高模型性能。

6.2.3. 参数研究 (Parameter Study)

图 3 展示了 NAGphormer 在不同参数设置下的性能。

该图像是图表，展示了NAGphormer在不同参数设置下的性能表现。图分为两部分，(a) 展示了在不同传播步数 $K$ 下的准确率变化，数据源包括 Aminer-CS、Reddit 和 Amazon2M；(b) 则展示了在不同Transformer层数 $L$ 时的准确率变化。整体趋势显示，在特定参数下，模型的性能表现有显著差异。

6.2.3.1. 参数 $K$ (传播步数) 的影响

• 实验固定 Transformer 层数 $L=1$，并改变传播步数 $K \in \{4, 6, ..., 20\}$。
• 分析:
  • 每个数据集的最佳 $K$ 值不同，这说明不同网络的邻域结构有所差异。
  • 即使 $K$ 相对较大（例如达到 20），模型性能也没有显著下降，甚至在 Reddit 数据集上变化微小（<0.1%）。这表明通过自注意力机制和基于注意力的读出函数从多跳邻域学习节点表示，可以有效缓解过平滑或过挤压问题。
  • 不同数据集上性能随 $K$ 变化的趋势不同，这可能因为它们是不同类型的网络，具有不同的特性。这再次强调了邻域信息对模型性能的影响因网络类型而异。
• 实践设置: 作者将 AMiner-CS 的 $K$ 设为 16，其他数据集的 $K$ 设为 10（因为在 Amazon2M 上，较大的 $K$ 会增加 Hop2Token 的时间成本）。

6.2.3.2. 参数 $L$ (Transformer 层数) 的影响

• 实验固定最佳 $K$ 值，并改变 $L \in \{1, ..., 5\}$。
• 分析:
  • 通常，较小的 $L$ 就能达到较高的准确率，而较大的 $L$ 会导致 NAGphormer 性能下降。这归因于较大的 $L$ 更容易导致过拟合 (over-fitting)。
• 实践设置: 作者将 AMiner-CS 的 $L$ 设为 3，其他数据集的 $L$ 设为 1。

6.2.4. 效率实验 (Efficiency Experiments)

原文 Table 6 比较了 NAGphormer 和三个可扩展 GNN 在大规模图上的训练成本（GPU 内存和运行时间）。 以下是原文 Table 6 的结果：

分析:

• 运行时间: NAGphormer 在 Amazon2M（包含 200 万节点和 6000 万条边）上比第二快的模型 PPRGo 快了近 3 倍（58.66 秒 vs 152.62 秒）。在 Reddit 和 AMiner-CS 上，NAGphormer 的训练时间也具有竞争力。

• 原因: NAGphormer 的时间复杂度主要取决于节点数量，而与边数量无关（其 Hop2Token 过程在模型训练前完成）。而其他 GNN 方法在训练和推理阶段都涉及传播操作，因此时间消耗与边数量和节点数量相关。

• GPU 内存: NAGphormer 采用了小批量训练，其 GPU 内存消耗由批量大小决定。通过选择合适的批量大小，即使在大型图上，其内存消耗也是可承受的。在内存方面，PPRGo 和 $GRAND+$ 表现稍好，但 NAGphormer 的内存占用仍远低于 GraphSAINT。

  这些结果共同证明了 NAGphormer 在大规模图上处理节点分类任务时，不仅性能优越，而且具有显著的效率优势。

7. 总结与思考

7.1. 结论总结

本研究提出了一种新颖且强大的图 Transformer 模型——NAGphormer，用于大型图上的节点分类任务。其核心创新在于 Hop2Token 模块，该模块将节点的多跳邻域特征提取并转化为一系列词元，使得每个节点可以被视为一个词元序列。这种“标记化”设计使得 NAGphormer 能够以小批量方式进行训练，从而有效解决了传统图 Transformer 在处理大规模图时面临的二次复杂度挑战，实现了模型的可扩展性。

此外，NAGphormer 还引入了基于注意力的读出函数，能够自适应地学习并聚合来自不同跳数邻域的信息，进一步提升了模型性能。理论分析也支持了 NAGphormer 相比解耦 GCN 能够学习到更具表达能力的节点表示。

通过在从小到大的多个基准数据集上进行的广泛实验，NAGphormer 持续展现出优于现有图 Transformer 和主流 GNN 的性能，并在大规模图上验证了其出色的效率和可扩展性。

7.2. 局限性与未来工作

论文作者指出了以下局限性和未来工作方向：

• 任务泛化: 目前 NAGphormer 主要针对节点分类任务进行了验证。未来工作可以将其推广到其他图挖掘任务，例如图分类 (graph classification) 等。
• Hop2Token 的扩展: Hop2Token 模块的 $K$ 值选择和其聚合方式仍有改进空间。虽然目前其离线计算的方式保证了效率，但探索更动态或自适应的邻域特征提取机制可能带来进一步的性能提升。
• 理论理解的深化: 尽管进行了与解耦 GCN 的理论比较，但对于 NAGphormer 在更广泛的 GNN 类别中的理论优势和表示能力限制仍有待深入研究。

7.3. 个人启发与批判

7.3.1. 个人启发

• “词元化”策略的创新: NAGphormer 最主要的启发在于其对“词元 (token)”概念的重新定义。将图中的节点视为序列，而序列中的元素是该节点的邻域词元，巧妙地规避了 Transformer 在图上直接应用时面临的 $O(N^2)$ 复杂度问题。这种局部化、基于邻域的词元化思想，为未来设计可扩展的图 Transformer 提供了一个非常有前景的方向。它从根本上改变了 Transformer 处理图数据的方式，使得 mini-batch 训练成为可能。
• GNN 与 Transformer 优势结合: Hop2Token 模块本质上是一种多跳消息传递机制（类似于解耦 GCN 的传播），它有效地提取了 GNN 擅长的局部结构信息。而 Transformer 则在此基础上，利用其强大的自注意力机制来建模这些多跳邻域词元之间的复杂关系，实现了 GNN 和 Transformer 优势的结合。这种模块化设计，可以推广到其他领域，即先用高效的局部特征提取器生成“词元”，再用 Transformer 建模这些“词元”之间的全局/局部关系。
• 缓解过平滑/过挤压: 实验结果表明，NAGphormer 在较大传播步数 $K$ 下性能并未显著下降，这暗示了 Transformer 的自注意力机制和基于注意力的读出函数可能在一定程度上缓解了 GNN 中常见的过平滑和过挤压问题。这是因为 Transformer 能够选择性地关注最重要的邻域信息，而非简单地平均或求和，从而保留了更多的区分度。

7.3.2. 批判

• Hop2Token 的局限性:

  • 静态聚合: Hop2Token 模块是非参数化的，在训练前离线计算。这意味着邻域聚合权重是固定的（由 $\hat{\mathbf{A}}$ 决定），无法在模型训练过程中动态调整以适应不同的任务或节点。虽然效率高，但牺牲了一定的灵活性和表达力。
  • 过度依赖邻接矩阵: Hop2Token 直接基于邻接矩阵的幂进行聚合，对于同质性较低 (heterogeneous) 或边属性丰富 (rich edge features) 的图，这种简单的聚合方式可能无法捕获复杂的邻域信息。
  • 潜在的信息损失: Hop2Token 将整个 $k$-跳邻域聚合为一个单一的词元。尽管 Transformer 能够建模这些词元之间的关系，但这种聚合操作本身可能已经损失了 $k$-跳邻域内部的细粒度结构信息。

• Transformer 层的深度限制: 论文中提到，较深的 Transformer 层 ($L>1$) 容易导致过拟合。这表明虽然其词元化策略解决了可扩展性，但 Transformer 本身在处理这种特定“邻域词元序列”时，可能仍然对深度敏感。如何设计更鲁棒、更深层的图 Transformer 仍是一个挑战。

• 结构编码的普适性: 虽然 Laplacian 特征向量是常用的结构编码方式，但其计算成本在大规模图上仍可能较高，并且对于动态图或异构图的适用性有待进一步探讨。

• 注意力机制的解释性: 尽管注意力机制提供了权重，但其真正的解释性仍然是一个复杂的问题。Hop2Token 生成的词元序列中，不同跳数词元的语义可能存在重叠，Transformer 如何有效区分和利用这些信息值得深入研究。

7.3.3. 潜在的改进方向

• 动态 Hop2Token: 探索参数化的 Hop2Token 变体，允许模型在训练过程中学习更优的邻域聚合权重，或引入注意力机制到 Hop2Token 内部。
• 异构图和边特征: 将 Hop2Token 扩展到能够处理异构图 (heterogeneous graphs) 和丰富的边特征 (edge features)，例如通过不同的聚合函数处理不同类型的边或节点。
• 更复杂的 Transformer 架构: 结合其他 Transformer 变体（如稀疏注意力 (sparse attention)、局部注意力 (local attention)）来优化 NAGphormer 的性能和效率，同时尝试解决深层 Transformer 的过拟合问题。
• 多任务学习: 将 NAGphormer 推广到多任务学习场景，例如同时进行节点分类、边预测和图分类等任务，以验证其表示学习的通用性。
• 可解释性增强: 深入分析 Transformer 内部的注意力权重，以更好地理解模型是如何利用不同跳数邻域信息的。