Graph Neural Transport Networks with Non-local

Attentions for Recommender Systems

用于推荐系统的非局部注意的图神经传输网络

来源：WWW 2022

摘要：通常，GNN通过在本地邻居之间传播和聚合消息来生成用户/项的嵌入。因此，GNN捕获远程依赖关系的能力在很大程度上取决于它们的深度。然而，简单地训练深度gnn会产生瓶颈效应，例如过拟合和过平滑等，无法得到较好的训练效果。为了解决这个问题，作者提出了图最优传输网络(GOTNet)来捕获在不增加GNN深度的情况下的长期依赖关系。GOTNet能够只使用浅层GNN来同时捕获图中的本地和非本地消息，从而避免了深度GNN的瓶颈效应。实验结果表明，与现有的GNN相比，GOTNet取得了更好的性能。

1 背景与简介

    图神经网络现已被广泛应用在推荐任务中，并且目前成熟的图神经网络推荐模型往往采用两层到四层的结构。虽然在理论上，深度GNN应该具有更强的建模复杂图结构的表达能力，能够学习到远距离依赖关系，但深度GNN在实践中遇到了几个挑战。首先，由于GNN的复杂度与层数呈指数关系，因此计算效率不高，导致对训练时间和GPU内存的需求很高。其次，它使优化变得困难。具体地说，深度GNN存在过拟合、过平滑和可能的梯度消失的问题。这些“瓶颈效应”可能会抑制深层GNN的潜在优势。第三，隐式用户项图，通常是复杂的，并表现出拓扑同质性或异质性的混合。因此，如果gnn没有很好地正则化，简单地训练深度GNN可能会导致意想不到的结果。

    作者提出了一个高度可伸缩的图最优传输网络(GOTNet)，以在不增加GNN深度的情况下捕获长期依赖关系。GOTNet结合了图的卷积和聚类方法，分别实现了有效的局部编码和非局部编码。具体来说，在每一层中，都使用图卷积，通过聚合来自本地邻居的信息来计算节点嵌入。然后，GOTNet对用户和项目的嵌入进行k-Means聚类，以获得他们的图级表示（例如，用户/项目质心）。进一步提出了一种非局部注意算子来度量每对（节点、质心）之间的相似性，使远程消息能够在遥远但相似的节点之间进行通信。

    同时，很关键的一点是，作者提出了一个全微分的k-均值聚类方法，通过将其转换为一个等价的最优传输任务，通过贪婪的辛克霍恩算法有效地求解。因此，gnn和k-Means的参数可以在尺度上进行联合优化。并且，GOTNet是与模型无关的，可以应用于任何gnn。作者对四个公共数据集进行了广泛的实验。结果表明，GOTNet在捕获远程消息的有效性方面的好处，导致5.21%的∼19.45%的性能提高。

2 基于GNN的推荐简介

    GNN的设计包括嵌入、聚合、池化和优化。

    嵌入层：首先对每个用户和项目的嵌入进行初始化，这里使用的是潜入查找表的方法：

    其中，u和i表示一个用户和一个项目的id；eu（0）∈Rd和ei（0）∈Rd分别为用户u和项目i的初始嵌入，d为嵌入大小。

    聚合层：GNN进行图卷积来聚合邻居的特征：

    池化层：GNN通常采用池化技术来获取一个节点的最终嵌入：

      优化：最后可以通过内积来估计用户对目标项目的偏好如下：

    贝叶斯个性化排序损失可以采用[32]来优化模型参数，这可以通过最小化下面的式子来实现：

    其中i表示u的正样本，j表示u的负样本，u，i，j一起组成了一个正负样本对。用α控制Θ的L2范数以防止过拟合。

    在等式中的聚合器（2）在从邻居那里收集消息方面起着关键的作用。然而，图的卷积本质上是局部算子，即eu在每次迭代中只从其一阶邻居Nu中收集信息。很明显，LightGCN捕获远程依赖关系的能力在很大程度上取决于它的深度：至少需要k个GNN层来捕获距离目标节点有k个跳数的信息。然而在上面我们已经阐述了深层GNN遇到的种种困难。于是，作者提出了这样一个问题，即是否可以通过使用gnn的浅层架构来捕获长期依赖关系。

3 GOTNET方法

图1 GOTNet概述

    GOTNet主要包括两个阶段：1)通过k-Means聚类获得用户和项目的聚类感知表示；2)通过成对的节点-质心注意力而不是节点-节点注意力来捕获长期依赖关系。如图1所示，虽然用户u1和u2彼此相距2跳，但u2的信息可以用质心c1紧凑地表示，质心c1可以通过一层GNN传递给u1。接下来，我们将详细介绍GOTNet。

  3.1 k-means

    由于具有相似兴趣的用户会购买相似的项目，作者将每一层gnn的用户/项目嵌入集群到不同的簇中。这允许在任何位置的节点感知来自所有节点的上下文消息，这将有利于gnn学习长期依赖关系。

    让表示等式中gnn的第l层中的所有N个用户嵌入，作者对用户嵌入执行k-Means聚类。为了使模型更加灵活，作者进一步通过投影函数把用户投影到空间，可以是一个神经网络，甚至是一个线性投影。这里作者简单地定义，1≤i≤N，其中W∈Rd×d是一个可训练的权重矩阵。然后在该低维空间中执行k-means聚类，通过最小化（6）获得K个用户质心

   其中， 表示用户i是否为质心k的簇成员，即，如果数据点被分配给集群ck，则为=1，否则为0。

    然而，解决等式（6）并不简单，因为涉及到另一个优化任务。由于k-Means中离散聚类分配的不可微性，em型方法不能使用标准的基于梯度的端到端学习与gnn或fθ联合优化。即如果把式6与bprloss做联合优化，由于这里=0或1，将会出现π·fθ在loss中进行反向传播更新参数时出现不可微的情况。于是作者将k-均值重写为一个最优传输（OT）任务，并推导出了一个联合训练的完全可微损失函数。

3.2 通过OT的可微k-means聚类

    k-Means和OT之间的联系是由Pollard发现的。粗略地说，OT算法等价于约束k-Means聚类。利用等式中的最优运输计划来参数化k-均值，便可以提出一个新的k-Means目标如下：

    其中w=[n1，……，nK]表示簇比例，即nk是分区k中的点的数目，。表示K*1维的单位向量，表示N*1维的单位向量。S.T.1则可以表示为每个点对于k个中心的π和为1（是个软分配）。S.T.2则表示每个中心点对于所有点的比重加和为w。作者简单地为平衡分区设置n1=···=nK=N/K。此外，作者在这两个约束条件上都明确地引入了归一化因子1/N，它遵循了OT中的概率单纯形的条件，并且不影响损失。通过这样做，等式（7）成为一个标准的OT问题，可以将集群分配π视为一个传输计划，而将欧氏距离∥fθ(eui)−ck∥22视为传输成本。

    使用的等式（7）可以通过线性规划(LP)求解，但计算负担较大。通过在该领域常用的Sinkhorn算法引入熵正则化，通过限制最优传输问题解的复杂度，可以大幅降低的复杂度得到最优传输问题的近似解：

    其中，ε>0是一个正则化参数。已知LP算法在顶点上达到最优值，而熵项使最优值远离顶点，得到更平滑的可行区域。请注意，所有辛克霍恩算子都是可微的，这使得k-Means完全可微，并允许以随机方式与gnn和fθ进行联合训练。类似地，我们也可以用类似的方式来定义项目集群损失。

    当计算出最优运输计划π∗时，我们可以细化质心：,k=1,2...k。

3.3 注意力混合

单头非本地注意力机制

    在gnn中，节点嵌入通过迭代消息传递进行更新。对于每一层0≤l≤L，我们通过微分k-Means聚类获得一组用户集群。类似地，项目集群可以通过聚类项目嵌入计算，其中K和P分别是用户和项目集群的数量。需要注意的是，作者假设K和P的值在gnn内是不变的。

    受注意机制的启发，作者试图通过非局部节点质心注意来收集相关的远程信息，给定等式中的GNN嵌入和，以及来自(l−1)第一层的用户/项目中心，注意机制给出了输出向量：

    其中，ATTEND(·)表示输出注意力分数的函数，利用注意力分数来聚合每个质心的消息特征。本质上公式9依旧使用的是QKV键值对的注意力机制。e‘u(l)和e’u(l)分别是第l层中用户u和第i项的集群感知表示。这些具有集群感知功能的表示紧凑地总结了所有用户和项的拓扑信息，其中包含了图中的远程消息。

多头非本地注意力机制

    作者通过使用多个OT头进一步改进了GOTNet。作者将用户的嵌入投影到H个单独的子空间，即，其中是头h的权重矩阵。于是，我们可以获得H个集群感知的用户表示和项目表示，其中每个元素都使用等式 (9)进行计算.然后，将它们连接起来：

    其中，{、}∈Rd分别是用户u和项目i的多头集群感知表示；{Wu，Wi}是学习到的权重矩阵，将用户和项目的多头注意力投射到d维空间。

本地与非本地混合注意力机制

    在等式（2）中的和从邻居那里收集本地消息，而等式（10）的和从质心捕获非本地消息，作者进一步介绍了通过使用混合技术来混合局部和非局部注意的想法：

   其中， ∈[0,1]是l跳混合系数，服从（0,1）均匀分布。

3.4 GOTNet的优化

    GOTNet的总体目标是：

    其中，β和γ为对应的正则化系数。

    由于GOTNets建立在gnn之上，而主要的网络架构保持不变，GOTNets是与模型无关的，可以无缝地应用于任何gnn，如PinSage、NGCF和LightGCN。事实上，如果我们简单地在等式（12）中设置β=γ=0和在等式（11）中设置混合系数λ(l)=1，GOTNets本质上等同于原始的gnn。

4 实验

     4.1 数据集

    数据集采用Movielens-1M, Gowalla, Yelp-2018, and Amazon-Book

    4.2 实验结果

表1 实验结果

    4.3 实验分析

    过平滑的影响：

图3 过平滑实验

    训练深度gnns时存在过平滑现象。为了说明这种影响，作者在{2、4、6、8}范围内进行了不同数量的L层的实验。图3显示了在NDCG@20方面的结果。我们观察到，在叠加2层或4层时达到峰值，但深度的增加会导致性能下降。相比之下，非本地gnn(例如，Geom-GCN、NLGCN和GOTNet)继续受益于更深层次的架构。具体来说，GOTNet在所有数据集上都明显优于Geom-GCN和NLGCN。原因是GOTNet显式地采用了局部和非局部聚合的混合，以防止所有节点表示收敛到相同的值，即使是使用更深层次的结构。此外，我们的多头投影允许用户和项目在多个不同的空间中具有可区分的表示，这使得节点表示不那么相似，并缓解了过度平滑的问题。

稀疏推荐：

表2 稀疏推荐的效果

    如前所述，图卷积本质上是局部算子，这有利于高度节点从其邻居那里收集足够的信息。然而，许多真实世界的图通常是长尾的和稀疏的，其中有相当一部分节点具有较低的度。对于这些尾部节点，gnn只聚合来自少量邻居的消息，这可能是有偏倚的或代表不足的。为此，GOTNet展现了了非局部gnn对稀疏建议的有效性。为此目的，作者关注至少有5个交互，但少于10个交互的用户和项目。表2显示了Yelp和Amazon的结果。

参数设置实验：

图4 参数设置