KGAT : Knowledge Graph Attention Network for Recommendation

0 ABSTRACT

在推荐系统领域中，为了使推荐结果更加准确、可解释性更高，不仅要考虑user-item之间的关系，引入外部知识丰富user-item之间的信息也非常有必要。在这方面比较常用的方法主要有FM算法（factorization machine，因子分解机），该方法主要问题在于将user-item作为相互独立的实例，忽视了item之间可能存在的相互作用关系。

本文提出了一种基于知识图谱和注意力机制的新方法-KGAT（Knowledge Graph Attention Network）。该方法通过user和item之间的属性将user-item实例链接在一起，摒弃user-item之间相互独立的假设。该方法将user-item和知识图谱融合在一起形成一种新的网络结构，并从该网络结构中抽取高阶链接路径用来表达网络中的节点。

1 INTRODUCTION

常用推荐算法主要有CF算法（collaborative filtering）和SL算法（supervised learning）。

协同过滤的模型一般为m个物品，m个用户的数据，只有部分用户和部分数据之间是有评分数据的，其它部分评分是空白，此时我们要用已有的部分稀疏数据来预测那些空白的物品和数据之间的评分关系，找到最高评分的物品推荐给用户。

一般来说，协同过滤推荐分为三种类型。第一种是基于用户(user-based)的协同过滤，第二种是基于项目(item-based)的协同过滤，第三种是基于模型(model based)的协同过滤。基于模型(model based)的协同过滤是目前最主流的协同过滤类型了，我们的一大堆机器学习算法也可以在这里找到用武之地。

基于用户的CF(User-Based CF主要思想是利用<user,item>的打分矩阵, 利用统计信息计算用户和用户, item和item之间的相似度。然后再利用相似度排序, 最终得出推荐结果。
在协同过滤中，一个重要的环节就是如何选择合适的相似度计算方法，常用的两种相似度计算方法包括皮尔逊相关系数和余弦相似度等。皮尔逊相关系数的计算公式为：

根据皮尔逊公式，基于用户的CF算法公式为：

该公式要计算用户$i$和用户$j$之间的相似度, $I_{ij}$是代表用户i和用户j共同评价过的物品, $R(i,x)$代表用户i对物品$x$的评分, $\overline{R(i)}$代表用户i所有评分的平均分:之所以要减去平均分是因为有的用户打分严有的松, 归一化用户打分避免相互影响。

基于项目的CF(Item-Based CF) 和基于用户的CF类似，只不过这时我们要求物品和物品之间的相似度，就先要找到（或获得）目标用户对某些物品的评分，那么我们就可以对相似度高的类似物品进行预测，将评分最高的若干个相似物品推荐给用户。比如你在网上买了一本机器学习相关的书，网站马上会推荐一堆机器学习，大数据相关的书给你，这里就明显用到了基于项目的协同过滤思想。
既然IBCF和UBCF是类似的，那就可以借鉴UBCF的思想，选一个合适的相似度呗——所以还可以用皮尔逊，最终得到IBCF公式：

我们从上面最最最传统的CF公式（好吧或者说是算法）可以看出它面临两个问题：

• 矩阵稀疏问题
• 计算资源有限导致的可扩展性不好

为什么会矩阵稀疏呢？

什么是稀疏矩阵：在矩阵中，如果数值为0的元素数目远远多于非0元素的数目，并且非0元素分布无规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。

那我还就稀疏了怎么着了？：稀疏矩阵会导致空间复杂度和时间复杂度的问题。1. 在空间上，非常大的矩阵需要大量的内存，稀疏的矩阵其零值比数据值要多，因为这些零值不包含任何信息，这显然是对内存资源的浪费。 2. 在时间上，对于我们输入的一个矩阵，如果该矩阵中大部分是零值，那么处理的时候计算机需要或将零值相加或相乘。而因为大多数O(N^3)算术运算都用于求解方程组或反转（invert）包含零操作数的矩阵。所以时间复杂

对于“可扩展性”也好理解，就以UBCF为例，随着系统用户数量的增大，计算Top-K Relevance User的时间会显著增长，使得该方法难以胜任用户量变化巨大的系统，该方法限制了系统的可扩展性。

回到论文中来：
为了解决CF上面的两个问题，现在国际惯例是用一个结合用户ID和项目ID的特征向量，扔到监督学习模型中，预测新用户和新项目的(契合)得分，比如我们的张量分解模型FM，xDeepFM模型云云…（下面我自己称这些方法叫SL方法吧）
考虑由导演$e_1$拍的电影$i_1$和客户$u_1$之间的交互影响(interact)（注意这里是电影和客户的交互而不是导员和客户的交互），CF算法会关注历史上同样看过电影$i_1$的用户，从而根据这些用户$u_4,u_5$对其他电影的喜好(如$i_2$)来推荐给$u_1$; SL算法关注导演的影响，$e_1$导演拍过$i_1和i_2$两部电影，那么是否把$i_2$也推荐给$u_1$呢？

但是现实往往是残酷的…作者说上面的想法是需要"high-order connectivity"的，SL算法不能考虑到比如黄圈里的$i_3,i_4$看过同样由$e_1$导演的其他电影

那么怎么理解这里的“传统算法无法接触到黄圈等‘高维信息’呢？”以下是我个人理解，不一定正确甚至可能犯理论上的错误
在论文 《Neural Collective Entity Linking》中，作者认为传统模型不能获得“高度辨别的语义信号,比如实体关系(highly discriminative semantic signals)”,举例如下：
对于一句(超长超长的)话·

Hussain, considered surplus to England’s one-day requirements, struck 158, his first championship century of the season, as Essex reached 372 and took a first innings lead of 82.

Youdao翻译成中文是：“Hussain被认为超出了英格兰队的单日比赛要求，他打出了158分，这是他本赛季第一次获得冠军，埃塞克斯达到了372分，并在第一局以82分领先”，那么这里的England应该被理解成
除非传统模型利用到在England、Hussain、Essex附近的，和话题"cricket"有相互干系的相邻信息，才可能消除England的歧义

其实我觉得，这里的意思是不是这里England可能机器把他理解为一个人了？或者是英格兰的国家？（一个叫英格兰的小伙？），需要知道下文的英格兰的城市埃塞克斯才可以知道具体指的是英格兰队？…那感觉这个“多义词”的例子举得不是很好啊…消歧消的是多义词对吧。

所以上文的作者提出用图模型解决这一距离过长的问题：下图展示了命名实体消歧(England,Hussian,Essex)
用箭头线连接的节点是候选实体，其中红色实线表示目标实体。
当然仅仅用图模型还是有很多缺陷，这也是 《Neural Collective Entity Linking》后续介绍的内容，但是图模型能将实体关系复杂化是很好的消息。

再扯回来，刚刚我们提出了两个目前对复杂高阶连通的挑战（黄色高亮），众多SL算法能够在一维实体关系层面解决上述两种挑战（计算能力和稀疏问题），那么我们现在只需要引入图模型，将SL算法扩展到在高维实体关系层面上。因此作者介绍了他的collective knowledge graph CKG模型：
作者认为，成功推荐的关键在于充分利用CKG图的高阶关系，比如这种(能够到达SL所及不了的黄圈和灰圈)远程连通性：

画饼简单，但是怎么用图模型具体实现呢？
考虑怎么实现，就要分析需要克服什么问题：

• 与目标用户具有高阶关系的节点随着阶数的增加而急剧增加，给模型增加了计算负荷（也就是为后文embedding layer做铺垫）
• 高阶关系对预测的贡献是不均衡的，这就要求模型仔细地权衡(或选择)它们（也就是为后文Attention引入的权值矩阵做铺垫）

接下来作者说，我们可以用图神经网络做，(但是这个我们目前懒(不)得做(会)，你们谁会谁去做吧）。所以稳妥起见，作者提出了KGAT方法，这种方法有两大宝具：

1. 递归嵌入传播(对复杂度宝具）
2. 基于attention的聚合方法（对预测宝具）

2 TASK FORMULATION

刚刚说我们KGAT有两大宝具，那么这两大宝具都是怎么被作出的呢？作者说，你们啊还是要学习一个，所以先提出了一些基本概念，不着急慢慢来：

2.1 User-Item Bipartite Graph

还是以看电影为例：用户(user)和电影(items)之间是有历史交互信息的，比如你们以前看过XXXX电影。那么我们把这个interaction data做成一个用户-项目的双边关系图$G_1$(哪位大侠能告诉我文章里这一块用的那个数学符号是啥名字吗嘤嘤嘤…），定义：G1={(u,yui,i)∣u∈U,i∈I}G_1=\{(u,y_{ui},i)|u\in U,i\in I\}G1?={ (u,yui?,i)∣u∈U,i∈I}其中$U$和$I$表示用户和项目的集合，连接$y_{ui}=1$代表观察到集合中某一个u和某一个i出现交互，反之为0

2.2 Knowledge Graph

针对2.1中的这个交互interactions，我们可以从中的得到项目的附加信息(side information)，比如电影的属性和外部知识（啥是外部知识？可以理解为比如一部电影的emmmm历史背景?_？）。通常这些辅助数据可以从真实世界的实体(电影导演)和它们之间的关系获得，进而组成一个电影(item)
比如形容一部电影可以从它的导演，灯光师，流派风格等等着手。那么我们把这些side information做成“由实体-属性-另一个对应的实体”三元组构成的有向图$G_2$：G2={(h,r,t)∣h,t∈ξ,r∈R}G_2 = \{(h,r,t)|h,t\in \xi ,r\in R\}G2?={ (h,r,t)∣h,t∈ξ,r∈R}其中每一个三元组表示一个从头实体$h$到尾实体$t$的双向关系（怎么理解？）

比如三元组 (Altria ActorOf Saber）代表在《命运之夜天之杯》电影中："人物阿尔托莉雅是角色Saber的饰演者"这层关系;而我们也可以表示成 (Saber ActorIn Altria）表明Saber的饰演者是型月著名女一号阿尔托莉雅小姐。然而无论是Saber还是阿尔托莉雅都不是用户user，这也就是说这个G2能囊括很多电影相关的信息

然而作者并非止步于谁是Saber谁是Fate这个深度，作者希望把老虚也拉进来，于是建立了"item-entity alignments"这层关系：A={(i,e)∣i∈I,e∈ξ}A=\{(i,e)|i \in I,e\in \xi\}A={ (i,e)∣i∈I,e∈ξ}从而拓宽了模型的深度（喜欢老虚的可能就能推荐Fate/Zero）

2.3 Collaborative Knowledge Graph

将用户喜好和电影知识形成统一的关系图，首先要用数学语言表示出“用户喜好”：$$(u,Interact,i)$$其中，$y_{ui}=1$表示在用户和电影之间有交互关系
基于2.2中后半部分的电影-老虚关系(item-entity)集合的思想，为了拓宽模型深度，作者一统天下，把用户-老虚(user-entity)图和2.2前半部分的KG图$G_2$整合成统一图：G={(h,r,t)∣h,t∈ξ′,r∈R′}G=\{(h,r,t)|h,t\in {\xi}',r\in R' \}G={ (h,r,t)∣h,t∈ξ′,r∈R′}其中${\xi }^{\prime }=\xi ?U$, $R^{\prime }=R?Interact$

换句话说这段意思就是：

• 对于实体：把用户和Saber、Altria、老虚…等等众多和item有关的因素实体合起来形成的新实体集合${\xi }^{\prime }$。
• 对于关系：将用户（用户只是众多实体中的一种实体）与电影的单向交互关系$Interact$和多种其他实体的双向关系结合起来，得到新关系集合$R^{\prime }$

2.4 High-Order Connectivity

作者再次重申了利用高阶连通性是优秀推荐的重要保障，并为我们描述了L阶连通性是什么亚子：
其中上面的$e_i$和$r_i$都来自新实体集合${\xi }^{\prime }$和新关系集合$R^{\prime }$。
上图写作$$(e_{l?1},r_l,e_l)$$读作第$l$个三元组，并称这个三元组序列的长度为L
##########################华丽的分界线##############################
至此，我们学习完了基本知识，但是为什么要学习这些知识呢？为啥要把这几个集合合起来呢？我要是不合起来会咋样呢？

不合起来，行，那就走传统路线，CF或者SL模型选一个吧！
好，CF模型的连通性结构长下面这个亚子：
可以看出来，CF方法建立在用户之间行为相似的基础上——更具体地说，相似的用户在项目上表现出相似的偏好。比如，我舍友(u1)喜欢(r1)看《Fate/Zero》，而我(u2)也喜欢看,然后我u2还喜欢看《超炮》，那我把超炮推荐给我舍友u1吗？事实上我舍友只喜欢看老虚这种风格的作品，超炮太治愈了舍友接受不了，所以这种连通不稳。

那换SL算法呢？
SL算法通常只考虑一个实体的一个特征，也就是说从一部电影到另一部电影只能考虑一个因素，比如上图中的$r_2$这一个因素，无法显示items和相关实例之间的相关性,比如：
这种情况（左边考虑导演喜好关系右边考虑演员喜好关系）就行不通。

3 METHODOLOGY

终于进入全篇高潮部分了，作者说KGAT模型由以下三个部分组成，嵌入层、注意力嵌入传播层和预测层，这些在图中表示的也很清晰：

3.1 Embedding Layer

为了将数据输入网络中，首先要进行嵌入，这里给自己啰嗦一下啥是图嵌入：

图嵌入是一种将图数据（通常为高维稠密的矩阵）映射为低微稠密向量的过程。我们都知道图是由节点和边构成，这些向量关系一般只能使用数学，统计或者特定的子集进行表示，但是嵌入之后的向量空间具有更加灵活和丰富的计算方式，方便进行机器学习。

图嵌入能够压缩数据， 我们一般用邻接矩阵描述图中节点之间的连接。 连接矩阵的维度是$|V|?|V|$，其中$|V|$是图中节点的个数。矩阵中的每一列和每一行都代表一个节点。矩阵中的非零值表示两个节点已连接。

将一个图embedding成低维稠密向量有两种方法，但这两种方法万变不离其宗的思想就是Worl2Vec思想(独热编码后扔到DNN中梯度下降入Softmax输出选择概率）

• 节点嵌入（以DeepWalk为例）：随机游走起始于选定的节点，然后从当前节点移至随机邻居，并执行一定的步数，该方法大致可分为三个步骤：
  

1. 采样：通过随机游走对图上的节点进行采样，在给定的时间内得到一个节点构成的序列
2. 训练skip-gram：随机游走得到的节点序列与word2vec方法中的句子相当。文本中skip-gram的输入是一个句子，在这里输入为随机游走采样得到的序列，然后通过最大化预测相邻节点的概率进而学习预测周围节点
   3)计算嵌入之

• 图嵌入方法：图嵌入是将整个图用一个向量表示的方法，Graph2vec同样由三个步骤构成：
  

1. 采样并重新标记图中的所有子图。子图是出现在所选节点周围的一组节点。子图中的节点距离所选边数不远。
2. 训练skip-gram模型,类比Word2Vec。经过训练，可以最大程度地预测输入中存在于图中的子图的概率。
3. 通过在输入处提供子图的id索引向量来计算嵌入

那么，咱们分析一下，这里用的是图嵌入还是节点嵌入呢？
我个人的理解是图嵌入，因为从KGAT的模型中从第一步就开始建立子图（三元组，就是图中的$e_{i_1}{}^0$等subgraph）,毕竟我理解的两种嵌入最大的区别就是是直接刚节点还是曲线救国积沙成塔整合区域节点为子图。

好了好了再扯回来…我们嵌入好了，就运用TransR模型：（关于TransR模型可以先简单理解为建立$(h,r,t)$的向量运算关系，是真正的数学层面关系）
$$TransR:e_t^r=e_h^r+e_r$$其中$e_h,e_t\in {\mathbb{R}}^d$代表一个三元组$(h,r,t)$经过嵌入embedding后的头实体和为实体，$e_r\in {\mathbb{R}}^k$同理。并且上角标$r$表示的是经过TransR变换到r超平面中的$e_h,e_t$。

为了解决之前提出的第二个高亮问题（分配不均衡），我们将输入特征转换为高层特征，这一过程需要一个可学习的线性转换（one learnable linear transformation）。为了达到该目标，我们考虑采用《Attention is All You Need》这篇神文的一个共享的线性转换，通过对每一个节点进行加权。我们称这一过程为self-attention。

对于一个给定的三元组，根据《Graph Attention Networks》给出的self-attention处理模型：
回过头针对这里的三个变量模型，我们建立自己的势能函数：
其中$W_r\in {\mathbb{R}}^{k\times d}$是关系$r$的变换矩阵，将${\mathbb{R}}^d$的实体空间转换到${\mathbb{R}}^k$的$r$关系超平面中（这一超平面就是之前TransR过程中的超平面，换言之，若你用TransE就不需要转换）

考虑到损失函数（loss function）是用来估量你模型的预测值$f(x)$与真实值$Y$的不一致程度，它是一个非负实值函数,通常使用$L(Y,f(x))$来表示，损失函数越小，模型的鲁棒性就越好。所以这里我们给出势能函数$g(h,r,t)$的损失函数：

其中$\sigma$是sigmoid函数，自变量趋于正/负无穷是输出1或-1。通常我们给正样例的分数高，负样例的分数低，保证括号内作差小于0 （外面一个负号，负负得正）从而保证训练过程每轮Loss大于0。

这里还需要啰嗦一句：$g(h,r,t^{\prime })和g(h,r,t)$的关系：前者表示不存在图中的三元组组合。啥意思咧？
咱们训练不是要正负样例吗（在SL基础上改的肯定要监督哇），我们用正样例，比如：(美国 总统 奥巴马) 去生成一个和这个正样例相关的负样例：(美国 总统 本拉登）。但是，万一我们的语料库中正好有拉登这个负样例，那就重复了嘛，所以这里还有专门的处理方法（我忘了，恳请各位大神补充）。

3.2 Attentive Embedding Propagation Layers

这一节讲的是传播。
我们先从单层的传播描述，然后再介绍从单层到多层的方法。

3.2.1 Information Propagation

一个实体可以包含在多个三元组中，理论上充当连接两个三元组和传播信息的桥梁，比如：

和

这里面$i_2$可以将$e_1$和$e_2$作为输入来enrich自己的特征，从而为用户$u_2$提供更多的选择推荐。这就是我们实现信息传递的中心思想。

考虑实体$h$,我们记"以实体$h$为头实体的所有三元组"为ego-network：

为了刻画实体$h$的一阶连通性结构，我们记$h$的ego-network网络的线性组合为：
其中$\pi (h,r,t)$决定三元组$(h,r,t)$上每次传播的衰减系数，可以理解为从$t$到$h$传播的信息中有多少与$r$有关。

通过公式怎么看出衰减系数依赖于在关系$r$向量空间中尾实体 $t$ 与头实体 $h$的距离，具体这个是怎么理解的？
我的理解是这样的：(这是我在知乎上的回答）
1 首先，这里的衰减系数π(h,r,t)，就是我们通常attention机制中的计算相似度的第四种方法，而这个π(h,r,t)是怎么来的呢？请看下文
2 在attention中，我们取一个非线性函数f(比如LeakyReLU就行)表征两个实体之间的相似度(在《Attention is all you need》这篇神文里指的是Q,V,K向量，可以了解一下)。那么我们经过多次迭代所有实体后，需要输出attention向量以计算对应特征的线性加权，所以就需要将得到的相似度进行归一化，就是文中的tanh（第四种）操作。所以这里的衰减系数π(h,r,t)，我谨理解为是相似度的归一化函数。
3 2中的非线性函数，在这篇文章中就是g(h,r,t)，所以衰减系数π(h,r,t)本质上是g的函数，而g(h,r,t)中是有着h与t的距离信息的。所以衰减系数π(h,r,t)就可能依赖于距离了

个人理解，可能不严谨或者完全不对，如有不正确的地方还望指出，也希望能和大家多多讨论。

3.2.2 Knowledge-aware Attention

下面这一部分就是Attention中的内容了，注意力函数$e_{ij}$也有很多种变体。四种注意力变体：加性注意力（additive attention）、乘法（点积）注意力（multiplicative attention）、自注意力（self-attention）和关键值注意力（key-value attention）。这里给出的是用tanh非线性激励函数加性注意力（additive attention）,可以使得注意力得分依赖于超平面$r$空间中$e_h$和$e_t$之间的距离，为更近的实体传播更多信息。
我们采用softmax函数对所有与刚刚说的与$h$头实体相连的三元组的系数进行归一化处理:

3.2.3 Information Aggregation

好了我现在得到每一层的输出的概率了，那么现在要把所有层加起来，大概对应于图中的这一步：
红圈是第一层，蓝圈是第二层，高亮黄框应该延伸到$W_1^l$和$W_2^l$的，这里是我涂鸦失误，误把这里的W和之前的$W_r$混淆了。

最后一步首先要完成聚合(aggregation)，这里我们以第一种聚合器为例，《Semi-Supervised Classification with Graph Convolutional Networks》提出的聚合器：输入是两个表示向量的和，然后与可训练权值的$d^{\prime }\times d$ 矩阵$W$相乘后再经过激活函数(这里取了LeakyReLU)后输出。其中$W$是可以提取有用的信息用于传播的权值矩阵（没错就是之前说的那个对预测宝具）。

3.2.4 High-order Propagation

我们可以进一步堆叠更多的传播层来得到高阶连接信息，收集从高阶邻点的传播信息。在第$l^{th}$步骤中，我们递归地将一个实体的表示形式表示为:
其中，$h$实体在$l?ego$第l阶的ego网络中传播的信息定义如下:
这个式子表示每个经过Softmax的注意力分数($\pi$)与其对应的值(实体e)相乘，这个过程会产生对应数量的对齐向量(alignment vector),我们通常称之为加权值。其中，$e_t^{l?1}$是从前面的信息传播步骤中由尾实体$t$产生的，包含着第$l?1$阶的所有邻点信息。所以高阶连通性如：
就可以通过以上四个过程得到了。（你看黄圈里面的$u_2$（在编码后叫做$e_{u_1}^{(3)}$）不就和最左边的$u_1$连上了吗）。

注意这里还没有合并，只是通过递归得到了我想要的阶次的实体表示$e_h^{(l)}$而已

3.3 Model Prediction

对应的是这一部分：
concatenate的输入是刚刚每层输出的各阶信息$e_h^{(l)}$(没错就是刚刚的加权值).通过分析不同layer的输出就可以得到从1到多阶的连通性,我们采用layer-aggregation机制（上文提到的另一种方法）进行concatenate这么多层的输出。(说白了就是对加权值求和，得到输出1）

最后，我们对用户和项目的表示e进行内积，从而预测它们的匹配分数：

3.4 Optimization

作者综合了多种Loss模型，提出了分别对KG和CF两种Loss合并起来算Loss:

基本内容如上，这之后的训练模型就是如论文中所述。感谢文章的作者提出的宝贵学术资料。

w_h = [
[0,0,1],
[1,1,0],
[0,1,0].
[1,1,0]]
w_r = [