Question

1. 随着电商平台和社交媒体平台的爆炸式增长，推荐算法已经成为很多企业不可或缺的工具。通常而言，推荐算法有两个主流方向：基于内容的推荐系统、基于协同过滤的推荐系统。

   • 基于内容的推荐系统使用 user 和 item 的内容信息来进行推荐，如用户的职业、item 的类型。
   • 基于协同过滤的推荐使用 user-item 交互数据（如购买、评分等）来进行推荐。

   论文 《Graph Convolutional Matrix Completion》 将矩阵补全问题视为一个图的链接预测问题：协同过滤中的交互数据可以由用户节点和 item 节点之间的二部图来表示，观察到的评分/购买由链接来表示。内容信息自然地以节点特征的形式包含在这个框架中。评分预测问题变为预测 user-item 二部图中的 labeled link 。

   论文提出了图卷积矩阵补全 graph convolutional matrix completion: GCMC：一种 graph-based 的自编码器框架用于矩阵补全，它建立在图上深度学习的最新进展的基础上。自编码器 auto-encoder 通过在二部图上消息传递的形式来产生 user latent feature 和 item latent feature 。这些潜在 user representation 和 item representation 用于通过双线性解码器重建评分链接rating link。

   当有额外的辅助信息side information 可用时，将矩阵补全问题视为二部图上的链接预测问题带来的好处尤为明显。将辅助信息和交互数据结合在一起可以有效缓解冷启动问题。论文证明了所提出的图自编码器模型有效地结合了交互数据和辅助信息。

2. 相关工作：

   • 自编码器auto-encoder：user-based 或 item-based 自编码器是最近一类 state-of-the-art 协同过滤模型，可以视为我们的图自编码器模型的一个特例，其中仅考虑了 user embedding 或仅考虑了 item embedding 。

     • 《Autorec: Auto-encoders meet collaborative filtering》 是第一个这样的模型，其中 user （或 item）部分观察到的评分向量 rating vector 通过编码器层 encoder layer 投影到潜在空间，并使用具有均方重构误差损失mean squared reconstruction error loss 的解码器层 decoder layer 进行重构。

     • 《A neural autoregressive approach to collaborative filtering》 提出的 CF-NADE 算法可以被认为是上述自编码器架构的一个特例。在 user-based 的设置中，消息仅从 item 传递给user；而在 item-based 的设置中，消息仅从 user 传递给 item 。

       我们的图自编码器同时考虑了 item 传递给 user ，以及 user 传递给 item 。

       注意，与我们的模型相比，CF-NADE 给未评分的 item 在编码器中被分配了默认评分 3 ，从而创建了一个全连接的交互图 interaction graph 。CF-NADE 对节点进行随机排序，并通过随机切割 random cut 将传入消息划分为两组，并仅保留其中一组。因此，该模型可以看做是一个降噪自编码器，其中在每次迭代中随机丢弃输入空间的一部分。

       我们的模型仅考虑观测的评分，因此不是全连接的。

   • 分解模型：很多流行的协同过滤算法都是基于矩阵分解 matrix factorization: MF 模型，这种方式假设评分矩阵可以很好滴近似为低秩矩阵：

     $$\mathbf{M}\simeq \mathbf{U}{\mathbf{V}}^{\mathrm{\top }}$$

     其中：

     • $\mathbf{U}\in {\mathbb{R}}^{|\mathbb{U}|\times d}$$ \mathbf U\in \mathbb R^{|\mathbb U|\times d} $ 表示用户 embedding 矩阵，每一行代表一个用户的 user embedding 向量，即user latent feature representation 。
     • $\mathbf{V}\in {\mathbb{R}}^{|\mathbb{V}|\times d}$$ \mathbf V\in \mathbb R^{|\mathbb V|\times d} $ 表示 item embedding 矩阵，每一行代表一个 item embedding 向量，即item latent feature representation 。
     • $d$$ d $ 为 embedding 向量的维度，并且满足$d\ll |\mathbb{U}|,d\ll |\mathbb{V}|$$ d\ll |\mathbb U|, d\ll |\mathbb V| $ ，$\mathbb{U}$$ \mathbb U $ 为 user 集合，$\mathbb{V}$$ \mathbb V $ 为 item 集合。

     在这些矩阵分解模型中：

     • 《Probabilistic matrix factorization》 提出的概率矩阵分解 probabilistic matrix factorization: PMF 假设$\mathbf{M}$$ \mathbf M $ 中的评分是带高斯噪声的独立随机变量，然后最大化观测评分。这种最大似然估计等价于$\mathbf{M}$$ \mathbf M $ 中的观测值和$\mathbf{U}{\mathbf{V}}^{\mathrm{\top }}$$ \mathbf U\mathbf V^\top $ 中对应的重建值之间的均方误差最小化。
     • 《Matrix factorization techniques for recommender systems》 提出的 BiasedMF 通过融合 user-specifc bias, item-specific bias, global-bias 来改进 PMF 。
     • 《Neural network matrix factorization》 提出的 Neural network matrix factorization: NNMF 通过将 latent user feature 和 latent item feature 传递给前馈神经网络来扩展 MF 方法。
     • 《Local low-rank matrix approximation》 提出的局部低秩矩阵近似介绍了使用不同低秩近似的组合来重建评分矩阵的思想。

   • 带辅助信息的矩阵补全matrix completion with side information：在矩阵补全问题中，目标是使用低秩矩阵来逼近$\mathbf{M}$$ \mathbf M $ 。但是，秩 rank 的最小化是一个棘手的问题。

     • 《Exact matrix completion via convex optimization》 使用最小化核范数nuclear norm（矩阵的奇异值之和）来代替秩的最小化，从而将目标函数变成了可处理的凸函数。

     • Inductive matrix completion: IMC 将 user 和 item 的内容信息融入到特征向量中，并预估 user$u_i$$ u_i $ 对 item$v_j$$ v_j $ 的评分为：

       $$m_{i,j}={\overrightarrow{\mathbf{x}}}_i^{\mathrm{\top }}\mathbf{U}{\mathbf{V}}^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_j$$

       其中${\overrightarrow{\mathbf{x}}}_i$$ \mathbf{\vec x}_i $ 为用户$u_i$$ u_i $ 的特征向量，${\overrightarrow{\mathbf{y}}}_j$$ \mathbf{\vec y}_j $ 为 item$v_j$$ v_j $ 的特征向量。$\mathbf{U}$$ \mathbf U $ 和$\mathbf{V}$$ \mathbf V $ 为低秩的、待学习的user embedding 矩阵和 item embedding 矩阵。

     • 《Matrix completion on graphs》提出的 geometric matrix completion: GCM 模型通过以 user graph 和 item graph 的形式添加辅助信息，从而对矩阵补全模型进行正则化。

     • 在 《Collaborative filtering with graph information: Consistency and scalable methods》 提出的 GRALS 将一种更有效的交替最小二乘优化方法引入了图正则化矩阵补全问题。

     • 最近，《Geometric matrix completion with recurrent multi-graph neural networks》 提出，通过在图上使用卷积神经网络将 graph-based 辅助信息融合到矩阵补全中，并结合递归神经网络来建模动态评分生成过程。

       和他们不同，GCMC 直接使用图卷积编码器/解码器对评分的二部图进行建模，通过一个non-iterative 步骤即可预测 unseen 的评分。

       相比之下，sRGCNN 需要用迭代式的多个 step 才能预测评分。

14.1 模型

1. 给定用户集合$\mathbb{U}$$ \mathbb U $ 以及 item 集合$\mathbb{V}$$ \mathbb V $ 。考虑评分矩阵$\mathbf{M}\in {\mathbb{R}}^{|\mathbb{U}|\times |\mathbb{V}|}$$ \mathbf M\in \mathbb R^{|\mathbb U|\times |\mathbb V|} $ ，矩阵的第$i$$ i $ 行、$j$$ j $ 列代表用户$u_i$$ u_i $ 对 item$v_j$$ v_j $ 的评分$m_{i,j}$$ m_{i,j} $ 。

   $$\begin{array}{c}{m}_{i,j}\{\begin{array}{ll}>0,& \text{observed}\\ =0,& \text{non-observed}\end{array}\end{array}$$

   我们将矩阵补全问题转化为链接预测问题。考虑二部图$G=(\mathcal{W},\mathcal{E},\mathcal{R})$$ G=(\mathcal W,\mathcal E,\mathcal R) $ ，其中：$\mathcal{W}=\mathbb{U}\cup \mathbb{V}$$ \mathcal W = \mathbb U\cup \mathbb V $ 为所有节点集合，$\mathcal{E}$$ \mathcal E $ 表示所有链接集合（每个链接表示一个观测评分），$\mathcal{R}=\{1,2,\cdots ,R\}$$ \mathcal R = \{1,2,\cdots,R\} $ 为评分等级（这里最高$R$$ R $ 级评分）。$(u_i,m_{i,j},v_j)\in \mathcal{E}$$ (u_i,m_{i,j},v_j)\in \mathcal E $ 表示用户$u_i$$ u_i $ 对item$v_j$$ v_j $ 的评分为$m_{i,j}\in \mathcal{R}$$ m_{i,j}\in \mathcal R $ 。

   如下图所示：

   • 左图为评分矩阵$\mathbf{M}$$ \mathbf M $ ，每一项对应于 user-item 之间的评分（评分在 1~5 分之间），或者未观测（评分记作 0）。
   • 第二幅图表示 user-item 评分的二部图，边对应于评分行为，边上的数字对应于评分数值。
   • 最后两幅图表示矩阵补全问题可以转换为二部图上的链接预测问题，并使用端到端的可训练的图自编码器进行建模。

   矩阵补全问题转化为链接预测问题的核心是：链接如何对应到评分？GCMC 的做法是：每个等级的评分对应一条边，因此有$R$$ R $ 种不同类型的边。

   • 每种类型的边都有一个编码器，所有编码器的结果聚合得到 node embedding 。
   • 每种类型的边都有一个解码器，所有解码器的结果求期望得到预估的评分。

   但是，这里没有考虑评分之间的大小关系：评分为 1 要小于评分为$R$$ R $ 。因此这里忽视了非常重要的评分排序关系。

   

2. 之前的 graph-based 推荐算法通常采用 multi-stage pipeline，其中包括图的特征抽取模型（如 graph embedding 模型）以及图的链接预测模型。这些模型都是独立分开训练。

   但是最近的研究结果表明：通过端到端的技术来建模图结构化数据可以显著提升效果。在这些端到端技术中，应用于无监督学习和链接预测的图自编码graph auto-encoder 技术尤为突出。因此我们提出一种图自编码器的变种来应用于推荐任务。

14.1.1 图自编码器

1. 图自编码器由一个编码器和一个解码器组成，其中：

   • 编码器模型：$\mathbf{Z}=f(\mathbf{X},\mathbf{A})$$ \mathbf Z = f(\mathbf X, \mathbf A) $ 。其中：

     • $\mathbf{X}\in {\mathbb{R}}^{|\mathcal{W}|\times d_f}$$ \mathbf X\in \mathbb R^{|\mathcal W|\times d_f} $ 为输入的特征矩阵，每一行代表一个节点的特征向量，$d_f$$ d_f $ 为节点的特征向量维度。
     • $\mathbf{A}\in {\mathbb{R}}^{|\mathcal{W}|\times |\mathcal{W}|}$$ \mathbf A \in \mathbb R^{|\mathcal W|\times |\mathcal W|} $ 为图的邻接矩阵。
     • $\mathbf{Z}\in {\mathbb{R}}^{|\mathcal{W}|\times d_e}$$ \mathbf Z\in \mathbb R^{|\mathcal W|\times d_e} $ 为节点的 embedding 矩阵，每一行代表一个节点的 embedding 向量，$d_e$$ d_e $ 为 node embedding 向量维度。

   • 解码器模型：$\hat{\mathbf{A}}=g(\mathbf{Z})$$ \hat{\mathbf A} = g(\mathbf Z) $ 。解码器以一对节点 embedding$({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)$$ \left(\mathbf{\vec z}_i,\mathbf{\vec z}_j\right) $ 为输入，并预测节点$i$$ i $ 和$j$$ j $ 之间的连接性，即预估的邻接矩阵的项${\hat{A}}_{i,j}$$ \hat A_{i,j} $ 。

2. 对于二部图$G=(\mathcal{W},\mathcal{E},\mathcal{R})$$ G=(\mathcal W,\mathcal E,\mathcal R) $ ，我们重新定义编码器为：

   $$[\mathbf{U},\mathbf{V}]=f(\mathbf{X},{\mathbf{M}}_1,\cdots ,{\mathbf{M}}_R)$$

   其中：

   • $\mathbf{U}\in {\mathbb{R}}^{|\mathbb{U}|\times d_e}$$ \mathbf U\in \mathbb R^{|\mathbb U|\times d_e} $ 为 user embedding 矩阵，$\mathbf{V}\in {\mathbb{R}}^{|\mathbb{V}|\times d_e}$$ \mathbf V\in \mathbb R^{|\mathbb V|\times d_e} $ 为 item embedding 矩阵。

   • ${\mathbf{M}}_r\in \{0,1{\}}^{|\mathbb{U}|\times |\mathbb{V}|}$$ \mathbf M_r\in \{0,1\}^{|\mathbb U|\times |\mathbb V|} $ 为评分等级为$r$$ r $ 的邻接矩阵，它的元素在 {0,1} 内取值，$1\le r\le R$$ 1\le r\le R $ 。并且当用户$u_i$$ u_i $ 对 item$v_j$$ v_j $ 的观测评分$m_{i,j}=r$$ m_{i,j} = r $ 时$M_r(i,j)=1$$ M_{r}(i,j) = 1 $ ，否则为零。

     因此，${\mathbf{M}}_r$$ \mathbf M_r $ 定义了原始评分矩阵中评分等级为$r$$ r $ 关联的邻接矩阵。

     这里对每种类型的边定义了一个邻接矩阵，不同的邻接矩阵代表了不同的模型，因此类似于 《Convolutional Networks on Graphs for Learning Molecular Fingerprints》 提出的 neural graph fingerprint 模型。

   类似地，我们重新定义解码器为：

   $$\hat{\mathbf{M}}=g(\mathbf{U},\mathbf{V})$$

   解码器输入一对 user-item 的 embedding 向量，并返回 user$u_i$$ u_i $ 对 item$v_j$$ v_j $ 预估的评分${\hat{m}}_{i,j}$$ \hat m_{i,j} $ ，其中${\hat{m}}_{i,j}$$ \hat m_{i,j} $ 为$\hat{\mathbf{M}}$$ \hat{\mathbf M} $ 的第$i$$ i $ 行第$j$$ j $ 列。

   我们通过最小化预测评分矩阵$\hat{\mathbf{M}}$$ \hat{\mathbf M} $ 和真实评分矩阵$\mathbf{M}$$ \mathbf M $ 之间的重构误差来训练该自编码器（注意：通常只考虑观测值上的重构误差）。通常评估重构误差的指标为 RMSE （将评分预测视为回归问题）或者交叉熵（将评分预测视为分类问题）。

   最后，我们注意到可以将最近提出的几个矩阵补全 state-of- the-art 模型纳入我们的框架中，并将它们视为我们模型的特例。

14.1.2 图卷积编码器

1. 这里我们选择了一种特定的编码器模型，它可以有效地利用图中 location 之间的权重共享，并为每种边类型$r\in \mathcal{R}$$ r\in \mathcal R $ 分配独立的处理通道。

2. 我们选择局部图卷积 local graph covolution 作为编码器模型。这类局部图卷积可以视为消息传递的一种方式，其中消息在图的链接之间传递和转换。

   在我们case 中，我们为每个评分等级分配一个level-specific 变换，使得从 item$v_j$$ v_j $ 到用户$u_i$$ u_i $ 的消息传递形式为：

   $${\overrightarrow{\mu }}_{j\to i}^{(r)}=\frac{1}{c_{i,j}}{\mathbf{W}}_r{\overrightarrow{\mathbf{x}}}_j$$

   其中：

   • $c_{i,j}$$ c_{i,j} $ 为归一化常数，通常选择为$|{\mathcal{N}}_i|$$ |\mathcal N_i| $ （左归一化left normalization） 或者$\sqrt{|{\mathcal{N}}_i||{\mathcal{N}}_j|}$$ \sqrt{|\mathcal N_i||\mathcal N_j|} $ （对称归一化）。${\mathcal{N}}_i$$ \mathcal N_i $ 为节点$u_i$$ u_i $ 的邻域节点集合，${\mathcal{N}}_j$$ \mathcal N_j $ 为节点$v_j$$ v_j $ 的邻域节点集合。

     根据论文的描述，这里应该是${\mathcal{N}}_i^{(r)}$$ \mathcal N_i^{(r)} $ 和${\mathcal{N}}_j^{(r)}$$ \mathcal N_j^{(r)} $ ，即类型为$r$$ r $ 的邻域。此外，还要求满足：$v_j\in {\mathcal{N}}_i^{(r)}$$ v_j\in \mathcal N_i^{(r)} $ 以及$u_i\in {\mathcal{N}}_j^{(r)}$$ u_i\in \mathcal N_j^{(r)} $ 。

   • ${\mathbf{W}}_r$$ \mathbf W_r $ 为评分等级$r$$ r $ 的 level-specific 权重矩阵。

   • ${\overrightarrow{\mathbf{x}}}_j$$ \mathbf{\vec x}_j $ 为节点$v_j$$ v_j $ 的特征向量。

   同理，用户$u_i$$ u_i $ 到 item$v_j$$ v_j $ 的消息传递形式为：

   $${\overrightarrow{\mu }}_{i\to j}^{(r)}=\frac{1}{c_{j,i}}{\mathbf{W}}_r{\overrightarrow{\mathbf{x}}}_i$$

   这里也可以选择使用不同的 level-specific 权重矩阵${\mathbf{W}}_{r,u2i},{\mathbf{W}}_{r,i2u}$$ \mathbf W_{r,u2i},\mathbf W_{r,i2u} $ （即 user -> item 和 item -> user 传递消息时，权重矩阵不同）。

   在消息传递之后：

   • 首先通过求和来聚合类型为$r$$ r $ 的所有邻居${\mathcal{N}}_i^{(r)}$$ \mathcal N_{i}^{(r)} $ 的消息，得到领域类型为$r$$ r $ 的单个representation 向量。
   • 然后将所有邻域类型的 representation 向量聚合，从而得到节点的单个聚合向量。
   • 最后对聚合向量进行变换，最终得到节点的 embedding 向量。

   以下公式为用户节点$u_i$$ u_i $ 的 embedding 计算公式，item 节点$v_j$$ v_j $ 的 embedding 也是类似的。

   $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_i=\sigma \left[\text{accum}(\sum _{v_j\in {\mathcal{N}}_i^{(1)}}{\overrightarrow{\mu }}_{j\to i}^{(1)},\cdots ,\sum _{v_j\in {\mathcal{N}}_i^{(R)}}{\overrightarrow{\mu }}_{j\to i}^{(R)})\right]\\ {\overrightarrow{\mathbf{u}}}_i=\sigma \left(\mathbf{W}{\overrightarrow{\mathbf{h}}}_i\right)\end{array}$$

   其中第一行公式称作卷积层，第二行公式称作 dense 层。

   注意：

   • 当没有辅助信息可用时， dense 层对于 user 和 item 都采用相同的参数矩阵$\mathbf{W}$$ \mathbf W $ 。

     当存在辅助信息可用时， dense 层对于 user 和 item 都采用单独的参数矩阵$\mathbf{W}$$ \mathbf W $ ，分别记作${\mathbf{W}}^{(U)},{\mathbf{W}}^{(V)}$$ \mathbf W^{(U)},\mathbf W^{(V)} $ 。

   • 这里卷积层只有一层。虽然可以堆叠更多的卷积层来构建更深的模型，但是在最初的实验中我们发现堆叠更多卷积层并不能提高性能。

     同理，堆叠更多的 dense 层也不能提高性能。因此，最终我们选择单层卷积层 + 单层 dense 层的组合作为图编码器。

   • 这里给出的模型仅仅是一种可能性。虽然编码器的选择相对简单，但是也可以选择不同的变种。例如：

     • 可以使用神经网络来计算消息传递（${\overrightarrow{\mu }}_{j\to i}^{(r)}=\text{nn}({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j,r)$$ \vec\mu_{j\rightarrow i}^{(r)} = \text{nn}\left(\mathbf{\vec x}_i,\mathbf{\vec x}_j, r\right) $ ），从而替换掉简单的线性变换。
     • 可以使用 attention 机制从模型中学习每个消息的权重，从而替代消息的归一化常数$c_{i,j}$$ c_{i,j} $ 。

14.1.3 双线性解码器

1. 我们使用双线性解码器 bilinear decoder 来重建二部图的链接。令用户$u_i$$ u_i $ 对 item$v_j$$ v_j $ 预估的评分为${\hat{m}}_{i,j}$$ \hat m_{i,j} $ ，则解码器输出预估评分为$r$$ r $ 的概率为：

   $$p({\hat{m}}_{i,j}=r)=\frac{\exp \left({\overrightarrow{\mathbf{u}}}_i^{\mathrm{\top }}{\mathbf{Q}}_r{\overrightarrow{\mathbf{v}}}_j\right)}{\sum _{s\in \mathcal{R}}\exp \left({\overrightarrow{\mathbf{u}}}_i^{\mathrm{\top }}{\mathbf{Q}}_s{\overrightarrow{\mathbf{v}}}_j\right)}$$

   其中每个评分等级$r$$ r $ 关联一个可训练的参数${\mathbf{Q}}_r\in {\mathbb{R}}^{d_e\times d_e}$$ \mathbf Q_r\in \mathbb R^{d_e\times d_e} $ ，$d_e$$ d_e $ 为 embedding 向量的维度。

   每个评分登记$r$$ r $ 关联一个${\mathbf{W}}_r$$ \mathbf W_r $ 用于编码、关联一个${\mathbf{Q}}_r$$ \mathbf Q_r $ 用于解码。

   模型最终预估的评分为所有评分等级预估结果的期望值：

   $${\hat{m}}_{i,j}=g({\overrightarrow{\mathbf{u}}}_i,{\overrightarrow{\mathbf{v}}}_j)={\mathbb{E}}_{p({\hat{m}}_{i,j}=r)}[r]=\sum _{r=1}^{R}r\times p({\hat{m}}_{i,j}=r)$$

14.1.4 模型训练

1. 损失函数：模型训练期间我们将 GCMC 模型的损失函数定义为：最小化预估评分${\hat{m}}_{i,j}$$ \hat m_{i,j} $ 的对数似然：

   $$\mathcal{L}=-\sum _{(i,j):{\mathrm{\Omega }}_{i,j}=1}\sum _{r=1}^{R}I(r=m_{i,j})\times \log p({\hat{m}}_{i,j}=r)$$

   其中：

   • $I(\cdot )$$ I(\cdot) $ 为示性函数：$I(\text{true})=1,I(\text{false})=0$$ I(\text{true}) = 1, I(\text{false}) = 0 $ 。
   • $\mathbf{\Omega }$$ \mathbf\Omega $ 为观测值的mask 矩阵：对于观测值对应的项，${\mathrm{\Omega }}_{i,j}=1$$ \Omega_{i,j} = 1 $ ；对于未观测值对应的项，${\mathrm{\Omega }}_{i,j}=0$$ \Omega_{i,j} = 0 $ 。

   因此，上述目标函数仅在所有观测的评分上优化。

2. GCMC 模型的整体框架如下所示。模型由图卷积编码器$[\mathbf{U},\mathbf{V}]=f(\mathbf{X},{\mathbf{M}}_1,\cdots ,{\mathbf{M}}_R)$$ [\mathbf U, \mathbf V] = f(\mathbf X, \mathbf M_1,\cdots,\mathbf M_R) $ 以及双线性解码器$\hat{\mathbf{M}}=g(\mathbf{U},\mathbf{V})$$ \hat{\mathbf M} = g(\mathbf U,\mathbf V) $ 组成。其中：

   • 编码器从 user-> item 或者 item -> user 传递并变换消息。
   • 解码器根据 user embedding 和item embedding 的 pair 对来预估评分。

   

3. node dropout：为使得模型能够很好地泛化到未观测的评分，我们以概率$p_{\text{dropout}}$$ p_\text{dropout} $ 随机丢弃某个节点传出的所有消息，我们称之为 node dropout 。注意：和常规 dropout 一样，在消息丢弃之后需要 rescale。

   这种 node-level 的 dropout 和常规的 dropout 不同。常规的 dropout 是在message-level进行 dropout，称作 message dropout 。

   • 在 message dropout 中，每条消息随机独立地丢弃，使得最终 embedding 对于边的扰动更为鲁棒。
   • 而在 node dropout 中，每个节点随机独立地丢弃，使得最终 embedding 对于特定用户和特定 item 的影响更为鲁棒。这会缓解一些热门用户或热门item 的影响。

   最后，我们还对卷积自编码器的 dense 层的隐单元使用了常规的 dropout 。

4. mini-batch 训练：为了训练较大的数据集（如 MovieLens-10M 数据集），我们需要对观测数据进行采样，从而进行 mini-batch 训练。这是将 MovieLens-10M 的完整模型加载到 GPU 内存所必须的。

   我们从每个等级的观测评分中采样固定比例的评分，然后仅考虑该 mini-batch 的损失。这样我们在训练过程中仅需要考虑当前 mini-batch 中出现的 user 和 item。这既是正则化的有效手段，又可以降低训练模型需要的内存。

   通过在 Movielens-1M 数据集上使用 mini-batch 训练和 full-batch 训练的实验对比（对比时针对二者分别调优了各自的正则化参数），我们发现二者产生了可比的结果。

   最后，对于 MovieLens-10M 以外的其它数据集，我们选择 full-batch 训练，因为 full-batch 训练相比 mini-batch 训练的收敛速度更快。

14.1.5 向量化实现

1. 在 GCMC 的实现中，我们可以使用高效的稀疏矩阵乘法来实现图自编码器模型，其算法复杂度和边的数量呈线性关系，即$O(|\mathcal{E}|)$$ O(|\mathcal E|) $ 。

   假设聚合函数 accum 为累加，则图卷积编码器为（采用左归一化）：

   $$\begin{array}{c}{\mathbf{A}}_r=\left[\begin{array}{cc}\mathbf{0}& {\mathbf{M}}_r\\ {\mathbf{M}}_r^{\mathrm{\top }}& \mathbf{0}\end{array}\right]\\ \left[\begin{array}{c}{\mathbf{H}}_u\\ {\mathbf{H}}_v\end{array}\right]=\sigma \left(\sum _{r=1}^R{\mathbf{D}}^{-1}{\mathbf{A}}_r\mathbf{X}{\mathbf{W}}_r^{\mathrm{\top }}\right)\\ \left[\begin{array}{c}\mathbf{U}\\ \mathbf{V}\end{array}\right]=f(\mathbf{X},{\mathbf{M}}_1,\cdots ,{\mathbf{M}}_R)=\sigma \left(\left[\begin{array}{c}{\mathbf{H}}_u\\ {\mathbf{H}}_v\end{array}\right]{\mathbf{W}}^{\mathrm{\top }}\right)\end{array}$$

   其中：

   • $\mathbf{D}$$ \mathbf D $ 为节点的度矩阵 degree matrix，$D_{i,i}=|{\mathcal{N}}_i|$$ D_{i,i} = |\mathcal N_i| $ 。

     这里是否要替换为${\mathbf{D}}_r$$ \mathbf D_r $ ，即评分等级$r$$ r $ 下的邻接矩阵的度矩阵？

   • $\sigma \left(\sum _{r=1}^R{\mathbf{D}}^{-1}{\mathbf{A}}_r\mathbf{X}{\mathbf{W}}_r^{\mathrm{\top }}\right)$$ \sigma\left(\sum_{r=1}^R \mathbf D^{-1} \mathbf A_r \mathbf X \mathbf W^{ \top}_r\right) $ 可以替换为向量拼接（而不是累加）。

   另外，采用对称归一化的图卷积编码器以及双线性解码器的向量化 vectorization 也以类似的方式进行。

14.1.6 辅助信息

1. 理论上可以将包含每个节点的信息（如内容信息）的特征直接作为节点的输入特征（即特征矩阵$\mathbf{X}$$ \mathbf X $ ），并直接作用到图自编码器中。但是，当内容信息不足以区分不同的用户（或者 item）及其兴趣时，将内容信息直接馈入图卷积层会导致严重的信息流瓶颈bottleneck of information flow 。

   此时，可以通过单独的处理通道 channel，从而将用户特征向量或 item 特征向量以辅助信息的形式纳入全连接层中。

   由于内容信息灌入到模型的最后一层，因此上述的信息流瓶颈不会出现，因为瓶颈只会出现在中间层。那么这么做对不对？理论依据是什么？

   我们选择输入特征矩阵$\mathbf{X}$$ \mathbf X $ 为一个单位矩阵，即每个节点的输入特征为节点的 one-hot 表示。令用户节点$u_i$$ u_i $ 的辅助信息特征向量为${\overrightarrow{\mathbf{x}}}_i^f$$ \mathbf{\vec x}_i^f $ ，则作用到全连接层之后，节点的embedding 为：

   $$\begin{array}{c}{\overrightarrow{\mathbf{f}}}_i=\sigma ({\mathbf{W}}_1^{(U,f)}{\overrightarrow{\mathbf{x}}}_i^f+{\overrightarrow{\mathbf{b}}}^{(U)})\\ {\overrightarrow{\mathbf{u}}}_i=\sigma ({\mathbf{W}}^{(U)}{\overrightarrow{\mathbf{h}}}_i+{\mathbf{W}}_2^{(U,f)}{\overrightarrow{\mathbf{f}}}_i)\end{array}$$

   其中：

   • ${\mathbf{W}}_1^{(U,f)},{\mathbf{W}}_2^{(U,f)}$$ \mathbf W_1^{(U,f)},\mathbf W_2^{(U,f)} $ 都是可训练的权重矩阵，${\overrightarrow{\mathbf{b}}}^{(U)}$$ \mathbf{\vec b}^{(U)} $ 为可训练的 bias 向量。

   • user 节点的参数为$\{{\mathbf{W}}_1^{(U,f)},{\mathbf{W}}_2^{(U,f)},{\overrightarrow{\mathbf{b}}}^{(U)},{\mathbf{W}}^{(U)}\}$$ \left\{\mathbf W_1^{(U,f)},\mathbf W_2^{(U,f)} , \mathbf{\vec b}^{(U)}, \mathbf W^{(U)}\right\} $ ，而 item 节点的参数为$\{{\mathbf{W}}_1^{(V,f)},{\mathbf{W}}_2^{(V,f)},{\overrightarrow{\mathbf{b}}}^{(V)},{\mathbf{W}}^{(V)}\}$$ \left\{\mathbf W_1^{(V,f)},\mathbf W_2^{(V,f)} , \mathbf{\vec b}^{(V)}, \mathbf W^{(V)}\right\} $ 。即 user,item 类型的节点使用两套不同的参数。

     因为 user 节点和 item 节点具有不同的输入特征空间。

   • 本文实验中使用的数据集中，用户内容以及 item 内容的信息大小有限，因此我们使用这种辅助信息的方式。

2. 注意：辅助信息不一定要以节点特征向量的形式出现，也可以是图结构（如社交网络）、自然语言或者图像数据。此时可以将上式中的 dense 层替换为适当的可微模块，如 RNN、CNN 或者其它图卷积网络。

14.1.7 权重共享

1. 编码器权重共享：在辅助信息的方式中，我们使用节点的 one-hot 向量作为输入。此时矩阵${\mathbf{W}}_r$$ \mathbf W_r $ 的第$i$$ i $ 列可以视为节点$i$$ i $ 在评分等级$r$$ r $ 下的潜在因子向量。这些潜在因子向量通过消息传递，被传递到与该节点相连的 user 节点（如果节点$i$$ i $ 为 item 节点）或者 item 节点（如果节点$i$$ i $ 为 user 节点）。

   但是，并非所有用户拥有评分等级为$r$$ r $ 的相同评分数量，也并非所有 item 拥有评分等级为$r$$ r $ 的相同评分数量。这将导致${\mathbf{W}}_r$$ \mathbf W_r $ 的某些列的优化频次明显低于其它列。因此，对于不同的$r$$ r $ 我们期待矩阵${\mathbf{W}}_r$$ \mathbf W_r $ 之间的权重共享，从而缓解该优化问题。

   遵从 《A neural autoregressive approach to collaborative filtering》我们实现了以下权重共享策略：

   $${\mathbf{W}}_r=\sum _{s=1}^r{\mathbf{T}}_s$$

   由于更高的评分等级包含的权重矩阵数量更多，因此我们称这种权重共享为有序权重共享 ordinal weight sharing 。

   为什么更高评分包含的权重矩阵数量更多？完全没有道理。

2. 解码器权重共享：对于成对双线性解码器，我们采用一组基权重矩阵 basis weight matrix$\{{\mathbf{P}}_1,\cdots ,{\mathbf{P}}_{n_b}\}$$ \{\mathbf P_1,\cdots,\mathbf P_{n_b}\} $ ，其中：

   $${\mathbf{Q}}_r=\sum _{s=1}^{n_b}{a}_{r,s}{\mathbf{P}}_s$$

   其中：

   • $n_b$$ n_b $ 为基权重矩阵的数量。注意，为缓解过拟合并减少参数数量，$n_b$$ n_b $ 应该小于评分等级数量$R$$ R $ 。
   • $a_{r,s}$$ a_{r,s} $ 为可学习的参数，用于决定对每个解码器权重矩阵${\mathbf{Q}}_r$$ \mathbf Q_r $ 的线性组合的系数。

   这种解码器的权重共享是一种有效的正则化手段。

14.2 实验

1. 数据集：我们在多个常见的协同过滤 benchmark 数据集上评估我们的模型。

   • MovieLens （100K,1M, 10M）数据集：包含多个用户对多部电影的评级数据，也包括电影元数据信息（如电影题材）和用户属性信息（如用户年龄、性别、职业）。该数据集有多个版本，对应于不同的数据量。
   • Flixster 数据集：来自于社交电影网站 Flixster 的电影评分数据集，数据集包含了用户之间的好友关系。
   • Douban 数据集：来自豆瓣的电影评分数据集，数据集包含用户之间的好友关系。
   • YahooMusic 数据集：来自 Yahoo! Music 社区的用户对音乐家的评分数据集。

   对于 Flixster,Douban, YahooMusic 数据集，我们使用《Geometric matrix completion with recurrent multi-graph neural networks》 论文提供的预处理的子集。预处理后，每个数据集包含 3000 个用户节点以及 3000 个 item 节点，以及对应的 user-user 或 item-item 交互图。

   下图给出了数据集的统计信息，其中Features 表示是否包含用户特征或者item 特征，Ratings 表示数据集的评分数量，Density 表示评分矩阵中已观测评分的占比，Rating level 表示评分等级范围。

   

2. baseline 模型：

   • 矩阵补全模型，包括 MC, IMC, GMC, GRALS, sRGCNN 。具体细节参考前文所述。
   • 矩阵分解模型，包括 PMF, I-RBM, BiasMF, NNMF 。 具体细节参考前文所述。
   • 协同过滤模型，包括 LLORMA-Local, I-AUTOREC, CF-NADE 。 具体细节参考前文所述。

   另外我们还对比了我们不带额外信息的GCMC 模型，以及带辅助信息的 GCMC+Feat 模型。

3. 参数配置：

   • 所有 baseline 方法直接采用原始论文中的实验结论数据（因此也不需要实现和运行这些 baseline 方法）。

   • 对于 GCMC 模型，我们通过验证集从以下超参数范围选择最佳的超参数：

     • 聚合函数accumulation ：stack vs sum。
     • 是否在编码器中使用有序权重共享：是 vs 否。
     • 编码器中$c_{i,j}$$ c_{i,j} $ 为归一化常数：左归一化 vs 对称归一化。
     • node dropout 比例：$p_{\text{dropout}}\in \{0.3,0.4,0.5,0.6,0.7,0.8\}$$ p_\text{dropout}\in \{0.3,0.4,0.5,0.6,0.7,0.8\} $ 。

     另外，除非另有说明，否则我们使用以下超参数配置：

     • 使用学习率为 0.01 的 Adam 优化器。
     • 解码器基权重矩阵数量$n_b=2$$ n_b = 2 $ 。
     • 编码器采用：维度 500 的单层卷积层（使用 ReLU 激活函数） + 维度 50 的单层 dense层（无激活函数）。

     最后，我们使用学习模型参数的指数移动平均（衰减因子 0.995）在保留的测试集上评估模型。

4. Movielens-100k 数据集（特征向量形式的辅助信息实验）：我们直接使用数据集原始的 u1.base/u1.test 的训练集/测试集拆分结果。对于该数据集，我们使用辅助信息来参与所有模型的训练。在该数据集我们对比了矩阵补全 baseline 方法和我们的 GCMC 方法，其中：

   • GMC, GRALS, sRGCNN 通过$k$$ k $ 近邻图来表示 user/item 特征。
   • 其它方法直接使用原始特征向量。

   对于 GCMC 的超参数，我们将原始训练集按照 80:20 进行训练集/验证集的拆分，然后通过验证集来调优超参数：在图卷积中使用 stack 作为累积函数，选择$p_{\text{dropout}}=0.7$$ p_\text{dropout} = 0.7 $ ，使用左归一化。一旦选择好超参数之后，我们就在整个原始训练集上重新训练模型，并利用训练好的模型来评估测试集。

   对于 GCMC 模型，我们不带任何辅助信息。对于 GCMC + Feat 我们使用辅助信息，并且辅助信息的 side information layer 使用维度大小为 10 的 dense 层（采用 ReLU 激活函数）。

   我们使用 1000 个 full-batch epoch 来训练 GCMC 和 GCMC + Feat 。我们随机重复执行 5 次并报告测试集上的平均 RMSE 结果。整体评估结果如下（baseline 数据直接来自于 《Geometric matrix completion with recurrent multi-graph neural networks》）。

   结论：

   • 我们的 GCMC 方法明显优于baseline 方法，即使在没有辅助信息的情况下也是如此。

   • 和我们方法最接近的是 sRGCNN 方法，它在用户和 item 的近邻图上使用图卷积，并使用 RNN 以迭代的方式学习表示。

     实验结果表明，使用简单的解码器（而不是复杂的 RNN）直接从学到的user embedding/ item embedding 中直接评估评分矩阵可以更有效，同时计算效率更高。

   

5. MovieLens-1M, MovieLens-10M 数据集（无辅助信息的实验）：在该数据集上我们和当前的 state-of-the-art 协同过滤算法（如 AutoRec, LLorma, CF-NADE ）进行比较。

   我们采取和 《A neural autoregressive approach to collaborative filtering》 相同的训练集/测试集拆分方式，拆分比例 90:10 。另外，baseline 方法的结果直接使用该论文的数值。

   该数据集不带任何辅助信息，因此我们没有比较 GCMC + Feat 。我们对原始训练集按照 95:5 随机拆分为训练集/验证集，然后通过验证集来调优超参数：

   • 对于 MovieLens-1M 数据集，我们使用 sum 作为累计函数，选择$p_{\text{dropout}}=0.7$$ p_\text{dropout} = 0.7 $ ，使用对称归一化。

   • 对于 MovieLens-10M，我们使用 stack 作为累计函数，选择$p_{\text{dropout}}=0.3$$ p_\text{dropout} = 0.3 $ ，使用对称归一化。

     另外考虑到该数据集的评分等级数量翻倍，我们选择解码器的基参数矩阵数量$n_b$$ n_b $ 用于翻倍（即$n_b=4$$ n_b = 4 $ ）。

   一旦选择好超参数之后，我们就在整个原始训练集上重新训练模型，并利用训练好的模型来评估测试集。

   对于 MovieLens-1M 我们训练 3500 个 full-batch epoch，对于 MovieLens-10M 我们训练 18000 个 mini-batch step（对应于 batch size =10000, epoch = 20 ）。

   我们按照 90:10 随机拆分原始训练集/测试集，并重复执行 5 轮，报告模型在测试集上的平均 RMSE。所有 baseline 评分来自于论文 《A neural autoregressive approach to collaborative filtering》 中的数据。对于 CF-NADE 我们报告了最佳性能的变体。

   结论：

   • GCMC 方法可以扩展到大规模数据集，其性能可以达到 user-based 或者 item-based 协同过滤的 state-of-the-art 方法。
   • CF-NADE 引入的几种技术，如：layer-specific 学习率、特殊的ordinal 损失函数、评分的自回归建模，这些都和我们的方法正交，因此这些技术也可以和我们的 GCMC 框架结合使用。

   

6. Flixster, Douban, YahooMusic （图形式的辅助信息实验）：这些数据集包含了一些图结构的辅助信息。我们通过使用这些图的邻接向量（根据degree 进行归一化）作为相应的 user/item 的特征向量，从而引入辅助信息。

   注意：辅助信息的图是社交网络等 user-user 图，或者 item-item 图。它们不同于 user-item 二部图。

   我们根据论文 《Geometric matrix completion with recurrent multi-graph neural networks》 的训练集/测试集拆分。所有 baseline 方法的结果都取自于该论文的数值。

   我们从训练集中按照 80:20 随机拆分为训练集/验证集，然后通过验证集来调优超参数：在图卷积中使用 stack 作为累积函数，选择$p_{\text{dropout}}=0.7$$ p_\text{dropout} = 0.7 $ ，使用左归一化。一旦选择好超参数之后，我们就在整个原始训练集上重新训练模型，并利用训练好的模型来评估测试集。

   对于 GCMC 模型，我们使用辅助信息，并且辅助信息的 side information layer 使用维度大小为 64 的 dense 层（采用 ReLU 激活函数）。

   我们使用 full-batch 训练 200 个 epoch 。

   最终我们重复执行 5 轮，并报告模型在测试集上的平均 RMSE。其中 Flixster 有两组结果：左侧结果表示同时引入了 user 辅助信息和 item 辅助信息；右侧结果表示仅考虑 item 辅助信息。

   结论：GCMC 在所有baseline 中取得了 state-of-the-art 效果。

   注意：GCMC 在所有三个数据集上都采用相同的超参数配置，如果针对各自数据集调优，效果会进一步提升。

   

7. 冷启动实验：为深入了解 GCMC 模型如何通过辅助信息来提升冷启动性能，我们选择 MovieLens-100K 数据集，随机选择固定数量的冷启动用户$N_c$$ N_c $ ，这些用户最多随机保留$N_r$$ N_r $ 个评分（整个实验中随机数种子固定，因此每次随机选择的结果都相同）。注意：MovieLens=100K 原始数据仅包含具有至少 20 个评分的用户。

   我们考察当$N_r\in \{1,5,10\},N_c\in \{0,50,100,150\}$$ N_r\in \{1,5,10\}, N_c\in \{0,50,100,150\} $ 时GCMC 的性能（$N_c=0$$ N_c=0 $ 表示所有用户都保留所有评分）。其中超参数和测试集如前面所述一样选择。结果如下图所示，虚线表示不带辅助信息时模型的表现。

   可以看到：对于冷启动用户，使用辅助信息能够带来显著的提升，在只有一个评分的用户上表现尤为突出。