graphSage还是HAN ？吐血力作综述Graph Embeding 经典好文
继 Goole 于 2013年在 word2vec 论文中提出 Embeding 思想之后，各种Embeding技术层出不穷，其中涵盖用于自然语言处理( Natural Language Processing, NLP)、计算机视觉 (Computer Vision, CV ) 以及搜索推荐广告算法(简称为：搜广推算法 )等。而在这其中，基于 Graph 产生 Embeding 的设计思想 就像这璀璨星河中最灿烂的明珠，不断带动着算法文明的征程滚滚向前～
在以前的一篇文章 深入浅出理解word2vec模型 (理论与源码分析) 中我们已经知道： embedding 可以把理解为用一个一维度的浮点数组 (tensor) 来表示某一个item对象(单词或则用户等)，两个item之间的语义关系计算可以用 他们的embeding 计算来代替。
通常，我们会在 图数据结构上 跑一些机器学习/深度学习的任务，一般来说，主要包括 节点和边 的 分类和回归任务以及整图预测。
(1) 节点的分类与回归：
一般用于预测给定节点的类型。例如：一个用户为异常用户的可能性，以及某个人的消费能力预测。
(2) 边的分类和回归：
我们一般用于预测某2节点之间是否有边以及边的权重大小。例如：预测抖音上一个人是否会评论某条抖音以及他评论的情感的正负，或则京东上一个人购买某个商品的可能性以及会买几件等。
(3) 整图预测:
我们一般可以把用于给定2个图，分析两者的相似性质，或则预测生物大分子的特性。
鉴于前一篇文章 一文揭开图机器学习的面纱，你确定不来看看吗？ 过于详细，很多人看到最后的Graph Embeding 部分已经精神不能集中了。基于此，本文于上文中择优进行了裁剪，仅仅抽取出其中与Graph embeding相关的内容。下面让我们开始本文的阅读吧 ～
(1) 图表示学习基础
基于Graph 产生 Embeding 的设计思想不仅可以 直接用来做图上节点与边的分类回归预测任务外，其导出的 图节点embeding 也可作为训练该任务的中间产出为别的下游任务服务。
而图算法最近几年最新的发展，都是围绕在 Graph Embedding 进行研究的，也称为 图表示学习(Graph Representation Learning ,GRL)。
图表示学习, 顾名思义，是从图上学习到各个 节点或则边的嵌入(Embeding)表示, 是表示学习和图结构数据相结合产生的方法，其目的是：将高维稀疏的图结构数据映射到低维稠密向量，同时来捕获网络拓扑结构及网络中节点的内在特征。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NNTneVuG-1673425582202)(null)]
在这里，我们必须要插入很重要的一点就是 ：
目前我们日常能接触到 传统机器学习/深度学习 和 图机器学习 以及 强化学习 的 样本 是有一些明显差别的。我们知道传统的 机器学习/深度学习 ，例如 前面一些文章提到的 点击率预估等模型 用到的样本，都是基于一个强假设，即：IID原则。三者的对比关系如下：
传统机器学习：样本独立同分布（Independent Identically Distribution,IID）,是指样本是从同一个数据分布里多次随机且独立的重复采样得到。
图机器学习：样本不独立，样本间相互关联，依一定方式构建了图结构。
强化学习：样本不独立，样本之间有时序上的前后关联。上一步的action产生的reward和下一步的action与reward在最初的数据集假设上有相互关联。
而进两年的图表示学习，从分类上又可以大致把分成2类： 基于游走的图结构表示学习 和 基于卷积的图深度表示学习。
(2)基于游走的图结构表示学习
应该知道，我们这里所说 基于游走 是指在已经建好的 逻辑图 上面去以 某种方式遍历某些节点而得到一些节点序列 的方式。 基于随机游走采样节点的图表示学习比较经典的实现有以下几种，分别是：Deepwalk 、 Node2Vector 以及 LINE。
再此之前我们需要明确一点就是： 基于游走的图结构表示算法 是一种基于邻域相似假设的算法，受启发于 word2vector 来学习节点的向量表示。
(2.1) Deepwalk 算法
Deepwalk 算法，又称为 深度游走算法。它通过随机游走的方式提取顶点序列，根据序列中顶点和顶点之间的共现关系(Co-occurrences) 来学习向量表示, 可以说随机游走是整个Deepwalk 最重要也最具有开创性的一部分算法。
随机游走是一种可重复访问已访问节点的深度优先遍历算法。对于给定图中的某个节点，随机从邻居节点中抽取一个节点作为下一个访问点，直到访问序列达到预设长度。
阿里巴巴的论文 Graph Embedding with Side Information（GES) 在 deepwalk 算法的基础上，引入了 item 的附属信息 来训练图嵌入, 可以解决商品冷启的问题，也是一种 deepwalk 算法 很经典且有效的拓展应用。
综上所述: Deepwalk 使用随机游走算法在图上获得序列，使用 Word2Vec 中的 Skip-Gram 算法来学习节点的Embedding, 是一种很经典的 Walk + Skip-Gram Loss 的架构。
(2.2) Node2Vecter 算法
我们知道，图和其他如队列、栈、树等基础数据结构一样，也具有 可遍历 的性质。我们在图上有目的的遍历算法又可以两种： 深度优先(DFS) 与 广度优先(BFS) 。
广度优先(DFS) 可以获得 每个节点的所有邻居，强调的是 局部微观视图; 而 深度优先(BFS) 则倾向于探索更大的网络结构，只有从更高的角度才能观察到更大的集群, 具有 全局视野 的潜质。
Node2Vector 在游走方式上对随机游走算法进行了改进，设计了一种灵活的邻居节点抽样策略，它允许用户在BFS 和DFS之间进行平衡。其具体公式如下图所示：
其中：P 为返回参数，q为进出参数 。p,q 分别控制着当时在邻居节点中采样的概率。
我们从上述公式也能看出：Node2Vec 算法引入了两步随机游走算法： 第一步从节点t 走到节点v, 第二步从节点v游走到其邻居节点，如 x1,x2,t 等。节点v 跳转到其邻居节点的概率不再是随机分布的，而是根据节点t 和节点x 共同决定， 可以表示为 f( vt+1 / vt, vt-1 ) , 这里是根据节点 t 与节点 x 的最短路径来确定。
我们可以想象一下，我们处于 节点v 的位置，x 表示下一个节点，t表示上一个节点。x到t的距离有三种：0、1和2。0表示回到来的节点，1表示停留在当前节点，2表示去向当前位置下一个和来的节点不同的邻居节点。这里需要结合上面的公式以及公式成立的条件，仔细想清楚采样逻辑。
综上所述： 对于 node2vec算法来说，也是基于上面提到的 Walk + Skip-Gram Loss 的架构。 其中&&改进的采样方式决定着在图上得到的行走序列，近一步决定着训练的嵌入的重点**。
(2.3) LINE 算法
LINE 算法的全称是：Large-scale Information Network Embedding ，其是对于上述两种算法的更进一步的改进。
书接上文，上文介绍的 Deepwalk 和 Node2Vector 算法 均只考虑了 成边的顶点之间的相似度，并未对不成边顶点之间关系的建模。 而本小节介绍的 LINE算法 即考虑了成边顶点对之间的关系(称为局域相似度)，也考虑了未成边顶点对之间的相似度(称为全局相似度)。
LINE算法为图的局域相似度和全局相似度设计了专门的度量函数，适用于无向图与有向图。
在line算法的建模过程中，该算法的局域相似度用 一阶相似度(First-order Promimity ) 描述, 表示图中直接相连的节点之间的相似度。其建模公式如下图所示：
其中：公式表示的是 Vi 、Vj 之间的一阶联合概率。
该算法的 全局相似度 用 二阶相似度(Second-order Proximity) 来衡量 2个节点的邻居之间的相似度。二阶相似度假设那些具有相同邻居节点的节点在特征上较为相似，直观来说，就是拥有共享邻居的节点更为相似。其建模公式如下图所示：
对上面的公式，我们可以这样来通俗理解： 对某个节点，另一个节点有多大概率是它的邻居(条件概率分布)以及是否真实数据集中是它的邻居(经验分布)，这2个分布要距离尽可能的小。其实就是学习的假如他们的邻居相似的话，让他们本身的embeding也尽可能的相似。
综上所述： LINE算法通过合并一阶和二阶相似的优化目标完成最终的模型的优化，而并不紧紧基于有边存在的节点对。
(2.4) 异构图 Metapath 学习
上面所说的算法，通常都是在同构图上进行采样节点的算法，当然我们也可以直接把 异构图转成同构图 用同样的方法来学习各个节点之间的关系，但是这样也就失去了构建异构图时更细腻的不同节点类别本身带有的信息。例如：把用户和商品用一样的建模方式，总归是不合理的。
在具体实践中，为了分辨异构图特点，引入了 元路径(meta-path) 的概念。元路径是在 异构图G上按照元路径模式 N1 -R1-> N2 -R2->N3 来游走产生路径。其中 N表示节点类型，R表示边关系类型。具体如下图所示：
我们知道：元路径游走是一种有偏游走。而基于元路径游走也产生了2种相关的算法，分别是： MetaPath2Vector 算法和 MetaPath2Vector++ 算法。
MetaPath2Vector 算法是基于 Metapath + Skip-Gram Loss 架构。 MetaPath2Vector 在 SoftMax 环节中没有分辨顶点类型，而是将所有顶点视作统一类型的顶点，也就是说在负采样环节采样的负样本并没有考虑顶点的类型。
而 MetaPath2Vector++ 则在softmax环节中，根据不同类型的顶点的上下文进行了归一化，也就是说给 Skip- Gram模型 每种节点类型 制定特定的负采样集合，进行了更细粒度的负采样控制。
(3) 基于卷积的图深度表示学习
说到 图卷积 (Graph Convolutional Network , GCN) 算法， 不得不提到 卷积算法的应用场景 与 使用图算法的数据特性。
(3.1) 图卷积基础知识准备
(3.1.1) 欧几里得数据和非欧几里得空间数据的概念
现实生活中有很多不规则的数据，例如在社交，电商，交通等领域中，用到的大都是实体之间的关系数据。这些数据通过庞大的结点和负责的交互关系，形成了特有的图结构，这种结构是非欧几里得空间数据。
这里我们需要区分下 欧几里得数据 和 非欧几里得空间数据的概念。
欧几里得数据： 它是一类具有很好的平移不变性的数据。对于这类数据以其中一个像素为节点，其邻居节点的数量相同。所以可以很好的定义一个全局共享的卷积核来提取图像中相同的结构。常见这类数据有图像、语言等。
而 非欧几里得数据，它是一类不具有平移不变性的数据。这类数据以其中的一个为节点，其邻居节点的数量可能不同。常见这类数据有知识图谱、社交网络、化学分子结构等等。
当然，我们也可以用CV 中填充图片的 pading方法来对节点邻居进行填充，但是假如说每个节点都需要不同粒度的填充的话，那实际实现是基本不可行的, 并且也没必要。
这里我们可以看到：图并不像图像中有着固定的邻居，图像上的卷积方法并不能在图上直接套用。
现实中，算法工程师们的创新总是无穷无尽的。所以该问题就有了以下的解决思路：把非欧空间转换成欧式空间, 找出一种可处理变长邻居节点的卷积核。
(3.1.2) 图与拉普拉斯矩阵
拉普拉斯算子 是 n维欧式空间 中的一个二阶算子，但如果将算子退化到离散二维图像空间，变成了 边缘检测算子。
拉普拉斯算子描述 中心像素与局部上下左右四邻居像素 的差异，这个性质可以用作图像上边缘检测算子。在图信号中，拉普拉斯算子也被用来描述中心节点与邻居节点之间的信号差异。
在N个节点的图G=(V,E) 中，拉普拉斯定义为 L= D – A 。 其中D为 图G的 度对角矩阵，D = diag(d(v1),…d(vn))
A(G)=(aij)是 图的 邻接矩阵。拉普拉奇定义为：度对角矩阵减去邻接矩阵。
我们可以知道: 拉普拉斯矩阵含有图的结构信息，作用可以理解为把非欧几里得空间数据用可以类似于欧几里得空间的处理方法进行处理。
(3.1.3) 谱域卷积与空域卷积
传统意义上的 傅立叶变换 是 时域到频域 的变换，而这种变化是通过一组 特殊的正交基 实现。结合上文所说的拉普拉斯矩阵，我们用 拉普拉斯矩阵表示图 , 它有一个很好的性质是： 傅里叶变换需要 基底ewit, 这个用拉普拉斯矩阵的 特征分解函数 就完成了 两者的结合。
谱卷积神经网络 就是直接根据 全图傅立叶卷积定义 的，其有一个缺点就是难以从卷积形式中保证节点的信息更新由近处邻居贡献，即无法保证局部性，且训练计算度大。
这里，我们又要引入 切比雪夫网络 的概念，它与谱卷积神经网络最大的不同就是： 不需要在对拉普拉斯矩阵进行特征分解，不用做全图的卷积计算，而且它的卷积核具有严格的空间局部性，仅仅考虑了中心节点的K阶邻居作为邻域节点。
而下文要说到的 图卷积(CCN) 则是只考虑一阶切比雪夫多项式的算法。**空域卷积(spatial Convolution)**则是从邻居节点信息聚合的角度出发，更加关注节点的局域环境。
图卷积算法中，我们将 邻接矩阵 与 节点的特征向量 相乘，本身具有聚合邻居节点信息的属性，已经同时具有 空域与谱域 的意义。
(3.2) 图卷积介绍
书接上文，我们先来说说最简单的 图卷积网络(GCN）,
我们知道：空域卷积与卷积神经网络的设计理念相似，其核心在于聚合邻居节点的信息，直接将卷积操作定义在每个节点的链接关系上。
通俗点理解，GCN实际上跟CNN的作用一样，就是一个 特征提取器，只不过它的特征提取对象是图数据。
其中，D负责提供权值的矩阵，邻接A矩阵控制应该融合哪些点, H表示上一层的embedding参数。
当然，我们在训练完成模型之后，拿到embeding之后可以灵活运用，进行下游的分类和回归任务。
这里我们需要注意: GCN正常层数只需要2–5层即可。 因为节点每更新一次，感受野就变大一些，如果网络太深，那么每个节点就会受无关节点的影响，有些节点的学习会有趋同的趋势，引起 过平滑 问题，导致最终目标效果反而下降。
(3.3) Graph Sage介绍
Graph Sage 全称为：Graph Sample And AGGregate, 就是 图采样与聚合。
在图神经网络中，节点扮演着样本的角色。
从前文我们已经了解到：在传统深度学习中，样本是 IID 的，这使得 损失可以拆分为独立的样本贡献，可以采用小批量的优化算法来并行处理总的损失函数。
但是图的样本之间是有着关系的，早期的GCN等网络都是采用全批次梯度下降方法进行训练，这种方式需要存储整个图的邻接矩阵。
2017 年提出的 Graph Sage 算法，基于GCN 邻居聚合的思想，但并不是把全部邻居聚合在内，而是聚合部分邻居，随机采样邻居K跳的节点。全邻居采样中给出了节点的抽取1跳和2跳的形式，而GraphSage只用抽取固定个数的近邻。如下图所示：
该算法的核心步骤是：Sample 和 Aggregate
sample : 采样，从内到外，选择固定个数的近邻，不够就重复采样
aggregate：聚合，从外到内 ，聚合被采样到的那些节点的embedding , 因为邻居节点也构成了一个embeding 序列，不光可以直接Sum求和，可以使用各种聚合方式，例如：max ,mean , lstm , transform 等。
注意： Graph Sage 算法本质上是 采样生成一个个小的子图 进行训练，局部更新，也可以对未出现节点的预测。
(3.4) 异构图的卷积(RGCN)
前文所说的GCN均是针对 同构图 的算法，而为了 捕捉不同节点的不同的关系 情况，工程师们又设计了基于异构图关系的卷积算法RGCN，全称是： Relation Graph Convolution Neural Networks。
其中：R 的个数也就是边类型的个数，论文中称为relation-specific。 其区别在于RGCN中，通往一个节点的不同边可以代表不同的关系。
在普通的GCN中，所有边共享相同的权重W。在R-GCN中，不同类型的边只有同一种关系才会使用同一个权重。
在上面公式中，我们可以看到：公式使用了 权重矩阵用于融合异构图中节点不同的邻居关系 。既然邻居节点又很多，可以构成一个序列，那我们是否可以学习出 不同类型的邻居占据有不同的权重贡献程度 呢？ 类似于起到一个 Attention 的作用？ 这就与下文我们提到的 GAT算法 与 HAN算法 有关了。
(3.5) Attention相关算法 GAT 与 HAN
从上文我们可以知道： GCN 首次提出了 卷积的方式融合图结构 特征，提供一个全新的视角。
但是，它也有一些显而易见的主要缺点：
(1) 融合时 边权值固定 的，不够灵活。(2) 可扩展性差，因为它是全图卷积融合，全图做梯度更新，当图比较大时，这样的方式就太慢了，不合适。(3) 层数加深时，结果会 极容易过平滑 ，每个点的特征结果都十分相似。
针对上面提出的不足，GAT 可以解决问题1 ，GraphSAGE 可以解决问题2，DeepGCN等一系列文章则是为了缓解问题3做出了不懈努力。
首先说说GAT，我们知道 GCN每次做卷积时，边上的权重每次融合都是固定的，可以加个 Attention，让模型自己学习 边的权重，这就是GAT网络了，下面是 核心Attention 的定义公式：
同理，HAN 针对异构图的不同类型权重融合进行了更进一步的精心设计，如下图所示：
从上图可以看到：HAN是一个 两层的attention架构，分别是 节点级别的attention 和 语义级别的attention。
前面我们已经介绍过 metapath 的概念，这里我们不在赘述，不明白的同学可以翻看 本文章前面的内容。
Node Attention: 在同一个metapath的多个邻居上有不同的重要性。
Semantic Attention: 多个meta path有不同的重要性。
在进行 图传播计算 的过程中，首先 固定metapath的类别 Φi ，通过 节点级别的attention 将中心节点的基于 Φi 的邻居节点进行聚合，得到每个metapath的特征向量 ZΦi ，然后再通过 语义级别的attention 将特征向量 ZΦ 进行聚合，得到最终的特征向量 Z 。最后通过一个MLP得到这个节点的预测值 yi 。
(4) 图上消息传递元语 MPNN
我们在实现图算法实现的时候，必不可少的就是要弄明白图上消息传播的计算逻辑，这里介绍一下 MPNN ，全称是：Massage Passing Neural Network 。
我们都知道 tensorflow 或则 pytorch 是 DNN深度学习框架，而实现 Graph Embeding 算法则需要使用 图深度学习/机器学习框架。基于 tensorflow 的图深度学习框架，这里推荐阿里巴巴 GraphLearn, 以前也叫AliGraph, 能够基于docker 进行环境搭建，容易上手。而 基于 pytorch 的图深度学习框架，这里则推荐亚马逊的 DGL ( Deep Graph Library ), 其完善而又通俗易懂的中文官方文档，简直是我的最爱，强烈推荐！！！
后面 我们的图机器学习/深度学习代码也基于 dgl 来实现 。首先这的消息传递元语说明，也是基于dgl。
dgl的消息传递范式 如下：
图上已经说的非常详细，我就不在赘述了。
同时，我们可以使用dgl的基础消息范式进行我们自己网络特征处理流程里消息传递过程的定义，举个栗子如下：
@ 欢迎关注微信公众号：算法全栈之路 def message_func(edges): return {'he': edges.src['hu'] + edges.dst['hv’]} # 推荐: dgl.function.u_add_v('hu', 'hv', 'he') def reduce_func(nodes): return {'h': torch.sum(nodes.mailbox['m'], dim=1)} # 推荐：dgl.function.sum('m', ’h‘) # 单独调用逐边计算: graph.apply_edges(fn.u_add_v('el', 'er', 'e’)) # 综合函数,推荐: graph.update_all(fn.u_mul_e('ft', 'a', 'm'), fn.sum('m', 'ft'))
如上文所示：Update_all() 参数是一个消息函数、一个聚合函数和一个更新函数。
更新函数update() 是一个可选择的参数，用户也可以不使用它，而是在 update_all 执行完后直接对节点特征进行操作。
由于更新函数通常可以用纯张量操作实现，所以DGL不推荐在 update_all 中指定更新函数。
到这里，一文揭开图机器学习的面纱，你确定不来看看吗 ? 的全文就写结束了，后面会针对更详细的图上任务结合进行讲解～
码字不易，觉得有收获就点赞、分享、再看三连吧~
算法全栈之路
