图平台技术及应用实践

在这个例子中，我们现在要查找员工Alice所处的部门名称。

Q：假设Alice可以同时任职于多个部门

在关系型数据库中，可能存在三张表：员工信息表、员工与部门关系表、部门信息表，我们写SQL进行查找，需要进行两次JOIN操作才能获取Alice所处的部门名称。

而对于使用图数据库来存储及检索的话，可以将员工和部门都定义为实体，而他们之间的关系就是从属关系，这样可以使用图查询语言一句话查找得到结果。

对比可以看到，无论是操作的复杂度还是所需计算复杂度，都大大降低了。

得益于图数据库在拓扑关系类分析中的优势，实际落地在有图应用的场景里面也变的越来越多，举几个典型的例子：

知识图谱，是图数据库最早发挥价值的场景之一。

从知识存储沉淀到知识检索发现，通过知识内部的关联关系不断拓展，强化知识表达的内容丰富度。

现在的知识图谱会扩充了更广义的应用场景，将NLP技术的应用加入进来。

从原始的非结构化文本中进行实体的抽取、关系的抽取和预测、实体的不同说法之间的消歧等等。这些都对知识图谱的图数据构建及使用提供了极大的便利和业务场景的拓宽。

社交网络与图结构天然适配，通过图数据库将社交网络中的实体与关系数据存储起来后，可以用作好友推荐、兴趣群组推荐等，现在这种网络也可以扩展到将社交网络与内容推荐网络整合起来，给用户推荐商品、咨询等。

除此之外，还有金融风控、企业IT运维等也可以将图数据库应用起来并发挥价值，比如金融机构可以通过图来分析个人及公司的信贷风险，IT运维工程师可以通过图来分析服务器异常、交换机故障的影响范围并制定应对措施等。

图计算：是图理论技术在实际应用中的另一个主要阵地，图计算的发展也经历了算力发展、场景丰富、技术研究对图计算的不断推进。

到现在为止，除了PageRank，LPA等常见的算法外，也有了与神经网络结合的图神经网络算法，可应用在对拓扑结构的嵌入向量表达及节点、关系预测中。

我们这里介绍几个常见的图算法：PageRank、Label Propagation、Random Walk。

PageRank：是Google公司所使用的对其搜索引擎搜索结果中的网页进行排名的一种算法。

PageRank本质上是一种以网页之间的超链接个数和质量作为主要因素粗略地分析网页的重要性的算法。

其基本假设是：更重要的页面往往更多地被其他页面引用。

（或称其他页面中会更多地加入通向该页面的超链接）

其将从A页面到B页面的链接解释为“A页面给B页面投票”，并根据投票来源（甚至来源的来源，即链接到A页面的页面）和投票对象的等级来决定被投票页面的等级。简单的说，一个高等级的页面可以提升其他低等级的页面。

该算法以谷歌公司创始人之一的拉里·佩奇（Larry Page）的名字来命名。谷歌搜索引擎用它来分析网页的相关性和重要性，在搜索引擎优化中经常被用来作为评估网页优化的成效因素之一。

当前，佩奇排名算法不再是谷歌公司用来给网页进行排名的唯一算法，但它是最早的，也是最著名的算法。

Label Propagation算法：是一种基于标签传播的局部社区划分算法。

对于网络中的每一个节点，在初始阶段，Label Propagation算法对每一个节点一个唯一的标签。在每一个迭代的过程中，每一个节点根据与其相连的节点所属的标签改变自己的标签。

更改的原则是选择与其相连的节点中所属标签最多的社区标签为自己的社区标签，这便是标签传播的含义。随着社区标签的不断传播，最终紧密连接的节点将有共同的标签。

Label Propagation算法最大的优点是其算法过程比较简单。

想比较于优化模块度的过程，算法速度非常快。Label Propagation算法利用网络的结构指导标签的传播过程，在这个过程中无需优化任何函数。在算法开始前我们不必要知道社区的个数，随着算法的迭代，在最终的过程中，算法将自己决定社区的个数。

Random Walk是一种数学统计模型，它是一连串的轨迹所组成，其中每一次都是随机的。

它能用来表示不规则的变动形式，如同一个人酒后乱步，所形成的随机过程记录。随机游走的探寻过程主要是基于过去的表现来选择下一步，无法预测将来的发展步骤和方向，类似于物理学中的布朗运动。

近几年深度学习的技术在CV和NLP领域取得了长足的发展，图在结合神经网络的基础上也发展出了图神经网络方面的相关算法。

主要有Graph Embedding、Graph Convolution Network、Graph Attention Network等；

其中Graph Embedding和GCN在实际的业务场景中的使用居多，我们这里主要对这两类方法做个简单介绍。

DeepWalk主要方式是与自然语言处理中重要的Word Embedding方法Word2Vec联系了起来，使得Network Embedding问题转化为了一个Word Embedding问题。

DeepWalk通过从每个结点出发n_walks次，每一步都采取均匀采样的方式选择当前结点的邻接结点作为下一步的结点随机游走。

当游走的路径长度达到walk_length后，停止一次游走。

这样就生成了一个个游走的序列，每个序列都称为一个walk。每个walk都被当成Word2Vec中的一个句子，而每个结点都是Word2Vec中的一个词。

有了具体的图中的“词”和“句子”后，之后的算法几乎和Word2Vec的SkipGram版本完全一样。使用一个大小为window_size的滑动窗口作为一条walk的context，使用一个context中的中心词去推测所有context中的其他词，使用的目标函数也与Word2Vec一致。

类比可知，这里的Embedding就是每个节点在整个图的拓扑结构中的嵌入表达。可以使用预训练得到的embedding向量做进一步的业务使用，如推荐等。

虽然DeepWalk通过随机游走的方式，将图结构数据转化为了自然语言处理的任务来完成。

但是，图结构中节点的关系往往比词上下文关系更加的复杂。通常部分的图结构数据中边具有权重，使用现有的Word2Vec方法无法很好的应对这个问题。

此外，在现实世界数据中，图的规模往往过于庞大，以至于存下所有的walk的开销将十分惊人。

LINE(Large-scale Information Network Embedding)不再采用随机游走的方法。相反，他在图上定义了两种相似度：一阶相似度与二阶相似度。

Node2Vec是一份基于DeepWalk的延伸工作，它改进了DeepWalk随机游走的策略。

Node2Vec认为，现有的方法无法很好的保留网络的结构信息。

例如图所示，有一些点之间的连接非常紧密(比如u, s1, s2, s3, s4)，他们之间就组成了一个社区(community)。网络中可能存在着各种各样的社区，而有的结点在社区中可能又扮演着相似的角色(比如u与s6)。

Node2Vec的优化目标为以下两个：

为此，Node2Vec就要在DeepWalk现有的基础上，对随机游走的策略进行优化。Node2Vec提出了两种游走策略：

1.广度优先策略

2.深度优先策略

就如上图的标注所示，深度优先游走策略将会限制游走序列中出现重复的结点，防止游走掉头，促进游走向更远的地方进行。

而广度优先游走策略相反将会促进游走不断的回头，去访问上一步结点的其他邻居结点。

这样一来，当使用广度优先策略时，游走将会在一个社区内长时间停留，使得一个社区内的结点互相成为context，这也就达到了第一条优化目标。

相反，当使用深度优先的策略的时候，游走很难在同一个社区内停留，也就达到了第二条优化目标。

那么如何达到这样的两种随机游走策略呢，这里需要用到两个超参数p和q用来控制深度优先策略和广度优先策略的比重，通过p和q的调整，就可以是业务跟进自己的特点来选择对于BFS和DFS的偏重了。

深度学习的应用中最广的是CV领域的CNN和NLP领域的RNN。但是这两者一种适用于处理规范的网格数据，一种适用于处理序列化数据。

而对于图数据，拓扑关系属于非欧结构的，比如CNN在Non Euclidean Structure的数据上无法保持平移不变性。

简单理解就是在图中的每个节点的邻居节点数据是不同的，所以无法使用同样一个尺寸的卷积核来进行卷积运算。

但是人们又希望在这样的数据结构上有效的提取空间特征来进行机器学习，所以GCN就成了研究的重点。

GCN的本质目的就是用来提取拓扑图的空间特征。

简单来说就是使用拉普拉斯矩阵来计算并构造卷积核，输入图网络结构，中间传递过程保持住了图的拓扑关联性。GCN可以用于节点预测、关系预测及生成Embedding向量用作其他场景的应用。

GraphEmbedding和GCN目前应用场景最多的当属推荐了，这里给一个推荐中使用DeepWalk进行效果提升的主流方案。

区别于传统推荐的基于用户和商品之间之间关联和画像特征来进行整合，并设计推荐算法。图神经网络在该场景中，从两个方面提出了新的思路：

针对这两类图均可以使用DeepWalk生成Embedding向量，并进一步用作推荐。

全文从三大部分进行图的技术及应用概述：

图数据库和图计算，这两个分支都是有很多内容值得详细深挖研究的，这里只做了概述性的引入，后续逐步来通过专题进行学习和分享。

投稿 | 机器学习平台团队

编辑 | sea

排版 | sea