1. 论文基本信息

1.1. 标题

线性时间图神经网络实现可扩展推荐系统 (Linear-Time Graph Neural Networks for Scalable Recommendations)

1.2. 作者

Jiahao Zhang* (The Hong Kong Polytechnic University), Rui Xue* (North Carolina State University), Wenqi Fan (The Hong Kong Polytechnic University), Xin Xu (The Hong Kong Polytechnic University), Qing Li (The Hong Kong Polytechnic University), Jian Pei (Duke University), Xiaorui Liu (North Carolina State University)。 * 表示共同第一作者。

1.3. 发表期刊/会议

ACM Web Conference 2024 (WWW '24), 于2024年5月13-17日在新加坡举行。WWW是计算机科学领域，尤其是在万维网和信息系统方面，享有盛誉的顶级会议之一。

1.4. 发表年份

2024年

1.5. 摘要

在信息爆炸的时代，推荐系统 (recommender systems) 是为用户提供个性化推荐的关键工具。推荐系统的核心是基于用户过去的互动行为预测用户未来的行为。鉴于图神经网络 (Graph Neural Networks, GNNs) 在捕获用户-物品交互数据中高阶连接性 (high-order connectivities) 方面的强大表达能力，近年来，利用 GNNs 提升推荐系统预测性能的兴趣日益增长。然而，经典的矩阵分解 (Matrix Factorization, MF) 和深度神经网络 (Deep Neural Network, DNN) 方法由于其可扩展性 (scalability) 优势，在实际大规模推荐系统中仍扮演着重要角色。尽管存在 GNN 加速解决方案，但 GNN-based 推荐系统能否像经典的 MF 和 DNN 方法一样高效扩展仍然是一个悬而未决的问题。在本文中，我们提出了一种线性时间图神经网络 (Linear-Time Graph Neural Network, LTGNN)，以将 GNN-based 推荐系统扩展到能够实现与经典 MF 方法相当的可扩展性，同时保持 GNNs 强大的表达能力以获得卓越的预测准确性。论文通过广泛的实验和消融研究 (ablation studies) 验证了所提出算法的有效性和可扩展性。基于 PyTorch 的实现已开源。

1.6. 原文链接

https://arxiv.org/abs/2402.13973 PDF 链接: https://arxiv.org/pdf/2402.13973v1.pdf 发布状态：预印本 (arXiv)，但已接受并在 WWW '24 上发表。

2. 整体概括

2.1. 研究背景与动机

2.1.1. 推荐系统的核心作用与演进

在当今信息爆炸的时代，推荐系统 (recommender systems) 已成为帮助用户从海量信息中发现个性化内容的关键工具。推荐系统的主要目标是通过分析用户历史行为 (user historical behaviors) 来预测用户潜在兴趣 (potential interests)，从而提供个性化的物品推荐。协同过滤 (collaborative filtering, CF) 作为一种主流技术，通过挖掘用户和物品之间的模式来预测用户偏好。

2.1.2. 现有推荐技术及其局限性

• 矩阵分解 (Matrix Factorization, MF) 和深度神经网络 (Deep Neural Networks, DNNs): 这些经典方法通过将用户和物品映射到低维嵌入空间来建模用户-物品交互。它们在现实世界的大规模推荐系统中因其计算效率和可扩展性 (scalability) 而占据主导地位。然而，这些方法通常侧重于局部连接性 (local connectivity)，难以有效捕获用户-物品交互图中复杂的高阶连接性 (high-order connectivities)，从而限制了其表达能力。
• 图神经网络 (Graph Neural Networks, GNNs): 近年来，GNNs 因其强大的高阶连接性建模能力而在推荐系统中受到广泛关注。GNNs 通过在交互图 (interaction graph) 中迭代聚合邻居嵌入 (neighbor embeddings)，能够编码局部和长程协同信号 (long-range collaborative signals)。例如，LightGCN 等模型展现了优越的预测性能。

2.1.3. GNNs 在大规模推荐中的可扩展性挑战

尽管 GNNs 具有强大的表达能力，但它们在大规模、工业级的推荐系统应用中并未被广泛采用，主要原因在于其可扩展性限制 (scalability limitations)。

• 计算复杂度问题: 传统 GNNs 的训练计算复杂度往往与传播层数 $L$ 呈指数关系，或与边数 $|\mathcal{E}|$ 呈二次关系，这远高于 MF 和 DNNs 的线性复杂度 ($O(|\mathcal{E}|d)$)。在大规模推荐场景中，用户-物品交互图的节点和边数量可达数十亿，使得非线性复杂度的 GNNs 变得不可行。
• 邻居爆炸问题 (Neighborhood Explosion Problem): GNNs 在聚合邻居信息时，随着传播层数的增加，每个节点的感受野 (receptive field) 会呈指数级增长，导致需要聚合的邻居数量急剧增加，带来巨大的计算和内存开销。
• 现有加速方案的不足: 尽管已有多种 GNN 加速解决方案，如邻居采样 (neighbor sampling) 和模型简化 (design simplification)，但这些方法通常仍无法实现线性复杂度，或以牺牲预测性能为代价。因此，GNN-based 推荐系统能否在保持强大表达能力的同时，像经典 MF/DNN 方法一样实现线性可扩展性，仍然是一个开放性问题。

2.1.4. 本文的切入点

本文旨在解决 GNNs 在推荐系统中的可扩展性挑战，核心动机是：

1. 保持 GNNs 的强大表达能力: 确保模型能够有效捕获高阶协同信号。
2. 实现线性计算复杂度: 使 GNNs 能够在大规模工业级应用中高效运行，达到与 MF 和 DNNs 相当的效率。

2.2. 核心贡献/主要发现

本文提出了一个名为线性时间图神经网络 (Linear-Time Graph Neural Network, LTGNN) 的新模型，其主要贡献总结如下：

• 关键复杂度分析和瓶颈揭示: 论文对当前广泛使用的协同过滤方法进行了批判性的复杂度分析和比较，揭示了它们的性能和效率瓶颈。
• 线性时间 GNN 模型 LTGNN: 提出了一种新颖的 GNN-based 模型 LTGNN，专为大规模协同过滤推荐设计。该模型仅使用一个传播层 (propagation layer)，但通过隐式图建模 (implicit graph modeling) 仍能捕获长程协同信号 (long-range collaborative signals)。
• 高效方差减少邻居采样策略 (Efficient Variance-Reduced Neighbor Sampling): 为处理大规模用户-物品交互图，LTGNN 设计了一种高效且改进的方差减少邻居采样策略。该策略能显著减少嵌入聚合时的邻居数量，并通过改进的方差减少技术有效地处理邻居采样引入的随机误差。
• 卓越的性能与效率验证: 在三个真实世界推荐数据集（包括一个具有数百万用户和物品的大规模数据集）上进行了广泛的对比实验和消融研究。实验结果表明，LTGNN 在显著减少 GNN-based CF 模型训练时间的同时，保持了与现有 GNN 模型相当的推荐性能。详细的时间复杂度分析进一步证明了其卓越的效率。

3. 预备知识与相关工作

3.1. 基础概念

3.1.1. 推荐系统 (Recommender Systems)

推荐系统是一种信息过滤系统，旨在预测用户对物品的“偏好”或“评分”，并向用户推荐他们可能感兴趣的物品。它们在电子商务、流媒体、社交媒体等各种在线应用中扮演着至关重要的角色。

3.1.2. 协同过滤 (Collaborative Filtering, CF)

协同过滤是推荐系统中最常用的技术之一，其核心思想是“物以类聚，人以群分”。它通过分析大量用户（“协同”）的行为模式，基于相似用户对物品的偏好，或相似物品被同一用户喜欢的程度，来预测用户对新物品的兴趣。

3.1.3. 矩阵分解 (Matrix Factorization, MF)

矩阵分解是协同过滤的一种流行方法。它将用户-物品交互矩阵（通常是稀疏的）分解为两个低秩矩阵：一个用户嵌入矩阵和一个物品嵌入矩阵。每个用户和物品都被表示为一个低维的隐向量（嵌入），通过计算这些嵌入的内积 (inner product) 来预测用户对物品的偏好。例如，$\hat{y}_{u,i} = \boldsymbol{p}_u^T \boldsymbol{q}_i$，其中 $\boldsymbol{p}_u$ 是用户 $u$ 的嵌入，$\boldsymbol{q}_i$ 是物品 $i$ 的嵌入。

3.1.4. 深度神经网络 (Deep Neural Networks, DNN)

深度神经网络是具有多层非线性变换的神经网络模型。它们能够学习复杂的数据模式和抽象特征。在推荐系统中，DNNs 可以用来学习用户和物品的表示，或者直接建模用户-物品交互，例如神经协同过滤 (Neural Collaborative Filtering, NCF) 模型。

3.1.5. 图神经网络 (Graph Neural Networks, GNN)

图神经网络是一类专门处理图结构数据的深度学习模型。它们通过在图上进行消息传递 (message passing) 或邻居聚合 (neighbor aggregation) 来学习节点（如用户和物品）的表示。GNNs 能够有效地捕获图中的结构信息和高阶连接性，因为它们可以迭代地从节点的邻居那里收集信息，从而将多跳邻居的信息融入到节点的嵌入中。

3.1.6. 用户-物品交互图 (User-Item Interaction Graph)

在推荐系统中，用户和物品之间的交互（如购买、点击、评分）可以自然地表示为一个二分图 (bipartite graph) $\mathcal{G} = (\mathcal{V}, \mathcal{E})$。其中，节点集 $\mathcal{V}$ 包含用户节点和物品节点，边集 $\mathcal{E}$ 表示用户和物品之间的交互。这种图结构能够直观地表示用户和物品之间的复杂关系。

3.1.7. 高阶连接性 (High-order Connectivities) / 协同信号 (Collaborative Signals)

高阶连接性指的是图中相距多跳 (multi-hop) 的节点之间的关系。在用户-物品交互图中，高阶连接性可以揭示更复杂的协同信号。例如，“与你兴趣相似的用户喜欢过的物品”就是一种协同信号，而“与你兴趣相似的用户的相似用户喜欢过的物品”则是更高阶的协同信号。GNNs 通过多层传播 (multi-layer propagation) 能够捕获这些高阶信息。

3.1.8. 稀疏矩阵乘法 (Sparse Matrix Multiplication)

在用户-物品交互图中，由于绝大多数用户只与少数物品发生过交互，因此其邻接矩阵 (adjacency matrix) 通常是高度稀疏的。稀疏矩阵乘法是一种优化技术，它只对非零元素进行计算，从而在处理大规模稀疏数据时显著提高计算效率。

3.1.9. PageRank / Personalized PageRank (PPNP)

PageRank 是一种衡量网页重要性的算法，通过迭代地计算网页之间链接的“投票”来确定。个性化 PageRank (Personalized PageRank, PPNP) 是 PageRank 的一个变体，它在随机游走时，除了按照图结构进行跳转，还有一定概率“传送”回起始节点，从而为每个节点生成一个个性化的重要性分数分布。在 GNN 领域，PPNP 被用于传播节点嵌入 (node embeddings)，以捕获长程依赖性，同时通过“传送”机制缓解过平滑 (over-smoothing) 问题。

3.1.10. Mini-batch 训练

在大规模数据集中，一次性处理所有训练数据（全批次训练，full-batch training）在计算和内存上都不可行。Mini-batch 训练是一种常用的优化策略，它将整个数据集分成若干个小的子集（mini-batches），每次训练迭代只处理一个 mini-batch。这既能提高训练效率，又能提供更稳定的梯度估计。

3.1.11. BPR Loss (Bayesian Personalized Ranking Loss)

BPR 损失是一种广泛用于隐式反馈 (implicit feedback) 推荐系统的成对损失函数 (pairwise loss function)。它旨在优化推荐列表中正样本 (positive samples) 排名高于负样本 (negative samples) 的概率。具体来说，对于一个用户 $u$ 和一对交互 (u, i)（正样本）和 (u, j)（负样本），BPR 损失促使模型学习到用户 $u$ 对物品 $i$ 的预测分数 $\hat{y}_{u,i}$ 大于对物品 $j$ 的预测分数 $\hat{y}_{u,j}$。

3.1.12. 邻居采样 (Neighbor Sampling)

在 GNN 中，当节点有大量邻居时，聚合所有邻居的特征会非常耗时。邻居采样是一种常用的加速技术，它在进行邻居聚合时，只从节点的邻居中随机选择一个子集进行聚合，从而减少计算量。然而，不当的采样可能引入较大的方差 (variance) 和近似误差 (approximation error)。

3.1.13. 方差减少 (Variance Reduction)

方差减少是一类统计技术，旨在降低随机估计量的方差，从而提高估计的准确性和稳定性。在 GNN 的邻居采样背景下，方差减少技术旨在通过巧妙的设计，在只采样部分邻居的情况下，仍能得到接近全邻居聚合的准确结果，同时控制采样带来的误差。常见的做法是利用历史信息或控制变量。

3.2. 前人工作

3.2.1. 经典协同过滤模型

• 矩阵分解 (MF): 作为最具代表性的协同过滤方法之一，MF 通过将用户和物品表示在低维嵌入空间中，利用内积预测交互。例如 Koren (2008) 的工作。
• 神经协同过滤 (Neural Collaborative Filtering, NCF) [25]: NCF 利用深度神经网络来建模用户-物品交互，超越了 MF 简单的内积操作，提高了表达能力。
• 其他早期方法: 例如物品相似度模型 [24, 31] 和其他 DNNs [25, 47]，它们主要关注局部连接性。

3.2.2. GNN-based 推荐系统

• GC-MC [1]: 早期将图卷积自编码器 (graph convolutional autoencoders) 应用于补全缺失的用户-物品交互，是 GNN 在推荐中应用的先驱。
• PinSAGE [49]: 针对大规模推荐场景，PinSAGE 将 GraphSAGE [22] 的思想引入推荐系统，通过邻居采样 (neighbor sampling) 实现了可扩展性。其传播规则包含聚合和标准化操作，但采样机制可能导致较大的近似误差，且计算复杂度与层数 $L$ 呈指数关系。
• NGCF (Neural Graph Collaborative Filtering) [42]: NGCF 明确提出了协同信号的概念，并利用消息传递 (message-passing) 机制在用户-物品交互图上建模高阶连接性。它通过迭代聚合邻居嵌入来学习用户和物品的表示。
• LightGCN [23]: LightGCN 简化了 NGCF，指出 GNNs 中非线性激活函数和特征变换对于推荐任务是冗余的。它仅保留了邻居聚合部分，通过简单的线性传播实现了高性能，并成为 GNN-based 推荐的主流骨干模型。其计算复杂度与传播层数 $L$ 和边数 $|\mathcal{E}|$ 均相关。
• DGCF (Disentangled Graph Collaborative Filtering) [43]: 尝试解耦不同协同信号，进一步提升 GNN 推荐的性能。

3.2.3. GNN 可扩展性加速方案

• 邻居采样 (Neighbor Sampling) [34, 49]: 通过对每个节点的邻居进行采样，减少聚合的计算量。例如 GraphSAGE [22]、FastGCN [3]、GraphSAINT [52]、VR-GCN [4] 和 MVS-GNN [6]。尽管这些方法缓解了邻居爆炸问题，但采样可能引入方差，且通常难以实现严格的线性复杂度。
• 模型简化 (Design Simplification) [23, 44]: 简化 GNN 架构，如 LightGCN 移除非线性激活和变换，SGC (Simplifying Graph Convolutional Networks) [44] 移除所有非线性层和权重矩阵。
• 基于历史嵌入 (Historical Embeddings) 的方法 [18, 50]: 利用前一个训练迭代或周期中计算出的嵌入来补充当前 mini-batch 中未采样到的节点信息，以近似全聚合结果。例如 GNNAutoScale [18] 和 GraphFM [50]。这些方法虽提高了效率，但在某些情况下仍需进行全邻居聚合，导致无法完全实现线性复杂度。
• 解耦特征变换与聚合 (Decoupling Feature Transformation and Aggregation): 例如，预计算方法 [44, 53] 和后计算方法 [26, 54] 分离特征变换和图传播过程，从而提高效率。

3.3. 技术演进

推荐系统从早期的基于内容、基于流行度，发展到以协同过滤为核心的 MF 模型。MF 模型的成功推动了其在工业界的广泛应用，但其表达能力有限。随着深度学习的兴起，DNNs 被引入推荐系统，如 NCF，提供了更强的非线性建模能力。然而，这些方法在建模高阶协同信号方面仍有局限。

GNNs 的出现为捕捉复杂的用户-物品交互图结构和高阶协同信号提供了强大的工具，如 NGCF 和 LightGCN。它们在预测性能上取得了显著突破。然而，GNNs 的计算密集性（尤其是在大规模图上的多层传播和全邻居聚合）成为了其在工业界落地的主要障碍。为了应对这一挑战，研究者们提出了各种 GNN 可扩展性方案，包括邻居采样、模型简化和基于历史嵌入的方法。

本文的工作正处于这一演进的交叉点：它试图在保持 GNNs 强大表达能力的同时，克服其在大规模推荐系统中的可扩展性瓶颈，特别是要达到与经典 MF 相当的线性时间复杂度。

3.4. 差异化分析

LTGNN 与相关工作的主要区别和创新点在于：

• 隐式图建模 (Implicit Graph Modeling) 与单层传播:
  • 区别: 大多数 GNNs (如 LightGCN, NGCF) 依赖于堆叠多层显式传播来捕获高阶信息。PinSAGE 虽使用采样，但其复杂度仍与层数 $L$ 呈指数关系。LTGNN 则借鉴隐式深度学习 (Implicit Deep Learning) 的思想，通过求解一个固定点方程来隐式地捕获相当于无限层传播的长程依赖，但实际计算只通过单层前向传播完成。
  • 创新点: 这种设计极大地减少了模型对层数 $L$ 的依赖，从而避免了传统 GNNs 中 $L$ 带来的指数级或多项式级计算复杂度的增长。它通过迭代间的历史信息积累来实现长程建模，而不是单次迭代内的多层堆叠。
• 高效方差减少邻居采样 (Efficient Variance-Reduced Neighbor Sampling, EVR):
  • 区别: 传统的邻居采样 (如 PinSAGE 中的采样) 会引入较大的近似误差。现有的方差减少 GNNs (如 VR-GCN, MVS-GNN) 虽然能降低误差，但通常需要在每个 mini-batch 迭代中执行一次全邻居聚合，这导致其计算复杂度仍为 $O(|\mathcal{E}|^2)$，无法在大规模图上实现线性扩展。
  • 创新点: LTGNN 提出的 EVR 策略通过周期性更新 (periodically updating) 历史嵌入内存变量 (memory variables)，避免了在每个 mini-batch 迭代中进行全邻居聚合的昂贵操作。它将计算历史聚合的开销分摊到每个 epoch 一次，从而将整体复杂度降至线性 $O(|\mathcal{E}|Dd)$，其中 $D$ 是采样的常数邻居数。
• 整体线性时间复杂度:
  • 区别: LightGCN 的复杂度为 $O(\frac{1}{B}L|\mathcal{E}|^2d)$，PinSAGE 为 $O(|\mathcal{E}|D^L d^2)$。这些都无法达到严格的线性复杂度。
  • 创新点: LTGNN 结合了单层隐式建模和 EVR，实现了 $O(|\mathcal{E}|Dd)$ 的线性时间复杂度，其中 $D$ 是一个小的常数。这使其在理论上和实践中都与 MF 和 DNNs 具有可比拟的可扩展性，是 GNN-based 推荐系统首次在保持高性能的同时达到这一效率水平。

4. 方法论

本节将详细阐述 LTGNN 的核心方法论，包括其隐式图建模和高效方差减少邻居采样策略。我们将公式的讲解无缝融入到方法步骤的描述中，并严格保持原文公式的完整性。

4.1. 方法原理

LTGNN 的核心思想是解决传统 GNN 在大规模推荐系统中的两大挑战：

1. 层数与表达能力 (Layer and expressiveness) 的权衡: 增加 GNN 层数 $L$ 可以捕获长程依赖，但会导致计算复杂度急剧增加。

2. 邻居聚合与随机误差 (Neighbor aggregation and random error) 的问题: 聚合所有邻居成本高昂；随机采样虽然效率高，但会引入较大的近似误差。

   为了解决这些问题，LTGNN 提出了两个关键设计：

• 隐式图建模 (Implicit Graph Modeling): 通过将 GNN 的传播过程建模为一个固定点方程 (fixed-point equation)，并使用单层传播来近似求解，从而在不堆叠多层的情况下捕获长程信息。
• 高效方差减少邻居采样 (Efficient Variance-Reduced Neighbor Sampling): 通过周期性更新历史聚合嵌入，显著降低了邻居采样的计算开销和随机误差，使得模型能够在大规模稀疏图上高效运行。

4.2. 核心方法详解

4.2.1. 隐式图建模 (Implicit Modeling for Recommendations)

LTGNN 借鉴了隐式深度学习 (Implicit Deep Learning) 的思想，将 GNN 的嵌入传播过程视为一个寻找固定点 (fixed point) 的过程，而非传统的逐层堆叠。

4.2.1.1. 从 PPNP 到固定点方程

个性化 PageRank (Personalized PageRank, PPNP) [32] 是一种经典的度量图中节点之间接近度的方法。它被 APPNP (Personalized Propagation of Neural Predictions) [19] 等 GNN 模型用于传播节点嵌入。PPNP 模型通过以下公式传播节点嵌入： $$E_{PPNP}^k = \alpha \Big( I - (1 - \alpha) \tilde{A} \Big)^{-1} E_{in}^k$$ 其中：

• $E_{PPNP}^k$ 是第 $k$ 次迭代的输出嵌入。

• $\alpha$ 是遥传因子 (teleport factor)，控制了随机游走跳回原始节点的概率，通常在 $(0, 1)$ 之间。

• $I$ 是单位矩阵 (identity matrix)。

• $\tilde{A}$ 是归一化带自环的邻接矩阵 (normalized adjacency matrix with self-loops)。

• $E_{in}^k$ 是第 $k$ 次迭代的输入节点嵌入。

  由于矩阵求逆的计算成本极高，APPNP 通过 $L$ 层迭代传播来近似求解这个固定点方程： $$\begin{array}{r l} & \quad E_0^k = E_{in}^k, \\ & \quad E_{l+1}^k = (1 - \alpha) \tilde{A} E_l^k + \alpha E_{in}^k, \forall l = 0, \ldots, L - 1 \end{array}$$ 这个迭代过程使得 APPNP 能够捕获 $L$ 跳 (L-hop) 高阶信息，同时通过遥传项 $\alpha E_{in}^k$ 缓解了 GNN 中常见的过平滑 (over-smoothing) 问题。LightGCN 虽然形式略有不同（它将不同层的嵌入加权平均），但其本质与 APPNP 密切相关。然而，APPNP 和 LightGCN 都面临多层递归特征聚合 (multi-layer recursive feature aggregations) 带来的可扩展性问题。

4.2.1.2. LTGNN 的隐式建模与单层传播

受隐式深度学习和隐式 GNNs [9, 20, 33, 48] 成功的启发，LTGNN 提出了隐式建模，直接计算上述固定点方程的解 $E_*^k$。这个固定点 $E_*^k$ 代表了嵌入传播的平衡态 (equilibrium state)，等效于无限次传播后的最终状态，因此能够有效地捕获图中的长程节点依赖 (long-range node dependencies)。

图 1(a) 展示了隐式建模的核心思想，即固定点方程： $$E_*^k = (1-\alpha) \tilde{A} E_*^k + \alpha E_{in}^k$$ LTGNN 的输出嵌入 $E_{out}^k$ 被隐式地定义为这个固定点方程的解。这种隐式建模提供了 GNN 设计的灵活性，允许我们使用方程求解器来获取 $E_*^k$，而不是简单地堆叠多层 GNN。

为了实现线性时间计算，LTGNN 提出通过单个前向传播层来近似求解这个固定点。如图 1(b) 所示，LTGNN 的前向传播公式为： $$E_{out}^k = (1 - \alpha) \tilde{A} E_{out}^{k - 1} + \alpha E_{in}^k$$ 其中：

• $E_{out}^k$ 是当前第 $k$ 次训练迭代的输出嵌入。

• $E_{out}^{k-1}$ 是前一次训练迭代 k-1 的输出嵌入，它作为固定点求解器的一个更好的初始化。

  这种单层设计相较于多层嵌入传播而言效率极高，但它仍然能够通过在不同训练迭代间的信息积累 (information accumulation across training iterations) 来捕获多跳邻居信息，从而实现长程依赖建模。

4.2.1.3. 隐式模型的后向传播

隐式模型的后向传播与前向计算是独立的 [9, 20, 48]。给定来自输出嵌入层 $\frac{\partial \mathcal{L}}{\partial E_{out}^k}$ 的梯度，输入嵌入 $E_{in}^k$ 的梯度可以基于固定点方程 (14) 计算： $$\frac{\partial \mathcal{L}}{\partial E_{in}^k} = \alpha \frac{\partial \mathcal{L}}{\partial E_{out}^k} \Big( I - \big( 1 - \alpha \big) \tilde{A} \Big)^{-1}$$ 然而，由于邻接矩阵维度过高，计算其逆矩阵是不可行的。因此，LTGNN 提出通过单个后向传播层来近似这个梯度： $$\frac{\partial \mathcal{L}}{\partial E_{in}^k} = (1 - \alpha) \tilde{A} \frac{\partial \mathcal{L}}{\partial E_{in}^{k - 1}} + \alpha \frac{\partial \mathcal{L}}{\partial E_{out}^k}$$ 其中：

• $\frac{\partial \mathcal{L}}{\partial E_{in}^k}$ 是当前第 $k$ 次训练迭代的输入嵌入梯度。

• $\frac{\partial \mathcal{L}}{\partial E_{in}^{k-1}}$ 是前一次训练迭代 k-1 的输入嵌入梯度，它作为固定点求解器的一个更好的初始化。

  综上所述，LTGNN 的单层 GNN 的前向和后向计算可以总结为： $$\mathbf{Forward:} E_{out}^k = (1 - \alpha) \tilde{A} E_{out}^{k - 1} + \alpha E_{in}^k$$

$$\mathbf{Backward:} \frac{\partial \mathcal{L}}{\partial E_{in}^k} = (1 - \alpha) \tilde{A} \frac{\partial \mathcal{L}}{\partial E_{in}^{k - 1}} + \alpha \frac{\partial \mathcal{L}}{\partial E_{out}^k}$$ 其中，历史计算 $E_{out}^{k-1}$ 和 $\frac{\partial \mathcal{L}}{\partial E_{in}^{k-1}}$ 通过在每次训练迭代结束时维护模型的输出和梯度来获得。

4.2.2. 高效方差减少邻居采样 (Efficient Variance-Reduced Neighbor Sampling)

前述隐式建模和单层设计显著降低了 GNN 的计算复杂度。然而，即使层数 $L=1$，如果每个目标节点聚合的邻居数量 $D$ 很大，计算复杂度仍可能很高。此外，简单的随机采样会引入大的近似误差，尤其是在高出度 (high-degree) 节点上。

4.2.2.1. 经典方差减少邻居聚合及其局限性

最近的研究探索了 GNN 上的方差减少 (variance reduction, VR) 技术，例如 VR-GCN [4] 和 MVS-GNN [6]，其聚合方式如下： $$(\hat{\boldsymbol X}^k)^{VR} = \hat{\boldsymbol A} (E_{in}^k - \overline{{E}}_{in}^k) + \tilde{\boldsymbol A} \overline{{E}}_{in}^k \quad (\approx \tilde{\boldsymbol A} \boldsymbol E_{in}^k)$$ 其中：

• $\hat{\boldsymbol A}$ 是归一化邻接矩阵 $\tilde{\boldsymbol A}$ 的无偏估计量。具体来说，如果节点 $v$ 被采样为目标节点 $u$ 的邻居，则 $\hat{\boldsymbol A}_{u,v} = \frac{|N(u)|}{D} \tilde{\boldsymbol A}_{u,v}$，否则为 0。

• $\overline{{E}}_{in}^k$ 是历史输入嵌入的平均值。

  这种方法需要对历史嵌入 $\overline{{E}}_{in}^k$ 进行全邻居聚合 (full neighbor aggregations)，即计算 $\tilde{\boldsymbol A} \overline{{E}}_{in}^k$。在每个 mini-batch 迭代中执行此操作会导致二次计算复杂度 $O(|\mathcal{E}|^2)$，这严重影响了大规模推荐系统的计算效率。其他基于历史嵌入的 GNN 加速方法 [18, 50] 也面临类似的全聚合问题。

4.2.2.2. LTGNN 的高效方差减少 (Efficient Variance Reduction, EVR)

为了进一步降低二次计算复杂度，LTGNN 提出周期性地 (periodically) 计算历史嵌入聚合，而不是在每个训练迭代中都计算。

为此，LTGNN 引入了两个内存变量 (memory variables)：

• $M_{in}$: 存储历史输入嵌入。

• $M_{ag}$: 存储完全聚合的历史嵌入，即 $M_{ag} = \tilde{A} M_{in}$。

  这些内存变量 $M_{in}$ 和 $M_{ag}$ 在每个训练周期 (epoch) 结束时更新一次。这种设计被称为高效方差减少 (EVR)。

EVR 的前向传播公式为： $$\begin{array}{r l r} (\hat{\boldsymbol X}^k)^{EVR} = \hat{\boldsymbol A} ({{\cal E}}_{out}^{k-1} - {{\cal M}}_{in}) + {{\cal M}}_{ag} & & (\approx \tilde{\boldsymbol A} {{\cal E}}_{out}^{k-1}), \\ (\hat{\boldsymbol E}_{out}^k)^{EVR} = (1 - \alpha) (\hat{\boldsymbol X}^k)^{EVR} + \alpha {{\cal E}}_{in}^k & & (\approx {{\cal E}}_{out}^k), \end{array}$$ 其中：

• $(\hat{\boldsymbol X}^k)^{EVR}$ 是方差减少后的聚合结果。

• ${{\cal E}}_{out}^{k-1}$ 是前一迭代的输出嵌入。

• ${{\cal M}}_{in}$ 是周期性更新的输入内存变量。

• ${{\cal M}}_{ag}$ 是周期性更新的聚合内存变量。

• ${{\cal E}}_{in}^k$ 是当前迭代的输入嵌入。

  图 1(c) 形象地展示了这种采样算法。

同样地，EVR 也可以应用于后向计算。对称地，方程 (19) 中的后向计算可以表示为： $$\begin{array}{r l r} & (\hat{\boldsymbol {G}}^k)^{EVR} = \hat{\boldsymbol {A}} (\frac{\partial \mathcal{L}}{\partial E_{in}^{k-1}} - M_{in}^\prime) + M_{ag}^\prime & (\approx \tilde{\boldsymbol {A}} \frac{\partial \mathcal{L}}{\partial E_{in}^{k-1}}), \\ & (\frac{\widehat{\partial \mathcal{L}}}{\partial E_{in}^k})^{EVR} = (1 - \alpha) (\hat{\boldsymbol {G}}^k)^{EVR} + \alpha \frac{\partial \mathcal{L}}{\partial E_{out}^k} & (\approx \frac{\partial \mathcal{L}}{\partial E_{in}^k}), \end{array}$$ 其中：

• $M_{in}^\prime$ 存储历史输入梯度。
• $M_{ag}^\prime = \tilde{A} M_{in}^\prime$ 维护完全聚合的梯度。

4.2.2.3. 随机聚合与 $\hat{\boldsymbol A}$ 的构建

在 Algorithm 1 的训练过程中，对于每个 mini-batch 采样的目标节点集合 $B$（包括用户、正向物品和负向物品），LTGNN 对 $B$ 中的每个目标节点 $u$ 采样 $D$ 个随机邻居（包括节点本身，不重复），形成采样邻居集合 $\hat{N}(u)$。原始邻居集合为 N(u)。

随机邻接矩阵 $\hat{\boldsymbol A}$ 的元素定义如下： $$\hat{\boldsymbol A}_{u,v} = \left\{ \begin{array}{l l} \displaystyle \frac{|{\cal N}(u)|}{D} \tilde{\boldsymbol A}_{u,v}, \quad \mathrm{if} u \in {\cal B} \mathrm{and} v \in \hat{\cal N}(u) \\ 0, \qquad \mathrm{otherwise} \end{array} \right. .$$ 基于此，矩阵形式的嵌入传播 $\hat{X} = \hat{A}E$ 等效于节点级的随机聚合： $$\hat{\pmb x}_u = \sum_{v \in \hat{N}(u)} \frac{|N(u)|}{D} \tilde{\pmb A}_{u,v} \pmb e_v, \qquad \forall u \in \pmb {B} .$$ 这个 $\hat{\pmb x}_u$ 是精确聚合 $x_u = \sum_{v \in N(u)} A_{u,v} \pmb e_v$ 的无偏估计量。其无偏性证明如下： $$\begin{array}{l} { {\displaystyle \mathbb{E}[\hat{\pmb x}_u] = \frac{|N(u)|}{D} \mathbb{E}[\sum_{v \in \mathcal{N}(u)} \tilde{A}_{u,v} \pmb e_v \mathbb{I}(v \mid u)] } } \\ { ~ = \displaystyle \frac{|N(u)|}{D} \sum_{v \in \mathcal{N}(u)} \tilde{A}_{u,v} \pmb e_v \mathbb{E}[\mathbb{I}(v \mid u)] } \\ { ~ = \displaystyle \frac{|N(u)|}{D} \sum_{v \in \mathcal{N}(u)} \tilde{A}_{u,v} \pmb e_v \frac{C_{|N(u)|-1}^{D-1}}{C_{|N(u)|}^D} } \\ { ~ = \displaystyle \sum_{v \in \mathcal{N}(u)} \tilde{A}_{u,v} \pmb e_v = x_u , } \end{array}$$ 其中 $\mathbb{I}(v \mid u)$ 是指示函数 (indicator function)，当 $v$ 被采样为目标节点 $u$ 的邻居时等于 1，否则为 0。这个无偏性对于前向和后向计算都成立。

4.2.2.4. LTGNN 训练过程 (Algorithm 1)

以下是 LTGNN 的详细训练过程：

算法 1: LTGNN 的训练过程 输入: 用户-物品交互 $\mathcal{R}$; BPR 批次大小 $B$; 训练轮次 $E$ 输出: 优化后的用户-物品嵌入 $E_{in}^{final}$

1. 初始化训练迭代计数器 $k \leftarrow 0$;
2. 初始化用户-物品嵌入 $E_{in} \sim \mathcal{N}(\mu, \sigma^2)$;
3. for $epoch = 1 ... E$ do
4. 计算方差减少内存 $[M_{in}, M_{ag}] \leftarrow \text{ComputeMemory}(\mathcal{R}, E_{in})$; // $O(|\mathcal{E}|d)$
5. for sample B interactions\hat{\mathcal{R}}^+from\mathcal{R}^+

**do** // $\frac{|\mathcal{E}|}{B}$ 个批次
6.     获取训练数据 $\hat{O} = \{(u, i, j)|(u, i) \in \hat{\mathcal{R}}^+ , (u, j) \in \mathcal{R}^-\}$;
7.     获取目标节点集合 $B = \bigcup_{(u,i,j) \in \hat{O}} \{u, i, j\}$;
8.     为 $B$ 中的每个目标节点采样随机邻居，以获取采样邻接矩阵 $\hat{A}$;
9.     根据公式 (21) 和 (22) 获取前向输出 $E_{out}$; // $O(n_B Dd)$
10.    计算损失函数 $\mathcal{L}_{BPR}$ (公式 (2)) 和输出层梯度 $\frac{\partial \mathcal{L}}{\partial E_{out}^k}$; // $O(Bd)$
11.    根据公式 (23) 和 (24) 计算隐式梯度 $\frac{\partial \mathcal{L}}{\partial E_{in}^k}$; // $O(n_B Dd)$
12.    使用任意优化器更新嵌入表 $E_{in}^{k+1} \leftarrow \text{UPDATE}(E_{in}^k, \frac{\partial \mathcal{L}}{\partial E_{in}^k})$; // $O(n_B d)$
13.    将 $E_{out}^k$ 和 $\frac{\partial \mathcal{L}}{\partial E_{in}^k}$ 存储到内存中，以备下一个训练迭代使用;
14.    $k \leftarrow k+1$;
15. **end for** // 循环总成本 $O(|\mathcal{E}|Dd)$
16. **end for**
17. **return** 优化后的嵌入 $E_{in}^{final}$。

    **内存变量计算 (`ComputeMemory`):** 在每个 epoch 开始时，通过对 $E_{in}$ 进行全图聚合来更新 $M_{in}$ 和 $M_{ag}$。这步操作的复杂度为 $O(|\mathcal{E}|d)$。

#### 4.2.2.5. 复杂度分析
在每个训练周期 (epoch) 中，效率瓶颈主要在于第 9 行和第 11 行的前向和后向计算。
*   根据公式 (25)，随机邻接矩阵 $\hat{A}$ 中有 $n_B D$ 条边（其中 $n_B$ 是 mini-batch 中的目标节点数，$D$ 是每个目标节点采样的邻居数）。
*   因此，方差减少邻居聚合的计算复杂度为 $O(n_B Dd)$，其中 $d$ 是嵌入维度。
*   由于内部训练循环（第 5-15 行）重复 $\frac{|\mathcal{E}|}{B}$ 次（其中 $|\mathcal{E}|$ 是总交互数，$B$ 是 mini-batch 大小），并且 $B$ 和 $n_B$ 具有相同的量级。
*   所以，LTGNN 的总计算复杂度为 $O(\frac{|\mathcal{E}|}{B} \cdot n_B Dd) = O(|\mathcal{E}|Dd)$。

    考虑到 $D$ 是一个小的常数，LTGNN 的复杂度不再依赖于 $|\mathcal{E}|^2$ 或 $L$（层数），而是**线性地 (linearly)** 依赖于边数 $|\mathcal{E}|$。这显著降低了计算成本。

**与基线模型的复杂度比较:**

以下是原文 Table 1 提供的复杂度比较：
以下是原文 Table 1 的结果：

| Models | Computation Complexity
| :----- | :---------------------
| LightGCN | $O( \frac{1}{B} L|\mathcal{E}|^2d)$
| PinSAGE | $O(|\mathcal{E}| D^L d^2)$
| MF | $O(|\mathcal{E}|d)$
| NCF | $O(|\mathcal{E}| L d^2)$
| LTGNN | $O(|\mathcal{E}|Dd)$

*   **LightGCN** 的复杂度为 $O(\frac{1}{B}L|\mathcal{E}|^2d)$，与 $|\mathcal{E}|$ 呈平方关系。
*   **PinSAGE** 的复杂度为 $O(|\mathcal{E}|D^L d^2)$，与层数 $L$ 呈指数关系。
*   **MF** 和 **NCF** 的复杂度分别为 $O(|\mathcal{E}|d)$ 和 $O(|\mathcal{E}| L d^2)$，它们是线性的。
*   **LTGNN** 的复杂度 $O(|\mathcal{E}|Dd)$，在 $D$ 为小常数时，实现了与 MF 相当的线性复杂度。

    值得注意的是，LTGNN 的方差减少聚合策略不会额外增加线性复杂度。方差减少的聚合操作与 PinSAGE 中普通的邻居采样具有相同的复杂度。而用于计算和更新方差减少内存的额外开销为 $O(|\mathcal{E}|d)$，这与最简单的 MF 模型效率相当。这意味着 LTGNN 在不牺牲训练效率的前提下，有效地减少了随机误差。

### 4.2.3. 模型推理 (Model Inference)
模型训练完成后，可以使用优化后的输入嵌入 $E_{in}^{final}$ 来预测用户偏好。
*   **最直接的方法:** 直接使用公式 (21)-(22) 进行推理，然后通过内积预测用户-物品交互。
*   **更精确的方法:** 由于训练过程中历史计算的复用可能引入微小误差，导致 $E_{out}^{final}$ 与准确的 PPNP 固定点 $E_{PPNP}^{final}$ 存在偏差。因此，另一种选择是在推理时，通过多层 APPNP 传播（如公式 (12)-(13)）来计算更精确的 $E_{PPNP}^{final}$。这种方法虽然略微增加了推理时间，但能减少训练和推理行为不一致 (behavior inconsistency) 带来的误差。

    论文指出，两种推理选择都能准确预测用户偏好，且对推荐性能影响不大。实际中，他们选择计算 $L=1$ 的输出嵌入作为输入，即 $E_{in}^{final}$。

## 4.3. 图像分析

![该图像是论文中的示意图，展示了LTGNN模型的核心部分，包括(a)隐式建模，公式为$\\mathbf{E}_{*} = (1-\\alpha) \\hat{A} \\mathbf{E}_{*} + \\alpha \\mathbf{E}_{in}$；(b)基于历史嵌入的一步求解器；(c)高效方差减少的邻居采样方法，图示了采样与聚合的流程。](/files/papers/690b14fc079665a523ed1d5a/images/1.jpg)
**图像 1: LTGNN 的隐式建模和高效方差减少**

这幅图直观地展示了 LTGNN 的三个核心组成部分：
*   **(a) 隐式建模 (Implicit Modeling):** 顶部方框显示了 LTGNN 的核心思想，即通过固定点方程 $E_{*} = (1-\alpha) \hat{A} E_{*} + \alpha E_{in}$ 来定义输出嵌入 $E_{*}$。这表明模型通过迭代收敛到一种平衡状态来捕获长程依赖，而不是通过堆叠多层显式 GNN。
*   **(b) 基于历史嵌入的一步求解器 (One-step Solver with Historical Embeddings):** 中间部分展示了如何实际地求解这个固定点。它通过将前一迭代的输出嵌入 $E_{out}^{k-1}$ 作为当前迭代的初始化，并进行单步传播，来近似当前迭代的输出 $E_{out}^k$。即 $E_{out}^k = (1-\alpha) \tilde{A} E_{out}^{k-1} + \alpha E_{in}^k$。这种设计使得模型在计算上保持高效，同时通过迭代间的积累实现长程建模。
*   **(c) 高效方差减少的邻居采样 (Efficient Variance-Reduced Neighbor Sampling):** 底部展示了如何处理邻居聚合。它结合了采样的邻接矩阵 $\hat{A}$ 和周期性更新的内存变量 $M_{in}$、 $M_{ag}$。采样部分 $\hat{A}(E_{out}^{k-1} - M_{in})$ 用于在当前 mini-batch 中进行高效的梯度计算，而 $M_{ag}$ (预计算的全聚合历史嵌入) 则作为方差减少的基线，以弥补采样的信息损失。这种方法确保了采样的效率和误差控制。

# 5. 实验设置

## 5.1. 数据集
论文使用了三个真实世界数据集来评估 LTGNN 的性能：

1.  **Yelp2018:**
    *   **来源:** 由 NGCF [42] 和 LightGCN [23] 基线发布。
    *   **规模:** 31,668 用户，38,048 物品，1,561,406 次交互。
    *   **特点:** 中等规模的推荐数据集。

2.  **Alibaba-iFashion:**
    *   **来源:** 可在 GitHub 仓库中找到。
    *   **规模:** 300,000 用户，81,614 物品，1,607,813 次交互。
    *   **特点:** 中等规模的推荐数据集，用户数量较 Yelp2018 大。

3.  **Amazon-Large:**
    *   **来源:** 基于 Amazon Review Data 网站上的评分文件构建。具体选择了三个最大的子集（图书、服装鞋饰珠宝、家居厨房），并保留了在所有三个子集中共享的用户交互（占总用户的 7.9%）。
    *   **数据预处理:**
        *   显式评分转换为隐式交互：只保留评分大于 4 的交互。
        *   数据质量控制：遵循广泛使用的 10-core 设置 [25, 41, 42]，移除交互次数少于 10 的用户和物品。
    *   **规模:** 872,557 用户，453,553 物品，15,236,325 次交互。
    *   **特点:** 大规模推荐数据集，用于验证模型在大规模场景下的可扩展性。

        以下是原文 Table 3 提供的详细数据集统计信息：
以下是原文 Table 3 的结果：

| Dataset        | \# Users | \# Items | \# Interactions
| :------------- | :------- | :------- | :--------------
| Yelp2018       | 31,668   | 38,048   | 1,561,406
| Alibaba-iFashion | 300,000  | 81,614   | 1,607,813
| Amazon-Large   | 872,557  | 453,553  | 15,236,325

选择这些数据集是为了全面评估模型在不同规模（中等规模和大规模）和不同类型（Yelp 的本地服务、Alibaba 的时尚电商、Amazon 的综合电商）推荐场景下的性能和可扩展性。Amazon-Large 数据集尤其具有挑战性，能够有效验证方法处理工业级大规模数据的能力。

## 5.2. 评估指标
论文采用推荐系统中两个广泛使用的评估指标：召回率 (Recall@K) 和归一化折损累计增益 (Normalized Discounted Cumulative Gain, NDCG@K)。默认设置 $K=20$，并报告所有测试用户的平均结果。

### 5.2.1. 召回率 (Recall@K)
1.  **概念定义:** 召回率衡量的是模型在推荐列表中成功识别出用户真正感兴趣的物品的比例。它关注的是模型“找回”相关物品的能力，即在推荐的 K 个物品中，有多少是用户实际交互过的。召回率越高，说明模型遗漏用户感兴趣物品的可能性越小。
2.  **数学公式:**

\text{Recall@K} = \frac{1}{|U|} \sum_{u \in U} \frac{|\text{R}(u) \cap \text{T}(u)|}{|\text{T}(u)|}
3.  **\text{符号解释}:**
    *   $U$: \text{测试用户集合。}
    *   $|U|$: \text{测试用户集合中的用户数量。}
    *   $\text{R}(u)$: \text{为用户} $u$ \text{生成的} Top-K \text{推荐列表。}
    *   $\text{T}(u)$: \text{用户} $u$ \text{在测试集中实际交互过的物品集合（真实正样本）。}
    *   $|\text{R}(u) \cap \text{T}(u)|$: \text{用户} $u$ \text{的} Top-K \text{推荐列表中与实际交互物品集合重叠的数量。}
    *   $|\text{T}(u)|$: \text{用户} $u$ \text{在测试集中实际交互过的物品数量。}

### 5.2.2. \text{归一化折损累计增益} (Normalized Discounted Cumulative Gain, NDCG@K)
1.  **\text{概念定义}:** NDCG \text{是一种综合考虑推荐列表质量和物品位置的指标。它不仅关注相关物品是否被推荐，还关注这些相关物品在推荐列表中的排名。排名靠前的相关物品会获得更高的权重（更大的增益），而排名靠后的相关物品则增益较小。}NDCG \text{的值越高，表示推荐列表越好，即相关物品不仅被推荐，而且排名靠前。}
2.  **\text{数学公式}:**
\text{NDCG@K} = \frac{1}{|U|} \sum_{u \in U} \frac{\text{DCG@K}(u)}{\text{IDCG@K}(u)}

其中，DCG@K 的计算公式为：

\text{DCG@K}(u) = \sum_{j=1}^{K} \frac{2^{\text{rel}_j} - 1}{\log_2(j+1)}
\$\$
IDCG@K (Ideal DCG@K) 是理想情况下，用户 $u$ 的推荐列表所能达到的最大 DCG@K 值（即所有相关物品按最高相关性从高到低排列）。

3. 符号解释:
   • $U$: 测试用户集合。
   • $|U|$: 测试用户集合中的用户数量。
   • $\text{DCG@K}(u)$: 用户 $u$ 的推荐列表中，前 K 个物品的折损累计增益。
   • $\text{IDCG@K}(u)$: 用户 $u$ 的理想推荐列表中，前 K 个物品的折损累计增益，作为归一化因子。
   • $j$: 推荐列表中物品的排名（从 1 到 K）。
   • $\text{rel}_j$: 排名第 $j$ 的物品与用户 $u$ 的相关性得分。在隐式反馈场景中，通常将相关物品的 $\text{rel}_j$ 设为 1，不相关物品设为 0。

5.3. 对比基线

为了全面评估 LTGNN 的性能和效率，论文将其与以下基线模型进行比较：

5.3.1. 经典协同过滤模型

• MF (Matrix Factorization) [31]: 经典的矩阵分解模型，通过用户和物品嵌入的内积预测交互。
• NCF (Neural Collaborative Filtering) [25]: 使用深度神经网络替代 MF 中的内积，以更强的非线性能力建模用户-物品交互。

5.3.2. GNN-based 推荐系统

• GC-MC (Graph Convolutional Matrix Completion) [1]: 早期将图卷积网络应用于推荐系统，通过图卷积自编码器补全交互矩阵。
• PinSAGE [49]: 针对大规模推荐场景设计的 GNN 模型，通过邻居采样实现可扩展性，并在工业界有广泛应用。
• NGCF (Neural Graph Collaborative Filtering) [42]: 通过消息传递机制明确建模高阶协同信号。
• DGCF (Disentangled Graph Collaborative Filtering) [43]: 尝试解耦不同的协同信号，以学习更精细的用户和物品表示。
• LightGCN [23]: 简化了 NGCF，移除冗余的非线性激活和特征变换，成为高性能的 GNN 推荐骨干模型。

5.3.3. LightGCN 的可扩展变体 (Scalable Variants of LightGCN)

为了公平比较，论文还实现了 LightGCN 结合典型 GNN 可扩展性技术后的变体：

• LightGCN-NS (Neighbor Sampling): LightGCN 结合了 GraphSAGE [22] 风格的邻居采样，以减少聚合计算量。
• LightGCN-VR (Variance Reduction): LightGCN 结合了 VR-GCN [4] 的方差减少技术，以在采样时控制误差。
• LightGCN-GAS (Global Aggregation and Storage) [18]: LightGCN 结合了 GNNAutoScale [18] 中基于历史嵌入的全局聚合和存储技术，以近似全聚合结果。

5.3.4. 额外基线 (附录 A.3)

• GTN (Graph Trend Filtering Networks) [12]: 作为最新的注重准确性的 GNN 骨干模型之一，也被用于与 LTGNN 比较。

  选择这些基线模型旨在全面评估 LTGNN 在性能和效率两方面的优势。MF 和 NCF 代表了经典的、可扩展性强的非 GNN 方法。GC-MC、PinSAGE、NGCF、DGCF 和 LightGCN 代表了不同演进阶段的 GNN-based 推荐模型，其中 LightGCN 是目前最流行的 GNN 骨干。LightGCN 的可扩展变体则直接对比了 LTGNN 在可扩展性方法上的创新。

5.4. 参数设置

• 实现框架: PyTorch 和 PyG 库。
• 通用设置:
  • 嵌入维度 (embedding size): 64。
  • BPR 批次大小 (BPR batch size): 2048。
  • 负样本数量 (negative sample size): 1。
• LTGNN 特定参数:
  • 学习率 (learning rate): 在 {5e-4, 1e-3, 1.5e-3, 2e-3} 中调优。
  • 权重衰减 (weight decay): 在 {1e-4, 2e-4, 3e-4} 中调优。
  • 优化器: Adam [29]。
  • 遥传因子 $\alpha$: 在 [0.3, 0.7] 范围内以 0.05 步长进行网格搜索。
  • 传播层数 $L$: 默认固定为 1。
  • 采样邻居数量 $D$: 在 {5, 10, 15, 20} 中搜索。
• 基线模型参数: 遵循其官方实现和论文建议设置。LightGCN 变体的层数 $L$ 基于 LightGCN 的最佳选择设置，其他超参数在与 LTGNN 相同的范围内搜索并报告最佳结果。
• 实验重复性: 所有实验重复五次，使用不同的随机种子，并报告平均结果。

6. 实验结果与分析

本节将详细分析 LTGNN 在推荐性能和效率方面的实验结果，并探讨其设计选择的有效性。

6.1. 推荐性能 (RQ1)

以下是原文 Table 2 提供的整体推荐性能比较结果： 以下是原文 Table 2 的结果：

从表 2 的结果可以得出以下观察：

• LTGNN 的优越性能: LTGNN 在所有三个数据集上都取得了与最强基线相当或更好的结果。
  • 在 Yelp 和 Alibaba-iFashion 数据集上，LTGNN 甚至优于所有基线模型。
  • 在 Amazon-Large 数据集上，LightGCN (L=3) 的 Recall@20 略高于 LTGNN (L=1)，但 LTGNN (L=1) 的 NDCG@20 优于 LightGCN (L=3)。考虑到 LTGNN 仅使用一个嵌入传播层和非常少的采样邻居，其效率远高于 LightGCN (L=3)。
• GNN 可扩展变体的性能牺牲: LightGCN 的可扩展变体（LightGCN-NS、LightGCN-VR、LightGCN-GAS）在大多数情况下以牺牲推荐性能为代价来提高可扩展性。例如，在 Amazon-Large 数据集上，这些变体的表现远不如原始的 LightGCN。
• LTGNN 兼顾性能与效率: 相比之下，LTGNN 在效率更高的同时，却能保持甚至超越这些变体的推荐性能。
• GNN 在大规模数据集上的挑战: 虽然 NGCF 和 LightGCN 等 GNN-based 方法在性能上优于 MF 和 NCF 等早期方法，但许多 GNN 模型（如 GC-MC、NGCF、DGCF）在 Amazon-Large 这样的大规模数据集上出现了内存不足 (OOM) 的情况。这凸显了在大规模工业场景中追求可扩展 GNN 的必要性。

6.2. 效率分析 (RQ2)

以下是原文 Table 4 提供的三个数据集上的运行时间比较： 以下是原文 Table 4 的结果：

从表 4 的运行时间比较中，可以得出以下结论：

• LTGNN 与单层 LightGCN 的效率: LTGNN (L=1) 在运行时间上与单层 LightGCN 采样变体（如 LightGCN-NS (L=1)）相当，并且优于原始 LightGCN (L=1) 和 LightGCN-VR (L=1)。这与论文在第 3.2 节的复杂度分析一致。特别是，LTGNN 优于 LightGCN-VR (L=1)，这得益于其改进和高效的方差减少 (EVR) 技术。
• LTGNN 显著优于多层 GNN: LTGNN (L=1) 相较于层数大于一的基线模型，展现出显著提升的计算效率。结合表 2 的结果，这表明 LTGNN 能够在保持高推荐性能的同时，大幅提高计算效率。
• LTGNN 与 MF 的可扩展性: 虽然 LTGNN 的运行时间比 MF 长几倍（Amazon-Large 上约 5.5 倍），但考虑到复杂度分析中常数因子 (Dd vs $d$) 的差异，LTGNN 已经展现出与 MF 相似的良好缩放行为。这支持了 LTGNN 在大规模推荐中相对于其他 GNN-based 方法具有更好的可扩展性。
• 大规模数据集上的意外观察: 在大规模数据集上，全图 LightGCN (例如 LightGCN (L=3) 在 Amazon-Large 上为 2999.35s) 竟然比带邻居采样的 LightGCN-NS (L=3) 运行时间更短 (4291.37s)。这主要是因为随机采样的 CPU 开销较高，限制了 GPU 的利用率。

6.3. 消融研究 (RQ3)

6.3.1. 隐式图建模的有效性

论文通过比较不同层数下 LTGNN 和 LightGCN 的性能来评估隐式图建模的有效性。

图像 2: 隐式图建模的有效性

这幅图展示了在 Yelp2018 和 Alibaba-iFashion 数据集上，LTGNN 和 LightGCN 在不同传播层数下的 Recall@20 和 NDCG@20 性能。

• 观察 1: 强大的长程建模能力: LTGNN 仅使用 1 或 2 个传播层，其性能就能超越 LightGCN 使用 3 层甚至更多层时的表现。这强有力地证明了 LTGNN 提出的隐式建模方法在捕获长程协同信号方面的强大能力，即使在低层数下也能达到优异的性能。
• 观察 2: 最佳层数选择: 增加 LTGNN 的传播层数并不能显著提高其性能。这意味着 $L=1$ 或 $L=2$ 是 LTGNN 在性能和可扩展性之间取得平衡的最佳选择。这进一步验证了隐式建模通过迭代间信息积累来捕获长程依赖的有效性，而不需要通过堆叠大量层来显式地延长信息传播路径。

6.3.2. 高效方差减少的有效性

论文通过比较 LTGNN 及其变体在不同邻居数量下的推荐性能来验证高效方差减少 (EVR) 算法的有效性。

图像 3: 高效方差减少的有效性

这幅图展示了在 Yelp2018 和 Alibaba-iFashion 数据集上，LTGNN (使用 EVR) 与其朴素邻居采样变体 LTGNN-NS (不使用 EVR) 在不同采样邻居数量 $D$ 下的 Recall@20 和 NDCG@20 性能。

• 观察 1: EVR 显著提升性能: 无论采样邻居数量 $D$ 如何，使用高效方差减少的 LTGNN 始终优于其朴素邻居采样变体 LTGNN-NS。这表明 EVR 能够有效地减少邻居采样引入的近似误差，从而提高推荐性能。
• 观察 2: 极低采样数下的稳定性: 即使在极端条件下（例如每个目标节点只采样 2 个邻居），使用 EVR 的 LTGNN 仍然表现出惊人的稳定性能。这表明 LTGNN 在仅使用一个传播层和少量随机邻居的情况下，具有在保持高性能的同时实现超高效率的巨大潜力，这对于大规模推荐系统至关重要。

6.3.3. 数值分析

为了验证 LTGNN 捕获长程依赖的能力和 EVR 的有效性，论文进行了数值分析，比较模型输出与理想 PPNP 嵌入的相对误差。

图像 4: 数值分析

这幅图展示了在 Yelp2018 和 Alibaba-iFashion 数据集上，LTGNN 及其变体（LTGNN-NS 和 LTGNN-Full）的输出嵌入 $E_{out}^k$ 与理想 PPNP 嵌入 $E_{PPNP}^k$ 之间的相对误差（即 $||E_{out}^k - E_{PPNP}^k||_F / ||E_{PPNP}^k||_F$）随训练迭代次数的变化。LTGNN 和其变体均设置为 $L=1$。

• 观察 1: 长程依赖建模能力: 在两个数据集上，LTGNN 的输出在大约 4000 次训练迭代（不到 10 个训练周期）后收敛到 PPNP 的嵌入。这证明了 LTGNN 仅使用一个传播层，通过迭代间的历史信息积累，确实能够捕获用户-物品图中的长程依赖。
• 观察 2: EVR 的有效性: 比较 LTGNN (使用 EVR) 与 LTGNN-NS (朴素邻居采样)，可以发现没有方差减少的邻居采样会严重损害 LTGNN 的建模能力，导致更大的误差和更慢的收敛。而 LTGNN (使用 EVR) 的收敛曲线与 LTGNN-Full (精确的全邻居聚合) 相似，表明 EVR 能够有效地在采样效率和准确性之间取得平衡，使其在近似全聚合方面表现良好。

6.4. 额外实验 (附录 A.3)

6.4.1. 与 GTN 的比较

以下是原文 Table 5 提供的与 GTN 的推荐性能比较： 以下是原文 Table 5 的结果：

| Dataset | Yelp2018 | | Alibaba-iFashion | | Amazon-Large | | :--------------- | :--------------- | :--------- | :--------------- | :--------- | :--------------- | :--------- | Method | Recall@20 | NDCG@20 | Recall@20 | NDCG@20 | Recall@20 | NDCG@20 | GTN | 0.0679* | 0.0554* | 0.0994* | 0.0474* | OOM | OOM | LTGNN | 0.0681* | 0.0562* | 0.1079* | 0.0510* | 0.0294 | 0.0259

* 标记的结果是在 GTN 官方设置下获得的。

以下是原文 Table 6 提供的与 GTN 的运行时间比较： 以下是原文 Table 6 的结果：

* 标记的结果是在 GTN 官方设置下获得的。

• 性能方面: 在 GTN 官方设置下，LTGNN 在 Yelp2018 和 Alibaba-iFashion 数据集上均取得了比 GTN 更好的 Recall@20 和 NDCG@20 性能。在 Amazon-Large 数据集上，GTN 出现 OOM，而 LTGNN 成功运行并给出了结果。
• 效率方面: LTGNN 在 Yelp2018 和 Alibaba-iFashion 数据集上的运行时间显著短于 GTN (例如在 Yelp2018 上 24.5s vs 97.8s)。 这些结果表明，即使与最新的、以准确性为导向的 GNN 骨干模型 GTN 相比，LTGNN 也在推荐性能和可扩展性方面展现出优势。

6.4.2. 超参数 $\alpha$ 的影响

图像 5: 超参数 $\alpha$ 的影响

这幅图展示了在 Yelp2018 和 Alibaba-iFashion 数据集上，超参数 $\alpha$ 对 Recall@20 和 NDCG@20 指标的影响。

• 鲁棒性: LTGNN 对超参数 $\alpha$ 表现出相当的鲁棒性。在 $\alpha \in [0.35, 0.55]$ 的范围内，性能下降并不明显。
• 最佳实践: 论文建议可以将 $\alpha$ 设置为 0.5 作为起点，因为它代表了在捕获长程依赖和保留局部结构表达能力之间的折中点，然后进行粗略的网格搜索以找到最优设置。

6.4.3. 不同方差减少设计的影响

为了评估不同方差减少设计对推荐性能的影响，论文比较了 LTGNN 的四种变体：

• LTGNN-NS: 使用隐式建模和朴素邻居采样（无方差减少）。

• LTGNN-FVR: 仅使用前向方差减少 (Forward Variance Reduction)。

• LTGNN-BVR: 仅使用后向方差减少 (Backward Variance Reduction)。

• LTGNN-BiVR: 同时使用前向和后向方差减少 (Bidirectional Variance Reduction)。

  以下是原文 Table 7 提供的消融研究结果： 以下是原文 Table 7 的结果：

| Dataset | Yelp2018 | | Alibaba-iFashion | | :--------------- | :--------------- | :--------- | :--------------- | :--------- | Method | Recall@20 | NDCG@20 | Recall@20 | NDCG@20 | LTGNN-NS | 0.06285 | 0.05137 | 0.08804 | 0.04147 | LTGNN-BVR | 0.06309 | 0.05160 | 0.08878 | 0.04185 | LTGNN-BiVR | 0.06321 | 0.05194 | 0.09241 | 0.04338 | LTGNN-FVR | 0.06380 | 0.05224 | 0.09335 | 0.04387

从表 7 可以得出：

• 方差减少的有效性: 所有带有方差减少的 LTGNN 变体（LTGNN-BVR, LTGNN-BiVR, LTGNN-FVR）都优于没有方差减少的 LTGNN-NS，这再次证明了 EVR 方法的有效性。
• 前向方差减少的突出表现: 仅使用前向方差减少 (LTGNN-FVR) 就足以获得令人满意的推荐性能，并且在两个数据集上都取得了最佳结果。
• 双向方差减少的局限: 令人惊讶的是，同时使用双向方差减少 (LTGNN-BiVR) 并没有超越单独的前向方差减少。论文指出这将在未来的工作中进行深入探讨。

6.4.4. 详细效率分析

为了更好地理解 LTGNN 的效率，论文对 LTGNN 和 MF 进行了详细的阶段性效率分析。

以下是原文 Table 8 提供的 LTGNN 与 MF 的详细效率比较： 以下是原文 Table 8 的结果：

从表 8 的详细效率分析中，可以得出以下观察：

• 负采样开销可忽略: 对于 MF 和 LTGNN，负采样 (Neg. Samp.) 的计算成本都非常小，对总运行时间影响微乎其微。

• LTGNN 训练核心的线性行为: 在排除邻居采样时间后，LTGNN 的模型训练 (Training) 时间与边数 $|\mathcal{E}|$ 呈线性关系，这与 MF 的训练时间相似。这验证了 LTGNN 在大规模和工业推荐场景中的高可扩展性。

• EVR 的高效性: 维护和更新方差减少内存 (Memory Access) 的计算开销非常小 (<0.005s)，这验证了所提出的 EVR 方法的高效率。

• 邻居采样是主要瓶颈: LTGNN 的主要额外计算开销来自目标节点的邻居采样 (Neigh. Samp.) 过程，在大规模 Amazon-Large 数据集上占总运行时间的一半以上 (512.55s / 705.91s $\approx$ 72.6%)。这阻碍了 LTGNN 实现完美的线性缩放行为。

  潜在优化方向: 论文指出，邻居采样的高开销是一个实现问题，可以通过更好的工程解决方案来改进。例如，可以采用 PinSAGE [49] 中的重要性采样 (importance sampling) 方法，为交互图中的每个节点分配一个固定的邻居集合，从而避免昂贵的随机采样过程。这被列为未来的工作。

7. 总结与思考

7.1. 结论总结

本文提出了 LTGNN (Linear-Time Graph Neural Networks)，一个为解决 GNN 在大规模推荐系统可扩展性挑战而设计的新模型。LTGNN 的核心创新在于结合了隐式图建模和高效方差减少邻居采样技术。通过将 GNN 传播建模为固定点方程，并使用单层传播和迭代间历史信息积累来近似求解，LTGNN 能够捕获长程协同信号，同时显著减少对深层 GNN 架构的依赖。高效方差减少 (EVR) 策略通过周期性更新历史聚合嵌入，进一步降低了邻居采样带来的计算开销和随机误差。实验结果表明，LTGNN 仅使用一个传播层和少量邻居，就能在与现有 GNN 模型相当的推荐性能下，将计算复杂度降低到与经典 MF 模型相当的线性时间 $O(|\mathcal{E}|Dd)$，从而展现出在大规模推荐应用中的巨大潜力。

7.2. 局限性与未来工作

• 双向方差减少的有效性: 论文发现同时使用前向和后向方差减少 (BiVR) 并没有超越单独的前向方差减少 (FVR)。这一现象的原因尚未深入探究，是未来工作的一个方向。
• 邻居采样的高开销: 尽管 LTGNN 实现了理论上的线性时间复杂度，但在实际实现中，邻居采样过程仍然占据了总运行时间的大部分，成为效率瓶颈。
• 扩展到更多推荐任务: 目前 LTGNN 主要在协同过滤任务上进行了验证。未来计划将其设计扩展到其他推荐任务，如点击率 (CTR) 预测。
• 工业级部署: 探索 LTGNN 在工业推荐系统中的实际部署。

7.3. 个人启发与批判

7.3.1. 个人启发

• 隐式建模的威力: 这篇论文为 GNNs 的设计提供了一个全新的视角。传统上，我们认为深层 GNN 才能捕获长程依赖，但 LTGNN 证明了通过隐式建模和迭代间的信息积累，单层 GNN 也能实现这一目标，这极大地降低了计算复杂度。这种思想可能适用于其他需要深层网络但受限于计算资源的图任务。
• 方差减少的关键性: 在大规模图上，采样是不可避免的，而采样引入的误差是性能下降的主要原因。LTGNN 提出的高效方差减少 (EVR) 策略，通过巧妙地利用周期性更新的历史信息来弥补采样损失，是兼顾效率和准确性的典范。这种思想对于任何涉及大规模数据采样和聚合的机器学习任务都具有借鉴意义。
• 理论与实践的结合: 论文不仅提出了理论上具有线性复杂度的模型，还通过大量实验证明了其在实际大规模数据集上的有效性和高效性。这种理论创新与实践落地相结合的研究范式值得学习。
• 工程优化的重要性: 详细的效率分析揭示了即使理论上最优的算法，其实现细节（如邻居采样的开销）也可能成为实际瓶颈。这提醒研究者在设计新算法时，不仅要考虑理论复杂度，还要关注实际实现中的工程优化。

7.3.2. 批判

• “隐式”的解释深度： 尽管论文将模型称为“隐式”，但其核心实现仍是一个迭代求解过程，只是将迭代从模型层内转移到了训练迭代间。对于初学者而言，这种“隐式”与传统意义上的隐式层（如 Deep Equilibrium Models 中通过反向传播解优化问题）可能存在概念上的混淆。论文在介绍时可以更清晰地界定其“隐式”的具体含义和实现方式。
• BiVR 未优于 FVR 的原因： 实验结果显示双向方差减少 (BiVR) 并没有带来额外的好处，甚至略逊于单独的前向方差减少 (FVR)。这可能表明后向传播中的方差减少机制设计可能存在未被充分利用的潜力，或者其对梯度的影响比对前向传播嵌入的影响更复杂。未来的工作应深入分析这一现象，例如是否后向传播的梯度更“稀疏”或“噪声更大”，使得方差减少难以有效。
• 邻居采样效率的进一步提升： 论文指出邻居采样是主要的效率瓶颈，并建议采用重要性采样等工程优化。虽然这被列为未来工作，但考虑到其对整体效率的巨大影响，如果在当前工作中能提供一个初步的工程优化方案（即使只是概念性的），将进一步增强模型的说服力。
• 超参数 $\alpha$ 的敏感性分析： 尽管论文指出 LTGNN 对 $\alpha$ 鲁棒，但在一些 GNN 模型中，$\alpha$ 的微小变化可能导致显著的性能差异（例如过平滑）。如果能提供更详细的敏感性分析，例如在更宽泛的 $\alpha$ 范围内或在不同数据集特性下的表现，将有助于更全面地理解模型对该关键超参数的依赖性。
• 对非图数据或异构图的泛化能力： LTGNN 主要关注同构的用户-物品二分图。未来的工作可以考虑其如何泛化到包含多种节点类型和边类型（异构图）的推荐场景，或者如何在没有明确图结构的数据（如序列推荐）中应用隐式建模的思想。