唯快不破! 比LightGCN还要快10倍的UltraGCN

点击蓝字关注，提升学习效率

公式太长可以左右滑动哦~

UltraGCN: Ultra Simplification of Graph Convolutional Networks for Recommendation
https://dl.acm.org/doi/pdf/10.1145/3459637.3482291

1. 背景

• GCN已经在推荐系统领域得到了广泛的应用，但是消息传播减缓了训练期间GCN的收敛速度。
• LightGCN已经提出了一定的解决方式，摒弃了GCN中的权重和激活函数，但是仍然存在一定的问题。

1.1 LightGCN的缺陷

如上式所示为lightGCN的每一层的计算方式，它直接聚合这些节点而不采用可学习权重和激活函数。其中u表示用户，i表示item，N(u)表示用户邻接的item集合，N(i)表示item邻接的user的集合，d表示节点的度。如上图所示，LightGCN是通过多层layer堆叠进行多层次的消息传递，从而进行节点之间的聚合，最后将两者的embedding求内积。但是这种堆叠的方式会影响基于GCN的推荐系统的训练效率和效果。以第 层为例，将上面lightgcn的定义中的item和user的embedding做内积可以计算得到下式，其中他u，v表示用户；i，k表示item。从下式可以发现做完内积后，模型在多个维度上进行了建模，包括用户-用户，用户-item，item-item。通过挖掘这些关系使得基于图的协同过滤方法能够起到好的效果。

但是存在以下问题：

• 缺陷1：对于给定的用户u，item k和item i对应的权重不一样，分别为 ,即对待目标item和邻居item的权重不一致，而这是不合理的，同样对于user层面也是权重不一致。这可能会导致模型进入局部最优。
• 缺陷2：消息传递递归地将不同类型的关系组合到建模中，虽然这种协作信号应该是有益的，但linghtgcn的消息传递公式未能捕捉到它们不同的重要性，linghtgcn这样的多层堆叠方式可能会引入噪声，有歧义的关系等。
• 缺陷3：多层堆叠消息传递可以捕获高阶信息，但是lightgcn只是堆叠了2,3层后性能就开始下降了，这可能是过度平滑造成的。

2. UltraGCN方法

UltraGCN总体框架如图所示，是一个多任务的形式，包含主损失和两个辅助损失。

2.1 User-Item图上学习

由于上述消息传递的局限性，作者开始质疑在协同过滤中，显式传递消息是否是必要的。缺陷3中提到了过度平滑问题，即经过多层消息传播后，每个节点的embedding可能会几乎一样，这就是简单理解的过度平滑。根据文献[1]，经过无限层的消息传播后，最终结果会趋向于一个固定值。而作者想通过跳过这种无限层的消息传递而近似达到模型的收敛状态。定义收敛条件为下式，即最后两层保持不变，前一层和聚合邻居信息后的输出的embedding是一样的时候。

那么，当达到收敛情况时，embedding可以写为下式，可以发现没有了上标，item的embedding也是同理。

简化后可以写成下式，这里的简化就是 左移后，等式左右除以系数

， item的embedding计算方式也是类似的。那么， 当每个节点达到下式的情况后，模型就是达到了消息传递的收敛状态了。

从上面的推导，我们可以发现，本文作者并不是采用多层堆叠的显式消息传递，而是希望直接近似得到收敛状态。为此，最直接的方式，就是最小化上面等式两边的误差，本文作者通过标准化embedding后，采用最大化两者的内积的方式，即最大化余弦相似度，如下式：

为了方便优化，作者引入了激活函数sigmoid和负对数似然，损失函数如下：

但是当前损失依旧会受到过度平滑的影响，因此，作者通过负采样来缓解该问题，加上负采样后，损失函数可以改写为下式，作者采用随机负采样得到负样本对。

2.1.1 优化

通常采用BPR或者BCE两类损失函数，本文采用BCE作为主损失函数，公式如下，形式和 类似，同样负采样通过随机负采样实现，并且为了简单起见，这两个损失采用相同的样本集(当然也可以不一样)。

这两个损失都是基于User-Item图的，因此现在可以得到一个base形式的损失函数即：

2.2 Item-Item图上学习

除了user-item关系，item-item，user-user关系同样很重要，在之前的方法中，这两类关系都是在user-item的图上进行消息传递过程中隐式学习到的，如“缺陷”上面的公式，是通过内积后，建立了不同的隐式关系。这不仅导致了上述“缺陷1”中的不合理的边权重分配，而且未能捕捉到不同类型关系的相对重要性。但是UltraGCN不是基于显式消息传递的，因此可以更加灵活的学习到别的关系以及不同的重要性，它可以扩展到不同的关系，user-user，item-item等。这里作者根据item的共现性构建item-item图。公式如下，其中A为原来的邻接矩阵，计算后得到 为带权邻接矩阵，表示item-item的共现关系。

根据上面 系数得到的过程，同样可以得到item-item上计算的系数w如下式，其中 表示度。

但是这里得到的矩阵G是一个稠密矩阵，直接优化可能存在较多的噪声，因此对于item i只保留topk的最相似的items S(i)。相似性通过上面的权重w衡量。相较于直接去构建item-item的共现关系图，本文采用的是通过user-item的邻接矩阵来构建，这样降低了整个多任务模型训练的难度，损失函数如下，对于每个正（u，i）对，首先对于在S(i)中的item j，构造K个加权正（u，j）对，即上面说的取topk的操作。然后用相似度分数w对其进行加权。

因此总体的损失函数如下：

3. 实验结果

可以发现结果还是有一定提升的。时间对比：

4. 总结

本文从推荐系统中的GCN存在的问题出发，再结合lightGCN本身存在的问题，提出了UltraGCN。该方法更加简洁，从时间上就可见一斑。主要的创新点在于，作者不在通过显式的信息传播，不再像LightGCN那样传统的方式去进行堆叠，而是通过设定收敛方式构建损失函数，从而避免了多层堆叠带来的问题。