Dual Channel Hypergraph Collaborative Filtering 阅读笔记

KDD 2020

Shuyi Ji, Yifan Feng, Rongrong Ji, Xibin Zhao, Wanwan Tang, Yue Gao.

前置知识

• 超图

  超图是一种广义上的图，主要特点是一条边可以连接任意数量的顶点

  形式上，超图H是一个集合组 $G=(\mathcal{V}, \mathcal{E})$G=(V,E) : $\mathcal{V}$V为顶点，$\mathcal{E}$E为超边，$\mathcal{E}$E是$\mathcal{V}$V的非空子集的集合。

切入点

• 现象

  从矩阵分解到基于图的方法，都需要大量训练数据，训练数据有限的情况下性能较差

• 原因

  1. User-Item建模不灵活,没有对刻意对两类节点进行区分

     例如：Item的关联多说明Item比较流行，但User的关联多不能说明用户流行。

  2. 高阶关联建模不足

     传统图只能表示成对连接，对高阶关联的建模和处理有一定限制。

方法

作者提出了一个双通道超图协同过滤框架DHCF。

首先采用分治思想提出了双通道的学习策略，分别在User-item两个子超图上学习embedding.

然后利用JHConv方法来在超图上传播带有高阶关联信息的embedding

1. 超图建模

   • 关联矩阵

     $\mathrm{H} \in\{0,1\}^{|\mathcal{V}| \times|\mathcal{E}|}$H∈{0,1}∣V∣×∣E∣

     $h(v, e)=\left\{\begin{array}{ll}1 & \text { if } v \in e \\ 0 & \text { if } v \notin e\end{array}\right.$h(v,e)={10​ if v∈e if v∈/​e​

   • 度

     一个点有多少个边

     一个边上有多少个点

   • 超边

     解释性：把有相似行为但没有直接关系的User关联起来，通过这种方式来表示高阶关联。

   • 高阶关联

     1. Item的K阶可达邻居。

        Item A — User1 — ItemB — User2 — Item C

        如果链中两个Item之间的User小于K，就称这两个Item为K阶可达邻居。

     2. Item的K阶可达User。

        如果User和Item B 有直接交互，且Item B 是item A 的K阶邻居，则该User是Item A 的K阶可达User。

        

2. 超图定义

   Item的K阶邻居

   $\mathbf{A}_{i}^{k}=\min \left(1, \operatorname{power}\left(\mathbf{H}^{\top} \cdot \mathbf{H}, k\right)\right)$Aik​=min(1,power(H⊤⋅H,k))

   Item的K阶可达User

   $\mathrm{H}_{B_{u}^{k}}=\mathrm{H} \cdot \mathrm{A}_{i}^{k-1}$HBuk​​=H⋅Aik−1​

   考虑一阶和二阶可达的超图

   $\left\{\begin{aligned} \mathbf{H}_{u}=f\left(\mathcal{E}_{B_{u}^{1}}, \mathcal{E}_{B_{u}^{2}}\right) &=\mathbf{H}_{B_{u}^{1}} \| \mathbf{H}_{B_{u}^{2}} \\ \mathbf{H}_{i}=f\left(\mathcal{E}_{B_{i}^{1}}, \mathcal{E}_{B_{i}^{2}}\right) &=\mathbf{H}_{B_{i}^{1}} \| \mathbf{H}_{B_{i}}^{2} \end{aligned}\right.$⎩⎨⎧​Hu​=f(EBu1​​,EBu2​​)Hi​=f(EBi1​​,EBi2​​)​=HBu1​​∥HBu2​​=HBi1​​∥HBi​2​​

   矩阵形式定义

   $\mathbf{H}_{u}=\mathbf{A} \|\left(\mathbf{A}\left(\mathbf{A}^{\top} \mathbf{A}\right)\right)$Hu​=A∥(A(A⊤A))

   $\mathbf{H}_{i}=\mathbf{A}^{\top} \|\left(\mathbf{A}^{\top}\left(\mathbf{A} \mathbf{A}^{\top}\right)\right)$Hi​=A⊤∥(A⊤(AA⊤))

​ 其中A是传统User-item二部图的邻接矩阵，$A \in\{0,1\}^{N \times M}$A∈{0,1}N×M

​ 高阶关联的主要信息包含在$\mathbf{A}\left(\mathbf{A}^{\top} \mathbf{A}\right)$A(A⊤A) 中，也就是实现了user-item-user-item这一作用链（二阶关联）的建模。

3. 超图卷积

   $\mathrm{X}^{(l+1)}=\sigma\left(\mathrm{D}_{v}^{-1 / 2} \mathrm{HD}_{e}^{-1} \mathrm{H}^{\top} \mathrm{D}_{v}^{-1 / 2} \mathrm{X}^{(l)} \Theta^{(l)}\right)$X(l+1)=σ(Dv−1/2​HDe−1​H⊤Dv−1/2​X(l)Θ(l))

   其中度矩阵作用类似GCN中的度矩阵，起到归一化的作用。

   主要部分是H HT 表示信息的传播路径：顶点-超边-顶点，实现了顶点间的高阶信息交互。

4. DHCF框架

   

   • 高阶消息传递

     $\left\{\begin{aligned} M_{u} &=\operatorname{HConv}\left(E_{u}, H_{u}\right) \\ M_{i} &=\operatorname{HConv}\left(E_{i}, H_{i}\right) \end{aligned}\right.${Mu​Mi​​=HConv(Eu​,Hu​)=HConv(Ei​,Hi​)​

     Mu和Mi分别从他们的高阶邻域学习了复杂的关联关系。

     HConv具体实现为：跳跃超图卷积

     $\mathbf{X}^{(l+1)}=\sigma\left(\mathbf{D}_{v}^{-1 / 2} \mathbf{H} \mathbf{D}_{e}^{-1} \mathbf{H}^{\top} \mathbf{D}_{v}^{-1 / 2} \mathbf{X}^{(l)} \Theta^{(l)}+\mathbf{X}^{(l)}\right)$X(l+1)=σ(Dv−1/2​HDe−1​H⊤Dv−1/2​X(l)Θ(l)+X(l))

     1. 同时考虑了自身信息和邻居信息
     2. 借鉴了Resnet的思想，使得网络更容易优化。

   • 联合消息更新

     $\left\{\begin{aligned} E_{u}^{\prime} &=\mathrm{JU}\left(M_{u}, M_{i}\right) \\ E_{i}^{\prime} &=\mathrm{JU}\left(M_{i}, M_{u}\right) \end{aligned}\right.${Eu′​Ei′​​=JU(Mu​,Mi​)=JU(Mi​,Mu​)​

     JU可以是任意神经网络，用第二个参数更新第一个参数。作者采用MLP。

5. 优化方法

   Loss:

   $\mathcal{L}=-\sum_{\left(u, i^{+}, i^{-}\right) \in \mathcal{T}}-\ln \sigma\left(\hat{r}_{u i^{+}}-\hat{r}_{u i^{-}}\right)+\lambda\|\Theta\|_{2}^{2}$L=−∑(u,i+,i−)∈T​−lnσ(r^ui+​−r^ui−​)+λ∥Θ∥22​

   BPRLoss

实验

数据集：

实验结果：

结果分析：

方法	分析
GC-MC	只用了一层GCN，只考虑一阶邻居。丢弃了当前节点的信息，鲁棒性较差。
PinSage	引入高阶连通性，保留当前节点和邻居信息
NGCF	节点更新策略更复杂，具有双重可训练参数，数据小的时候，容易出现过拟合。
DHCF	明确建模了高阶关联，减少了模型参数

感悟

1. 找论文的能力得到了进一步提升，先前缺少追踪最前沿成果的经验，找论文原文花费了不少时间。

   记录下经验：会议官网，预印本平台，ResearchGate，搜索引擎都无果的情况下，可以按照作者的线索来寻找。本文是通过作者的实验室主页找到的，如果作者的个人主页和实验室主页都找不到的话，也可以考虑发邮件向作者请求PDF档。
   本文连接 ,感谢作者！

2. 传统图卷积的本意是在同构图中提取信息，近年来的方法一般是通过拼接邻接矩阵和其转置为大矩阵的方法，把User-item看做同种结构，一起学embedding。如果要考虑多种关联，传统思路一般是增加GCN的层数，并融合在一起。但是增加网络层数可能会带来训练过程中的梯度消失等问题。

   作者通过超图的概念，一举两得，同时达到了分开学习更好Embedding 和 建模高阶关联的作用。

3. 超图中如何表示高阶关联，一开始比较模糊，自建了一个小网络跟着论文一步步推导之后才逐渐明了。

4. 类似NCF，给出了超图上做协同过滤的框架，其中超图的定义，超图卷积，联合消息更新都可以自定义。提出框架的工作一般会比单独的模型影响力大，后续写作过程中可以想办法把工作提炼升华成框架的形式。

5. 分治思想比较重要，往往让一套embedding去拟合两个目标，如本文中提到同一套embedding同时拟合user和item,NCF中提到的同一套embedding同时拟合MF和MLP，效果都不如分别训练embedding去拟合各自的目标。