正文

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

v_JULY_v  v_JULY_v  2022-11-29  207

关键词：

原始视频：七月在线公开课《图神经网络在推荐广告场景中的应用》，课件可以打开视频页面下载
分享老师：推荐吴老师，推荐/广告算法专家，曾任部门算法负责人，年薪....不低
字幕校对：天保，全程校对了字幕，但因为是公开课，互动性很强，所以去掉了很多互动性的语句
笔记撰写：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，你有什么想法呢，它缺什么？

在展开之前先说下相关公式符号，比如上图公式里面的是一个从到的非正规化的转移概率，最简单的一种计算方式就是，对于无权图，，而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仅能用于无权图)。

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

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

比如和这两个顶点(类比节点6和7)的边权为，定义经验分布

其中

表达的意思为节点和的边权值在所有边权值之和里所占的权重；

然后你向量化Embedding之后，和两个顶点之间的联合概率为

其中，、分别为顶点、的低维向量表示，整个式子可以看作一个内积模型，计算两个顶点之间的相近程度；

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

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

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

考虑到

且，所以有

且类似，有

另因为、为常数，所以、都为常数，可以忽略不计，从而最终可得

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

节点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），从而可以认为具有相同或相似上下文分布的顶点被认为是相似的。换言之，因此，在这种场景下，每个顶点既是顶点本身，也是其他顶点的上下文。

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

从而通过学习每个节点的两个向量表示、来最小化这个目标函数，最终得到每个节点的维向量表示。

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

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

根据，可得

使用KL距离代替，从而有

考虑到，且假设，统统代入可得

；

因为是常数项，所以上述式子可得

因为为常数，所以也是常数，从而忽略常数项可得

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

两个节点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

展开之前，说一下相关公式符号的表达，比如就是节点到节点的最短路径，这个最短路径的取值只能是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是当前这次采样到的节点，已经是下次他要采样的结点；

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

P是控制的回头率，假设P是无限大，就不回头一直往前走，假设P是0.1，那么回头的概率就很大，10 对不对；
Q 控制的是 BFS 与 DFS 的一个平衡，假设Q=1，那么你到都是1，是不是权值是一样的，那么要么BFS、要么DFS，不做任何的区分，那么如果Q非常的大，那么它是倾向于 BFS 的，你看他会倾向于往走，对不对；如果要是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的第一层邻居用表示(图出自此处)

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

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

则有：

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

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

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

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

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

其中表示第k层中，所有指向u的边中权重大于该层平均权重的数量，具体的式子为，其中表示第层所有边权的平均值。

直白讲，实际上表示了第k层中有多少节点是与节点u相似的，如果u与很多节点都相似，说明此时一定处于低层次，考虑的信息太少，那么查看详情

清华最新《图神经网络推荐系统》综述，阐述gnn：阶段场景目标和应用

...是当今互联网上最重要的信息服务之一。近年来，图神经网络已成为推荐系统的新技术。在这个调研中，我们对基于图神经网络的推荐系统的文献进行了全面的回顾。我们首先介绍了推查看详情

《深入浅出图神经网络》gnn原理解析☄学习笔记图的概述(代码片段)

《深入浅出图神经网络》GNN原理解析☄学习笔记（一）图的概述文章目录《深入浅出图神经网络》GNN原理解析☄学习笔记（一）图的概述图的基本定义图的基本类型邻居和度子图与路径图的存储与遍历邻接矩阵和... 查看详情

《深入浅出图神经网络》gnn原理解析☄学习笔记卷积神经网络(代码片段)

《深入浅出图神经网络》GNN原理解析☄学习笔记（三）卷积神经网络文章目录《深入浅出图神经网络》GNN原理解析☄学习笔记（三）卷积神经网络卷积与池化信号处理中的卷积单通道卷积多通道卷积池化卷积神经... 查看详情

什么是图神经网络？

什么是图神经网络？GNN将深度学习的预测能力应用于丰富的数据结构，这些数据结构将对象及其关系描述为图中由线连接的点。当两种技术融合时，它们可以创造出新奇而美妙的东西——比如手机和浏览器融合在一起... 查看详情

论文合集|大规模图上的高效gnn

...除转载于：图与推荐????AwesomeEfficientGraphNeuralNetworks图神经网络在工业界应用非常受欢迎，这是一篇关于高效图神经网络和大规模网络中图神经网络应用的精选论文列表。链查看详情

论文合集|大规模图上的高效gnn

...除转载于：图与推荐????AwesomeEfficientGraphNeuralNetworks图神经网络在工业界应用非常受欢迎，这是一篇关于高效图神经网络和大规模网络中图神经网络应用的精选论文列表。链查看详情

图神经网络学习笔记|基础知识与gnn介绍直观透彻理解

一、基础知识GNN是指使用神经网络来学习图结构数据，提取和挖掘图结构数据中有效的特征和模式，满足聚类、分类、预测、分割、生成、异常检测等图学习任务需求的算法总称。GCN实现了CNN在图上的平移不变、局部感知和权值... 查看详情

《深入浅出图神经网络》gnn原理解析☄学习笔记神经网络基础(代码片段)

《深入浅出图神经网络》GNN原理解析☄学习笔记（二）神经网络基础文章目录《深入浅出图神经网络》GNN原理解析☄学习笔记（二）神经网络基础机器学习基本概念机器学习分类机器学习流程概述常见的损失函数... 查看详情

深入浅出图神经网络|gnn原理解析☄学习笔记图信号处理与图卷积神经网络(代码片段)

深入浅出图神经网络|GNN原理解析☄学习笔记（五）图信号处理与图卷积神经网络文章目录深入浅出图神经网络|GNN原理解析☄学习笔记（五）图信号处理与图卷积神经网络矩阵乘法的三种形式图信号与图的拉普拉... 查看详情

深入浅出图神经网络|gnn原理解析☄学习笔记表示学习(代码片段)

深入浅出图神经网络|GNN原理解析☄学习笔记（四）表示学习文章目录深入浅出图神经网络|GNN原理解析☄学习笔记（四）表示学习表示学习表示学习的意义离散表示与分布式表示端到端学习基于重构损失的方法—... 查看详情

论文笔记acomprehensivesurveyongraphneuralnetworks(gnn综述)

...分类：在本篇文章中，作者总结了目前主要的图神经网络模型，并提出了一种新的分类方法将目前的图神经网络分为以下四种：循环图神经网络（RecGNN），卷积图神经网络(ConvGNN)，图自动编码器(GAE)... 查看详情

论文笔记acomprehensivesurveyongraphneuralnetworks(gnn综述)

...法的研究。在本篇文章中，作者总结了目前主要的图神经网络模型，并提出了一种新的分类方法将目前的图神经网络分为以下四种& 查看详情

论文阅读gnn阅读笔记

Agentleintroductionongnn前言发表在distill的文章图神经网络在应用上才刚刚开始搭建了一个GNNplayground什么是图图是表示实体之间的关系可以分别表示成点向量、边向量、图向量图可以分为有向图和无向图数据是怎么表示成图图片表示... 查看详情

4位gnn一线大佬新书出版了！

Datawhale推荐推荐人：张钹、周志华、李航等广大图神经网络（GraphNeuralNetwork，下文简称GNN）研究人员翘首以盼、吴凌飞、崔鹏、裴健、赵亮4位GNN领域的中青年影响力学者联合编写《图神经网络：基础、前沿... 查看详情

深入浅出图神经网络|gnn原理解析☄学习笔记图的概述(代码片段)

《深入浅出图神经网络》GNN原理解析☄学习笔记（一）图的概述文章目录《深入浅出图神经网络》GNN原理解析☄学习笔记（一）图的概述图的基本定义图的基本类型邻居和度子图与路径图的存储与遍历邻接矩阵和... 查看详情

《深入浅出图神经网络：gnn原理解析》

深入浅出图神经网络：GNN原理解析https://cread.jd.com/read/startRead.action?bookId=30567027&readType=1 作者:ZZU_chenhao仅仅是一名普通的研究生而已。原创【学习日记】《深入浅出：图神经网络》：第四天---表示学习表示学习表... 查看详情

李宏毅机器学习|图神经网络graphnerualnetworks(gnn)|学习笔记-part1

...IN(GraphIsomorphismNetwork)前言最近看的论文里面主要是就是图神经网络GraphNerualNetworks，然后就来学习下李宏毅机器学习中的图神经网络的内容，记个笔记。视频地址1Introduction GNN简单来说就是Graph+NerualNetworks,关键问题就是... 查看详情