WWW 2024 | 港理工等联合提出线性时间图神经网络，适用于大规模推荐系统

©PaperWeekly 原创 · 作者 | 谢淇名

单位 | 南京理工大学

研究方向 | 大语言模型

论文题目：
Linear-Time Graph Neural Networks for Scalable Reommendations

论文链接：
https://arxiv.org/pdf/2402.13973.pdf代码链接：
https://github.com/QwQ2000/TheWebConf24-LTGNN-PyTorch论文作者：
张嘉淏（香港理工大学），薛睿（北卡州立大学），范文琦（香港理工大学），徐鑫（香港理工大学），李青（香港理工大学），裴健（杜克大学），刘孝睿（北卡州立大学）

介绍

在当今信息爆炸的时代，推荐系统通过提供个性化的物品推荐，极大地提升了用户的网络体验。这些系统的关键在于有效理解用户与物品的历史交互，从而捕获用户偏好，精准预测用户未来的行为。

现代推荐系统中最具代表性的技术之一是协同过滤（CF），这一技术的核心目标在于将用户和物品表示为具有强大表征能力的低维嵌入向量，从而使得我们能够利用这些向量之间的相似关系来预测用户对物品的交互倾向。

早期的协同过滤方法，如基于矩阵分解（MF）和深度神经网络（DNNs）的模型，主要关注用户和物品的局部连接关系。这些模型提供了简单高效的解决方案，但是它们对于用户-物品交互中长距离关系的建模有所缺失，这限制了它们对用户偏好的表征能力。

近年来，由于图神经网络（GNNs）在理解用户-物品长程依赖关系上的巨大潜力，基于 GNNs 的推荐模型得到了研究者的广泛关注，并被证明能够有效提升推荐系统的预测性能。

尽管 GNNs 在部分推荐场景下取得了成功，这类模型在可扩展性（Scalability）上仍具有巨大的局限性，这限制了它们在工业级的大规模推荐系统中的广泛使用。

在本文中，研究者指出，现存的主流 GNNs 推荐算法，在计算复杂度上对于用户-物品交互记录的数量具有非线性的依赖关系，这使得此类模型在真实的大规模电商、短视频等场景下难以得到有效应用。

因此，本文着力解决这样一个悬而未决的问题：基于 GNNs 的推荐模型是否可以既像经典的 MF 和 DNNs 一样对数据线性扩展（scale linearly），又表现出优秀的长程建模能力和强大的预测性能？

在本文中，研究者的主要目标围绕保留 GNN 固有的强大表达能力，同时实现与 MF 和 DNNs 等传统 CF 模型相当的线性计算复杂度。然而，追求这种高度可扩展的 GNN 设计需要克服如下两个主要挑战：

GNN 层数与表达能力：增加 GNNs 中的层数可以捕获交互图中的长距离依赖关系，但是 GNN 的复杂度在层数很多时很难呈线性（比如 PinSAGE 的复杂度）。
邻居聚合与随机误差：GNN 层中每个目标节点聚合的邻居数量会极大地影响计算成本和近似误差。聚合所有邻居（例如 LightGCN）的成本很高，而随机采样的聚合会产生较大的随机误差（例如 PinSAGE）。

为了解决这些挑战，来自香港理工大学、北卡州立大学、杜克大学的研究者们提出了线性时间图神经网络（Linear-Time Graph Neural Networks, LTGNN）。该模型（如图 1 所示）将用户-物品交互图上的嵌入传播问题建模为一个不动点方程求解问题，并用一种仅包含一个传播层的 GNN 设计来有效求解这一不动点。这一设计利用了模型的历史输出，可以在无需叠加 GNN 传播层的前提下有效捕获图上的长程交互关系。除此以外，LTGNN 还包括一个高效的方差缩减（VR）邻居采样算法。该算法可以显著降低传播层需要聚合的邻居数量，并且有效应对由邻居采样引起的随机误差。研究者指出，LTGNN 的时间复杂度和 MF 相比仅相差一个微小的常数，这表明该模型对于大规模数据有非常良好的可扩展性，在工业级推荐场景下具有重的大应用潜力。

▲ 图1 模型结构图

方法

为了实现 GNNs 的线性复杂度，研究团队在原文 2.3 节中进行了详细的复杂度分析，该分析显示出线性时间 GNN 所需要的两大性质，即极少的聚合层的数量和较少的目标节点聚合邻居数量。研究者们首先提出了适用于推荐系统的隐式图建模，该方法可以通过复用过去的模型输出，有效降低聚合层数量。随后，对于聚合层的设计，研究者们还提出了一种具有高效方差缩减（Efficient Variance Reduction, EVR）的邻居聚合方法，从而使得每个目标节点仅需要聚合极少数量的邻居节点，而其他未被聚合的节点嵌入均可通过复用内存中保留的完整聚合快照（Full Aggregation Snapshot）补齐。

2.1 适用于推荐系统的隐式图建模

为了在减少聚合层数的同时，不牺牲 GNNs 的长距依赖表达能力，研究者们首先利用不动点方程建模 GNNs 在无限次传播下的平衡状态，从而使得长距依赖表达问题可以通过求解一个线性系统解决，避免了堆叠多个 GNN 层。具体来说，模型的输出可以被形式化为如下的方程求根过程：

考虑到过往的模型输出可以为方程求根提供更好的初始化，研究者们提出通过单个前向传播层求解该不动点方程，从而打通了通往线性时间 GNNs 的道路，如图 1(b) 所示：

其中是上一次训练迭代的模型输出。与多层嵌入传播相比，LTGNN 的单层设计非常高效，但仍然可以通过反复积累过去训练迭代的输出来捕获多跳邻居信息。由于模型的前向过程为不动点方程的求解过程，模型的前向输出仅由隐式的不动点方程决定，这导致模型的反向传播过程南以用简单的链式法则求解。因此，研究者们还推导了模型反向规则，并得到了如下所示的模型设计：

其中用到了前一个训练迭代的历史前向输出和梯度输出。

2.2 具有高效方差缩减的邻居聚合

在 2.1 节中介绍的 GNN 隐式建模与单层设计显著降低了 GNNs 的计算复杂度。例如，当层数时，PinSAGE 的复杂度仅为。若随机采样的邻居数量和嵌入向量维度是很小的常数，那么模型的时间复杂度将达到线性。然而，考虑到对于 GNNs 的随机误差有较大的影响，直接降低将会不可避免地影响 GNNs 的性能，这促使着我们追求一种平衡随机误差和计算成本的高效邻居采样设计。现有方法多采用方差缩减（Variance-Reduction, VR）等技术，以达到在减少邻居采样的数量的同时控制聚合随机误差的目的。此类方法一般复用上个训练迭代的历史嵌入，并用历史嵌入来弥补随机聚合中丢弃节点的嵌入向量。然而，研究团队发现这些方法在聚合历史嵌入时具有不利的计算复杂性，这与本文追求高效 GNN 设计的目的相悖。为了解决这个问题，研究者们提出了一种高效的 VR 邻居采样方法，在控制随机误差的同时实现与简单邻居采样相同的效率，从而保证了 LTGNN 的线性复杂度。该方法维护一个完整聚合的历史快照，周期性的计算历史嵌入的完整聚合，并且在进行聚合操作时，直接从内存中读出未采样节点的嵌入聚合结果，从而避免了传统 VR 技术中频繁而低效的历史嵌入聚合操作。这一技术被称为高效方差缩减（Efficient Variance-Reduction，EVR），并可表述为如下公式：

其中用于近似公式（18）中的一项，该公式中的第二项保持不变。这一算法的实现细节在图 1（c）中展示。

这种方差缩减方法也可以适用于反向梯度计算，如下列公式所示：

对于 LTGNN 的额外实现细节，以及详细的时间复杂度分析，在原文的第三章和附录的 A.1 小节中有更为详细的论述。

实验评估我们在两个中等规模数据集（包括 Yelp2018 和 Alibaba-iFashion）以及一个具有百万级别节点数量的大型数据集 Amazon-Large 上评估了我们提出的 LTGNN 和其他基线模型。由于本文主要关注 GNNs 在大规模数据集上的可扩展性，我们主要与推荐系统中最广泛使用的 GNN 骨干（backbone）模型 LightGCN 及其用典型的 GNN 可扩展性技术增强后的变体进行比较。除此以外，我们也比较了其他一些代表性的推荐骨干模型，如 NGCF，PinSAGE 等。3.1 推荐性能研究者在两个中等规模数据集（包括 Yelp2018 和 Alibaba-iFashion）以及一个具有百万级别节点数量的大型数据集 Amazon-Large 上评估了本文提出的 LTGNN 和其他基线模型。实验结果表明，即使只需要一个 GNN 嵌入传播层和少量一跳邻居，LTGNN 仍然与所有基线相比，取得了相当或更好的结果。

3.2 效率分析

为了体现 LTGNN 的运行效率，研究团队比较了 LTGNN 与目前最具代表性的模型 LightGCN 及其多种可扩展变体在三个数据集上的训练时间。可以发现，LTGNN 的性能虽然明显优于一层 LightGCN，与三层 LightGCN 相当或更优，但是其运行时间仅相当于一层 LightGCN 及其可扩展变体。结合表 2 的结果，可以发现 LTGNN 在保持高性能的同时，实现了计算效率的大幅提高。

3.3 参数分析

3.3.1 模型层数的影响作者进行了一项参数分析，对 LightGCN 和 LTGNN 使用相同的设置，并更改层数的数量，以显示模型层数和长程关系学习能力的关系。如图 2 所示，仅具有 1 或 2 个传播层的 LTGNN 比超过 3 层的 LightGCN 相比可以达到更好的性能。除此以外，还可以发现在 LTGNN 中添加更多传播层并不会显著提高其性能，这意味着或是平衡 LTGNN 性能和可扩展性的最佳选择。

3.3.2 采样邻居数量的影响

作者通过展示邻居数量对推荐性能的影响，来证明高效方差缩减（EVR）算法的有效性。如图 3 所示，无论邻居数量有多少，具有 EVR 的 LTGNN 始终优于其普通邻居采样变体（即 LTGNN-NS），这说明了 EVR 能够有效减少邻居采样引起的随机误差。

即使在极端条件下（例如，每个目标节点仅采样 2 个或 5 个邻居），具有 EVR 的 LTGNN 的推荐性能也相对稳定。这表明 LTGNN 在大规模推荐方面具有巨大潜力，因为与之前具有大量模型层数和邻居采样个数的模型相比，仅具有一个传播层和极少数随机邻居的 GNN 将非常高效。

总结

本文是香港理工大学、北卡州立大学以及杜克大学联合完成的大规模图神经网络论文，该文章已被数据挖掘领域顶级学术会议 The Web Conference 2024（WWW'24）接收。文中提出的模型利用隐式图建模和高效方差缩减采样等技术，实现了线性时间复杂度，以及和 MF 等传统推荐模型相似的扩展行为，展现出在工业大规模场景下为用户提供精确推荐服务的巨大潜力。

更多阅读