推荐|GNN通俗笔记：图神经网络在推荐/广告中的应用

原始视频：七月在线公开课《图神经网络在推荐广告场景中的应用》，课件可以打开视频页面下载
分享老师：推荐吴老师，推荐/广告算法专家，曾任部门算法负责人，年薪....不低
字幕校对：天保，全程校对了字幕，但因为是公开课，互动性很强，所以去掉了很多互动性的语句
笔记撰写：July，在原有公开课/课件基础上做了大量的解读、补充、说明、深入、扩展
交流讨论：涉及到多名同事、讲师，包括且不限于推荐吴老师、北邮团博士、助教杜老师等等

前言

下午在社区上看到一篇面经《本科毕业10年从传统IT转风控：曾自学后通过集训营拿下多个40 50万offer》，面经作者在文章里面提到：“我早在2014年左右就关注July的csdn，他的很多博文受益匪浅”，包括之前有一学员在其朋友圈提到：“七月在线的July老总写的理解SVM的三层境界和掌握比赛大杀器Xgboost很好，多揣摩是很好的”，便激发了自己想再度更新博客的想法。毕竟我这个两千万访问量级的博客，历经过去十年，影响力还是足够大的。

加之，最近图神经网络很火，我们还特地开了个《实战CV下的图神经网络》课，且去年10月底，推荐吴老师专门做了一次GNN公开课，耳濡目染中，总会有点想法，故本文基于吴老师的GNN公开课成文，既是笔记、备忘录，更会在笔记基础上不断扩展、深入，以成为了解图神经网络和其在推荐/广告上应用的一篇综合导论性的文章。

本文先后涉及如下内容：

GNN通俗导论，包括什么是图神经网络、什么是Embedding、什么是Word2Vec、图神经网络之GE（GE之DeepWalk、GE之LINE、GE之GraRep、GE之Node2Vec、GE之Struc2Vec、GE之GraphSAGE、GE之GraphWave、GE总结）、图神经网络之GCN；
GNN在推荐/广告中的应用，包括End2End建模与两阶段建模、End2End之GCMC、End2End之PinSage（PinSage之构图实践、PinSage之GNN模型、PinSage之Training、PinSage之Servering）、End2End之淘宝EGES、两阶段案例；
GNN体系结构简介，包括阿里高性能图服务-Euler（Euler 之分布式图引擎、Euler 之图操作算子、Euler之GQL查询接口Euler 2.0、Euler之MP抽象层）。

之后则是Q&A，比如做推荐算法工作需要具备什么样的能力，以及如何提升工程能力等等。最后，若有疑问/问题，欢迎留言/指正哦。

1 GNN通俗导论

今天这个公开课，主题是图神经网络在推荐广告场景中的一个应用，分享的内容分为三大块

第一个是图神经网络的一个介绍；
然后第二块就是图神经网络在推荐广告中的一些应用、一些案例；
然后第三块是图神经网络在工业界落地的时候，它需要有哪些必要的组件。因为我们不仅仅需要有图神经网络的这些个算法，还需要一些其他的工程组件，算是一个组合。

1.1 什么是图神经网络

在了解图神经网络之前，我们有必要了解一下为何会有图神经网络这个结构。

一般而言，一个技术的诞生都是伴随着解决某个或某类问题的，那图神经网络解决什么问题呢？已有的倚天屠龙CNN、RNN不香了么？这个问题问得好！

众所周知，CNN主要用于图像类数据的处理（详细了解可看此文：CNN通俗笔记），RNN则主要用于时序类数据的处理（详细了解请看此文：从RNN到LSTM）。然现实中，在越来越多的应用程序中，数据是从非欧几里得域生成的，并表示为具有复杂关系和对象之间相互依赖的图形。图数据的复杂性给现有的机器学习算法带来了巨大的挑战。

比如下图左为图像（欧几里得空间），右为图（非欧几里得空间）：

传统的神经网络结构如CNN、RNN等都是接受欧几里得空间的数据作为输入，他们无法处理非欧几里得空间的数据结构。而对于图这类数据，图神经网络就更加适合处理，也导致了近年来图神经网络的研究热度不断提升，如下图所示：

总之，图是一个非常常用的数据结构，包括典型的我们的社交网络、用户商品图、蛋白体结构，以及交通路网知识图谱，这些都是可以描述成Graph的一个结构，然后甚至规则的网格数据，它其实也是图的一种特殊形式。因此，图是一个非常值得研究的领域。

第二，我们说Graph的研究一般分类有哪几种：

第一种就是经典的图算法，比如路径搜索、二分图，这个在哪里能用到呢？如果你要去百度地图或高德地图，那么这个RP算法、这个路径搜索，也就是说我们会用到Graph的一些算法。然后二分图在哪用呢，这个典型的场景就是滴滴，滴滴这个分单算法是一个二分图匹配；
还有一类问题叫概率图模型，比如条件随机场，这个学NLP的大家都知道这个CRF用的特别多（想更好理解CRF可以看下这个CRF视频）；
然后第三块就是我们今天介绍的一个主题，就是图神经网络，主要包括Graph Embedding以及GCN这两大块，还有一些知识图谱的内容我们这里不做过多涉及。

然后第三个说一下图神经网络，他从18年开始是一个非常火热的研究方向，然后这里边有几个原因，第一个就是深度学习在其他领域的一个成功，包括CV以及NLP，然后这些都是规则的一些网格数据，而在不规则的网络数据自然也想有一个拓深。
那么第二个就是广泛的使用场景，上面也说到了，很多的场景都可以建成Graph的一个问题，这边我列了一个KDD2020的一个选题，GNN它其实是力压群雄的，他就是排名第一，并且这一个是从18年大概就一直是这样一个趋势，这边附赠大家一个CV的全景图：

这边是我总结的到2018年左右的，这个图给大家show出来其实有两个目的吧：

第一个目的就是GNN，我刚才说了GNN，他的这个出发点是什么，他是怎么能够想到这样一个问题，就是由于这个CNN在视觉领域的一个成功以及深度学习在NLP的成功，所以想做一个迁移；
然后第二块呢，想给大家一个提醒，就是说算法的内核其实是一致的，不管是CV、NLP 还是推荐、广告还是其他所有的，它们之间其实都是非常相关的，至少底层的东西都是一致的，并且有一个发展的先后顺序。一般来说我们认为CV领先NLP 1~2 年，然后NLP又领先推荐1~2年，所以如果你要是想做推荐，或者正在学习推荐的同学，你可以多关注一下CV以及NLP的一些最近的发展，里边会给你提供很多的输入以及一些 insight。

举个最简单的例子，比如我们现在在用的Relu优化器，最近在工作中其实我们都知道NLP、Transformer、BERT，他用了GLUE，我们换成GLUE的时候他就是在某些场景它能够有个一定的提升、带来一定的业务收益。

当然还有这个Attention。这里我给大家提一个问题，大家都知道这个注意力机制，那我想问一下注意力机制最开始来源于哪里呢？CV、NLP还是推荐呢，大家有人知道吗？对，其实是CV啊。我看到有同学回答对了，它其实是CV先有了这样一个思想，然后到了NLP，在NLP里我们都知道是RNN加这个Attention，这个Attention在NLP领域发扬光大后又反哺给了CV。

注意，考虑到本篇文章侧重图神经网络在推荐/广告中的应用，故关于图神经网络的一些基础概念可以看下这篇文章，比如

空域卷积（图卷积神经网络主要有两类，一类是基于空域的，另一类则是基于频域的。通俗点解释，空域可以类比到直接在图片的像素点上进行卷积，比如1.4.6节要讲的GraphSage，而频域可以类比到对图片进行傅里叶变换后再进行卷积）；
消息传递网络；
图上的傅里叶变换等等。

1.2 什么是Embedding

我们接着往下看图神经网络，首先介绍Graph Embedding，那么我们先说一下什么是Embedding。

Embedding 在数学上是一个函数，就是一个X到Y这样一个函数，从一个空间映射到另一个空间，通常情况下是高维抽象的空间映射到一个低维具象的空间；
第二个性质呢Embedding一般是稠密的、分布式的表示，这是对应于这个OneHot编码的，待会细说。

其次，为什么会出现Embedding这样一个东西：

第一个原因就是抽象的事物，它本应有一个低维的表示。我们知道当你看到一个图片的时候，图片里面有一只狗，比如上图右侧上方那个图：像素图，你看到它是一条狗，但是其实它最底层的表示是什么，它最底层的表示是一堆的像素，对不对，这一堆的像素的表示就是狗这个图片在视觉领域的最低维的一个表示；同样你看到一个单词dog，那么它本身也应该有一个类似的表示，这就是我们说的这个Word2Vec。换言之，当我们看到一个哈士奇、一个金毛、一个比熊，那么它本身也有自己的性格对不对，甚至每一只狗都有他自己的性格，都有一个最底层的表示。
第二个原因是计算机比较善于处理低维的信息，这也是为什么CV发展要较NLP要较快一点，因为它善于处理这样的信息；
第三个原因是解决OneHot编码的一个问题，OneHot编码有什么问题？两个：

第一个问题就是他随你的物料、随你的词汇增大而增大，比如你去做Word2Vector，那么你的corpus假设有10万个单词，那你OneHot编码就得有10万维，如果有1000万，那么你的OneHot编码就是1000万维，所以它是不固定的；

然后第二个问题就是OneHot编码是一个讨巧的方式，它每一个单词或者每一个 Item它只有一个 1，对不对。这样的话你没有办法去表示谁和谁相近的这样一个这样一个关系，但是Embedding它是可以做到，现在Embedding用的很成熟了，从Word2Vec开始然后到 Item2Vec、Node2Vec以及今天我们讲的这个 Graph Embedding都算Embedding的范畴。

1.3 什么是Word2Vec

我这里只是show出来，我这里不再单独讲了，大家只需要看一下，最右边这个式子这个是最原始的推导，大家看到这个式子的时候有没有很熟悉，我想问一下，我想问一下这个式子跟softmax有什么关系（点我了解什么是softmax）？

有同学知道吗，看着是不是很像一个softmax 的一个回归？其实Word2Vec呢，它本身最终优化的一个式子就是一个softmax的形式，但是他跟softmax的区别是什么呢？

输入是否是确定的。softmax 回归或者我们叫LR回归，它的输入是确定的，比如你对图片做一个二分类，那么你输入的是一堆像素，对不对？这一对像素不会再变化了；但我们做Word2Vec的时候，我们本身要求的那个东西就是输入的那个向量，他是你要求的，然后还有一个网络的参数也要求，所以它是输入与参数都不确定，是你都要优化的一个问题。
优化方法不一样。正因为softmax跟Word2Vec的本质区别就是输入的不确定，这也导致了它们优化方法的不同。softmax我们知道是一个凸优化问题，你可以直接求解，对吧？然后Word2Vec呢，由于它输入以及里边的参数都不确定，所以我们需要有一个类似于SGD（坐标上升）这样一个方法去求。

第二个，我们要增加大家一定的敏感度，大家知道上图右下角小圈圈起来的那个式子叫什么吗？不管是softmax还是Word2Vec，下面那个我们通常就叫做Z，这个Z表示的是配分函数，就是你对全局做一个计算、全局做一个求和，这个计算是不是很耗时，那Word2Vec是怎么做的，我们知道负采样对不对，负采样其实它的学名叫做NCE，即噪声对比估计（给大家一个提醒，就是以后你只要遇到这样一个配分函数的计算，那么首先想到的就是噪声对比估计），也就是我们常说的负采样。
关于负采样为什么最后的优化是跟原来的式子优化是等价的呢，这样一个证明，有兴趣的同学可以再看一下：噪声对比估计杂谈。

更多关于word2vec的理解可以看下此文：如何通俗理解word2vec。

1.4 图神经网络之GE

现在我们就来看一下Graph Embedding的一个全景图

当然这个Graph Embedding从16年开始到现在，它已经有很多的这样一个分支了，这里边甚至还没考虑知识图谱的TransE、TransR、TransH等技术，我们今天只介绍一些特别重要特别必要掌握的，不管你是在工作中还是你去面试，只要你说学过或者了解过Graph Embedding，那么这些东西一定会被问到的，我们就讲这些最必要的东西。

1.4.1 GE之DeepWalk

第一个就是DeepWalk，这个就是Graph Embedding的始祖了啊，他的思想非常的简单，他就是纯粹借鉴了Word2Vec，我们想象一下，假设我现在有一个图，我要让你去做Graph Embedding，那么参照Word2Vec，你有什么想法呢，它缺什么？

在展开之前先说下相关公式符号，比如上图公式里面的 $\pi _{vx}$ 是一个从 $v$ 到 $x$ 的非正规化的转移概率，最简单的一种计算方式就是 $\pi _{vx} = w_{vx}$ ，对于无权图， $w_{vx} = 1$ ，而Z是一个正规化常量。

Word2Vec首先有几个要素：

第一个要素是词库词表，我们的词对应于这个Graph上，词表是对应每个node，一个node就是一个单词，你这个图上有一亿个节点，那么你的词表就是1亿
还有一个概念叫句子，做Word2Vec的时候会有一个句子，然后句子会做一个n-gram，比如我们就做 5-gram 吧，那么也就是我们用 skip-gram 的方法的话，就是用中心词去预测前面两个以及后面两个对不对，那我们需要构造这个句子，即在图上怎么构造这个句子；
然后第三个要素是语料库，也就是一堆的句子组成的一个语料库。

那么DeepWalk其实就是解决了这三个要素。那我怎么去从 Graph 上去做这三个要素，做成一批句子以及语料库、词表，然后去按照Word2Vec的方法去优化呢？它的思想其实非常简单，就是随机游走，这其实也能看得出来，就是在一个领域初始的时候，我们想做出一点贡献是相对简单些的，像这篇论文引用量应该已经非常高了。

具体怎么做的呢？比如我们有一个图，我在这里边简单给大家画一个，比如一个十字架上，右侧线路的权值是 1，下侧线路的权值是 2，左侧线路的权值是 3，上测线路的权值是 4；
对于这张十字架图，从某个节点开始，去随机游走，按照什么方式游走呢，这个式子其实看见PI_vx，就是从V到x是表现的一个条件概率，从V节点游走到下一个节点X的一个概率，这个 Z 就是配分函数，然后 PI_vx 就是他的权值；
比如十字架的中心叫 1 节点吧，十字架的下侧节点叫 2 节点，它的概率等于什么呢？等于：(1~2的权值)/(1+2+3+4)，这就是它的随机游走的概率，那么你可以并行地去随机游走多个，然后随机出来一些句子，然后按照Word2Vec的一个方法去优化就可以了。

1.4.2 GE之LINE

接下来，LINE这个算法在工业界中已经用的非常多了，这个方法虽然跟DeepWalk在建模上是一个思路，但其实已经很不一样了，比如它已经不借鉴Word2Vec，它的思想是定义两种相似度，一个是一阶相似度，一个是二阶相似度。

如浅梦所说，LINE也是一种基于邻域相似假设的方法，只不过与DeepWalk使用DFS构造邻域不同的是，LINE可以看作是一种使用BFS构造邻域的算法。此外，LINE还可以应用在带权图中(DeepWalk仅能用于无权图)。

一阶相似度用于描述图中成对顶点之间的局部相似度，形式化描述为若 $v_{i}$ 和 $v_{j}$ 之间存在直连边，则边权 $w_{ij}$ 能看出两个顶点的相似度，若不存在直连边，则一阶相似度为0。如下图，节点6和7之间存在直连边，且边权较大，则认为两者相似且一阶相似度较高，而节点5和6之间不存在直连边，则两者间一阶相似度为0。

一阶相似度的具体计算过程如下（上图右侧的第一套公式就是一阶相似度）：

比如 $v_{i}$ 和 $v_{j}$ 这两个顶点(类比节点6和7)的边权为 $w_{ij}$ ，定义经验分布

$\hat{p_{1}}(v_{i},v_{j}) =\frac{w_{ij}}{W}$

其中

$W = \sum_{{(i,j)\epsilon E}}^{}w_{ij}$

表达的意思为节点 $v_{i}$ 和 $v_{j}$ 的边权值在所有边权值之和里所占的权重；

然后你向量化Embedding之后， $v_{i}$ 和 $v_{j}$ 两个顶点之间的联合概率为

$p_{1}(v_{i},v_{j}) = \frac{1}{1 + exp(-\vec{u_{i}}^{T}\cdot \vec{u_{j}})}$

其中， $\vec{u{_{i}}}$ 、 $\vec{u{_{j}}}$ 分别为顶点 $v_{i}$ 、 $v_{j}$ 的低维向量表示，整个式子可以看作一个内积模型，计算两个顶点之间的相近程度；

从而，咱们优化的目标就是这个 $O_{1} = d(\hat{p}_{1}(\cdot ,\cdot ),p_{1}(\cdot ,\cdot ))$ ，目的是为了缩小两个分布之间的距离，使两个分布之间的差异性尽可能的小、尽可能的相似。也就是说，现在我们需要通过不断拉近一阶相似度的真实分布与经验分布之间的距离 $d(\cdot ,\cdot )$ ，最后达到两者的均衡，使得一阶相似度的损失尽可能的小；
考虑到常用的衡量两个概率分布差异的指标为KL散度，且离散条件下为

$KL(p||q) = \sum p(x)log\tfrac{p(x)}{q(x)}$

故两个分布之间的差异性可以用KL-散度来进行表示，使用KL散度并忽略常数项后，得到最终的一阶相似度的目标函数为

$O_{1} = - \sum_{{(i,j)\epsilon E}}^{}w_{ij}log\ p_{1}(v_{i},v_{j})$

喜欢刨根问底的同学可能问了，上面最后一步是怎么一个计算过程呢？以下是详细推导(注：因为 $p$ 、 $\hat{p}$ 加个下标1只是为了与后面二阶相似度公式区分开，没别的特殊含义，为推导方便，下述推导过程中下标1省去)：

考虑到

$D_{KL}({\hat{p}(v_{i},v_{j}) || p(v_{i},v_{j})}) = \sum_{(i,j)\epsilon E}\hat{p}(v_{i},v_{j})log\frac{\hat{p}(v_{i},v_{j})}{p(v_{i},v_{j})}$

且 $\hat{p}(v_{i},v_{j}) =\frac{w_{ij}}{W}$ ，所以有

$O_{1} = D_{KL}({\hat{p}(v_{i},v_{j}) || p(v_{i},v_{j})}) \\ = \sum_{{(i,j)\epsilon E}}^{} \frac{w_{ij}}{W}log\frac{w_{ij}}{W\cdot p(v_{i},v_{j})}$

且类似 $Xlog_{a}\frac{M}{N\cdot D} = Xlog_{a}M - Xlog_{a}(N\cdot D)$ ，有

$O_{1} \Rightarrow \mathop \sum_{{(i,j)\epsilon E}}^{} w_{ij} log\frac{w_{ij}}{W\cdot p(v_{i},v_{j})} \\ = \sum_{{(i,j)\epsilon E}}^{}w_{ij} logw_{ij} - \sum_{{(i,j)\epsilon E}}^{}w_{ij}log(W\cdot p(v_{i},v_{j})) \\ = \sum_{{(i,j)\epsilon E}}^{}w_{ij}logw_{ij} - \sum_{{(i,j)\epsilon E}}^{}w_{ij}logW - \sum_{{(i,j)\epsilon E}}^{} w_{ij}log\ p(v_{i},v_{j})$

另因为 $w_{ij}$ 、 $W$ 为常数，所以 $\sum_{{(i,j)\epsilon E}}^{}w_{ij}logw_{ij}$ 、 $\sum_{{(i,j)\epsilon E}}^{}w_{ij}logW$ 都为常数，可以忽略不计，从而最终可得

$O_{1} = - \sum_{{(i,j)\epsilon E}}^{}w_{ij}log\ p(v_{i},v_{j})$

仅有一阶相似度就够了吗？显然不够，如下图：

节点5和6之间不存在直连边，用一阶相似度判定的话，他们不相似，对吧？但这个结论会不会有问题呢，举个现实中的例子，某两个人虽然暂时不是朋友，但如果这两人有一堆共同的朋友，是不是可以看出这两人是相似的呢？毕竟交友的偏好接近。
所以，节点5和6虽然没直接相连，但它们有很多相同的邻居顶点(1,2,3,4)，那如果用它们的邻居的重合度定义为二阶相似度的话，是否可以得出5和6其实是相似的呢？
好，接下来问题在于怎么定义邻居的重合度。对于节点5和6，5有1 2 3 4这4个邻居，6也有1 2 3 4这4个邻居，假设 5 到1 2 3 4的这个边权设为1 2 3 4，然后6到1 2 3 4的边权也是1 2 3 4，则他们的边权也就是完全一样的，那么通过二阶相似度的式子优化（本小节开头大图右侧的第二套公式就是二阶相似度），我们就得到5和6的相似度是1，他们是完全相似的。

那二阶相似度的计算流程是什么呢？

二阶相似度假定具有大量相同邻接顶点的两个顶点是相似的，在这种情况下，每个顶点可以看作是一个特定的上下文/邻居（context），从而可以认为具有相同或相似上下文分布的顶点被认为是相似的。换言之，因此，在这种场景下，每个顶点既是顶点本身，也是其他顶点的上下文。

基于此，作者提出了两种向量表示 $\vec{u{_{i}}}$ 和 ${\vec{u{_{i}}}}'$ ，其中 $\vec{u{_{i}}}$ 为顶点 $v_{i}$ 作为顶点本身时的向量表示，而 ${\vec{u{_{i}}}}'$ 为该顶点 $v_{i}$ 作为其他顶点的上下文时的向量表示。
对于每个有向边 $e_{ij}$ ，作者定义了给定顶点 $v_{i}$ 的条件下，产生上下文/邻居顶点 $v_{j}$ 的条件概率为 $p_{2}(v_{j}|v_{i}) = \frac{exp({\vec{c}_{j}}^{T}\cdot \vec{u}_{i})}{\sum_{k=1}^{|V|} exp({\vec{c}_{k}}^{T}\cdot \vec{u}_{i})}$ ，其中|V|为顶点 $v_{i}$ 的上下文顶点的个数，其实就是对于 $v_{i}$ ，各节点为其context的概率(分母可以看作是归一化因子)。比如 $v_{1}$ 的邻居 $v_{2}$ $v_{3}$ $v_{4}$ ， $v_{5}$ 的邻居 $v_{2}$ $v_{3}$ $v_{6}$ ，如果 $p_{2}(\cdot|v_{1})$ 和 $p_{2}(\cdot|v_{5})$ 的概率分布是相似的(即两个顶点 $v_{1}$ 和 $v_{5}$ 的context相似)，那么这两个节点就second-order proximity而言是相似的。
所以，为了保留Second-order Proximity，我们希望每个顶点在其上下文上的条件分布能最大程度的拟合其经验分布，自然而然，则需要最小化这个目标函数： $O_{2} = \sum_{i\epsilon V}^{} \lambda _{i}d ({\hat p_{2}(\cdot |v_{i}),p_{2}(\cdot |v_{i}))$ ，其中 $\lambda _{i}$ 为控制节点重要性的因子，可以通过顶点的度数或者PageRank等方法估计得到。其中 $d(\cdot ,\cdot )$ 表示两个分布之间的距离，作者同样采用了KL散度来度量，另外作者通过引入 $\lambda _{i}$ 来表示不同的顶点在网络或图中的重要性，该值可以通过PageRank等考察顶点重要性的方法来获得。
而上式中的经验分布 $\hat{p}_{2}(\cdot|v_{i})$ 可以表示为 $\hat{p}_{2}(v_{j}|v_{i}) = \frac{w_{ij}}{d_{i}}$ ，其中 $w_{ij}$ 表示边 $e_{ij}$ 的权重， $d_{i}$ 表示顶点 $v_{i}$ 的出度，对于带权图， $d_{i} = - \sum_{{k\epsilon N(i)}}^{}W_{ik}$ ，其中 $N(i)$ 是 $v_{i}$ 节点的“出”邻居（从i节点出发的邻节点）；
假设 $\lambda_{i} = d_{i}$ ，然后使用KL散度（采用KL散度作为距离函数，即使用KL距离代替 $d(\cdot ,\cdot )$ ），并忽略常数项，有： $O_{2} = - \sum_{{(i,j)\epsilon E}}^{}w_{ij}log\ p_{2}(v_{j}|v_{i})$

从而通过学习每个节点 $v_{i}$ 的两个向量表示 $\vec{u}_{i}$ 、 ${\vec{u{_{i}}}}'$ 来最小化这个目标函数，最终得到每个节点的 $d$ 维向量表示。

我把本篇笔记发到推荐高级班的群里后，有同学对上面第5步的计算有疑问，另一位李同学马上就手推了一下

首先，我们要求解的目标是

$O_{2} = \sum_{i\epsilon V}^{}\sum_{{(i,j)\epsilon E}}^{}\lambda _{i}d ({\hat p_{2}(v_{j}|v_{i}),p_{2}(v_{j}|v_{i}))$

根据 $D_{KL}(p||q) = \sum p(x)log\tfrac{p(x)}{q(x)}$ ，可得

$D_{KL}({\hat p_{2}(v_{j}|v_{i})||p_{2}(v_{j}|v_{i})) \\ = \sum_{{(i,j)\epsilon E}}^{} {\hat p_{2}(v_{j}|v_{i}) log\frac{\hat p_{2}(v_{j}|v_{i})}{p_{2}(v_{j}|v_{i})}$

使用KL距离代替 $d(\cdot ,\cdot )$ ，从而有

$O_{2} = \sum_{i\epsilon V}^{} \sum_{{(i,j)\epsilon E}}^{} \lambda_{i} {\hat p_{2}(v_{j}|v_{i}) log\frac{\hat p_{2}(v_{j}|v_{i})}{p_{2}(v_{j}|v_{i})}$

考虑到 $\hat{p}_{2}(v_{j}|v_{i}) = \frac{w_{ij}}{d_{i}}$ ，且假设 $\lambda_{i} = d_{i}$ ，统统代入可得

$O_{2} = \sum_{i\epsilon V}^{} \sum_{{(i,j)\epsilon E}}^{} d_{i} \frac{w_{ij}}{d_{i}} log\frac{\hat p_{2}(v_{j}|v_{i})}{p_{2}(v_{j}|v_{i})}$ ；

因为 $d_{i} = - \sum_{{k\epsilon N(i)}}^{}W_{ik}$ 是常数项，所以上述式子可得

$O_{2} = \sum_{i\epsilon V}^{} \sum_{{(i,j)\epsilon E}}^{} {w_{ij}} log\frac{\hat p_{2}(v_{j}|v_{i})}{p_{2}(v_{j}|v_{i})} \\ = \sum_{{(i,j)\epsilon E}}^{} {w_{ij}} log\frac{w_{ij}}{d_{i}} - \sum_{{(i,j)\epsilon E}}^{} w_{ij}logp_{2}(v_{j}|v_{i})$

因为 $w_{ij}$ 为常数，所以 $d_{i} = - \sum_{{k\epsilon N(i)}}^{}W_{ik}$ 也是常数，从而忽略常数项可得

$O_{2} = - \sum_{{(i,j)\epsilon E}}^{} w_{ij}logp_{2}(v_{j}|v_{i})$

二阶相似度相比一阶相似度确实要抽象。举个例子

两个节点a1 b1，a1的三个邻居a2 a3 a4，边权分别为(1，2，3)，b1的三个邻居a2 b2 a3，边权分别为(3，2，2)，
那a1和b1的二阶相似度的目标就是最小化softmax(1/6，2/6)～softmax(3/7, 2/7)之间的差距

就是看两个node的一阶邻居有多么相似，这两个node可以不直接相连。再比如一个极端的例子，a1的邻居和b1的邻居完全相同，边权也完全相同，那么a1和b1二阶相似度就是1。

接下来，我们考虑另外一个问题。我不知道LINE这个算法你们有没有实操过？对于LINE，我们能不能两个相似度一起优化，也就是 loss 一阶相似度加 loss 二阶相似度直接加起来一起优化呢？

其实是不可以的，因为我们回顾一下这个例子

比如5和6在一阶相似度的时候，他们相似度是 0 对不对，它没有边权，但是你在二阶相似度的时候，他们是完全相似的，也就是相似度是 1，相当于一个 loss 使得他们俩无限的接近，另一个 loss 使他们俩无限地推远，这样你是学不出来的。

所以正常的做法，我们是分别优化的，也就是通过一阶相似度求一个Embedding，通过二阶相似度求另外一个Graph Embedding，两个Graph Embedding可以通过Pooling的方法，不管是concat，还是 Average pooling或Sum pooling ，给弄在一起，最后得到一个Graph Embedding（如果面试中你说了解LINE的话，这个很容易被问到）。

1.4.3 GE之GraRep

然后这样还有一个启发，就是我们这里考虑了一阶相似度，二阶相似度，那么我们可不可以考虑，3阶相似度、4阶相似度呢？如果你聊一聊算法肯定会问你。

答案是完全可以考虑，比如上图中所有的上一行，a 比 e 、b 比 f 、c 比 g 和 d 比 h，相似度都比下一行大，比如第一个a是因为权值大，第二个b是因为他们的路径多，比如从A1到A2有4条路径可以走，但是下面这个只有一条，这些都是类似的。

1.4.4 GE之Node2Vec

下面介绍另一个在工业界特别常用的一个算法，叫Node2Vec

展开之前，说一下相关公式符号的表达，比如 $d_{tx}$ 就是节点 $t$ 到节点 $x$ 的最短路径，这个最短路径的取值只能是{0,1,2}，因为二阶的随机游走只看两层。

这个算法肯定很多人也听说过，我在这里也给大家再简单地介绍一下。这个Graph Embedding的方法来源还是Word2Vec，不过改进了，它最重要的一个贡献就是改进了DeepWalk。

我们知道DeepWalk的Graph Embedding方法是可以理解为基于DFS的。比如下面这个图，从U到s4到s5到s6，这是一个DFS一直往前走，通过DFS找到一个序列然后再去做Word2Vec，这是很明显的DFS走法。

然后第二个叫内容相似性，内容相似性的假设就是我跟谁的边权越大，我跟谁就越相似，LINE就是一个典型的这种算法，因为它去优化U 跟 s1 s2 s3 s4 的相似度，且在一阶相似性的情况下使用BFS构造邻域。

那么Node2Vec呢，它是定义了一个二阶的一个Random Walk，平衡了DFS与BFS，我们看这个图

这个图 t 是刚刚上一次采样到的节点，V是当前这次采样到的节点， $x_{1}$ $x_{2}$ $x_{3}$ 已经是下次他要采样的结点；

那么P和Q就控制着采样的一个算法

P是控制的回头率，假设P是无限大，就不回头一直往前走，假设P是0.1，那么回头的概率就很大，10 对不对；
Q 控制的是 BFS 与 DFS 的一个平衡，假设Q=1，那么你到 $x_{1}$ $x_{2}$ $x_{3}$ 都是1，是不是权值是一样的，那么要么BFS、要么DFS，不做任何的区分，那么如果Q非常的大，那么它是倾向于 BFS 的，你看他会倾向于往 $x_{1}$ 走，对不对；如果要是Q非常的小，~~也就是这条边，跟这条边很大，~~那么他就倾向于DFS往前走，他采样到这个序列以后呢，就跟DeepWalk是一样的，然后就做Word2Vec的一个优化就行了，就解那个Embedding

这里边其中有两个应用，一个是腾讯的，一个是Facebook的，他们都是一个广告的应用，LookaLike大家可能都了解吧，我再简单复述一遍，就是广告主给你了一批种子用户，也就是我想把这个广告只投在种子用户上，但是广告主的思维是有限的，他只了解这些种子用户，其实我们平台上有更多的用户，我们可以去给它智能的放量，这在字节跳动叫做智能放量，在其他公司里面可能叫 LookaLike，定制化受众，对不对？我可以自动给你放大我的量，就是你给了一批人，然后我给你再寻找一批，跟他相似的人也给你投放，然后你的收益是不是就更高了，这是Node2Vector在这上面的一些应用。

有同学问：Node2Vec有什么Trick ，实际效果用起来微乎其微？

Node2Vec Trick 的话，一般我们都是直接用的，像LINE用的也比较多，办法对样本加权，这个就是构图的方法了，不是你去在算法上做改进，而是你在构图上做改进。

我举个例子，比如你在广告领域，那么我们可以用点击图，以及点击边和转化边，那么我们转化边跟点击边，它应该有一个权值的兑换，比如你点击的权值是1，那么你转化的权值可能是5，也可以是10或20，这个需要调，然后对应一个采样的概率。
比如你一个User，对某些广告有着非常高的点击，但是对他们转化很低，但是你对另一些广告你转化很高，所以其实所谓广告的优化最终优化的是广告主的价值，更希望是转化的价值大，所以要让他们去更多的往肯转化的这样一个广告上去随机游走。
所以Graph Embedding，其实最重要的不是这些算法，而是你构图，构图是最底层的基础建设。

1.4.5 GE之Struc2Vec

然后我们就去看一下这个Struc2Vec。首先，再次回顾下结构相似性(DFS)与内容相似性(BFS)的区别。

刚才我们介绍了，内容相似性的定义就是说相邻的节点它更相似，类似于BFS。

那么结构相似性的局限性体现在哪呢？比如我们看这个U和这个V：

他们在图中的地位周围的环境相似，那么他们应该具有更大的相似度，这是结构相似性。那么DFS能不能解决这样的问题呢，一定程度上能，因为你的随机游走，可以游走的比较长，但是呢，如果这个图很大U和V中间隔了很多，那么你U是游走不到V的，所以DFS解决结构相似性有一定的问题。
那么Struc2Vec怎么做的，它在Node2Vec的基础上更进一步，通过一个分层定义了一种结构相似性。

Struc2Vec的一个最大的应用是在风控领域，算是一个标配了（比如这是蚂蚁金服的一个在人工智能大会上的介绍，他们相对于Node2Vec，AUC从70到90，有了质的飞跃，这个我们一会解释一下为什么）。Struc2Vec相对于Node2Vec，在风控这样一个场景下，有更好的这样一个适用性。

我们先介绍一个Struc2Vec是怎么做的。比如在我们有这样一个图之后，我们怎样去定义结构相似性呢？

Struc2Vec给出了一个方案

咱们去比较这个U和V，但换个角度，我们去比较U和V他的邻居相不相似，如果他的一阶邻居相似，那么我们就去比较它的二阶邻居是不是相似，如果他的二阶邻居还相似，我们就去比较三阶对不对，总能比较到一个不相似，假设U和V在第10层，都是很相似的，那他们确实很相似了；
如果U和另一个节点比如 X 节点他们在一阶相似、二阶相似，但是在三阶就不怎么相似了，那U和X的相似度是不是没有U和V的相似度大，对不对，就是这样一个思想啊。

必须进一步讲细致些。如果u的第一层邻居用 $R_{1}u$ 表示(图出自此处)

Struc2Vec就是去比较u、v各自不同阶层邻居R_k(u)、R_k(v)的相似性

另用 s(S) 对某个节点集合V中的节点按照度的从小到大顺序排序后形成的序列，S的取值范围是[0,n-1]；
$R_k(u)$ 是距离u点最短路径为k的节点集合， $R_k(v)$ 是距离v点最短路径为k的节点集合；
$f_{k}(u,v)$ 就是距离u，v相距为k的那些节点之间的结构距离， $f_{k-1}(u,v)$ 则表示考虑k-1跳邻域时的距离，再加上只考虑k跳邻居的距离，就形成了k跳邻域的距离了，初始值 $f_{-1} = 0$ ；
g(D1,D2)用来度量两个经过排序的度序列D1、D2之间的距离， $s(R_{k}(u))$ 、 $s(R_k(v))$ 分别表示与u，v距离为k的节点按照度数大小排序后的度序列（当然，包含的元素个数可能会不一样，可以用DTW可以用来计算两个有序的度序列之间的距离）

则有：

所以当K变大的时候（K就是我说的几阶相似度），K变大是不是等价于CNN的感受野变大，一阶的时候感受野只有 1，对不对，二阶的时候感受野变成 2，所以自底向上地比较一个相似度。

实话说，吴老师讲到这里的时候，我一时半会没反应过来。其实直白来讲，有点类似比较两个倒立的金字塔；更直白点讲，有点类似分别比较在二环、三环、四环、五环的朋友，如果二到五环的朋友都相似，考虑到物以类聚人以群分，那他俩本身能不相似么？

ok，上面得到了每个节点对在不同的k上的结构距离，接下来怎么操作呢？

第一步，首先构建分层网络。为进一步解释，援引下陌上疏影凉的说明：

在同一层里边，两个节点之间的边的权重的计算公式为： $w_{k}(u,v) = e ^{-f_{k}(u,v)}, k = 0,...,k^{*}$ ， $k^{*}$ 代表临近区域的直径。根据“ 如果u，v越相似，那么它们的结构距离 $f_{k}(u,v)$ 就越小，或者越趋向于0 ”，那么(u,v)在图中的权重越大，当 $f_{k}(u,v) = 0$ 时权重达到最大值1。也就是说，在每层的图中，边表示任意两个节点的结构相似性，相似性越大的权重越大。
层与层之间是通过有向边相连的，具体的，对于第k层的任意节点 $u_{k}$ ，都有有向边 $(u_{k},u_{k-1})$ 和 $(u_{k},u_{k+1})$ ，权重分别为： $w(u_{k},u_{k+1}) = log(\Gamma _{k(u)}+e),k = 0,\cdots ,k-1$ ， $w(u_{k},u_{k-1}) = 1,k = 1,\cdots ,k$ ;

其中 $\Gamma _{k}(u)$ 表示第k层中，所有指向u的边中权重大于该层平均权重的数量，具体的式子为 $\Gamma _{k(u) = \sum_{v\epsilon V}^{}1(w_{k}(u,v) > \bar{w_{k}})$ ，其中 $\bar{w_{k}$ 表示第 $k$ 层所有边权的平均值。

直白讲，实际上 $\Gamma _{k}(u)$ 表示了第k层中有多少节点是与节点u相似的，如果u与很多节点都相似，说明此时一定处于低层次，考虑的信息太少，那么 $\Gamma _{k}(u)$ 将会很大，即 $w(u_{k},u_{k+1}) > w(u_{k},u_{k-1})$ ，对于这种情况，就不太适合将本层中的节点作为上下文了，应该考虑跳到更高层去找合适的上下文。

第二步，上一步多层网络M的构建就是为了寻找合适的上下文，而寻找上下文的方法与DeepWalk一样是采样随机游走的方式。

再次援引陌上疏影凉的说明：

具体的，假设随机游走走到了节点 $u_{k}$ ，那么它下一步可能的节点为 $u_{k+1}$ 、 $u_{k-1}$ 、 $v_{k}$ 、 $w_{k}$ （见上图左半边）。留在本层继续游走的概率为q，自然跳层的概率就是1-q。

在本层中，向其他节点游走的概率跟边的权重有关，也就是对权重做一次归一化得到概率：

$p_{k}(u,v) = \frac{e^{-f_{k}(u,v)}}{Z_{k}(u)}$

分母是归一化因子：

$Z_{k}(u) = \sum_{v\epsilon V v\neq u}^{} e^{-f_{k}(u,v)}$

如果跳层，同样分两个方向，概率也跟边的权重有关：

$p_{k} (u_{k},u_{k+1}) = \frac{w(u_{k},u_{k+1})}{w(u_{k},u_{k+1}) + w(u_{k},u_{k-1})}$

$p_{k} (u_{k},u_{k-1}) = 1 - p_{k}(u_{k},u_{k+1})$

注意到当层数越高，因为考虑的邻域更广，节点间的结构相似性计算越苛刻，因此在底层计算出两个节点结构相似的，在高层则不一定相似，并且高层很多节点之间 $f_{k}(u,v)$ 的可能根本没有定义。这就导致如果随机游走在某个节点u跳到了更高的层，那么在随机游走的序列中，其左边的节点是k层，而右边的节点是k+1层的。而左右两边的取值范围是不同的。

换言之，某个节点可能会出现在左边，但不会出现在右边，因为虽然它跟中间那个节点u在k层是相似的，但在k+1层可能无定义或者 $f_{k+1}(u,v)$ 太大导致随机游走在k+1层走到这个节点的概率几乎可以忽略。

另外从源码可以发现，当在节点u处跳层时，只会添加一次节点 $u_{k}$ ，而不会将 $u_{k}$ 、 $u_{_{k+1}}$ 都添加到随机游走中。有了上一步采样出来的随机游走，之后直接套用word2vec中SGNS（skip-gram with negative sampling）就可以学习模型了。

~~————————————————~~
下面就可以讨论一下，为什么风控场景下Struc2Vec相对于Node2Vec有提升。比如当你在蚂蚁金服的时候，你看到Struc2Vec，这样一个算法之后，你说你用不用呢？其实最本质的原因是这样的，Node2Vecr它是通过平衡DFS和BFS采样得到一个序列，然后做Graph Embedding，他无法获得长距离的这样一个结构相似性，Struc2Vec可以，那么风控场景就需要这种结构相似性。

我给你举个例子，你在支付宝里边会有很多的关系，在淘宝里面，比如关注很多商家，有一些大V 有一些有些大的机构，他们都有很多的边，他的还款能力强不代表你的还款能力就一定强，但是如果这样一个商家跟另外一个商家，他们有同样的体量，那他们的还款能力，或者借助能力其实是更相似的，也就是在社交领域其实也比较像。
比如你在微博里边你的相似度，你关注了很多大V但是你跟别人其实可能相似度没有那么大，但是大V跟大V之间，他们在网络中的影响力可能差不多，然后第二个，我们还看到这个 Z_k，我们已经见到很多Z_k了，一定要敏感的看到Z_K 这个论文中使用的是层次softmax。我们知道Wrod2Vec的时候，Z_k 它有两种优化方法，一个就是层次Softmax，一个就是NCE，对不对。

现在目前我们基本常用都是NCE了，Softmax很少提了，这里边为什么，他可以用 Softmax 而不是 NCE 呢，首先可不可以用 NCE ，那其实肯定可以的。只要看到这个 Z_k 都是可以用 NCE 的，但是这里也可以用Softmax，为什么？

你们想象一下，Word2Vec的层次softmax是怎么构图的、怎么建这个树的，通过哈夫曼树是不是？那哈夫曼树的权值是什么？词频，那你在NLP领域，词频天然就是不公平的，I love，以及 it、you 这些单词频非常的高，但是有一些词appreciate以及一些非常长的词，它的这个词频就低，那么它构建的哈夫曼树一定是不怎么平衡的。

但是对于Graph Embedding这样，一个图，每个节点出现的词频都是一，所以他构建的哈夫曼树一定是平衡的，所以他可以用，你在Word2ec的话，效果就没有那么理想，这是一个本质的原因。

1.4.6 GE之GraphSAGE

接下来，介绍这个GraphSAGE算法

刚才给大家介绍Struc2Vec，不是说他在推荐系统应用广泛，而是想给大家介绍一个结构相似性以及内容相似性的一个概念，而GraphSAGE就是在推荐系统、广告大规模落地的情况下一个非常犀利的武器。

这里再介绍一个概念归纳式学习和直推式学习，刚才所有的介绍的算法都叫直推式学习

直推式学习指的是，你有了一个图，那么我可以用任何的算法，Node2Vec、Struc2Vec、LINE这些Graph Representation都可以，你学到了图中每一个节点的Embedding，然后你给他存到了一个词表里边，它不能动了，当你图变化之后你需要重新学习的；
对于归纳式学习，GraphSAGE就是一个代表，指的是我既学习你的Embedding，同时我在学你Embedding的时候，我还学到了一个方法论，我怎么得到你这个Embedding，那么当你的图有一定的变化的时候，我可以迅速的响应你这个变化，你没有见过的这个结点我能够通过我学到的这个方法论、通过他的邻居聚合到，你这样一个节点上，得到你这个节点的一个Embedding，然后通过不停的迅速响应变化这样子。这在推荐系统非常重要，毕竟对于推荐系统的图，第一，非常非常的巨大，第二变化性非常的快，你用户每一次操作都会对这个图产生影响。

下面，再更具体的看一下GraphSAGE，它相对于前面那几个非常的好理解，这个算法分两步，第一个采样，第二个聚合。

对邻居进行随机采样，你去采他的一阶邻居采几个，对二阶邻域采几个，比如你对一阶邻居，你规定采10个，我们看这个图，他只采了三个，对不对，我们有padding，padding到10个，但你二阶邻域只采了5个；
生成目标节点的向量化表示/embedding：先聚合二阶邻居的特征生成一阶邻居的embedding，再聚合一阶的embedding，生成目标节点的embedding，从而获得二阶邻居信息；
将目标节点的embedding作为全连接层的输入，预测目标节点的标签。

我们具体看下这个算法

这个h0，这个 x_v 就是我输入的这个原始的embedding，比如，如果你是推荐的场景下，那就是推荐的原始的embedding，你用其他的方法，第一开始先学到了embedding，然后你再用GraphSAGE去让他去学到网络的结构，然后V就是所有的结点了，大K就是你要采样的这个层次；

刚才我们一阶邻居、二阶邻域采样嘛，从第一层开始，对于每一个结点u，你采样了他的几个邻居。采样完了之后，这样一个邻居跟他通过一个聚合函数，然后聚合到了第K层，第K层的这个所有邻居的这样一个表示，就是你先对边上的这一些做一个聚合，对吧；
然后聚合完了之后，你还需要跟中心这个结点。我们在所有的Graph Embedding上其实都有一个暗喻的一个假设，就是这样一个自连边，你在跟自己，v这个节点跟v的一个邻居，然后再去做一个NN嘛 concat 出来，然后做一个激活就完了，然后最后一个Norm这就出来了，所以这个算法非常简单，简单有效。

我们简单说一下，这个采样算法。

采样算法，一般我们就是Random采样了，采样K阶的一定数量的节点就行了，然后聚合算法我们一般有几种，一个是MeanPooling，一个是MaxPooling，以及LSTM（了解什么是LSTM，请点击此文），这是论文中提到的。

LSTM的话这里边要提醒一下，每次要 shuffle 一下，因为是LSTM，它是一个序列的算法，但是我们采样是需要跟序没有关系的，因为Random采样的时候就跟序没关系，你第一次可能采要1234，你第二次可能采到同样的这几个点，但是可能采到的是4 2 3 1，对不对，所以你需要shuffle一下，你shuffle一下就可以解决了。
GraphSAGE后面会介绍，他在推荐中的一个逻辑就是PinSage算法，这个算法目前在很多的推荐场景都有落地。

1.4.7 GE之GraphWave

最后一个，我只简单的给大家show出来，也不再给大家讲，这个也是结构相似性的一个假设，问题是非监督、完全非监督的。

回顾一下 Struc2Vec。Struc2Vec 我们的假设是什么呢，一个先验的知识是节点的结构相似性可以由它邻居节点的度的序列来表达，并且可以分层的表达，这是你输入的一个先验，但是GraphWave是不需要任何先验的，你只要给我一个图，我通过一些方式就能够得到你的Embedding的一个函数。
大家可以看一下这个效果啊，左边是今天没有讲的一个算法，中间是Struc2Vec，然后最右边这个是GraphWave，我们可以看到，他把这个结点分的特别清，每个颜色其实代表，一类他能够分的特别清，所以这个效果还是很不错的，并且不需要学习速度非常的快，如果有需要在某些场景中，需要结构相似性的话大家可以试一下。

1.4.8 GE总结

这个理论部分我们也过了一会了，Graph Embedding其实最主要的问题就是你要怎么选，因为 Graph Embedding 到现在，我从一开始给大家show的那个，大家族里边它有很多的算法，实际上一定要跟你的实际问题相关，从而决定你选择什么样的模型。

总之，你选用什么样的模型取决于你的问题，然后最重要的是构图，大家一定要记住这句话，在图神经网络领域你不是所有的图都是天然成的、包括社交网络，它虽然是个天然的图，但是这个图你需要去做一定的 refine，比如你的权值需要做一些先验的加工，电商领域也是，你一定要把这个图构好了，图构好是你解决问题的过程中最关键的。

1.5 图神经网络之GCN

GCN，此处不做过多介绍，因为GCN涉及到普图理论、普图卷积，所以这方面这个背景知识更多，我只给大家类比下

GE类比在NLP里面是Word2Vec，然后GCN类比的一个算法就是CNN
然后GE一般对应于两阶段建模，也就是我先用一种算法，比如LINE在一个图上出了一个Embedding，然后这个Embedding再赋能给上游，给上游推荐做了一个特征，然后GCN一般都是End2End的，比如你直接做一个分类，然后GCN可以生成Embedding；
GCN的，你可以做有监督的学习，但是你有监督的学习完之后，比如你做 Link prediction，就是你做节点预测、连接预测，你做完连接预测之后，GCN产生的最上层的那个Embedding，你就可以作为一种GE，然后给上层的任务再用，然后广义的话，GCN其实是属于GE的，比如刚才我们说的这个 GraphSAGE，很多人会叫他叫GCN，其实我不喜欢叫他GCN，因为我喜欢把GCN，用另一种说法来说，然后GE一般都是单层网络，比如 Word2Vector，然后LINE网络，LINE，其实他就，它参数就少嘛；
然后Node2Vec都是用Wrod2Vector的方法，单层网络，然后GCN的话，也可以很深，做的很Deep，就跟CNN一样，一层一层往上套，大家只需要记住GCN，可以用来生成Embedding，就是跟GE没有多大的区别。

有小伙伴说GCN性能太慢了，因为它要在全图领域做一个卷积，GCN在工业界暂时没有很好的落地场景，这方面的理论有兴趣的可以去看下。

然后这个Github里面有PPT，还有这个文档都有，想了解理论的可以去看一下，然后我给大家稍微说一下，这个GCN是怎么回事，GCN分为两大类：

一个就是普通卷积，就是在傅立叶域做卷积变换，这个有需要比较深的数学的理论；
另一种是非普通卷积，这种卷积也没必要介绍，他其实你可以认为是一种非普通卷积，直接做卷积，然后普通卷积，有一套统一的理论，但是它会受到拉普拉斯算子的一个限制，他所有的所有的理论核心都是这个 L 拉普拉斯算子，在空域卷积更加灵活，但是主要的困难在于选择邻域上，比如GraphSAGE那个邻域有更好的选择算法吗？你说Random，Random选择是不是特别好，是不是有一些加权的选择，这些都是工业实践的一些Trick，有很多模型千奇百怪没有统一的理论，更多的是一种实践。

2 GNN在推荐/广告中的应用

然后我们就进入今天的这个实践部分

GNN在推荐广告中的一些应用的一个案例，给大家讲解一下。

2.1 End2End建模与两阶段建模

先给大家说一下这个范式，就是GNN在推荐广告中的应用有这么两大范式

一个是两阶段
一个是End2End的

对于End to End

首先你有一个Graph对不对，比如假设以商品推荐为例，那么你可以构建商品的同构图，就是商品和商品之间的图，你也可以构建User到Item之间的一个点击、收藏、加购、关注，以及购买、退货这样一个异构图，类似于一个知识图谱。然后还有 Other Feature，Other Feature 就正常于应对于比如你在做召回的时候，正常的User侧的特征、Item特征对不对？你做双塔的时候可能就是两侧的特征，你要有match的特征就是match的特征；
然后这两个作为输入，你的中间的模型是有两块，一个是GNN用于处理 Graph，一个是你正常的model用于处理其他的feature；
然后上层可以做分类、Ranking或其他的，对不对？

然后这里边中间这一部分，还是有两种方式：

第一种，就是你以这个Model为主模型，GNN作为一个附加的组件，比如你要做一个双塔在召回中用，如上图，左边是User侧，右边Item侧的向量，然后你在上层做了一个logit。那么现在有了一个图，然后你在Train的时候，你每来一个User，你可以去图中去找这个User，然后找到这个User之后去取它的邻居，然后这个Item也是，你可以去找，这个都是实时地在Train中你就找。当然，这个去图中找user/item邻居的过程是通过GNN去拿的，即GNN去访问去给你得到这个User的Graph Embedding以及 Item 的 GraphEmbeding，给你赋到这个user、item那边去，然后你就可以往上再做卷积/点击得到 logit。这就是一个双塔怎么嵌入，以及双塔中怎么嵌入GNN。
还有一种方式，GNN作为主模型，这个后边我们介绍一个案例，GNN作为主模型，然后你其他的 feature是放在图里边的，你直接出来一个Graph Embedding，然后Graph Embedding不用再做任何操作，直接做点积、做相似度了。

然后两阶段的呢，两阶段目前在工业界没有特别成熟的应用，它标上有一些应用都是不是特别公开的，不是特别好讲。
比如这有一个Graph，我先通过一个pretrain的，一个GNN然后去得到一个Graph Embedding，这个是存起来的，你可以理解为存一个KV，也可以存数据库。

假设我们存的是KV吧，比如user一个Embedding ad，一个Embedding这样存上了，或者是这个Item 一个 Embedding，然后这样一个Other feature，然后你这个东西，是作为主模型的一个特征进去的，然后比如你在精排里边，作为主模型的一个特征，然后主模型可以进行对它一个 fine-tune ，然后model在跑，就一直在更新记忆，GNN那边也在更新，但是这两个更新，你这个更新怎么去解决他们更新的一个冲突，这是一个关键的问题。然后上面可以做 Ranking，做其他的事。

这是一个范式，目前所有的工业界的应用不会跑出这两个范式的范围，下面给大家介绍这个是2018年的一个文章。

2.2 End2End之GCMC

这个文章思想就很简单了，我们去在做推荐的时候，推荐的最核心的一个理论就是这个矩阵填充。

你所有的推荐都可以理解为矩阵填充的一个问题，一些有值的这就是你的 ground truth，有一些 0 的，就是你要去填的。

我把这个建成了一个二部图User 侧和 Item 侧，有一些连接，连接完了之后，我去对这个图做一个Graph Embedding 或者 GCN，反正你最终能得到User的一个Embedding UE，然后 Item 也能得到一个 Embedding IE是吧，然后你就可以去做另一个prediction，User u_i 跟 item_i之间它们的一个相似度。

比如你对于这个吧，我这个叫做 1，这个叫做 1，这个叫做 2，那么 $u_{1}$ 跟 $i_{2}$ ，它们的相似度边权是1 是吧，那么你需要去求解，他们的 Embedding 之后的相似度也是 1，当然这个 1 我说的，它不是真正的 1 啊，你这个 $u_{1}$ 它只跟 $i_{2}$ 相连，那就是 1 了，如果你 $u_{1}$ 还跟 $i_{1}$ 相连它是 3，那么你应该让他去Embedding之后得到的值应该是1/4，做的就是这样一个事情，忘了说一句，这个文章的GAE用的就是多层级GCN，它不具备落地性。

为什么不具备落地性，刚才有同学已经说了，普通理论的GCN是在拉普拉斯算子上的，拉普拉斯算子是在等于整个Graph的，他没有办法去做一个采样什么的，所以每一次的运算都是在全图上的，在整张图上做消息传递，所以耗时太严重了，工程复杂性太高了，没办法落地，这只是PR的一个文章，大家可以简单的理解一下GCN在召回，是怎么用的就行了。

2.3 End2End之PinSage

2.3.1 PinSage之构图实践

下面，这个文章我们主要介绍一下，叫PinSage，这个是基于 GraphSAGE 的，这也是一个落地，并且工业界的推荐广告都在用他们这个方法，在各自的业务场景在落地，这个算法是Pinterest 和 Stanford 共同研究的，一个大规模Graph GNN 的一个落地，推荐长期下的一个落地。

这篇论文非常值得推荐，大家可以看一下，因为这篇论文里边有很多的工程实践。

我们做算法工程师，不是说我们去研究这些数学，研究这些算法就好了，我们的 title 是工程师，也就是我们在正常的工作中，你要有很强的工程能力的，现在在大厂你有一篇一作的 paper甚至顶会的一作 paper，这个只能作为加分项。

最终面试的时候，还是要求你的工程能力、算法能力都要很强，不管是字节跳动还是阿里还是腾讯面过试的同学，大家都知道如果应届生的话可能要求会低一点，但是如果社招的话，你的工程能力一定要很强。

首先我们对这个仔细的讲一下，首先就是构图，他怎么构图的呢？下图左侧代表图片，右侧代表收藏夹。

这个业务场景是一个图片推荐，你可以理解为刷抖音，抖音上你滑过去的不是一个视频，而是一个一个的图片，然后你看到很多图片之后，你可以加到你的收藏夹里边，这个 pins就是一个个的图片，这个 boards 就一个个的收藏夹，然后一个图片如果位于一个收藏夹内，它就连一个线，如果多个图片位于同一个收藏夹内，它们可能具有相似性，对不对，它就是这样一个二部图。

这样有一个思考，还是最基本的问题是怎么构图的问题，这个是影响我们最终效果的一个图网络。比如电商场景如何构图：

有一种方式是你可以只构建Item的图
另一种方式是你可以只构建User的图
还有一种你可以构建异构的图，user 跟 item 之间的一个点击、加购、喜欢、收藏、购买、退货这样一个异构的图

新闻推荐如何构图呢？新闻推荐点击，然后以什么停留时长，转发、评论是吧，这些构图，都会相对于 PinSage 的构图都要更复杂一些，我们传统的推荐还是蛮复杂的一个工作。

2.3.2 PinSage之GNN模型

它的基因模型是什么？我们先看左边这个图，它首先是基于GraphSAGE，而GraphSAGE 我们已经知道是基于采样以及聚合的，其次给大家形象的解释一下

首先假设我们采样 A 这个节点，我们要最终得到A这个节点的 Embedding，他是怎么做的呢，先采样 A 的邻接点(邻居)，比如我们采样三个（图里边是全采样了，但是我们一般是采样一定的数量），那我们 B C D 是不是都采样到了；
然后对于BCD我们还需要再采样，那么B采用了AC，然后C采样了AEF，F采样了CE，E采样了CF，D采样了A ，对不对，就是这样一个图，对吧；
A采样了BCD且采样完了之后，假设 K=2，我们只采 two top（两跳）这样一个邻域，那么我首先会去对采样到的所有的这一部分节点做一个聚合，如上图最右侧部分所示，比如这个 B C D，对BCD及A都做这么一步：首先B是AC经过聚合得到的B，其次C是通过这4个节点聚合的，D通过A这个节点聚合的，A这个节点是通过BCD聚合的，这个是可以并行计算的，算完之后最右侧那一部分就可以舍弃了；
最后再用刚才计算得到的 BCD 的 Embedding，再聚合一次得到A，这就得到了h_A(2)。

具体我们看一下这个算法，给大家详细的介绍一下。

首先，你有所有的节点，这个是V，然后你有一个 batch_size，就是M个节点，你这个 batch_size 处理M个节点，然后你有一个参数K，这个K可以就是说刚才我们说的采样的深度，刚才我们是 2 是不是。最终是想得到本 batch_size 里边所有的结点的 Embedding，然后它采样。

所以，整个过程相当于分为两部分，一个是采样，一个是聚合，那么先是采样算法：

采样这一部分，他跟 GraphSAGE 稍微有一点看着别扭，他是反着来的，比如我K是2的时候，假设M等于A、B这两个节点，那么S2就等于{A B}，这是一个邻域；
S1呢？他是先把S2赋值给S1，然后对于S2 中的每一个结点{A B}再去取它们的邻居。换言之，S1首先是AB，之后加上A的邻居B C D，然后再加B的邻居AC，最后把重复的去掉，这样最终S1的集合为{A B C D}；
至于S0是什么呢？比如你现在S1已经是等于了A B C D，然后你对A、B、C、D再分别采他们各自的邻居，总之，最后S0 = S1∪S1的一阶邻居（即ABCD + BCD AC AEF A，去掉重复为：ABCDEF）；

然后是它的聚合算法，从外向内，因为你S0最大，你S0包含了最边界的情况，也就是你S0相当于包含了 A C A B这些东西嘛，你要先把这些给它聚合好了，因为后边聚合再往内聚合的时候，他们就不动了。具体看一下吧：

首先对于h0，h_u 的每一个第零次的一个Embedding都是等于原始的Embedding，这个是S0，S0是最大的集合对不对？而k=1到K，首先k=1时，即对S1中的每个结点（即ABCD），比如A，首先考虑他的邻居，A的邻居在S0中已经有了，对于A的所有的邻居聚合一次，聚合一次之后执行 CONVOLVE 算法。这个算法你就可以理解为是一个聚合，比如你要聚合得到A，就是A的邻居以及当前这个A的一个 Embedding 表示，聚合之后得到A的下一层地表示，然后再去执行 S2；
这个步骤执行完之后，A B C D的Embedding是不是都求完了，A是由A的邻居求得的，B是由B的邻居求的，C是由C的邻居求的，D是由D的邻居求的，求完了之后你再去求S0的时候，是不是就剩AB了，A的邻居是B C D对不对，B的邻居是A C，对不对。你第二层再去拿B C D去聚合得到A的，然后去拿AC去得到B的，这样就执行完了。执行完了之后，他再对 batch_size 里边的所有的再做一个变换，然后这下边是一个CONVOLVE算法，这个CONVOLVE算法也很简单，对所有的邻居先聚合一下；
然后再把自己慷慨的心态再过一个 NN，过一个激活函数，然后 Normalize 一下，这就是最终的结果。

以上，是他的GNN模型的一个描述。

2.3.3 PinSage之Training

然后我们说他训练，他这个是一个有监督的训练啊，其实 PinSage、GraphSAGE都既可以做有监督的，也可以做无监督的，然后这篇文章是做有监督的，它的正例是什么呢，就是用户在点击了item_q 之后，如果马上点击了，他设了一个时间，比如5秒之内又点击了item_i，那么我认为 i 是 q 的好的候选，即(q, i)是一个正例，那么其他的就是负例，它最终优化的是max-margin ranking loss。
这里说一句，这种 ranking loss 其实有很多，你还可以是ranknet 的一个 loss，这个 loss 的说法就是去让正例比较接近，然后让负例拉远就行了，负例就是通过负采样。

2.3.4 PinSage之Servering

刚才 train 说完了，我们接下来说下Servering。Servering 它有一个优化，它是通过一个MapReduce生成这个Embedding，然后进而进行ANN的一个检索，ANN检索我就不说了，就是召回的常用套路，比如最近邻相似的一个检索，他这个东西为什么要用 MapReduce生成 Embedding 呢？

为什么 Servering 的时候跟Training的时候不一致呢，因为正常的网络，我们知道正常的不管是DNN还是什么乱七八糟的模型，我们Training跟Servering 唯一的区别就是不做 backward，是不是，这里有一点不同，为什么不同，是因为它有一个很多的重复计算。

比如，你现在要按 Training 的方式去求解这一组所有的最终的Embedding，那么你会去计算上图最左侧第一个图里的那个绿点，你去计算了一次，这是第一层，计算完之后，第二层你计算到左侧第二个小图里的又一个绿点，你又去算了一次，是吧，它有很多的冗余计算，绿点在这又计算一次，在图很大的时候，你这个是无法有效地满足Servering 的，所以他做了一个 MapReduce这个任务比较简单的，我给大家解释一下。

把上图中最底部的第一层所有的节点都做一个 Embedding，然后去一下重，都做这样一个聚合，然后再往上，相当于不是说为了谁单独算一次，而是我对所有的这些节点只算一遍算完之后存下来(因为它们是同样的计算)，然后我再往上算，如果你要是有10层，我就每一层这样算，下一层的结果是用的上一层的，下一层的输入是上一层的输出，就这样，因为MapReduce是一个K嘛，我们的K就直接能够达到去重的效果。

而这个文章里边，之所以推荐大家读是因为它有很多工业上的优化，是一个非常诚意满满的论文最佳的工业实践，我给大家举几个例子：

第一个就是邻居采样算法的一个优化，它不是基于Random Walk进行采样的，而是基于重要性采样的，意思就是谁重要谁采样的权值就大；
第二个Warm up，这个是在我们训练的时候，工业界大 batch 训练的时候都会遇到的一个场景，当你的 batch 非常大的时候，比如几万，你一个 batch 需要优化几万个这个 Item-user-item 对，那么其实你太大的话需要有一个 Warm up 的过程，否则你的训练会容易跑偏；
第三个是分布式异步训练，这个其实在很多主流的大公司，现在都有Parameter server、haven、Tensorflow这些基础设施，他是怎么通过异步以及分布式在多个卡上同时训练，然后梯度再去在每一个GPU上算不同的梯度，算完之后，再去汇总到一个里边，然后最终再传到 Parameter server上，然后进行一个异步的更新，也就是下一次再优化的时候，你可能用的并不是最新的，因为他去更新梯度的时候，他也是异步的；
还有一个就是Hard negative。其实我也写过一篇科普的文章叫做困难样本挖掘，你光用简单的样本，就是用正例，而且是真正的正例，然后你负例就是用的随机采样，那么其实你学不到特别好，因为你的负例太好学了，随便一个网络就学好了；
还有一个就是 MapReduce。

上面提到的Hard negative 是怎么做的？比如正例不是 q_i 吗，那么负例呢？假设你 q 是 query ，你去查询的时候，你对每个 item都会有一个排名，然后你可以选择i 在1000~2000的一个 rank来作为他的困难样本，你在这里面选一些，然后再随机负采样，再采几个，这样你就加入了困难样本，使得 q 能够更好地去跟 i 去区分。

然后这里给大家提一个问题，因为困难采样，负采样这个东西在工业界也是一个非常好的优化的Trick。大家想一想，为什么，他这个文章里边第一开始的时候，不是 Hard negativ而是用一步一步地增加的，你一开始用的纯的Random 负采样，然后你会慢慢地去增加Hard negative 的一个比例。

如果只用 Hard negative会出现什么问题呢，为什么不一下子最难分的负样本，然后让他学得更好呢？有了解吗，其实是有一个问题的，如果你实践过你会发现，如果你一开始就用所有的都是 Hard negatives，那这个网络会学不好。因为一开始他的Embedding是初始化的，是没有区分能力的，在你没有区分能力的时候你就加大难度是不可取的，一般的话就是慢慢的去加入，这是一个常见的做法。

有同学可能问了，怎么考量Embedding 效果好？

一般我们现在没有特别好的方法，要想考量你的 Embedding ，你必须上线做实验，不是上线做实验。首先是offline去看你的上游模型，下游模型是不是有更好的AUC，有更好的NDCG什么的线下的指标要好，线下的指标如果好了，或者持平了，可以上线去做一把AB测试。
当然还有一些别的方法，你可以线下分析的，比如做一些聚类，然后看一看可视化，但是一般没有什么大的用啊，做一些心理安慰，你做完之后你还是会想去上线做一把，所以这个东西一般我们都去看上线的效果。

所以还是最终再强调一句PinSage 这个算法，我这边讲的可能也没有特别的好、特别的细致，里边还有很多的内容，还是推荐大家课后去读一读。

2.4 End2End之淘宝EGES

然后再介绍一下这个淘宝怎么做的Graph Embedding。刚才说了电商怎么构图，这里给大家介绍一个方案，这篇文章说的是一个Session，一个Session的概念就是，你可以理解为比如30秒一个Session，也可以理解为他一连串的操作，然后隔了一段时间停了，然后又回来操作，那就换了一个Session这样一个概念。

如果一个用户在一个Session内操作了一个商品的序列，那么他们就构成了一个有向的图，比如D A B，那么就是D到A到B这样一个有向图；
然后BE，D E F他就这样构图，这个就是构图的方案；
然后构完图之后，你可以做一个RandomWalk；
采样一些序列，然后就可以学到一个Graph Embedding。

这是淘宝的原来的Embedding，也就是在18年之前，他这个文章发出来之前，应该是在16年 17年的时候用的是这种Graph Embedding来做召回的，召回一般我们都是多路召回，这个肯定是其中的一路。

然后在2018年的时候或者17年，他们升级了淘宝的Graph Embedding，他们只做前面，这个就考虑很简单，你只有实体的信息，你没有任何附加的一个信息，他们后面考虑了一个 Side Info。Side Info 指的就是商品的一些其他的一个属性，比如价格、品牌之类的。不知道这里还记得吗，这个范式，他就用的第二种范式，GNN作为主模型，其他的 feature作为 Graph 里边的一个内容一些属性。

这里边就是说，SI 指的就是第 i 个 item的一个 Embedding，就是我们刚才用最原始的这个方法求出的Embedding，然后他求完这个 Embedding 之后，它又把它的一些属性，比如你这个商品是某个品牌的，那么它本身是一个OneHot的，是不是它往上做一个 Embedding，然后你是有哪些关键词、什么价格，价格一般做分桶、做OneHot、做Embedding，然后往上Concate起来，当然你可以直接去做。

Word2Vec也就是那个softmax最后要求解的那个东西，你已经可以做了，它这里还做了一个优化，就是一个Attention的概念。

因为你某些属性可能没有那么重要，有些属性是非常重要的，所以他就是有一个Attention的操作。总之，这个实践还是非常的好的，在很多公司都有类似的做法。

2.5 两阶段案例

然后两阶段建模，但是两阶段大家可以知道因为很多公司都是在用的，我给大家举个例子，比如对阿里来说，阿里有很多的数据，你在淘宝、天猫里面的数据，虽然是相通的，但是你在淘宝线的话，你去训练模型，你用的就是淘宝的数据，你在天猫的时候，你用的就是天猫的数据，1688、口碑，这些数据都是不通的，但是你可以用全站的数据去建一个Graph，并且用GNN去Train出一个GE，然后你这个GE就可以赋能各个产品的推荐了。

举个最简单的例子，比如你淘宝里边某些用户，你去点击了，比如你去购买了一个剃须刀，但是你在天猫上，甚至是推荐系统都没有发现这个东西，当然你在用全站的数据，去Train这样一个GE的时候，他会让你知道，我这个用户其实喜欢剃须刀的，可能最近他在天猫上可能会给你推，这样就是一个 Transfer 的概念；
对腾讯来说，也是全站数据，新闻、浏览器、QQ 这些东西都可以构建；
对字节跳动也是一样了，今日头条、西瓜视频、抖音一般这种方法，两阶段的这种建模，一般都是对于大体量的公司，这样一个做法

你要小体量的一个公司，就一个App，你没必要对不对，这一部分大家有什么想问的吗，看看大家的问题。

有同学问到，Side Concat 起来构建样本吗？
不是构建样本，是你的样本已经确定的情况下，你会把 Side Info的 Embeding 考虑进来作为你的优化的一个点，你去学习 Graph Embedding 的同时，你也去学习了它的品牌的Embedding、学习了它的价格的Embeeding，这些都考虑进去了，Margin怎么选取一般都是工业界的调参了。

3 GNN体系结构简介

最后一部分我们介绍一下GNN在工业界落地的时候，有哪些必要的组件

一般对于大公司来说倾向于自研，对于一些中小公司来说，他们会使用开源的软件作为一个基础，然后在开源上面做一些二次开发。比如你在字节、阿里，这个都是自研的，你在其他的公司它可能会用一些开源的。
对于GNN来说，除了算法，还有很多问题要解决

第一个就是图过大怎么存，这个在推荐广告中就是常规操作了，亿级别的这个点就是常规操作；
如何实现高性能的图操作，你采样你在亿节点上，然后百亿的边上你采样，你那心能扛不扛得住，刚才我给大家介绍那个范式的时候，你在召回的时候，你甚至可以在召回的训练的阶段，直接去访问一个图服务，然后这个图服务帮你非常实时的采样，然后并且帮你算一个Embedding，算完之后给你附加到那个双塔上，让你算，这样一个操作是怎么实现的；
以及 GNN与 DL是怎么深度结合的

3.1 阿里高性能图服务-Euler

因为阿里的高性能服务Euler做的也不错，而且开源了，我就基于它给大家介绍下，很多公司自研的也都是这一套，这个地方偏向一些工程

大家先看一下这个图

最底层的就是Graph的一个分布式的存储，大图你肯定没办法单机存储，你肯定得是分布式存储的，分布式存储一般有按点、有按边的；
然后往上层会有一个GQL源，类似于SQL，你去写这样一个句子，他就给你转化成一个有向无环图，然后去在这个图里边去做一些操作；
再往上是一个MP：Message Passing，这个东西是一个抽象层，因为GNN的所有的操作，都可以理解为Message Passing；
然后这个里边有一些基础的算子，比如卷积，比如聚合，比如 Combine 这个算法，所有的这个上层都是有不同的，这样的卷积、不同的聚合、不同的 Combine组合起来的；
然后上层会实现一些常用的算法，然后供你快速的调研使用。

3.1.1上 Euler 之分布式图引擎

我先说一下这个图分布式引擎

我给大家举个例子ABCD现在有这样一个图，你在分布式存储的时候，有两种做法

一个就是按点分布式
一个就是按边分布式

第一个，上面这就是按点分布式，我们在每个shard上去存，首先你要是点的分布式的话，你会对每个点做一个哈希，然后去哈希完了之后去存到某一个shard上，比如你这个shard1上存了A和B，然后为了采样的方便，我会把他的一阶邻居也顺便存上去

比如A这个地方存了A这个结点，我顺便也会把它的一阶邻居B和C存上，然后B就存B了，然后shard2上存了C、D这两个节点，C 有一个一阶邻居叫D也一块存上来。

然后第二个是按边这个partition，按边 partition 的话是，这个就很简单了，你对边作编号，然后对边做完编号之后，再做一个哈希存上就行了。

比如第一个shard 存的是A到B这个边，以及A到C这个边，然后第二个shard 存的是C到D这个边，这两个 Partition，一般都有各自的好处。

第一个就是 Node Partition，Node Partition的好处是什么呢，方便并行地采样，因为你一个 batch 的时候，比如你有AC，那么你去分布式的时候，分布式采样的是非常方便，你只需要在 shard1 找到 A节点，然后做邻居采样，然后shard2，找到C结点，做邻居采样就行了，高性能实行高性能采样的一个基础；
你在Edge Partition 这种情况下，你就不好操作，因为你这A这个节点，可能在 shard1 上，在 shard2 上还有，因为你可能是A到C这个边存到了在shard2上，所以就不是特别好，做这个并行的采样。

但是 Node Partition 上有一个问题，它受到一些热点的一个限制，比如你在推荐上非常常见，你有一些结点就非常的热，有一些用户就天然喜欢点广告，有一些用户就天然喜欢，它活跃度非常高，然后有很多的冷用户，那么你把这个用户，存到了某个shard上，你这个shard上会附带它的很多的一阶邻居节点会导致shard支持不住。

这种一般工业界是怎么做的呢，其实也没有什么好的办法，我们就是对他的一阶邻居做一个限制，比如说不超过1万个，然后超过1万个了之后，就做一些随机的裁剪，就是这样一个方法，然后Edge Partition的话不存在这样一个倾斜问题，不会受到一些热点的影响。

3.1.1下 Euler 之图操作算子

我怎么去做高性能的邻居采样，实践是怎么实现的，比如Euler 里边怎么实现的，对吧。一般这个图我们都是异构图，现在 Euler 不管，其他公司都是支持这种异构图的，我给大家画了这个图

大家看一下这个user-item的一个图，user这个0代表一种边，1代表另一种边，0代表一种边，1代表另一种边，0怎么理解呢？比如在广告场景0 可以理解为点击编，1 理解为转化边，0这个边它有各自的权值。比如你点击了某个item点击的次数，可以用次数作为边权的一个衡量，比如0.5、1、0.8，然后这个转化也可以有边权，你转化的边权怎么设计呢？你可以以转化这个广告带来的最终的收益为边权，也可以是转化的次数，也可以别的什么，这个需要你设计了。
还是那句话构图是非常重要的，这个图一定要构建的，符合你的业务场景，一旦你把图构建完了，你的工作完成了80%，甚至超过80%，图构建完了，图构建的好，那么直接决定你最终能不能做出收益。

有这样一个图之后，我们怎么做采样的呢，首先它存了一些东西

第二就是 Edge_type

我们现在有两种编码就01，然后有个 Node_offset，每个节点都有这样一个东西，每个节点都有，比如 user 的节点，它就 Node_offset 指的是第 3 ，3 指的就是我 0 这个边，0 这个边的邻居是到 3 结束，另一个边1是到 5 结束；
然后这个权重和前缀权重的前缀和，就是0这个边它有2.3，即0.5+1+2.8 是2.3，然后1呢是把所有的加起来是5.6；
当你采样的时候比如，你要假设你不分边，你随便采，那么首先他做了一个前缀和，item1的前缀和就是0.5自己嘛，item2的就是item2的加item1的，item3就是它们3个加起来，这样一个前缀和；
然后你有这个前缀和，假设你不分这个边权的，边的类型直接采样的话，你只需要设置一个 random，你首先 random 一个数，然后乘以它的最大和5.6，乘以5.6之后，你就得到了一个0~5.6的一个数；
然后做二分查找，因为它是有序的，然后这个东西就可以并行，刚才我们按 Node Partition 做的话，也可以并行所以非常快的，如果你要想结合某种边，比如你这次只想采零这个边也一样
你首先通过这个前面这些数据结构Node_offset到3，那么你只你首先只到 3 3这个地方，然后乘个2.3，而不是乘个5.6就行了，然后如果你只采样 1 这个边，那么你还是乘以5.6，但是乘完之后，你要减掉2.3，对不对，你最终的这个范围，首先就是3.6到5.6，然后再二分查找就行了，是吧。这是一种采样的设计。

3.1.2 Euler之GQL查询接口Euler 2.0

然后就是GQL语言，这个GQL语言不详细讲了，大概就是它会设计一个类似于SQL的一个语言，因为你在SQL的时候，我们都知道，你SQL语言，写完之后他的底层可以做各种各样的优化的。

GQL语言也一样的，你写完之后，他会给你，首先给你建成一个 D A G，有向无环图，然后在图上给你进行一些操作，一些采样，一些取属性这样一个操作
建完这个图之后，它还会给你进一步的优化，比如说你采样的一些重复点，然后你这个属性，然后是不是可以做一些剪枝，他都会在这个GQL语言里边设计的时候就会给你优化。

3.1.3 Euler之MP抽象层

然后第三个模块就是 MP 抽象层。我们说了所有的 GNN 都可以理解为GCN 我们先不考虑，因为GCN那个东西，现在还没有真实的落地场景。

我们以Graph SAGE来看的话，就分为三个模块吧。
第三个模块一般我们不要
第一个模块就是子图抽样，子图抽样就是采样，首先你采几个结点，然后结点再采几个邻居，这就是走的方向，然后就是图卷积层、图卷积技术，就是做Graph SAGE 真正的聚合的，你有了邻居怎么聚合
然后第三个就是可选的池化模块，一般我们不要，目前我们工业界落地的时候大部分都不需要。

这边给大家列了一些，他们都是哪种类型的这样一个，这样一个东西。

首先我们来说一下子图抽样，子图抽样，就是刚才说的，我们结合，因为MP下层有几个支撑，一个GQL，一个是这个图分布式存储，以及高性能采样的一个模块。

你采样了这个黄色的点，采样之后，这首先是随机采样，然后随机采样之后，他再给你采样邻居。

我们刚才回过来看这个，这个其实比如 sampleN，就是采样N个结点，随机采样N个节点，然后 sampleNB 呢，就是在这N个节点的基础上，B就是neighbor的意思采样，每个再在采样一个 NB count，一个neighbor，就这个意思。

对应这里边，就是先采样这个黄点，然后每个黄点再采样一些邻居，然后就最终得到这样一个东西，是不是得到这样一个东西之后。

你再接下来进行这个卷积操作，这一步就完成了，子图采样这一部分就完成了。

然后图卷积这一块，你有了采样的东西，这一块已经采样好了，我们只有一个结点，我们只采用了一个黄色的结点 x1，然后它采样了三个邻居结点，那么它有三种方法需要实践。

这里边一般都是用各种虚拟类实现，你想要它会帮你实现一些，然后你想要添加的话在模块里边，再继承一下就行了，重写一下消息传递函数，消息传递函数就是个 PI，这个 PI 指的是你从邻居上，怎么传递消息，到这个目标节点上，比如x2怎么传到x1，x3怎么传到x1这样传的，在GraphSAGE是怎么传呢，Graph SAGE直接先把他们所有的东西过一个NN，过完之后再跟x1聚合在一起；
消息聚合函数，你每个结点传完之后，它怎么聚在一起的，刚才GraphSAGE 它是第一步消息传递做完了，其实要分开的话，也是可以的。你 x2用矩阵乘一遍，然后就放这 X3用矩阵乘一遍放在这，x4用矩阵乘一遍放在这，然后再做一个Sum pooling、Average pooling，这样一个东西，这是聚合；
聚合完了之后，怎么更新x1呢，Graph SAGE怎么做的呢？GraphSAGE就是把 x1 原来的，跟他的邻居 Concate 起来，是不是，然后再过一个W，然后再过一个RELU，这是GraphSAGE的一个做法，是吧，当然你可以实现各种各样的这些东西。

最后的算法层实现了很多算法，包括知识图谱的、异构图的，一些常见的表征学习的这些都会实现，你可以选用。

Q&A

Q 现在工业界除了GNN这种，还有其他高召回的非常规方法没

一般我们现在正常的

我们现在的召回一般都是双塔在做的，目前这阶段都是双塔
然后有一些公司不公开的，比如字节跳动、阿里，他们有一些自研的高效的一个召回的算法，因为召回我们用双塔的话，它其实有一些限制，你user侧和item侧自己做计算，但是没有match，没有match的话，你就跟精排的精度差很多，现在各大公司都在研究，怎么使用match特征，这是一种方法；
第二种就是一些自研的，Structural learning，这个词在最近的学术界工业界都有，就是你学的不是最终的一个Embedding，然后去做点积、去做召回，而是你对每一个Embedding，Embedding他召回的时候去学了一个路径 structure，然后你这个 user 也学了一个 structure，然后这个 item 学了一个 structure，然后 structure 做一些那个什么。

然后还有一些工程的优化

比如召回的话，因为我们候选集特别大，所以一般有一些有一些优化方法，我比如给大家，介绍一下ANN，ANN这个大家都知道，最近邻检索嘛，一般用的是HSW这块给大家，多多介绍一下
工业界的一些实践，还有一个是叫做 quant，一般我们最终算的 Embedding 都是 float16，你最终去做点积计算的时候，但其实，我们可以把它 quant 成 int8，做成 quant int8，我们是不是就不需要 ANN 检索了，我们就可以暴力去做了1000万的广告库，或者你上亿的推荐，我可以稍微增加一点机器，然后做 int8，做 int8 之后，然后我就可以全暴力计算了，是不是就能，更高性能的然后做了
然后还有一种，还有一种就是PQ ，PQ刚才就是对应了一个这种 structure 学习，大家有兴趣可以（自己研究）这里不做深度的介绍

给大家稍微说一下，广告的召回，我先从上往下看，Euler单机版10万条样本，这个不知道，我们都是分布式的，一般一个结点也就是几十万个，因为我们的单机，每一个 pod 都不大
GNN在推荐场景做了半年，比如GNN好像在阿里貌似还是一个挺大的部门的，因为 Euler他们做的都挺不错的，别的就不多说了。

Q 刚开始上图模型有啥迭代路径嘛

刚开始上图模型，最简单的，你就直接去用LINE去train一个，或者 GraphSAGE train一个，看你是想做两阶段建模，还是一阶段建模，刚才那个范式我已经给大家介绍了，大家可以按照那个范式去，去建模就行了。

Q 广告的召回和推荐的召回有什么不同

这个同学回答的不错

广告的召回，是要考虑商业价值的，广告的整个Rank链路，都要考虑这个商业价值的，我们都叫做 ecpm 或者 sorted ecpm，考虑了商业价值以及非商业价值，不管是在召回，在粗排，还是在精排都会考虑商业价值
推荐的话，一般考虑是另外的目标，比如停留时长，用户的留存，考虑这些目标不一样

但是整体的架构都是一样的。你比如字节跳动。他们做中台的这种。广告、推荐。他们中台都是同一套。

Q 做推荐算法工作需要具备什么样的能力

首先，我花几分钟给大家介绍一下七月在线的这个推荐系统高级班，目前现在是我了解到是到第7期了（截止到21年q2 是第九期），每一期的就业率最终都是 100%，而且每个老师后面可以帮助大家内推，一般我们的老师我了解，还是都很棒的，级别也都不错，内推的话会有一定的效果。
而且第7期推荐课的内容，我看内容还是蛮丰富的，除了会讲一些推荐系统的常用方法召回、精排，还会结合业界一些前沿的，你不能光讲一些现在在用的。
我说一下我来面试的经验。就是说对于看你的经验。如果你的经验少。比如你校招。或者是你就刚做一年，那么其实我不太care你的项目。你的项目其实在我们眼中，除非你在大厂确实做得不错，否则的话，一般你们的项目，我们就听一听，不是特别重要
我们会非常在意你的基础

首先是coding，刷题大家都是一定要刷的
然后算法的一个基础，你对召回精排，这方面有没有一些 insight，给你一个问题，你能不能想到一个优化的思路
其次，在真正的工作中，我们有很多组件，大家都建好了你需要一点一点的去突破的，你需要去想到优化的点
那么我去给你一个实际问题的时候，比如我是在工作中，我遇到这个问题，我想到了比较好的解决方案，并且上线实践了，那么我会给你同样的场景，我问你能不能想出来，你可以不想得跟我一样的，但是如果你也有比较好的解决方案，我认为你的建模能力不错
算法工程师说白了，第一是个工程师，第二，是一个解决问题的工程师，这上面除了有经典的常用的算法，还有一些前沿的算法，包括特征工程，然后还会讲一些工程的，比如 flink、scala、spark，这些你在工作中都是有需要的，你如果是校招的话，你要说你懂spark，然后懂scala，懂 flink，懂 kafka，那其实你的算法能力，我可以给你要求不那么高。
当然你一定要有一个点特别突出，要么你就算法特别好，要么你就工程也不错，加上算法也不错，这种都可以。

然后这边推荐课，一般还会有几个项目，就是实战老师带着大家去真正地去实践，工业中的，这样一个做法，一般我们都是在工业界，现在在打磨的，我们了解工业界该怎么做，所以我们给你们讲的也都是最实用的，不管你们面试还是以后工作呢都是很受用的。

如果你们读过研究生你们就知道研究生的课

第一，时间长
第二，他们的课件可能非常的老旧、经常的不变，那么你在七月在线，首先校长，都会让我们定期的更新课件
第三，你可以花大约研究生1/10的精力，学到真正的实操，真正你工作中用到的技能，甚至比研究生学到的还要多，我说实话，在研究生学到的东西，在工作中用到的其实特别少，但是你让工业界的老师，给你们讲的话，其实有事半功倍的效果。

对了，我待会会选几名同学，送每人1000块钱的视频课。
因为现在我们是一个开放时间，比如你以前不是做推荐的，你想做推荐有什么路径，或者是GNN有什么想问的，或者说广告啊，这些都可以问一问，包括七月在线的这些，我看校长也在，你们要是有什么问题的话，还可以问一下。
有同学问，阿里社招P7年包有100么这个东西还是要看，要是看你的面试效果这个 range 比较大，可能60万到150万之间都有的。

Q 构图有什么技巧，多讲一些 trick

因为这次是个公开课，然后具体的这些 trick、实践这些东西，也是在正式课里面，肯定是更清楚的，因为是要上手的。

构图有一些技巧的话，就是你要对业务有一个深刻的理解，假如说我举个例子，你在做广告，你做的时间长了，你就知道click 点击跟转化需要一个什么样的比例，你是确定1:3的还是1:10呢，这个东西就是工业的一个业务的经验。

构图考虑有哪些维度一般构图实践中，，一般是两种维度
第一种维度是，你纯考虑这种行为，比如广告，就是点击、转化是吧；
然后你还可以考虑一种跟业务目标相关的，比如你转化了多少钱，你转化之后，带来的收益是多少，这个东西你可以加进去。
点击也是一样一般是两种维度，一个是不考虑最终的目标，一个是考虑最终目标。

Q 二部图和同构图有什么区别

比如阿里做的商品的同构图，你最终只能得到item的Embedding，而不能得到 user 的 Embedding，这是最大的一个区别，二部图的话，你既可以得到 user 的 Embeeding，也可以得到，Graph的Embedding或者这个 item 的 Embedding，这是一个最大的区别；
然后第二个区别就是同构图你没有办法考虑更多的一个交互，你比如，他建模的Session内的点击的序列，你就点击了，当然如果你二部图的话，你可以做得非常丰富用户跟 item 的所有的交互你都可以放上去，然后你可以设计一些

刚才我也给大家说了，采样的时候你可以按边采样，你可以按，比如你每一个batch，你可以采样，假设是电商推荐啊，我给大家先说一下，这个图怎么构的，这个图就是，点击、加购、购买，然后退货，这样一个图
然后你可以采样啊，你可以采样的是，比如你每个batch，你采样三个购买，然后5个点击，然后两个退货，这样总共10个，你可以按不同的边来采样，还可以是这样子
一般我们现在倾向于，如果好做的话就做异构图

看时间也快两小时了，今天还是万圣节，要是没什么问题，我们就先到此为止，然后后面如果想报名七月在线的高级班的话，里边很多内容会讲得更细。
因为这次公开课，第一时间有限，第二毕竟是个公开课，我也不了解大家的基础，所以很多内容，也不是说有的放矢，你说基础理论讲不讲的，有的同学他可能知道，有的同学他可能不知道，是不是。

Q 课程之外，还有什么渠道提升工程能力

如果你现在是一个在校生的话，Kaggle比赛，天池比赛去参加参加，这些是一个实践的机会，但是真正的工程能力提升，还是要去大厂实习，由于大厂的那些，首先你这个数据量，你在比赛或者什么东西都是没有办法的，所以你真正的工程能力还是要去大厂实习的，还是建议大家，可以去大厂实习看一看，真正的工业界是怎么做的。
因为你真正地参加一个比赛，他数据都给你弄好了，比如你在真正的工业界，比如流式训练怎么做的，流式训练他有很多的坑。

流式训练，我给大家举个简单的广告的例子，广告，你点击还行，你点击了之后，它马上就能回传了，是不是，我能知道你点击了，但是转化
比如我下载了，下载了某个游戏，你下载之后，回传是厂商，是游戏商他来决定的，他一般会成批量地给你回传，那么这时候，你就会遇到一个问题，你的正样本回传不过来，你每次你流失训练的时候，你每次见到一个正样本，你要等它是不是正样本、负样本，你要等一两天，甚至一周怎么办呢。

大家都会有一些优化，比如 emit，fast emit，只要来一个样本，我不管你是正样本，负样本，先当作负样本处理，然后等你真正传回来了正样本，我再把你当做正样本，再处理一遍，并且加了一些规则通过一些算法的推导，告诉你这样是无偏的
真正的算法工程师的工作内容有两大块

第一块就是idea，你作为算法工程师，跟工程的最大区别，就是你一定要有 idea，你一定要知道，你往哪些方向优化，这也是算法工程的价值，你有idea之后，你就能提升业务的价值，比如推荐，广告更是这样了，你有一个idea，你提升了业务，那么你就提升了公司的挣钱能力，对不对，那你不是高绩效，谁是高绩效，是吧？
第二个工程能力不能少，你有了idea之后，然后你把模型建出来，建模，建模完了之后，你一定要了解工程，因为很多方面，比如精排，精排和混排，精排依赖模型重一点，你在召回那侧，他其实有很多工程的优化，你在工程上比如我刚才说的这个 ANN ，这是工程，quant 是工程，quant 跟 PQ 都既是算法又是工程。

你算法的优化是一方面，然后如果你工程，提出一些工程内容，那也是很棒的，所以大家都是要平衡发展的，不是说你会写论文就行了啊，大家可能都知道，现在有些Lab发展的不是特别好，在公司内部，也没有什么人权，地位也比较低下，绩效也不高，高绩效的都是这些业务部门，因为它给公司带来的价值，Lab 部门不是光写论文，得往上赋能，能力不够的话还是不行。

Q 要不要考虑公司的业务部门

最后一点，给大家找工作的一个建议，大家一定要摒弃掉业务不好的一个想法，做业务是非常好的，你在公司你就得做业务，你不做业务就去研究所做研究。
你要想在公司做研究，说实话你的发展一定不是特别好，除非你是业界的大佬，你要么就是在斯坦福读个博士，然后在业界非常有名，你去带一个团队，做 Lab 的实验室主任是吧，这可以，否则的话，建议大家去业务部门。

我之前找工作的时候，也是想做纯 reserch，但是 reserch 这个东西我做过，做完之后感受不是特别好，还是做业务跟算法的结合，是最能让你感受到一个满足感的。

你能有idea，idea之后上线完之后看到收益，你这个收益可能每天都给公司赚100万，虽然你的年薪可能也才一两百万、可能几百万，但是你每天都能给公司多挣100万，你再有个提升，每天又能给公司多赚几十万，这就是你的价值。

今天跟大家也聊了不少，现在也马上两个小时了，我们今天都先到这边，欢迎大家来参加七月在线的集训营/高级班，我这边结束了，也感谢同学们今天的参与。

后记

我整理完这次公开课后，发现吴老师的视野确实广，每年关注顶会paper，对业界前沿熟练于心，最后也给了很多想做推荐同学的建议，比如算法工程要两不误，比如要深入业务扎根业务，通过提升业务发挥技术的价值等等等，洋洋洒洒，长文一篇。

为了让本文的可读性更强、更通俗，以下是修改记录：

3.18第一次修改，主要理顺1.4.2 GE之LINE中一阶相似度、二阶相似度的公式定义；
3.20第二次修改，主要理清1.4.5 Struc2Vec中的分层对比逻辑，且清晰化GraphSAGE算法；
3.21第三次修改，主要理清2.3.2 PinSage之GNN模型的算法流程，比如明晰化S0 = S1∪S1的一阶邻居；
3.23第四次修改，主要细化1.4.2 GE之LINE算法中对于二阶相似度计算公式的推导；
3.27第五次修改，主要理顺相关描述，让语句更通顺、更好理解，主要针对第一大部分；
4.6第六次修改，和北邮团博士全面讨论本文第一部分 GNN通俗导论，完善相关描述、公式的细节。

最后预告下，下一篇推荐方向的笔记，将针对另一位大牛老师推荐王老师的公开课《推荐系统算法技术发展(各模型的演进)》，欢迎期待。

前言