image.png
Enhanced Graph Learning for Collaborative Filtering via Mutual Information Maximization
https://dl.acm.org/doi/pdf/10.1145/3404835.3462928
1. 背景
基于user-item二分图的图神经网络推荐系统已经得到了广泛的应用与研究。对于一些隐式反馈，用户没有被观察到的一些行为，在图中不会存在边，在图学习的过程中会学习到一些隐式行为，而这些行为中，有一部分是能够反映用户真实偏好的。但是这些行为中会混合着无用信息，我们可以理解为噪声 。本文所做的工作就是如何有效的捕获这些真实偏好。
在本文中，作者认为节点embedding学习和图结构学习可以在 CF 中相互增强 ，因为更新的节点嵌入是从先前的图结构中学习的，反之亦然（即，根据当前节点嵌入结果优化新更新的图结构）。因此本文EGLN模型，该模型主要包含两方面：
让增强图学习模块和节点embedding模块在没有任何特征输入的情况下迭代地相互学习。 设计局部-全局一致性优化函数来捕捉增强图学习过程中的全局属性
2. EGLN方法
2.1 总体结构 文中涉及到一个概念残差图（residual graph） ，这里所谓的残差图可以简单理解为一个新的邻接矩阵，他是加在原始矩阵后面的，所以取了这个名字。 用户集
U(|U|=M) ，item集
V(|V|=N) ，交互矩阵为
R \in \mathbb{R}^{M\times N} ，user-item的二分图
\mathcal{G}=\{U\cup V,A\} ，邻接矩阵可以定义为：
\mathrm{A}=\left[\begin{array}{cc}
\mathbf{0}^{M \times M} & \mathbf{R} \\
\mathbf{R}^{T} & \mathbf{0}^{N \times N}
\end{array}\right]
。
在以往的模型中，通常就是直接将作为输入，在图学习的过程中会学校到一些隐式行为，而这些行为中，有一部分是能够反映用户真实偏好的。但是这些行为中会混合着无用信息，我们可以理解为噪声。因此，相对于一直采用固定不变的图进行学习，本文在学习过程中对图结构进行优化 。增强的图结构可以表示为：，其中,表示需要学习的残差非负边权重矩阵。使用残差图学习结构，因为原始user-item二分图中的所有现有边都表示用户的积极偏好，并且对于用户和item的embedding学习很有价值。通过使用残差图结构，修正后的图结构通过未观察到的行为中的可能的积极偏好得到增强(这句话有点绕，简而言之就是通过可能的潜在偏好修正图结构 )。
因此，想要得到一个好的增强图，就需要找到一个好的残差图。因此，所提方法包含两部分：残差图学习和节点embedding学习。这两个方面是紧密相关的，一方面 ，残差图学习需要依赖于现有的embedding从而得到可能的
A^E ，其中的
A^R 可以建模为
A^R=GL(P,Q,U,V) ，其中GL为图学习模块；另一方面 ，在得到了残差图后，可以利用基于图的CF来优化得到更好的embedding：
[P,Q,U,V]=GCF(A+A^R) 。P，Q 表示初始embedding；U，V 表示经过信息传播后得到的最终embedding。框架图如下图所示：
2.2 利用Embedding学习增强图 正如上面所说的，我们需要用两个模块分别迭代来相互优化，这一节就是利用已有的embedding来学习得到更好的增强图。其中
\mathrm{A}^{R}=\left[\begin{array}{cc}
0^{M \times M} & \mathrm{~S} \\
\mathrm{~S}^{T} & 0^{N \times N}
\end{array}\right]
，
S \in \mathbb{R}^{M\times N} 表示残差的用户偏好。其中每个位置的计算方式为：
\mathbf{s}_{a i}=\sigma\left(\frac{<\mathbf{p}_{a} \times \mathbf{W}_{1}, \mathbf{q}_{i} \times \mathbf{W}_{2}>}{\left|\mathbf{p}_{a} \times \mathbf{W}_{1}\right|\left|\mathbf{q}_{i} \times \mathbf{W}_{2}\right|}\right) ，即计算两者的相似度，<>为内积，p，q为P，Q矩阵中的向量。当然，通过这种相似度计算得到的矩阵是稠密矩阵，因此要对其进行稀疏化，本文采用阈值的方式取top-k。公式如下：
s_{a i}=\left\{\begin{array}{cl}
s_{a i}, & s_{a i} \in t o p K\left(s_{a}\right) \\
0, & s_{a i} \notin t o p K\left(s_{a}\right)
\end{array}\right. 2.3 利用增强图学习embedding 在得到上述增强图后，我们可以利用邻接矩阵
A^E 来得到新的user和item的embedding
[P,Q,U,V]=GCF(A^E) 。
本文同样采用GCN进行编码，初始embedding设置为
P^0=P,Q^0=Q ，传播层数为K，经过信息传播后得到最终的embedding U和V。以第k+1层为例公式如下，其中
A_{a}^{E}=\left\{j \mid A_{a j}^{E}>0\right\} \subseteq V 表示和用户a相关联的item的集合，
A_{M+i}^{E}=\left\{b \mid A_{(M+i) b}^{E}>0\right\} \subseteq U 表示和item i相连的用户的集合，AGG表示聚合函数，可以是拼接，求和等。
\begin{array}{l}
\mathrm{p}_{a}^{k+1}=A G G\left(\mathrm{p}_{a}^{k},\left\{\mathrm{q}_{j}^{k}: j \in \mathrm{A}_{a}^{E}\right\}\right) \\
\mathrm{q}_{i}^{k+1}=A G G\left(\mathrm{q}_{i}^{k},\left\{\mathrm{p}_{b}^{k}: b \in \mathrm{A}_{(M+i)}^{E}\right\}\right)
\end{array} 在LightGCN中已经得到证实的是，在推荐系统中，权重和激活函数的意义不大，因此本文也直接采用邻居的embedding进行聚合，而不进行加权和激活函数，具体如下：
\begin{array}{l}
\mathbf{p}_{a}^{k+1}=\mathbf{p}_{a}^{k}+\frac{1}{\sum_{j=0}^{M+N-1} \mathbf{A}_{a j}^{E}} \sum_{j \in \mathbf{A}_{a}^{E}} \mathbf{A}_{a j}^{E} \mathbf{q}_{j}^{k}, \\
\mathbf{q}_{i}^{k+1}=\mathbf{q}_{i}^{k}+\frac{1}{\sum_{b=0}^{M+N-1} \mathbf{A}_{(M+i) b}^{E} b \in \mathbf{A}_{M+i}^{E}} \mathbf{A}_{(M+i) b}^{E} \mathbf{p}_{b}^{k} .
\end{array} 矩阵形式为：
\left[\begin{array}{l}
\mathrm{P}^{k+1} \\
\mathrm{Q}^{k+1}
\end{array}\right]=\left(\left[\begin{array}{l}
\mathrm{P}^{k} \\
\mathrm{Q}^{k}
\end{array}\right]+\mathrm{D}^{-1} \mathrm{~A}^{E} \times\left[\begin{array}{l}
\mathrm{P}^{k} \\
\mathrm{Q}^{k}
\end{array}\right]\right) 经过K层的信息传播后，可以得到最终的embedding
U=P^K,V=Q^K 。最后通过内积计算相似度
\hat{r}_{ai}=\left \langle u_a,v_i \right \rangle
3. 优化设计和模型训练
3.1 最大化互信息 3.1.1 边级别的约束 \arg \min _{\Theta_{G}} \mathcal{L}_{s}=\left\|\mathbf{A}-\mathbf{A}^{R}\right\|_{F}^{2}
约束如上式所示，其中
\Theta_G 为可学习参数，该约束所要达到的目的就是希望学到的残差图应该保有原始图中的正反馈的信息。然而，这种边约束只学习了单个链接的相关性，而无法捕捉到全局图的属性。
3.1.2 图级别的约束 这部分约束在全图级别上进行约束。在增强图中，对于每条边
(u_a,v_i) 。以user-item对为中心的子图作为局部表征。局部表征计算公式如下：
h_{ai}=[\sigma(u_a),\sigma(v_i)]
得到局部表征后，我们再去计算得到全局表征，全局表征计算方式如下，其中Z表示在增强图中边的数量，sign(x)表示当x>0时，值为1，反之，值为0。
\begin{array}{l}
Z=\sum_{a=0}^{M-1} \sum_{i=M}^{M+N-1} \operatorname{sign}\left(\mathbf{A}_{a i}^{E}\right) \\
\mathbf{g}=\sum_{[a, i] \in \mathcal{G}^{E}} \frac{\mathbf{h}_{a i}}{Z}
\end{array} 在得到局部表征和全局表征之后，通过互信息来约束两者的一致性。公式如下，其中w为可学习参数。
D(h,g)=h^TW_dg
3.1.3 负样本 为了学习D，需要采样负样本，本文采用了三种方案。首先假设节点embedding的矩阵表示为F，那么
\mathcal{G}^E 可以表示为
\mathcal{G}^E=(A^E,F) 。三种方案分别为：
Fake Edge ：随机采样在中为0的边作为局部表征的负样本，然后结合全局表征g，作为D学习的负样本Feature shuffling ：通过随机打乱既定比例的特征来得到假的表征\tilde{F} ，然后局部表征的负样本从
(A^E,\tilde{F}) 中采样得到
\tilde{h} ，全局采样依旧从
(A^E,h) 中采样得到g。
Structure perturbation ：在邻接矩阵A^E 中随机的去掉或者添加一些边，从而生成
\tilde{A}^E ,然后局部表征的负样本从
(\tilde{A}^E,F) 中采样得到
\tilde{h} ，全局采样依旧从
(A^E,h) 中采样得到g。
采样后，可以构建损失函数为：
\arg \min _{\Theta_{D}} \mathcal{L}_{d}=-\sum_{z=0}^{Z-1} \frac{\log \mathcal{D}(\mathbf{h}, \mathbf{g})+(1-\log \mathcal{D}(\tilde{\mathbf{h}}, \mathbf{g}))}{Z}
3.2 模型训练 \arg \min _{\Theta_{G}} \mathcal{L}_{r}=\sum_{a=0}^{M-1} \sum_{(i, j) \in D_{a}}-\ln \sigma\left(\hat{r}_{a i}-\hat{r}_{a j}\right)+\lambda\|\mathbf{P}\|^{2}+\lambda\|\mathbf{Q}\|^{2}
本文采用BPR损失函数，
D_a=\left\{(i,j) | i \in R_{a} \wedge j \notin R_{a}\right\} 表示训练样本对，其中R表示和用户a有交互的item的集合。最终的损失函数可以构建为：
\arg \min _{\Theta} \mathcal{L}=\mathcal{L}_r+\alpha \mathcal{L}_s+\beta \mathcal{L}_d
4. 实验结果
image.png
5. 总结
本文主要是通过构建一个新的邻接矩阵来发掘用户和item之间的潜在关系，而这个邻接矩阵的构建是基于已学习到的embedding，因此这两个是相互促进的关系。一方面 ，需要利用已有的图关系来得到更优的embedding；另一方面 通过已有的embedding来构建新的残差图，即发掘user-item的新关系。这里作者主要采用embedding之间的相似度来构建新的邻接矩阵。过往的方法本身也能发掘高阶关系，但是作者认为通过多层堆叠进行发掘的隐式关系中存在噪声，因此采用这种更加直接的方式 。
