# 矩陣分析論文閱讀 I

> 閱讀3篇論文及寫相關筆記

## Diffusion Convolutional Recurrent Neural Network: Data-Driven Traffic Forecasting

预测道路流量（Traffic Forecasting），路网距离和实际空间距离不是一个概念。例如两条道路，离得近的可能是相向而行的两条不同的道路，而隔得较远的两段路可能正好是同一条大道的不同路段，显然后者的依赖会更强。

已有的图卷积过于关注邻域，我们需要具有全局视角的图卷积。

### Contribution

提出了扩散卷积（Diffusion Convolution）使得卷积层的感受野扩大，并以此为基础构建了一个扩散卷积层，采用多个独立的扩散卷积层将P维特征映射到Q维输出。此处还证明了基于谱的无向图卷积等价于扩散卷积。

利用扩散卷积层替代GRU中的矩阵乘法，得到DCGRN（扩散卷积门控循环单元）

为了解决测试集（未来）与训练集（历史）的分布偏移问题，在训练时以一定概率选择使用模型的预测值或真实值作为输入，以此让模型去学习预测较远的未来

### Method

扩散卷积的启发在于将节点特征对周围的影响类比于状态转移过程，让每个节点的特征尽可能向四周扩散，而根据状态转移理论这一扩散最终会收敛到一个稳定的概率分布，类似于扩散过程。$\alpha$是随机游走概率，表示这一时间步发生状态转移的概率。$D_o$是出度矩阵。W表示邻接矩阵，其中每个元素表示两个顶点之间的相关性（浮点数）。k表示随机游走的次数。得到的


最后就是我个人认为比较不好理解的一幅整体框架图。其中每一层是一个时间步，虚线的回转线代表着GRU的迭代。中间的“投掷硬币”的图表示在训练阶段以一定概率选择模型预测的结果替换Ground Truth进行训练。


### Experiment

采用METR-LA和PEMS-BAY数据集，与ARIMA以及LSTM等进行了比较，证明其在15min、30min、1hour的不同时长的预测上均超越已有方法。

同时进行了对扩散卷积的消融实验，证明了扩散卷积的加入有助于收敛并且降低了验证集上的误差。


证明了扩散卷积步数K大概在3以上就差不多了（说明每个节点的影响基本不超过3-hop），以及Q的值大概在64左右最佳。

## BPR: Bayesian Personalized Ranking from Implicit Feedback

项目推荐是预测对一组项目（例如，网站，电影，产品）的个性化排名的任务。在本文中，我们使用隐式反馈（例如点击次数，购买次数）调查最常见的情况。从矩阵分解（MF）或自适应k近邻（kNN）等隐式反馈中有很多项目推荐方法。尽管这些方法是针对个性化排名的项目预测任务而设计的，但它们都没有直接针对排名进行优化。在本文中，我们提出了一个通用的优化标准BPR-Opt，用于个性化排序，这是从问题的贝叶斯分析得出的最大后验估计。 我们还提供了一种通用学习算法，用于优化与BPR-Opt相关的模型。学习方法基于随机梯度下降和自举采样。我们展示了如何将我们的方法应用于两个最先进的推荐模型：矩阵分解和自适应kNN。我们的实验表明，对于个性化排名的任务，我们的优化方法优于MF和kNN的标准学习技术。结果显示了为正确标准优化模型的重要性。

推荐内容是许多信息系统中的一项重要任务。例如，像亚马逊这样的在线购物网站为每个客户提供用户可能感兴趣的产品的个性化推荐。其他示例是像YouTube这样向客户推荐电影的视频门户。个性化对于可以增加销售或观看的内容提供商以及更容易找到有趣内容的客户都具有吸引力。在本文中，我们关注项目推荐。项目建议的任务是为一组项目创建用户特定的排名。用户关于项目的偏好是从用户过去与系统的交互中学习的——例如，他的购买历史，观看历史等

推荐系统是一个活跃的研究课题。最近的工作是在用户提供明确反馈的情况下，例如在评级方面。然而，在实际情况中，大多数反馈并不是明确的，而是隐含的。隐式反馈会自动跟踪，例如监控点击次数，查看次数，购买次数等。因此，收集起来要容易得多，因为用户无需明确表达自己的品味。事实上，几乎所有信息系统都已提供隐式反馈——例如， Web服务器记录日志文件中的任何页面访问。

在本文中，我们提出了一种学习个性化排名模型的通用方法。这项工作的贡献是：

1. 我们提出了从最大后验估计器导出的通用优化准则BPR-Opt，以获得最佳个性化排名。我们展示了BPR-Opt与ROC曲线下面积最大化的类比。
1. 为了最大化BPR-Opt，我们提出了基于随机梯度下降和训练三元组的自举(bootstrap)采样的通用学习算法LearnBPR。我们证明我们的算法优于标准梯度下降技术，以优化关于BPR-OPT
1. 我们将展示如何将LearnBPR应用于两个最先进的推荐模型类。
1. 我们的实验经验表明，对于个性化排名的任务，使用BPR学习模型优于其他学习方法。

### Related Work

> 最受欢迎的推荐系统模型是k近邻（kNN）协同过滤。传统上，kNN的相似性矩阵通过启发式计算——例如,Pearson相关性——但在最近的工作中，相似性矩阵被视为模型参数，并且专门针对该任务进行了学习。最近，矩阵分解（MF）在推荐系统中变得非常流行，用于隐式和显式反馈。在早期工作中，已经提出奇异值分解（SVD）来学习特征矩阵。通过SVD学习的MF模型显示出非常容易过度。因此提出了正则化学习方法。对于项目预测Hu等人和Pan等人提出了一个带有case weights的正则化最小二乘优化(WR-MF)。case weights可用于减少负例的影响。 Hofmann 提出了项目推荐的概率潜在语义模型.Schmidt-Thieme 将问题转化为多类问题，并用一组二进制分类器解决它。即使上面讨论的关于项目预测的所有工作都是在个性化排名数据集上进行评估，但这些方法都没有直接优化其模型参数以进行排名。相反，他们优化以预测用户是否选择了某个项目。在我们的工作中，我们推导出基于项目对（即两个项目的用户特定顺序）的个性化排名的优化标准。我们将展示如何针对该标准优化诸如MF或自适应kNN的最先进模型，以提供比通常学习方法更好的排名质量。详细讨论了我们的方法与Hu等人的WRMF方法之间的关系和Pan等人以及最大边际矩阵分解可以在第5节中找到。在4.1.1节中，我们还将讨论我们的优化准则与AUC优化的关系，如中所述。

在本文中，我们专注于模型参数的学习。将学习方法扩展到在线学习场景——例如添加了一个新用户，他的历史记录从0增加到1,2 ,….反馈事件——已经针对相关的评级预测任务研究了MF。相同的折叠策略可用于BPR。

还有关于学习与非协同过滤模型排名的相关工作。一个方向是模拟排列的分布。 Burges等人优化神经网络模型，使用梯度下降进行排名。所有这些方法只学习一个排名——即它们是非个性化的。与此相反，我们的模型是学习个性化排名的协同过滤模型，即每个用户一个单独的排名。在我们的评估中，我们凭经验证明，在典型的推荐设置中，我们的个性化BPR模型甚至优于非个性化排名的理论上限。

### Personalized Ranking

个性化排名的任务是向用户提供排序的项目列表。这也称为项目推荐。一个例子是想要推荐用户可能想要购买的个性化排序项目列表的在线商店。在本文中，我们研究了必须从用户的隐式行为（例如，过去的购买）推断出排名的场景。对隐式反馈系统感兴趣的是只有正面观察可用。未观察到的用户-项目对——例如，用户尚未购买物品——是真实负面反馈的混合物（用户对购买物品不感兴趣）和缺失值（用户可能希望将来购买物品）。

### Formalization

设U是所有用户的集合，I是所有项目的集合。在我们的场景隐式反馈S⊂U×I
可以使用（见图1的左侧）。这种反馈的示例是在线商店中的购买，视频门户中的视图或网站上的点击。推荐系统的任务现在是为用户提供个性化的所有项目的总排名>u⊂I2
中的，其中>u 必须满足总顺序的属性：

为了方便,我们也定义:

### Analysis of the problem setting

正如我们之前所指出的，在隐式反馈系统中，只观察到正类。其余数据是实际负值和缺失值的混合。应对缺失值问题的最常见方法是忽略所有这些问题，但是典型的机器学习模型无法学习任何东西，因为它们无法再区分这两个级别。

项目推荐系统的通常方法是预测个性化的分数x̂ ui
项反映了用户对项目的偏好。然后根据得分对项目进行排序。项目推荐系统的机器学习方法通常通过一对(u,i) ∈S为正类标签，(U×I)\\s为负类标签的所有其他组合(见图1)。这意味着对模型进行了优化，以预测S中元素的值为1，其余元素为0。该方法存在的问题是，在训练过程中，将模型未来((U×I)\\S)中所有应该排序的元素作为负反馈呈现给学习算法。这意味着一个具有足够表达能力的模型(它不能准确地拟合训练数据)根本不能排名，因为它只能预测0s。这种机器学习方法之所以能够预测排名，唯一的原因是为了防止重复，比如正规化。


我们使用不同的方法，使用项目对作为训练数据，并优化正确排名项目对而不是评分单项，因为这更好地代表问题，而不仅仅用负面替换缺失值。从S中我们尝试重建>u
的每个用户部分。如果用户已经查看了项目i——即(u,i)∈S——那么我们假设用户更喜欢这个项目而不是所有其他未观察到的项目。例如在图2中，用户u1已查看项目 $i_2$ 但未查看项目i1，因此我们假设此用户优先于项目$i_2$而不是 $i_1:i_2>ui_1$。对于已经被用户看到的项目，我们无法推断任何偏好。对于用户尚未看到的两个项目（例如，用户$u_1$的项$i_1$和$i_4$）也是如此。为了形式化，我们创建了训练数据DS：U×I×I 通过：


(u,i,j)∈DS 的语义是假设用户u更喜欢i而不是j.由于>u 是反对称的,负案例被认为是隐含的。


作者的方法有两个优点:

我们的训练数据包括正负对和缺失值。两个未观察到的项目之间缺少的值正是将来必须进行排序的项目对。这意味着从两两的角度来看，训练数据 $D_S$
和测试数据是不相交的。
针对排名的实际目标创建训练数据，即，将$>_u$ 的观察子集 $D_S$ 用作训练数据。

### Bayesian Personalized Ranking(BPR)

在本节中，我们推导出一种用于解决个性化排名任务的通用方法。它由个性化排名的一般优化标准BPR-Opt组成，它将通过使用p(i>uj|θ) 的似然函数的贝叶斯分析和模型参数先验概率p(θ)。我们显示了排名统计AUC（ROC曲线下面积）的类比。对于关于BPR-Opt的学习模型，我们提出算法LearnBPR。最后，我们展示了BPROpt和LearnBPR如何应用于两种状态的推荐算法，矩阵分解和自适应kNN。通过BPR优化，这些模型能够比通常的训练方法产生更好的排名。

#### BPR Optimization Criterion

发现所有项目i∈I正确个性化排名的贝叶斯公式是最大化下述后验概率其中θ
表示任意模型类的参数向量(例如,矩阵分解)

p(θ|>u)正比于p(>u|θ)p(θ) 其中,＞u 是用户u所需的但潜在的偏好结构.假定所有用户彼此独立行动.我们还假设特定用户的每对项目(i,j)的排序与每个其他对的排序无关.因此,上述用户特定的似然函数p(>u|θ) 可以首先被重写为单个密度的乘积,并且第二个被组合用于所有用户u∈U。


其中δ是指示函数


到目前为止，通常无法保证获得个性化的总顺序。为了确定这一点，需要充分考虑已经提到的声音特性（总体性，反对称性和传递性）。为此，我们将用户真正更喜欢项目i而不是项目j的个体概率定义为：


其中σ 是逻辑sigmoid：

这里$x̂ u_ij$ 是模型参数向量θ的一个任意实值函数,他能捕获用户u,项目i和项目j的特定关系.换句话说，我们的通用框架将建模u,i和j之间的关系的任务委托给基础模型类,如矩阵分解或自适应KNN,它负责估计$x̂ u_ij$.因此，对个性化的总顺序>u进行统计建模是可行的。为了方便起见,在接下来我们将跳过来自x̂ uij的参数θ。

到目前为止，我们只讨论了似然函数。 为了完成个性化排序任务的贝叶斯建模方法，我们引入了一般的先验密度p(θ)，它是具有零均值和方差-协方差矩阵的正态分布∑θ。


在下面，为了减少我们设置的未知超参数的数量∑θ=λθI。现在我们可以制定最大后验估计来推导出我们用于个性化排名BPR-Opt的通用优化标准。


其中λθ 是模型特定正则化参数

Analogies to AUC optimization

通过贝叶斯个性化排序(BPR)方案的建立，可以很容易地理解BPR与AUC的相似之处。每个用户的AUC通常定义为:


因此平均AUC是:


使用我们的 $D_S$表示法，可以写成：


其中$z_u$是标准化常数:


等式（1）和BPR-Opt之间的类比是显而易见的。除了归一化常数zu之外，它们仅在损失函数中有所不同。 AUC使用与Heaviside函数相同的非差异损失δ(x>0)：


相反，我们使用差异损失lnσ（x）。通常的做法是在优化AUC时替换不可分离的Heaviside函数。替换的选择通常是启发式和类似形状的函数σ使用（参见图3）。在本文中，我们得出了由MLE推动的选择替换lnσ(x)。

## LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation

### 摘要

GCN模型是不是越复杂越好呢？这篇文章分析发现，GCN中常用的矩阵变换（feature transformation）和非线性激活函数（nonlinear activation）没有作用，甚至有反作用，据此作者提出了一个非常简单的GCN模型LightGCN，模型参数只有节点的embedding。这么简单的模型在推荐任务上，比大多数复杂模型的性能都要好，而且作者从理论分析了如此设计存在的若干好处。

### 简介

作者所在团队在2019年发表了一个NGCF的模型，该模型基于user和item的交互关系网络，使用GCN训练得到user和item的embedding，然后使用embedding相似度进行推荐。

简单来说，第k+1层的user和item的embedding使用如下公式计算。其中的W1是直接对embedding进行变换的矩阵，W2是对user和item点乘之后进行变换的矩阵；而σ是非线性激活函数。

以user为例，右边有两项，第一项是对user在第k层的embedding进行矩阵变换；第二项是邻居聚合。其中邻居聚合又有两项，第一项是对item的embedding进行矩阵变换；第二项是对user和item点乘之后进行矩阵变换。


作者发现，对于协同过滤任务来说，由于user和item都只有ID本身，没有很多的属性，所以并不需要复杂的矩阵变换和非线性激活函数。言下之意是，如果节点有丰富的属性信息的话，非线性变换和激活有用？感觉可以这么理解：有些属性重要，有些属性不重要，所以需要非线性激活函数进行识别？如果只有节点ID的话，ID的embedding的所有维度都是重要的，不需要非线性激活，直接线性加权聚合就行了。

然后作者对NGCF模型进行了简单的消融实验，如下表所示，NGCF就是原始的NGCF，NGCF-f、-n、-fn分别表示去掉矩阵变换W1和W2、去掉非线性激活函数σ、同时去掉W1、W2和σ。很意外的是，-f、-n、-fn居然都比原始的NGCF效果好，而且-fn效果最好。说明对于只有user和item顶点，没有属性的网络来说，不用过于复杂的矩阵变换和非线性激活，效果反而更好。


按道理NGCF的参数空间比NGCF-f大，且前者能覆盖后者（只需要把W1和W2设置成单位矩阵），为什么前者的效果反而比后者差呢？作者进一步分析了两者训练时的loss和recall曲线，发现NGCF的参数空间虽然比NGCF-f大，但其收敛后的loss更大，recall更小。也就是说训练效果反而不如NGCF-f。作者认为，加入过多的矩阵变换和非线性变换，导致模型过于复杂，难以训练到较好的效果。据此，作者提出了一个更简单的模型LightGCN，具体看下一节介绍。

### 方法

既然前面分析说矩阵变换和非线性激活函数会起副作用，LightGCN的方法非常简单，就是把这两个操作去掉。如公式3所示，每个节点的embedding表示直接等于其邻居的embedding的线性加权求和，既没有矩阵变换，也没有非线性激活函数，如此的简单。而且，对比公式3和公式1可知，LightGCN没有显式使用自回路，即计算某个节点的embedding的时候，只用了其邻居的embedding，没有用自己的embedding；而NGCF在公式1中使用了自回路。


其网络结构图如下：


最后，节点的最终embedding等于其各层embedding的加权求和。如公式4所示，权重系数α可以手工指定，也可以使用注意力网络来自动学习。为简便起见，本文直接设置为等权重，所有系数都等于1/(K+1)，相当于所有层embedding求平均。


节点最终embedding等于各层embedding的加权求和有如下三个好处：

* GNN存在over-smoothing的问题，即随着网络层数越深，深层网络的输出结果趋向于相同。即所有节点的最后一层的输出有可能很接近。而如果把所有层加起来的话，能一定程度上缓解这个问题
* GNN不同层捕获的语义信息不一样，使用所有层输出能增强表达能力，这个和CNN的道理是类似的。
* 所有层embedding求和可以捕获自回路的信息。也就是说虽然公式3没有显式使用自回路，但计算顶点最终embedding时（公式4）可以隐含自回路的信息，这个后面会给出证明。

除此之外，由于LightGCN很简单，所以也很好训练，更容易收敛，收敛效果更好。总之，虽然LightGCN很简单，但它很强大，而且有很多好处。

### 模型分析

接下来，作者分析了为什么LightGCN可以学习到自回路，其证明思路是这样的。另一篇工作SGCN和这篇工作很像，也做了很多简化，且显式添加了自回路。作者通过分析发现LightGCN可以表达SGCN的形式，间接说明LightGCN隐含可以考虑自回路。下面是具体的证明过程。

首先定义user和item的交互矩阵 $R \in R^{M X M}$其中M和N分别表示user和item的个数。 $R_{ui}$为1表示u和i有交互，等于0表示没有交互。则全图的邻接矩阵可以表示为公式6：


公式3的矩阵形式可以表示成公式7，其中矩阵D为度矩阵。对照下原始的GCN公式，其实就是把原始GCN的变换矩阵W和非线性激活函数σ去掉了。


由于LightGCN是将多层embedding加权求和，所以最终结果是公式8：


然后作者对SGCN的公式进行了简单的变换，发现形式上和公式8是一致的，所以LightGCN也能隐含学习到自回路特征。

此外，作者还分析了另一个模型APPNP，APPNP借鉴pagerank的思想，可以缓解GNN过深带来的over-smoothing问题。然后作者如法炮制，对APPNP的公式进行变换，发现也和公式8等价，所以LightGCN也能缓解GNN的over-smoothing问题。其实这个从LightGCN不只使用最后一层，而是使用所有层embedding就能得到这个结论，不需要这么大费周章证明。

### 实验

最后是实验环节。作者将LightGCN和本文开头提到的NGCF进行了对比，实验结果表明，LightGCN的性能相比NGCF有显著提升，而且比NGCF-fn也高。作者提到，虽然NGCF-fn已经去掉了矩阵变换和非线性激活函数，但NGCF-fn仍然还有自回路、user和item的点积、dropout等等，还是比较复杂，不好训练。而LightGCN非常简单，只有embedding和邻居的线性加权，所以LightGCN还是比NGCF-fn好。真的很神奇啊，照这个说法，难道连dropout也会起副作用？

此外，在消融实验中，作者还对比了LightGCN和LightGCN-single，LightGCN-single是只用LightGCN的最后一层作为节点的embedding。作者发现，当网络层数增大到4层时，LightGCN-single性能显著下降，出现了over-smoothing的问题。而LightGCN由于多层组合的操作，不会有over-smoothing的问题。考虑到性能和收益，LightGCN使用了3层神经网络。

### 评价

结果有些意外，LightGCN这么简单的模型，效果居然比复杂模型还要好？感觉即使是NGCF，模型也不复杂啊，和CV、NLP那些大模型相比简单多了，怎么就训练不好了呢？难道是GNN特有的现象？

感觉和数据有关，本文测试的数据是只包含user和item顶点，顶点没有属性。如果是属性图的话，也许结论会有变化。

不过至少提供了调参的思路：去掉矩阵变换、去掉非线性激活函数、甚至是去掉dropout。另外重要的一点是，不要只用最后一层的embedding，而是组合所有层的embedding进行加权求和。

另外，本文开篇提到的NGCF和本文是同一批作者，自己批判自己一年前发表的工作，不免让人担心这篇工作的可靠性。。。以及当时的NGCF难道没有做本文开篇的消融实验吗？难道不应该吗？