GCMC - 图卷积矩阵完成 图卷积矩阵完成 KDD 2018

论文：Graph Convolutional Matrix Completion （GCMC） 图卷积矩阵补全

作者：来自于荷兰阿姆斯特丹大学的Rianne van den Berg, Thomas N. Kipf（GCN的作者）, Max Welling

来源：KDD 2018 Workshop

论文链接：https://www.kdd.org/kdd2018/files/deep-learning-day/DLDay18_paper_32.pdf

Github链接：https://github.com/riannevdberg/gc-mc

图卷积神经网络（GCN）是现在深度学习的热点之一，这篇文章基于user-item的二部图（Bipartite graph），提出了一种图自编码器框架，从链路预测的角度解决推荐系统中的评分预测问题。此外，为了验证所提出的消息传递方案，在标准的协同过滤任务上测试了所提出的模型，并展示出了一个有竞争力的结果。

1 相关介绍

1.1 背景

随着电子商务和社交媒体平台的爆炸式增长，推荐算法已经成为许多企业不可或缺的工具。
其中，推荐系统的一个子任务就是矩阵补全。文中把矩阵补全视作在图上的链路预测问题：users和items的交互数据可以通过一个在user和item节点之间的二分图来表示，其中观测到的评分/购买用links来表示。因此，预测评分就相当于预测在这个user-item二分图中的links。

据此，作者提出了一个图卷积矩阵补全（GCMC）框架：在用深度学习处理图结构的数据的研究进展的基础上，对矩阵进行补全的一种图自编码器框架。这个自编码器通过在二部交互图中信息传递的形式生成user和item之间的隐含特征。这种user和item之间的隐含表示用于通过一个双线性的解码器重建评分links。

当推荐图中带有结构化的外部信息(如社交网络)时，将矩阵补全作为二部图上的链接预测任务的好处就变得尤为明显。将这些外部信息与交互数据相结合可以缓解与冷启动问题相关的性能瓶颈。实验证明了作者提出的的图自编码器模型能够有效地将交互数据与side information结合起来。进一步证明了，在纯协同过滤场景中，这种方法能够与最新最先进的方法竞争。

1.2 side information

边信息（Side Information）：是指利用已有的信息Y辅助对信息X进行编码，可以使得信息X的编码长度更短。

边信息一个通俗的例子是：假设到马场去赌马，根据每个马的赔率可以得到一个最佳的投资方案。但是如果知道赌马的一些历史数据，例如上几场的胜负情况，那么可以得出一个更优的投资方案。赌马中的历史数据就是边信息。

1.3 contributions

• 将图神经网络应用于带有结构化side information的矩阵补全任务，并证明这种简单消息传递模型比基于复杂图形的方法有更好的性能
• 我们引入了节点dropout，这是一种有效的正则化技术，它以固定的概率删除单个节点的所有传出消息的整个集合

1.4 相关介绍

自编码器

下面的基于user或item的自动编码器是一类最新最先进的协同过滤模型，可以看作是文中的图数据自编码器模型的一个特例，其中编码器只考虑user或item的embedding。

• Autorec: Autoencoders meet collaborative filtering，WWW 2015
• Dropout: a simple way to prevent neural networks from overfitting，2014
• [CF-NADE] A neural autoregressive approach to collaborative filtering，ICML 2016

Autorec是这的第一个这样的模型，在这个模型中，其中，部分观察到的user或item的评分向量通过编码器层投影到潜在空间，并使用均方重建误差损失的解码器层重建。

CF-NADE算法可视为上述自动编码器体系结构的一个特例。在基于user的场景中，消息只从items传递给users
，在基于item的情况下，反之亦然。和文中的自编码器不同的是，评级的items在编码器中被分配了默认的3级，从而创建了一个完全连接的交互图。CF-NADE在节点上强制执行随机排序，并通过随机剪切将传入的消息分成两组，只保留其中一组。因此，该模型可以看作是一个去噪自动编码器，在每次迭代中，输入空间的一部分被随机丢弃。

矩阵分解模型

文中提出的模型和很多矩阵分解方法有关：

• 概率矩阵分解(Probabilistic matrix factorization，2008) (PMF)：采样概率的方法，将矩阵$M$分解为$M\approx U{V}^T$
• BiasedMF( Matrix Factorization Techniques for Recommender Systems，2009):通过合并一个user和item的特定bias以及全局bias来改进PMF
• 神经网络矩阵分解 （Neural network matrix factorization，2015） (NNMF)：扩展了MF方法，通过前馈神经网络传递潜在的users和items特征
• 局部低秩矩阵近似（ Local low rank matrix approximation，ICML 2013）：利用低秩近似的不同(与entry相关)组合来重建评价矩阵entries

Matrix completion with side information

• 在matrix completion (MC)（Exact matrix completion via convex optimization，2012）中，目标是用一个低秩评分矩阵去近似一个评分矩阵。然而，秩最小化是一个棘手的问题，论文中将秩最小化替换为核范数最小化(矩阵奇异值的总和)，将目标函数转化为可处理的凸函数。
• Inductive matrix completion (IMC)（Provable inductive matrix completion，2013）将users和items的内容信息合并到特征向量中，将评分矩阵中观察到的元素近似为$M_{ij}=x_i^{T}U{V}^T{y}_j$，其中$x_i$和$y_j$分别代表user$i$和item$j$的特征向量。
• geometric matrix completion (GMC) model（Matrix completion on graphs，2014）通过以user图和item图的形式添加side information，引入了MC模型的正则化
• Collaborative Filtering with Graph Information: Consistency and Scalable Methods（INPS 2015） 针对图正则化矩阵补全问题，提出了一种更有效的交替最小二乘优化方法(GRALS)。
• RGCNN（Geometric matrix completion with recurrent multi-graph neural networks，NIPS 2017） 是和本文最相关的工作。探讨了基于切比雪夫多项式的users和items k-nearest图的谱图滤波器的应用。文中的模型在一个编码器-解码器步骤中直接建模评级图，而不是使用递归估计，速度有显著的提升。
• PinSage，这是一个高度可扩展的图卷积网络，基于GraphSAGE框架，用于推荐的web级图，其中对邻居进行下采样以增强可扩展性。与PinSage相比，此文关注包含于图的side information，例如以社交网络图的形式，并进一步引入正则化技术来提高泛化。

2 在二部图中矩阵补全作为一种连接预测

2.1 符号定义

• $M$:评分矩阵，维度为$N_u\times N_v$，其中$N_u$是users的数量，$N_v$是items的数量
• 非零的$M_{ij}$表示user$i$对item$j$的评分，$M_{ij}=0$表示一个没有观测到评分

图1表示了整个模型的流程。在一个二分的user-item交互图中，矩阵补全任务(即对未观察到的交互的预测)可以转换为链接预测问题，并使用端到端可训练的图自编码器进行建模。

• 交互数据可以用无向图G表示：$G=(\mathcal{W},\mathcal{E},\mathcal{R})$
• $\mathcal{W}={\mathcal{W}}_u\cup {\mathcal{W}}_v$；${\mathcal{W}}_u$表示user节点的集合,维度为$N_u$；${\mathcal{W}}_v$表示item节点的集合,维度为$N_v$
• 边 $\left(u_i,r,v_j\right)\in \mathcal{E}$带有含评分等级类型的标签， r ∈ { 1 , … , R } = R r \in\{1, \ldots, R\}=\mathcal{R} r∈{1,…,R}=R

2.2 Revisiting graph auto-encoders 图自编码器

先前的推荐系统的基于图的方法通常采用多级pipline（此论文有介绍：Recommendation as link prediction in bipartite graphs: A graph kernel-based machine learning approach），其中包括图特征提取模型和链接预测模型，所有这些都分别进行训练。 然而，通过使用端到端学习技术对图结构数据进行建模，通常可以显着改善结果，特别是使用图自动编码器用于在无向图上进行无监督学习和链接预测。

本文采用（Thomas N. Kipf and Max Welling. Variational graph auto-encoders. NIPS Bayesian Deep Learning Work- shop, 2016.）中介绍的setup，因为它可以有效利用（卷积）权重共享，并允许以节点特征的形式包含边信息。其中

图自编码器模型：$Z=f(X,A)$

• 输入：一个$N\times D$的特征矩阵$X$和一个图邻接矩阵$A$,$D$表示节点特征的数量
• 输出：一个$N\times H$的节点embedding矩阵$Z={\left[z_1,\dots ,z_N\right]}^T$,$H$表示embedding的size

解码器：$\check{A}=g(Z)$

• 输入：节点的embedding对$(z_i,z_j)$
• 输出：预测邻接矩阵中的各个tntries：${\check{A}}_{ij}$

对于推荐系统的二部图$G=(\mathcal{W},\mathcal{E},\mathcal{R})$，将编码器重新公式化:

• $\left[Z_u,Z_v\right]=f\left(X_u,X_v,M_1,\dots ,M_R\right)$，其中 M r ∈ { 0 , 1 } N u × N v M_{r} \in\{0,1\}^{N_{u} \times N_{v}} Mr​∈{0,1}Nu​×N

  上一篇： 点积、叉积、内积、外积 [摘要比较] - 叉积（corss 积）

  下一篇： docker 学习笔记 8：Centos docker 安装 Redis