协同过滤(2)： KDD2020- HyperGraph CF 基于超图

前言

发表在KDD2020上的一篇关于通用CF推荐的论文
码字不易，好心人随手点个赞
本文为自己的论文阅读笔记，如有错误/问题欢迎评论区指正，
本篇文章为本人原创内容，如需转载引用，请务必提前联系本人并在文中附上原链接及相应说明，包括作者信息（阿瑟）

摘要

协同过滤推荐系统是当今众多推荐系统中最流行和最重要的推荐方法之一。

尽管已经被广泛采用，但是现有的基于 cf 的方法，从矩阵分解到新兴的基于图的方法，在训练数据非常有限的情况下表现不佳（数据稀疏问题）。

本文首先指出了造成这种不足的根本原因，并指出现有基于 CF 的方法固有的两个缺点，即: 1)用户和物品建模不灵活; 2)高阶相关性建模不足。

在这种情况下，文中提出了一个双通道超图协同过滤(DHCF)框架来解决上述问题。

首先，引入双通道学习策略(Dual-Channel)，全面利用分治策略，学习用户和物品的表示，使这两种类型的数据可以优雅地相互连接，同时保持其特定属性。

其次，利用超图结构对用户和具有显式混合高阶相关性的物品进行建模。提出了跳跃超图卷积(JHConv)方法，实现高阶关系嵌入的显式和有效传播。

引言

推荐系统的核心是一系列的推荐算法，这些算法能够**根据用户的个人特征有效地从爆炸式信息筛选出信息。协同过滤是目前最受欢迎和广泛采用的方法之一。

CF 持有一个基本的假设，当向用户提供推荐时: 那些行为相似的人(例如，经常访问同一个网站)很可能在物品(例如，音乐、视频、网站)上分享相似的偏好。
为了实现这一点，一个典型的基于 CFbased 方法执行一个两步策略: 它首先利用历史交互区分相似的用户和项目; 然后基于上面收集的信息，向特定用户生成推荐。

现有的 CF 方法可以分为三类。

第一类 CF 方法是基于用户的方法，基于用户之间的相似性来产生推荐，用户与用户之间的相关性描述了不同用户与同一物品的交互之间的关系。
类似地，基于物品的方法，作为第二类方法，只使用物品相关性进行推荐。
基于用户的方法和基于物品的方法预测用户-物品关系时都只采用了部分历史信息，因此不可避免地会带来较差的预测效果。
第三种 CF 方法，包括矩阵分解和基于图的方法，尝试整合用户和物品来推荐。矩阵分解方法将用户和物品建模在一个隐空间中。基于图的方法构建图中同时表示用户和项目，可以联合研究这些用户和物品之间的相关性，从而进一步提高性能。

虽然 CF 方法已经研究了多年，但仍然存在局限性，特别是在训练的先验知识非常有限的情况下。为了理解这些缺陷，深入挖掘现有 CF 方法的内在机制得到以下局限性:

用户和物品建模不灵活。基于图的 CF 方法虽然将用户和项目模型化为不可区分的节点，但用户和物品之间并不存在必要的区别。当一个物品与很多用户连接时，这样的物品可能会相当受欢迎。相反，当用户链接到不同的物品时，这并不意味着用户很受欢迎(可以理解为：用户和物品在实际交互中有区别，图方法忽略了这种区别，将其看作相同的节点)。在这种情况下，需要对用户和物品进行更加灵活的建模。
高阶关系建模不足。用户和物品之间的高阶关系对于建模至关重要。现有的方法试图结合高阶相关性，而使用的图结构对高阶相关性建模和处理有约束，因为只有成对的连接可以表示在一个图中。（传统图结构的局限性，只能表示二元关系，一条边连接两个点）

针对问题一：双通道建模，采用分而治之的策略，既整合用户和物品信息，又保持用户和物品各自特性。
针对问题二：引入超图的结构，构建跳跃超图卷积JHConv，提取高阶关系。
具体来说，如上图所示，首先根据给定的用户和物品的数据构造多个连接组。这里的连接生成规则可以看作是描述原始数据的一个新的视角，可以灵活地定义。例如，它可以将具有相似行为但没有直接连接的用户关联起来，因此在连接组中基于这种关联规则构造的关系可以表示高阶相关性，从而构成超图中的超边。

基于这些生成的连接组，即超边，可以分别为用户和物品构造两个超图，即两个通道的表示。本文提出了一种新的跳跃超图卷积算法(JHConv) ，该算法通过聚合邻域的嵌入并引入先验信息，有效地在超图上进行信息传播。(与传统的基于图的方法对比，用户超图和项目超图，可以更灵活地进行复杂的数据关联建模，并与不同类型的数据结合。)

超图定义

超图定义为 $\mathbf{G}=(V, \mathbf{\varepsilon })$ ，V表示图节点， $\mathbf{\varepsilon }$ 表示超边集合，超图邻接矩阵 $\mathbf{H}$ 描述节点与超边的关系

此外还有节点度矩阵

和超边度矩阵

(均为对角阵)。
参考图卷积操作，超图的卷积操作可以定义为

其中训练参数为

文中给出了一个通俗的超图卷积解释，详细的知识需要看作者2019年在IJCAI上的相关的超图论文。
可以看作是对超图结构进行顶点-超边-顶点特征的两阶段变换。超图关联矩阵

\mathbf{H}

定义了从超边(列)到顶点(行)的消息传递路径。类似地，

\mathbf{H}^T

定义从顶点(列)到超边(行)的路径。
然后，通过超图上的信息传播过程来描述超图卷积。对角矩阵 Dv 和 De 用于特征归一化，对超图上的消息传递路径没有影响。首先，在

\mathbf{H}^T

下消息传递，根据超边集合顶点特征，形成超边特征;。然后通过

\mathbf{H}

聚合相关的超边特征，生成精细化的顶点特征。

DHCF模型

总体框架

在高层次上，DHCF 首先通过一个双通道超图框架学习用户和物品的两组嵌入，在此框架上，DHCF 通过计算用户和物品嵌入查找表的内积，进一步计算出用户-项目偏好矩阵。基于这样的偏好矩阵，DHCF 估计用户对某个商品感兴趣的可能性。

总体分为三步：

对用户和物品嵌入进行初始化
高阶信息传递 (high-order message passing)
联合信息传递 (joint message passing)

Step 1. Initialization

构建用户和物品嵌入矩阵：

而k个超边组可以根据自定义的关联规则来生成

可以通过融合不同的超边群来构造一个具有混合高阶相关性的超图关联矩阵

\mathbf{H}

f(\cdot)

表示超边融合操作

Step2. High-order Message Passing

为了在预定义的混合高阶关系上聚合相邻消息,执行以下高阶消息传递:

输出

M_u

和

M_i

分别从高阶邻居那里学到复杂的相关性。这里的邻居是一个抽象描述，超越了历史交互中的直接联系，它可以揭示潜在行为空间中的相似性。然后使用

M_u

和

M_i

联合更新

E_u

和

E_i

Step3. Joint Message Updating.

为了提取有区别的信息，我们对用户和物品定义为

JU(\cdot,\cdot)

表示任意可学习的网络。

综上所述，上述两个过程构成了一个集成的DHCF 层，允许对用户和物品进行明确的建模和编码，并通过强大的嵌入功能进一步更新和生成更精确的嵌入超图结构。这种精细嵌入可以进一步应用于推荐系统中的各种下游任务。

Jump Hypergraph Convolution 跳跃超图卷积

与传统 HGNNConv 相比，JHConv 允许模型同时考虑其原始特征和聚合相关表示，在另一方面，这样的 resnet结构的跳跃连接使模型能够避免由于集成了许多其他连接而导致的信息稀释。

High-order Connectivity Definition 高阶关联定义

引入高阶关联来实现构建超边，根据自定义的规则分别对用户和物品进行高阶关联提取

用户侧

定义1: 物品的 k 阶可达邻居。在用户-物品交互图，更具体地说是二部图中，如果在 itemi 和 itemj 之间存在一个相邻顶点序列(即一条路) ，且该路径中的用户数小于 k，itemi (itemj)是 itemi (itemi)的 k 阶可达邻居。

定义2：物品的 k阶可达用户。在物品-用户二部图中，如果用户 j 和物品 k 之间存在直接交互作用，则用户 j 是 itemi 的 k 阶可达邻居，而物品 k 是 itemi 的 k 阶可达邻居。

对于 itemi，其 k 阶可达用户集称为 $B_u^k(i)$ 。从数学上讲，超图可以定义在一个集簇上，其中每个集代表一个超边。因此，这里可以通过物品的 k 阶可达用户集构建超边。

然后在用户 k 阶可达规则的基础上构造高阶超边组，该超边组可表示为:

该超边集合节点为用户。K阶物品可达矩阵可以定义为下面的形式：

用户-物品二部图对应的邻接矩阵为

那么用户的K阶可达规则可以表示为矩阵：

矩阵形式看起来很复杂，其实就是一个邻接矩阵变换的过程，查找到两个节点之间K关联

假设通过K阶可达规则，构造a个超边组，最后的超图需要将这a个超边组做融合，见上面的总体框架中的描述。

文中直接用矩阵拼接的形式，将多个超边邻接矩阵进行拼接。(这样多个 $N \times M$ 的矩阵直接拼接，最后整个矩阵会很大呀)

物品侧

同理，按照相似的K阶可达的规则，对物品进行分析，构成物品的超边(N个用户，M个物品)

这部分的操作可以简单地理解为通过用户-物品二部图，找到用户和物品之间的高阶关联/图上的多跳联系，通过下图可以直观地理解整个高阶关联操作的过程

DHCF设置

1. Construction of Hybrid High-order Connections

对于用户和物品，都取K=1/2，构成两个超边集组

前面总体框架中提到的具体实现方式如下图所示：

完整的矩阵计算过程如下：

模型训练

采用标准的pairwise learning的形式，用BPRLOSS作为损失函数：

实验设计

主要在4个数据集上进行实验，前两个为公开数据集：

在实验中，每个用户观察到的交互中的10% 被随机选择用于训练，其余的数据用于测试。这样的设置增加了 CF 任务的难度，因为模型只能获取非常有限的观察到的交互。此外，由于数据的高度稀疏性，它可以很好地评价模型从有限的隐式数据集中挖掘有用信息的能力。对于所有四个数据集，每个用户至少有两个用于训练的交互。

部分实验结果如下：

总结

这篇工作基于超图结构，提出了一种新的CF框架，与基于图神经网络的CF相比，超图结构更符合实际情况；此外，双通道的思路也值得借鉴，之前也分析的一篇双通道BPR的论文。近年来，基于图神经网络的推荐已经成为研究主流，而其中超图相关的工作少之又少，最近看到的另一篇是SIGIR2020上的一篇Next Item Recommendation with Sequential Hypergraphs，在超图神经网络上并没多大的改进，重点仍然在于如何用这种结构去解决存在的问题。

END

如果觉得有用，欢迎点赞关注赞赏，若对推荐感兴趣欢迎评论区/私信交流~~~