我们在上一篇博客中介绍了 “知识图谱是什么”，正如博客中所说，NLP（Natural Language Processing，自然语言处理）是知识图谱的技术上的难点之一。实际上，作为当前人工智能主要的两个研究领域之一，NLP 的难度比 CV （Computer Vision，计算机视觉）大很多。

今天，我们仍然只关注一个问题：自然语言处理能做什么？

推荐一个网站：https://nlpprogress.com/ 。网站收录了几乎所有的 NLP 研究分支，并且跟踪 NLP 在这些任务上的进展（SOTA，state-of-the-art）。网站更新比较及时，至少，当前我们能在部分榜单上看到 XLNET。（北京时间： 20190724）

自然语言处理是当前人工智能领域最重要（也是最难的）的研究方向之一，是计算机如何处理和分析自然语言的科学。实际上，自然语言处理不是一个单独的研究领域，它拥有众多研究分支，从文本输入到图像、音频输入，从词法到语法，再到语义，不同分支之间的差异，可能比 NLP 和其他深度学习方法的差异还大。

简言之，自然语言处理，就是让计算机 ”理解“ 自然语言的研究。关于自然语言处理的研究分支的划分，在阅读大量材料之后，仍然没有找到一个标准和完美的分类方式。这是因为许多 NLP 研究分支，会使用到其他研究分支的技术和方法，层层嵌套，互有重叠。本文尽可能从应用的角度切入，介绍自然语言处理的重要研究分支（我们更多叫自然语言处理任务，NLP Tasks）。

语言模型（Language Model）

语言模型根据前文预测下一个字词（word）是什么。下图就是 N-gram 语言模型的示意图，模型根据前几个词的输入，预测下一个词。

语言模型无疑是自然语言处理中最重要的研究分支。语言模型是一项基准任务，可帮助我们衡量我们理解自然语言的进度。并且，语言模型是很多其他自然语言任务的组成部分，尤其是涉及生成文本或估计文本概率的任务。

实际上我们每天都在使用语言模型。例如，输入法工具会根据你之前输入的内容，自动生成下一个字词或者短语，方便我们的输入。又如，我们使用搜索引擎时，搜索引擎会自动生成常用搜索项。

此外，语言模型可以在手写字符识别，语音识别，语法纠错，甚至自动摘要等多个自然语言处理任务中。我们会在后文涉及部分任务的介绍~

语音识别（ Speech Recognition）

以我们天天使用的 IPhone 为例，不论是打字时候的语音输入功能，还是强大的智能助理 SIRI，当我们使用语音和机器进行交互时，背后就有语音识别算法的支持。从语音输入，到手机上识别出来的文字，语音识别完成了从语音数据到文本数据的转换。

语音作为人类最为重要的交流方式，是很多 AI 产品重要的一环，极大关乎用户体验。例如，开车需要导航的时候，我会更倾向于使用百度地图而不是高德地图（百度看到此条请点赞赏，支持点广告费~），因为驾驶员可以仅用语言与导航进行交互，从而完全解放双手，保证行车安全。高德地图则需要点击一下语音输入的按键（2019年04月 9.02.0 版本已加入 “你好小德” 语音助手功能）。（圆回来了，高德也可以点赞赏~）

机器翻译（Machine Translation）

机器翻译我们这些英语没学好的人的福音【笑脸】。我们将一段特定语言（例如英语）的文字输入，输出我们期望的语言（例如中文），输入输出在语义上保持一致。

很久很久以前，机器翻译是一整套算法的集合。例如1954年，第一个机器翻译系统 “Brain”，将俄语翻译为英语。历史好的同学可能已经发现了，那时正值冷战时期，是冷战促成了机器翻译系统的发展【笑脸】。翻译系统首先保存了一份俄语到英语的字典，然后语言模型将翻译好的字词梳理成更合理的语句。

如今，机器翻译基本使用端到端的训练模型，采用 Encoder 和 Decoder 的组合，直接训练整个神经网络模型。我们甚至可以很轻松的识别多种语言（Multi-Language）的输入。

自动问答/对话（Question Answering/ Dialogue）

虽然这里将两个任务放在了一起，自动问答与对话在技术要求上差别很大。一般来说，自动问答有明确的答案，自动对话更多需要人工评估。

阅读理解就是典型的自动问答问题，计算机在阅读一段文字之后，回答一些与文字相关的问题。下图是 BERT 模型在 SQuAD 2.0 数据集上的一个问题可视化结果。SQuAD 是自动问答领域重要的评估数据集。

自动对话则相对复杂，需要计算机能够在对话中表现出人的反应。在这个研究领域，又有很多细分支，有人在研究如何让计算机对说话人的行为进行分类（Dialogue act classification），有人尝试跟踪对话的状态（Dialogue state tracking），也有人在做生成式的对话机器人（Generative-based Chatbot），能够根据对话生成引人入胜的回应。

情绪分析/文本分类/自然语言推理（Sentiment analysis/ Text Classification/ NLI）

情绪分析是当前应用较广的自然语言处理技术。通常，我们将情绪分析当做一个文本分类问题，对文本的情绪进行定性判断。IMDB 评论（IMDB Reviews）是比较常用的数据集之一，拥有 5w 条用户评论及评分，任务需要根据用户评论判断用户情绪是正向的还是负面的，数据集已事先根据用户评分将评论分为正向（Positive）和负面（Negtive）两类。

文本分类问题的范围更大一些，将句子或者文档分配到特定的类别，通常我们将文本划分到特定的主题类别。AG‘s news 是比较常用的文本分类数据集，要求根据新闻标题和简介判断新闻的类别。

自然语言推理（Natural Language Inference，简称 NLI）是自然语言理解一个重要组成，是检验语义理解的重要评价方式，且研究成果具有高迁移性。自然语言推理判断两个句子（前提句 Premise 和假设句 Hypothesis）在语义上是否存在推理蕴含关系。这也是一个分类任务，任务需要最终给出三分类（Entailment，Contradiction，Neutral）中的一个。Entailment 表示句子存在推理蕴含关系，Contradiction 表示句子存在推理矛盾关系，Neutral 表示两者皆否。

信息检索（Information Retrieval）

搜索引擎就是信息检索很好的例子。信息检索任务需要根据输入的信息，返回与之相关的资源，例如网页、论文、图片等等。我们在图算法中介绍的 TF-IDF 算法，就是一个典型的信息检索评分算法。

关于信息检索，推荐一本书《Introduction to Information Retrieval》（https://nlp.stanford.edu/IR-book/information-retrieval-book.html ），作者 Chris Manning。你也可以在这里（https://web.stanford.edu/class/cs276/ ）找到在线课程。

信息抽取（Information Extraction）

我们在前序博文中介绍过知识图谱（Knowledge Graph），可以说，是信息抽取技术催生了基于互联网信息的大型知识图谱。

信息抽取任务从大量的网页信息中识别出实体（Entities）和它们之间的关系（Relations），获得这些 fact 之后，还要进行实体和关系的消歧与合并。所以，信息抽取是一系列的任务的集合，包括命名实体识别（Named Entity Recognition），词性标注（Part-Of-Speech tagging），指代消解（Coreference Resolution），关系抽取（Relationship Extraction），时间抽取（Event Extraction）等等。

生成类任务（Generation）

这个名字你可能会很陌生，然而生成类算法离我们并不遥远。自动摘要（Automatic Summarization）是一个典型的任务，根据输入的一段文字，生成一段相对简短的摘要。

此外，其他文本生成类任务例如生成歌曲、诗歌，例如根据图片自动生成描述文字（image caption），例如对输入文本进行风格改写等等。对了，语言模型也是生成类任务的一部分。

句法规则相关（Tagging/ Chunking/ Syntax/ Parsing）

句法规则是语言学较为关注的任务，也是很多其他任务的组成部分。句法规则关注如何把字词和短语组合成句子的规则。上小结提到的词性标注（POS tagging）就是典型的例子。

文本分块（chunking，一般也叫浅语法，Shallow syntax）关注文本的句法结构。

Constituency parsing，从句子中抽取分析树：

Dependency parsing 分析句子中的依赖关系：

总结

今天的总结，没有 Reference 了，推荐一些材料或课程作为 NLP 入门吧~

1. 《数学之美》，吴军，2012。本书鲜有公式，更多地从数学趣味的角度讲解计算机技术，篇幅中不少涉及了自然语言处理的内容，对小白是一个很好的入门
2. CS224n: Natural Language Processing with Deep Learning，Stanford Winter 2019，http://web.stanford.edu/class/cs224n/ 。斯坦福在自然语言处理的地位是不言而喻的，斯坦福的公开课是一个非常好的系统化的课程
3. 《Speech and Language Processing》，Dan Jurafsky & James H. Martin，https://web.stanford.edu/~jurafsky/slp3/ 。最经典的自然语言处理课本，截止2019年7月25日，本书第三版还在草稿中，你可以从这个链接找到最新的章节

我们可能已经了解了很多机器学习和深度学习的算法，但是那似乎离我们心中的 “人工智能” 还很遥远。我们训练的模型，更像是一个具有统计知识的机器，从关联和概率的角度出发，试图在描述世界背后的 “真理”。然而，我们更希望的是，像人一样，具有分析和推理能力的机器智能。如果你问我，哪一种形式最接近我心中的 “人工智能”，我会说：知识图谱。

今天，就让我们来解决一个问题：什么是知识图谱？

知识图谱 “考古史”

2012 年 5 月 17 日，Google 正式提出了知识图谱（Knowledge Graph）的概念，其初衷是为了优化搜索引擎返回的结果，增强用户搜索质量及体验。

假设我们想知道 “王健林的儿子” 是谁，百度或谷歌一下，搜索引擎会准确返回王思聪的信息，说明搜索引擎理解了用户的意图，知道我们要找 “王思聪”，而不是仅仅返回关键词为 “王健林的儿子” 的网页：

编者按：知乎文章《为什么需要知识图谱？什么是知识图谱？——KG的前世今生》是一个很好的入门文章，感兴趣可以进一步阅读：https://zhuanlan.zhihu.com/p/31726910 。《知识图谱的技术与应用（18版）》是一个更为全面和详细的介绍，https://zhuanlan.zhihu.com/p/38056557 。

实际上，知识图谱并不是一个全新的概念，早在 2006 年就有文献提出了语义网（Semantic Network）的概念，呼吁推广、完善使用本体模型来形式化表达数据中的隐含语义，RDF（resource description framework，资源描述框架）模式和 OWL（Web ontology language，万维网本体语言）就是基于上述目的产生的。用电子科技大学徐增林教授的论文原文来说：

知识图谱技术的出现正是基于以上相关研究，是对语义网标准与技术的一次扬弃与升华。

目前，随着智能信息服务应用的不断发展，知识图谱已广泛应用于智能搜索，智能问答，个性化推荐等领域。

知识图谱定义

知识图谱，本质上，是一种揭示实体之间关系的语义网络。

如果你看过网络综艺《奇葩说》第五季第17期：你是否支持全人类一秒知识共享，你也许会被辩手陈铭的辩论印象深刻。他在节目中区分了信息和知识两个概念：

• 信息是指外部的客观事实。举例：这里有一瓶水，它现在是7°。
• 知识是对外部客观规律的归纳和总结。举例：水在零度的时候会结冰。

“客观规律的归纳和总结” 似乎有些难以实现。Quora 上有另一种经典的解读，区分 “信息” 和 “知识” 。

有了这样的参考，我们就很容易理解，在信息的基础上，建立实体之间的联系，就能行成 “知识”。当然，我认为叫事实（Fact）更为合适。换句话说，知识图谱是由一条条知识组成，每条知识表示为一个SPO三元组(Subject-Predicate-Object)。

知识图谱实际上就是如此工作的。曾经知识图谱非常流行自顶向下(top-down)的构建方式。自顶向下指的是先为知识图谱定义好本体与数据模式，再将实体加入到知识库。该构建方式需要利用一些现有的结构化知识库作为其基础知识库，例如 Freebase 项目就是采用这种方式，它的绝大部分数据是从维基百科中得到的。

然而目前，大多数知识图谱都采用自底向上(bottom-up)的构建方式。自底向上指的是从一些开放链接数据（也就是 “信息”）中提取出实体，选择其中置信度较高的加入到知识库，再构建实体与实体之间的联系。

知识图谱的体系架构

知识图谱的架构主要包括自身的逻辑结构以及体系架构，

知识图谱在逻辑结构上可分为模式层与数据层两个层次，数据层主要是由一系列的事实组成，而知识将以事实为单位进行存储。如果用（实体1，关系，实体2）、（实体、属性，属性值）这样的三元组来表达事实，可选择图数据库作为存储介质，例如开源的 Neo4j、Twitter 的 FlockDB、JanusGraph 等。模式层构建在数据层之上，主要是通过本体库来规范数据层的一系列事实表达。本体是结构化知识库的概念模板，通过本体库而形成的知识库不仅层次结构较强，并且冗余程度较小。

知识图谱的体系架构是指其构建模式的结构，如下图所示：

大规模知识库的构建与应用需要多种智能信息处理技术的支持。通过知识抽取技术，可以从一些公开的半结构化、非结构化的数据中提取出实体、关系、属性等知识要素。通过知识融合，可消除实体、关系、属性等指称项与事实对象之间的歧义，形成高质量的知识库。知识推理则是在已有的知识库基础上进一步挖掘隐含的知识，从而丰富、扩展知识库。分布式的知识表示形成的综合向量对知识库的构建、推理、融合以及应用均具有重要的意义。

知识抽取

知识抽取主要是面向开放的链接数据，通过自动化的技术抽取出可用的知识单元，知识单元主要包括实体(概念的外延)、关系以及属性3个知识要素，并以此为基础，形成一系列高质量的事实表达，为上层模式层的构建奠定基础。知识抽取有三个主要工作：

• 实体抽取：在技术上我们更多称为 NER（named entity recognition，命名实体识别），指的是从原始语料中自动识别出命名实体。由于实体是知识图谱中的最基本元素，其抽取的完整性、准确、召回率等将直接影响到知识库的质量。因此，实体抽取是知识抽取中最为基础与关键的一步；
• 关系抽取：目标是解决实体间语义链接的问题，早期的关系抽取主要是通过人工构造语义规则以及模板的方法识别实体关系。随后，实体间的关系模型逐渐替代了人工预定义的语法与规则。
• 属性抽取：属性抽取主要是针对实体而言的，通过属性可形成对实体的完整勾画。由于实体的属性可以看成是实体与属性值之间的一种名称性关系，因此可以将实体属性的抽取问题转换为关系抽取问题。

知识表示

近年来，以深度学习为代表的表示学习技术取得了重要的进展，可以将实体的语义信息表示为稠密低维实值向量，进而在低维空间中高效计算实体、关系及其之间的复杂语义关联，对知识库的构建、推理、融合以及应用均具有重要的意义。一直在关注我们公众号的朋友肯定阅读过上一篇博文，graph embedding 就是一种表示学习。

知识融合

由于知识图谱中的知识来源广泛，存在知识质量良莠不齐、来自不同数据源的知识重复、知识间的关联不够明确等问题，所以必须要进行知识的融合。知识融合是高层次的知识组织，使来自不同知识源的知识在同一框架规范下进行异构数据整合、消歧、加工、推理验证、更新等步骤，达到数据、信息、方法、经验以及人的思想的融合，形成高质量的知识库。

其中，知识更新是一个重要的部分。人类的认知能力、知识储备以及业务需求都会随时间而不断递增。因此，知识图谱的内容也需要与时俱进，不论是通用知识图谱，还是行业知识图谱，它们都需要不断地迭代更新，扩展现有的知识，增加新的知识。

知识图谱应用

知识图谱为互联网上海量、异构、动态的大数据表达、组织、管理以及利用提供了一种更为有效的方式，使得网络的智能化水平更高，更加接近于人类的认知思维。

智能搜索

如同我们在开篇介绍的例子，用户的查询输入后，搜索引擎不仅仅去寻找关键词，而是首先进行语义的理解。比如，对查询分词之后，对查询的描述进行归一化，从而能够与知识库进行匹配。查询的返回结果，是搜索引擎在知识库中检索相应的实体之后，给出的完整知识体系。

深度问答

问答系统是信息检索系统的一种高级形式，能够以准确简洁的自然语言为用户提供问题的解答。多数问答系统更倾向于将给定的问题分解为多个小的问题，然后逐一去知识库中抽取匹配的答案，并自动检测其在时间与空间上的吻合度等，最后将答案进行合并，以直观的方式展现给用户。

苹果的智能语音助手 Siri 能够为用户提供回答、介绍等服务，就是引入了知识图谱的结果。知识图谱使得机器与人的交互，看起来更智能。

社交网络

Facebook 于 2013 年推出了 Graph Search 产品，其核心技术就是通过知识图谱将人、
地点、事情等联系在一起，并以直观的方式支持精确的自然语言查询，例如输入查询式：“我朋友喜欢的餐厅”“住在纽约并且喜欢篮球和中国电影的朋友”等，知识图谱会帮助用户在庞大的社交网络中
找到与自己最具相关性的人、照片、地点和兴趣等。Graph Search 提供的上述服务贴近个人的生活，满足了用户发现知识以及寻找最具相关性的人的需求。

垂直行业应用

从领域上来说，知识图谱通常分为通用知识图谱和特定领域知识图谱。

在金融、医疗、电商等很多垂直领域，知识图谱正在带来更好的领域知识、更低金融风险、更完美的购物体验。更多的，如教育科研行业、图书馆、证券业、生物医疗以及需要进行大数据分析的一些行业。这些行业对整合性和关联性的资源需求迫切，知识图谱可以为其提供更加精确规范的行业数据以及丰富的表达，帮助用户更加便捷地获取行业知识。

总结

从技术来说，知识图谱的难点在于 NLP，因为我们需要机器能够理解海量的文字信息。但在工程上，我们面临更多的问题，来源于知识的获取，知识的融合。搜索领域能做的越来越好，是因为有成千上万（成百万上亿）的用户，用户在查询的过程中，实际也在优化搜索结果，这也是为什么百度的英文搜索不可能超过 Google，因为没有那么多英文用户。知识图谱也是同样的道理，如果将用户的行为应用在知识图谱的更新上，才能走的更远。

知识图谱肯定不是人工智能的最终答案，但知识图谱这种综合各项计算机技术的应用方向，一定是人工智能未来的形式之一。

References

1. 知识图谱技术综述，徐增林等，电子科技大学学报，http://ir.sdu.edu.cn/~zhuminchen/KG/xuzenglin2016.pdf
2. 知乎文章：为什么需要知识图谱？什么是知识图谱？——KG的前世今生，作者：SimmerChan，https://zhuanlan.zhihu.com/p/31726910
3. 知乎文章：把知识变成图谱一共需要花几步？89页全网最全清华知识图谱报告，作者：智东西，https://zhuanlan.zhihu.com/p/56903119
4. 知乎文章：知识图谱-从入门到跑路（1），作者：cavities，https://zhuanlan.zhihu.com/p/62824358
5. 知乎答案：知识图谱的构建流程？，作者：Hooke，https://www.zhihu.com/question/299907037/answer/519394870
6. 知乎答案：知识图谱的构建流程？ ，作者： 陈运文，https://www.zhihu.com/question/299907037/answer/537482952
7. 知识图谱的应用 - 李文哲的文章 - 知乎，https://zhuanlan.zhihu.com/p/20394260
8. 鲍捷：知识图谱在金融领域的发展与应用 - 鲍捷的文章 - 知乎，https://zhuanlan.zhihu.com/p/27995887
9. 知识图谱的技术与应用（18版） - 李文哲的文章 - 知乎，https://zhuanlan.zhihu.com/p/38056557

Embedding 是深度学习十分重要的“基本操作”，不论是 NLP，搜索排序，还是推荐系统，Embedding 都扮演着重要的角色。本文借由 Graph Embedding 切入，不用一个公式，带领大家从 Word2Vec 到 DeepWalk，再到 Node2Vec，你也能成为算法大神~

之前的博文，给大家介绍了很多图算法，它们看起来很酷炫，却不知道如何使用？本期我们关注 Graph Embedding，不但可以“实践”很多图算法，更可以快速了解 Embedding 在深度学习推荐系统中的使用，从 Word2Vec 到 DeepWalk，从 LINE 到 Node2Vec，希望能收获满满~ 另外，推荐一个知乎专栏：王喆的机器学习笔记，关于 Graph Embedding，专栏用了几篇文章相对系统地进行了说明，阅读之后受益很多。

本文不含公式，需要基本的图算法基础，包括 Random Walk、BFS、DFS 等。如果这些名词对你来说还很陌生，建议阅读前序博文。

Embedding is all you need

允许我做一次标题党，Embedding 必须是深度学习中的“基本操作”。不论是 NLP（Normal Language Processing，自然语言处理），搜索排序，还是推荐系统，或者 CTR （Click-Through-Rate，点击通过率）模型，Embedding 都扮演着不可或缺的角色。

什么是 Embedding？

Embedding 在数学上表示一个映射关系， F: X -> Y， 也就是一个函数。函数具有两个性质：injective 和 structure-preserving。Injective，即我们所说的单射函数，对于每个 Y 只有唯一的 X 对应，反之亦然；structure-preserving，结构保存，比如在 X 所属的空间上 X1 < X2，那么映射后在 Y 所属空间上 Y1 < Y2。

简单点说，深度学习中，Embedding 特指用一个低维度向量表示一个实体，可以是一个词（Word2Vec），可以是一个物品（Item2Vec），亦或者网络关系中的节点（Graph Embedding）。

Embedding 所获得的低维度向量具有一些特殊的性质。如下图，我们使用 Word2Vec 将单词映射（word embedding）到新的向量空间，获得单词的新的表达（word representation）。我们能从图中很容易得出：Embedding(Moscow) - Embedding(Russia) ≈ Embedding(Tokyo) - Embedding(Japan)，说明 Embedding 之后向量可以进行计算。并且，Embedding 之后，距离相近的向量对应的实体有相近的含义，比如 Embedding (Russia) 和 Embedding (Japan) 之间的距离就会很接近，但 Embedding (Russia) 和 Embedding (Tokyo) 的距离就会远一些。

可见，Embedding 拥有很多优点：得到的向量表达维度更低，并且表达了实体间内在的关系。下面以商品推荐为例，进一步解释。假设我们有千万级别的商品，我们通常使用 One-Hot 编码数字化地代表，则能够得到千万个向量，每个向量代表一种商品，并且每个向量都拥有千万级别的维度。向量只有一位是 1，其他位均为 0，信息量十分“稀疏”。此时，任何商品之间的距离都是一样的。并且，由于深度学习的特点以及工程方面的原因，深度学习并不善于处理稀疏特征的向量。相反，Embedding 之后，千万级别的维度可以缩小到自定义的维度大小（例如1000）。变成向量之后的商品，可以直接通过计算向量相似度，寻找相似的商品，直接推荐给客户。

这些优点带来的好处是显著的，Embedding 主要的三个应用方向：

• 在深度学习网络中使用 Embedding 层，将高维稀疏特征向量转换成低维稠密特征向量，从而减少后续模型参数量，后续模型可以是深度学习模型，或者传统的机器学习模型；
• 作为预训练技术，直接使用别人训练好的 Embedding 向量，与其他特征向量一同输入后续模型进行训练，例如 Word2Vec；
• 通过计算用户和物品的 Embedding 相似度，Embedding 可以直接作为推荐系统或计算广告系统的召回层或者召回方法之一，例如 Youtube 推荐系统。

什么是 Graph Embedding？

Graph Embedding 用低维、稠密、实值的向量表示网络中的节点。目前，Graph Embedding 已经是推荐系统、计算广告领域非常流行的做法，并且在实践后取得了非常不错的线上效果。

为什么能有这样的效果呢？

我们很容易理解（如果有困难，可以尝试阅读下一章节），Word2Vec 通过序列（sequence）式的样本：句子，学习单词的真实含义。仿照 Word2Vec 思想而生的 Item2Vec 也通过商品的组合去生成商品的 Embedding，这里商品的组合也是序列式的，我们可以称他们为“Sequence Embedding”。然而，在更多场景下，数据对象之间更多以图/网络的结构呈现。例如下图，由淘宝用户行为数据生成的物品关系图（Item Graph）：

从上图的例子中，我们已经能触碰到一些 Graph Embedding 的本质。Graph Embedding 之所以能好于 “Sequence Embedding”，是因为 Graph Embedding 能够生成一些“不存在”的序列。例如，上图数据中没有这样的用户行为数据：B-E-F、D-E-C等等。但是在物品关系图中，我们有机会生成这样的序列。

Graph Embedding 常见的同义词

除了 Graph Embedding，我们还会经常看到 Network Embedding、Node Embedding、Graph Representation 或者 Network Representation Learning，这些名词可能在定义上会有差异，大部分时间，我们可以在特定场合将他们视为同义词。

下面就让我们从 Word2Vec 开始，了解 Graph Embedding 吧~

Embedding 流行起点：Word2Vec

Google 的 Tomas Mikolov 在 2013 年的两篇论文标志着 Word2Vec 的诞生，论文提出了 CBOW 和 Skip-gram 两种 Word2Vec 模型结构。下图是两种模型结构的架构图：

CBOW 使用目标词周边的词来预测目标词，Skip-gram 使用目标词预测周边的词。两种架构差别不大，我们在 Embedding 中更多使用Skip-gram。图中输入输出均使用词向量，词向量初始随机赋值，随着预测任务的进行，词向量在迭代中慢慢优化，使得预测任务指标越来越好，而我们最终需要的是训练好的词向量。两种模型的训练数据均使用标准的自然语言语料，利用词与词的关系（也就是语料序列）去训练词向量。

也就是说，只要我们找到词与词之间的关联关系，就能通过 Skip-gram 方法训练词的向量。

Word2Vec 有很多技术细节，例如使用 Hierarchical Softmax（层序 Softmax） 和 Negative Sampling 来减少由于词汇空间过大带来的计算量，例如优化目标的设置等等等等。由于与主旨无关，本文不作介绍。（事实是网上可以找到太多博文，毫无重写一份的激情……）

Graph Embedding 早期技术：DeepWalk

Word2Vec 诞生之后，Embedding 的思想迅速从 NLP 领域扩散到几乎所有的机器学习领域。我们可以对语料序列中的词进行 Embedding，那么自然用户购买序列中的商品，或者用户观看序列中的电影，都可以进行 Embedding。这就是 Item2Vec。

回顾上一节的重点：是词与词的关联关系实现了 Embedding 的过程。序列（sequence）是一种“一维”的关系，而图（graph）是一种“二维”的关系，同样可以进行 Embedding。然而，我们目前能进行 Embedding 的 “工具” 只有 Skip-gram，只能处理序列这样一维的关系输入。因此，我们需要在二维关系上进行 “采样”，采样的过程可以使用随机游走算法（Random Walk，我们已在前序博文中进行了介绍）。

DeepWalk 就是 Random Walk 与 Skip-gram 的组合。上图是 DeepWalk 算法伪代码，核心步骤 6 和 7 就是 Random Walk 与 Skip-gram。下图是算法流程示意：

Random Walk 负责对图进行采样，获得图中节点与节点的共现关系，Skip-gram 从关系（也就是采样的序列）中训练节点的 Embedding 向量。

上述结果中，比较临近的节点再 Embedding 空间更为接近，且结构更为相似的节点，距离也更近。这就是网络节点的同质性（homophily）和结构性（structural equivalence），进一步的说明会在下一小节。

所以，DeepWalk 以 Random Walk 的方式从网络中生成序列，进而转换成传统 word2vec 的方法生成 Embedding 向量。该算法可以视为 Graph Embedding 的 baseline 方法，用极小的代价完成从 word2vec 到 graph embedding 的转换和工程尝试。

DeepWalk 的改进：从 LINE 到 Node2Vec

DeepWalk 之后，比较重要的工作是微软亚洲研究院在 2015 年发布的 LINE（Large-scale Information Network Embedding）。阅读到这里，我们已经可以知晓，在网络上 “相似” 的节点，最终会拥有相似的 Embedding 向量。在 LINE 的论文中，定义了两种相似：

First-order proximity（1 阶相似度）：用于描述图中成对顶点之间的局部相似度，形式化描述为若节点之间存在直连边，则边的权重即为两个顶点的相似度，若不存在直连边，则 1 阶相似度为0。 如下图，节点 6 和 7 之间存在直连边，且边权较大，则认为两者相似且 1 阶相似度较高，而 5 和 6 之间不存在直连边，则两者间 1 阶相似度为 0。也就是我们上一小节所说的同质性相似。

Second-order proximity（2 阶相似度）：仅有1阶相似度就够了吗？显然不够，如下图，虽然节点 5 和 6 之间不存在直连边，但是他们有很多相同的相邻节点 （1,2,3,4），这其实也可以表明5和6是相似的，而 2 阶相似度就是用来描述这种关系的。 形式化定义为，令表示顶点 u 与所有其他顶点间的1阶相似度，则 u 与 v 的2阶相似度可以通过 p_u 和 p_v 的相似度表示。若u与v之间不存在相同的邻居顶点，则2阶相似度为0。也就是我们上一小节所说的结构性相似。

相比 DeepWalk 纯粹随机游走的序列生成方式，LINE 可以应用于有向图、无向图以及边有权重的网络，并通过将一阶、二阶的邻近关系引入目标函数，能够使最终学出的 node embedding 的分布更为均衡平滑，避免 DeepWalk 容易使 node embedding 聚集的情况发生。下图是论文中的结果对比：

从图中可以看出，LINE 的效果最好，DeepWalk 对不同颜色的点分得也不错，但是图形中部很多点都挤在一块，而这些点都是出度很大的点，文章提了一句说对于这种点的处理 DeepWalk 会产生很大噪音，但没有详细对此分析。论文还指出，DeepWalk 利用随机游走去捕获邻近关系，更像是深度优先搜索；而LINE的方式更像是广度优先搜索，相对而言更合理。上图中的 GF 代表 graph factorization，本文不作介绍，感兴趣的话可以自行 Google。

在 DeepWalk 和 LINE 的基础之上，斯坦福大学在 2016 年发布了 Node2Vec。算法不但关注了同质性和结构性的相似，更可以在两者之间进行权衡。如何做到的呢？让我们先来回顾，什么是深度优先（DFS），什么是广度优先（BFS）。

那么，节点 u 与其相连的节点 s1、s2、s3、s4 的 embedding 表达应该是接近的，这是同质性相似。节点 u 和节点 s6 都是各自局域网络的中心节点，结构上相似，其 embedding 的表达也应该近似，这是结构性相似。

如果我们在随机游走的过程中以 BFS 为主，例如获得序列 u-s1-s2-s3，训练出来的 Embedding 向量更多反映了结构性的相似；如果随机游走以 DFS 为主，例如获得序列 u-s4-s5-s6 ，则训练出来的 Embedding 向量，更多反应同质性的相似。至于为什么，大家可以先自己思考。

那 Node2Vec 是如何权衡同质性和结构性相似的呢？换句话说，Node2Vec 如何参数化控制随机游走是更倾向 BFS 还是 DFS 呢？下图足以说明：

上图是 Node2Vec 算法中 Random Walk 的说明，假设我们随机游走到了节点 V，下一步有不同的概率到达临近的节点。假设节点 t 是访问节点 V 之前的节点，设置参数 p 为 “返回参数”（return parameter），控制节点 V 返回到节点 t 的概率，p 越大，从节点 V 返回节点 t 的概率越小。设置参数 q 为 “进出参数”（in-out parameter），控制节点 V 去往节点 x2、x3 的概率，q > 1 时，节点 V 之后更倾向于访问前序节点 t 的共同邻居，q < 1 时，节点 V 之后，更不倾向访问前序节点 t 的邻居。节点 x1 显得有点特殊，因为节点 x1 同时是节点 t 和 V 的邻居，我们设置权重为 1。通过修改参数 p 和 q，我们就能控制 Random Walk 采样过程，是更倾向 DFS 还是 BFS。

上图是 Node2Vec 的结果，同种颜色代表 Embedding 向量比较接近，节点比较相似。图中上部分参数 p = 1，q = 0.5，结果表现为同质性相似的节点更为接近。下部分参数 p = 1，q = 2，结果表现为结构性相似的节点更为接近。

Node2Vec 所体现的网络的同质性和结构性在推荐系统中也是可以被很直观的解释的。同质性相同的物品很可能是同品类、同属性、或者经常被一同购买的物品，而结构性相同的物品则是各品类的爆款、各品类的最佳凑单商品等拥有类似趋势或者结构性属性的物品。毫无疑问，二者在推荐系统中都是非常重要的特征表达。由于 Node2Vec 的这种灵活性，以及发掘不同特征的能力，甚至可以把不同 Node2Vec 生成的 embedding 融合共同输入后续深度学习网络，以保留物品的不同特征信息。

Graph Embedding 最佳实践：EGES

我们介绍了一堆概念和算法，那么实际应用，效果如何呢？

2018 年，阿里巴巴发表论文，提出了能够落地的 EGES（Enhanced Graph Embedding with Side Information）算法，在约十亿的用户和二十亿的商品这个数据量，进行了 Graph Embedding。其基本思想是 Embedding 过程中引入带权重的补充信息（Side Information），从而解决冷启动的问题。让我们赶紧来看下流程图：

步骤如下：

1. 首先，我们拥有上亿用户的行为数据，不同的用户，在每个 Session 中，访问了一系列商品，例如用户 u2 两次访问淘宝，第一次查看了两个商品 B-E，第二次产看了三个商品 D-E-F；
2. 然后，通过用户的行为数据，我们可以建立一个商品图（Item Graph），可以看出，物品A，B之间的边产生的原因就是因为用户U1先后购买了物品A和物品B，所以产生了一条由A到B的有向边。如果后续产生了多条相同的有向边，则有向边的权重被加强。在将所有用户行为序列都转换成物品相关图中的边之后，全局的物品相关图就建立起来了。
3. 接着，通过 Random Walk 对图进行采样，重新获得商品序列；
4. 最后，使用 Skip-gram 模型进行 Embedding 。

仔细的读者已经能够发现，如果出现了新的商品怎么办，如果有个商品从没有被人浏览过怎么办？没有关系，就意味着在图上是孤立的点，也意味着，无法获得 Embedding，这就是冷启动的问题。淘宝商城每个小时就有百万级别的商品上线，这些商品该如何推荐呢？

答案其实已在上面给出，新上线的商品虽然没有被人浏览，但是他们也有类别，品牌，所在城市，性别，风格等等各种属性，也就是 Side Information，我们可以通过这些属性建立商品间的关联。下图是一个简单的例子：

如何实现呢？其实并不难。如下图，在训练 Embedding 的时候，不同的补充信息各自经过 Embedding，加权平均汇总到隐含层之后，再用来预测序列中的目标商品。

论文对模型性能进行了 A/B Test，在 2017 年 9 月的一周里，EGES 最终比 Base 模型 CTR 高了约 0.5 个百分点。

阿里的 EGES 并没有过于复杂的理论创新，但给出一个工程性的结合多种 Embedding 的方法，可好解决了冷启动问题，是实用性极强的 Embedding 方法。

结论

本文一路小跑，终于穿过各种概念，各种算法，不用一个公式，“友好” 地介绍了 Graph Embedding 技术。作为深度学习推荐系统的最新流行，Graph Embedding 肯定会有新的发展。除了本文涉及的算法，还有许多：Laplacian Eigenmaps，Structure Preserving Embedding (SPE)，Graph Factorization (GF)，Structural deep network embedding (SDNE) 等等。学海无涯，祝你航行愉快。

References

1. 【DeepWalk】DeepWalk- Online Learning of Social Representations，https://arxiv.org/pdf/1403.6652
2. 【LINE】LINE - Large-scale Information Network Embedding，微软 2015，https://arxiv.org/pdf/1503.03578
3. 【Node2vec】Node2vec - Scalable Feature Learning for Networks，斯坦福 2016，https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5108654/
4. 【EGES】Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba，Alibaba 2018，https://arxiv.org/pdf/1803.02349.pdf
5. 【Word2Vec】Efficient Estimation of Word Representations in Vector Space，Google 2013，https://arxiv.org/pdf/1301.3781
6. 【Word2Vec】Distributed Representations of Words and Phrases and their Compositionality，Google 2013，https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf
7. 知乎答案：有谁可以解释下 word embedding?，作者：寒蝉鸣泣，https://www.zhihu.com/question/32275069/answer/80188672
8. 知乎文章：Embedding 从入门到专家必读的十篇论文，作者：王喆，https://zhuanlan.zhihu.com/p/58805184
9. 知乎文章：万物皆 Embedding，从经典的 word2vec 到深度学习基本操作 item2vec，作者：王喆，https://zhuanlan.zhihu.com/p/53194407
10. 知乎文章：深度学习中不得不学的 Graph Embedding方法，作者：王喆，https://zhuanlan.zhihu.com/p/64200072
11. 知乎文章：关于 Node2vec 算法中 Graph Embedding 同质性和结构性的进一步探讨，作者：王喆，https://zhuanlan.zhihu.com/p/64756917
12. 知乎答案：Graph Embedding 和 Network representation learning一样吗？，作者：张小磊，https://www.zhihu.com/question/292232005/answer/480368644
13. 知乎文章：【Graph Embedding】DeepWalk：算法原理，实现和应用，作者：浅梦，https://zhuanlan.zhihu.com/p/56380812
14. 知乎文章：【Graph Embedding】LINE：算法原理，实现和应用，作者：浅梦，https://zhuanlan.zhihu.com/p/56478167
15. 知乎文章：Graph Embedding：从DeepWalk 到 SDNE，作者：羽刻，https://zhuanlan.zhihu.com/p/33732033

编者按：本文作者 Meng Qi，来自 Teradata Data Science 团队，牛津大学统计系 2013 届研究生。本期博文，就让我们了解一下 R 语言如何进行数据可视化。当统计学家最爱的 R 遇上 “A graph is worth a thousand words” 的可视化工具，会发生什么呢？

“The simple graph has brought more information to the data analyst’s mind than any other device.” — John Tukey

数据可视化在学术界和工业界都有广泛的应用——除了许多论文里的实验数据图表外，企业的KPI报表、股市的K线图、制造业的传感器数据监测、航空公司的上客监控，包括每年大家喜（ji）闻（si）乐（ren）见（le）的春运大数据，都是可视化的应用。数据可视化可以让我们更直观地从数据中获取信息。

英国新闻巨头BBC有一个数据新闻团队（Data Journalism），专注于“从大量数据中发现值得注意的事实”。近期，该团队分享了他们基于R开发的工具包bbplot，使大家能够简单方便地绘制出达到出版标准的图表。专业化的绘图工具正在被越来越多的行业所使用。本期博文，就让我们了解一下R语言如何进行数据可视化。

R 的绘图系统

R语言有两大绘图系统：基础绘图系统和Grid绘图系统，两者相互独立。基础绘图系统直接在图形设备上画图；而Grid系统将界面分成矩形区域（viewport），每个区域有自己独立的坐标体系，并且相互可以嵌套，使得Grid系统可以画出更复杂的图形。

用过R的朋友们知道，R的功能是通过一个个库（package）——也就是我们常说的工具包实现的。基础绘图系统依赖于graphics包。基于Grid系统的包有grid，lattice，ggplot2等。grid包仅提供低级的绘图功能（如点、线等），并不能画出完整的图形。更高级的图形是两个主流绘图包lattice和ggplot2来实现。

让我们来关注最常用的三个包：graphics， lattice、ggplot2。

graphics包

基础绘图包graphics，在安装R时默认安装，启动R时默认加载。它囊括了常用的标准统计图形，如条形图，饼图，直方图，箱线图，散点图等。在R里运行：

1

demo(graphics)

会给出一些常用图形的样例（如下图），及生成这些图形的代码。

lattice包

在使用之前，需要先加载lattice包。lattice包提供了大量新的绘图类型、默认颜色、图形排版等优化。同时，它还支持“条件多框图”—— 如下图，在不同月份（Month），观察臭氧浓度（Ozone）与气温（Temp）之间的关系。这里，“月份”就是我们所说的条件，条件多框图可以让我们更清楚地看到Ozone与Temp的关系是否受月份的影响而发生变化。

1
2
3
4
5

library(lattice)
xyplot(Temp ~ Ozone |factor(Month),
	data = airquality,
	main="Temp(F) vs Ozone(ppb) by Month",
	layout=c(5,1))

ggplot2包

ggplot2由Hadley Wickham根据Grammar of Graphics（图形的语法）中提出的理论而开发。它将绘图视为一种映射，即从数学空间映射到图形元素空间。它的绘图方式类似于我们平时生活中画图，先创建一个画布，然后一层层往上叠加信息。ggplot2是R中最常用到同时也是功能最强大的绘图包（Python中也有了ggplot2的实现——plotnine，你只需要对R语言中的ggplot2代码稍作修改，就能直接在Python中运行）。

我们用ggplot2中自带的数据diamonds为例来描述绘图过程：绘制钻石克拉数（carat）与价格（price）的关系，同时将纯度（clarity）作为颜色变量。在代码中，carat, price, clarity分别被映射到了x轴，轴y及color。

1
2
3

library(ggplot2)
ggplot(data=diamonds, mappings=aes(x=carat, y=price))+
	geom_point(aes(color=clarity))

如果我们想在图中增添统计变换，如两变量关系的平滑曲线，仅需增加一行代码

1
2

ggplot(data=diamonds, mappings=aes(x=carat, y=price))+
	geom_point(aes(color=clarity))+stat_smooth()

同样的，如果我们想分析在不同切工（cut）下克拉数与价格的关系（类似于lattice中的条件多框图），也是一行代码的工作量

1
2
3

ggplot(data=diamonds, mappings=aes(x=carat, y=price))+
	geom_point(aes(color=clarity))+
	stat_smooth()+facet_wrap(~cut)

ggplo2的基本概念有：

• 数据(data)和映射(mapping)
• 几何对象(geometric)
• 标度(scale)
• 统计变换(statistics)
• 坐标系统(coordinate)
• 分面(facet)

使用ggplot2绘图的过程就是选择合适的几何对象、图形属性、标度、统计变换、坐标系统和分面等来充分展现数据中所含有的信息的过程。ggplot2的强大之处就在于它的灵活性，通过不同图层的叠加可以做出非常有意思的图形。

R Graph Gallery

除了上述提到的三个常用绘图包，R还有很多其他图形绘制的工具，如绘制3D图形的plot3d，rgl，绘制地图的ggmap，leaflet，交互式可视化plotly等等。在这里，我们介绍一个神奇的网站 THE R GRAPH GALLERY (https://www.r-graph-gallery.com)。这个网站为我们提供了平时常用的8大类46种共计数146个（日期：2019-05-13）可视化样例及代码，及他们使用的工具包。

例如，点击Sankey diagram（倒数第二行最后一个）的图标，会进入如下的界面。可以看到NetworkD3这个包能用来绘制Sankey图。

点击图形下的链接，网站会给出该图形的详细信息及实现的代码

THE R GRAPH GALLERY 网站不仅提供各类统计图形的R的实现方式，同时也在收录相对应的Python的实现，是学习可视化非常好的资源。

R Shiny

在我们的分析工作中，有时不仅要展示模型结果，还需要把分析历程展示给听众；同时，听众也希望能够参与到分析探索中来。这就需要我们将不同部分的分析 —— 如数据探索，模型构建及评估的过程整合到一起，同时增添可交互性。

Shiny （http://shiny.rstudio.com/）是由RStudio开发的一个开源的 R 包，它为使用 R 构建 Web 应用提供了一个有力的 Web 框架。使用Shiny，我们可以用R语言轻松开发交互式web应用。在Shiny的官网上给出了一些App的应用案例：

我们通过官网上Kmeans example的例子（Demo）来看一看Shiny App的基本功能。这个例子中用的是R自带的鸢尾花（iris）数据，用过R（或者Python）的朋友应该对这个数据非常熟悉。数据里包含了花萼长度(Sepal.Length)，花萼宽度(Sepal.Width)，花瓣长度(Pepal. Length)，花瓣宽度(Pepal.Width)及花的品种(Species)信息。

在Demo中假设品种未知，通过其它变量将鸢尾花样本分群。默认选项是将样本按照Sepal.Length和 Sepal.Width分成3群。

通过Demo左侧的工具栏，我们可以选择不同的分群变量（Pepal. Length，Pepal.Width）及分群个数（2），来观察不同的分群效果

实现这样一个Shiny App的需要两部分脚本：用户交互（shinyUI）及服务器（shinyServer）脚本。

• shinyUI部分控制页面的布置和展示。一方面，在这里可以定义一系列的小工具，如滑动条（sliderInput），选项卡（radioButtons），输入框（numericInput）等来接收用户传入的参数，储存在input变量里。另一方面，它接收shinyServer传来的output变量，并根据用户的定义把它展示在前端。

• shinyServer生成所要展示的结果。它从shinyUI读取input变量，将其作为参数进行模型计算或图形绘制，然后将结果储存在output变量里，传给shinyUI前端。

总结来说，shinyUI用于根据用户的输入生成input，同时展示output结果，shinyServer接收input参数，计算生成output。有兴趣的朋友可以在Shiny的官网找到详细的培训教程。

总结

在本文，我们介绍了一些R的常用绘图包以及学习资源：graphics通常用于快速基本的分析绘图，个性化的图形建议使用ggplot2来实现。R Graph Gallery从需求出发，归纳总结了各类图形的使用案例。而Shiny整合前面的所有，生成可交互式的dashboard。这些都是工具，而作为数据科学家，我们要做的就是利用这些工具让数据“说话”。

Reference

1. BBC Visual and Data Journalism cookbook for R graphics https://bbc.github.io/rcookbook/
2. Paul Murrell（2011）R Graphics Second Edition
3. ggplot2 Reference https://ggplot2.tidyverse.org/reference/
4. THE R GRAPH GALLERY https://www.r-graph-gallery.com
5. Shiny http://shiny.rstudio.com

上一篇博文中，我们已经对图数据库基础作了分享，介绍了图和图数据库的基本概念，今天我们的主题是：图算法。本篇博文的主要内容来源于 O’Reilly 系列的《Graph Algorithms》，作者 Amy E. Hodler & Mark Needham。你肯定没有读过这本书，因为这本书的发布日期是2019年5月。本文会覆盖该书的大部分内容，读完这篇，你能够了解图算法的基本概念。关于此书，作为市面上为数不多的面向数据科学应用的图算法书籍，写的比较全面系统和易懂。当然，书在细节上的提高空间还有很多。今天内容很多，坐稳~

图算法 & 图分析

图分析使用基于图的方法来分析连接的数据。我们可以：查询图数据，使用基本统计信息，可视化地探索图、展示图，或者将图信息预处理后合并到机器学习任务中。图的查询通常用于局部数据分析，而图计算通常涉及整张图和迭代分析。

图算法是图分析的工具之一。图算法提供了一种最有效的分析连接数据的方法，它们描述了如何处理图以发现一些定性或者定量的结论。图算法基于图论，利用节点之间的关系来推断复杂系统的结构和变化。我们可以使用这些算法来发现隐藏的信息，验证业务假设，并对行为进行预测。

图分析和图算法具有广泛的应用潜力：从防止欺诈，优化呼叫路由，到预测流感的传播。下图是 Martin Grandjean 创建的航线网络图，这幅图清楚地展示了航空运输集群高度连接的结构，帮助我们了解航空运力如何流动。航线网络采用典型的辐射式结构（hub-and-spoke structure），这样的结构在有限运力的前提下，增大了航线的网络的始发-到达对（OD Pair），然而却也带来了系统级联延迟的可能。

图基础知识

我们已经在前一篇博文中介绍了属性图的概念。我们已经知道了节点、关系、属性（Property）、标签等概念。

子图（Subgraph）是一张图的一部分。当我们需要对图中的特定节点，特定关系，或者特定标签或者属性进行特定分析时，子图就会很有用。

路径（Path）是一组节点及他们的关系的集合。以上图为例，“Dan” 开过型号为 “Volvo V70” 的车，这辆车是属于 “Ann” 的。那么节点 “Dan” “Ann” “Car”和关系 “Drives” “Owns” 组成了一个简单的路径。

我们在介绍图算法前，先梳理一下图的不同属性（Attribute）。

连通图与非连通图

连通图（Connected Graphs）指图内任意两个节点间，总能找到一条路径连接它们，否则，为非连通图（Disconnected Graphs）。也就是说，如果图中包含岛（Island）,则是非连通图。如果岛内的节点都是连通的，这些岛就被成为一个部件（Component，有时也叫 Cluster）。

有些图算法在非连通图上可能产生无法预见的错误。如果我们发现了未预见的结果，可以首先检查图的结构是否连通。

未加权图与加权图

未加权图（Unweighted Graphs）的节点和边上均没有权重。对于加权图（Weighted Graphs），所加权重可以代表：成本、时间、距离、容量、甚至是指定域的优先级。下图给出了示意图。

基本的图算法可以通过处理权重来代表关系的强度。许多算法通过计算指标，用作后续算法的权重。也有些算法通过更新权重值，来查找累计总数、最小值或最优化结果。

关于加权图的一个典型用途是路径寻找算法。这些算法支持我们手机上的地图应用程序，并计算位置之间最短/最便宜/最快的运输路线。例如，下图使用了两种不同的方法来计算最短路线。

如果没有权重，计算最短路径时，实则在计算关系（Relation，也称 Hop）的数量。那么在上图左边，我们找到 A 和 E 之间的最短距离为 2，经过 D 点。如果像上图右边所示，边被赋予了权重，用以代表节点之间的物理距离（单位：KM）。那么我们可以找到 A 和 E 之间的最短距离是 50 KM，需要经过 C 和 D 两个点。而此时，在未加权图中计算的最短路径 A-D-E 距离为 70 KM，比我们找到的路径 A-C-D-E 距离远。

有向图与无向图

在无向图（Undirected Graphs）中，节点的关系被认为是双向的（bi-directional），例如朋友关系。而在有向图（Directed Graphs）中，节点的关系可以指定方向。边如果指向了一个节点，我们称为 in-link，边如果从一个节点出发，我们称为 out-link。

边的方向加入了更多维度的信息，同样关系的边，却包含不同的方向，则代表了不同的语义信息。如下图所示，有向图绘制了一个简单的同学网络，边的方向代表着 “喜欢”。那么从图中，我们可以知道，同学中 “最受欢迎的” 的人是 “A” 和 “C”。

我们还可以用道路网络帮我们理解为什么需要有向图和无向图。例如，高速公路一般都是双向的，我们使用无向图即可。但是，在城市内部，经常会有单向车道，我们必须使用有向图。

非循环图和循环图

图论中，循环指一些特殊的路径，它们的起点和终点是同一个节点。在非循环图（Acyclic Graph）中，不存在循环路径，相反则为循环图（Cyclic Graphs）。如下图所示，有向图和无向图都可能包含循环，所不同的是，有向图的路径必须遵循边的方向。图中的 Graph 1 是一个典型的 DAG（Directed Acyclic Graph，有向无循环图），并且 DAG 通常有叶子节点（leaf node，也称 dead node）。

Graph 1 和 Graph 2 是无循环的，因为我们在不重复任何一条边的情况下，无法从任何一个点出发，再回到它。Graph 3 中有一个简单的循环 A-D-C-A。而 Graph 4 中，我们可以发现多个循环：B-F-C-D-A-C-B，C-B-F-C 等等。

循环在图中非常常见。有时，我们为了提高处理效率，会将循环图转化为非循环图（通过剪除一些关系）。DAG 在调度、版本控制等问题中十分常见。实际上，我们在数学或者计算机科学中经常遇见的树（Tree）就是一个典型的 DAG，只是对于树来说，只能拥有一个 Parent，而 DAG 没有这个限制。

图算法

我们关注三类核心的图算法：路径搜索（Pathfinding and Search）、中心性计算（Centrality Computation）和社群发现（Community Detection）。

路径搜索算法

图搜索算法（Pathfinding and Search Algorithms）探索一个图，用于一般发现或显式搜索。这些算法通过从图中找到很多路径，但并不期望这些路径是计算最优的（例如最短的，或者拥有最小的权重和）。图搜索算法包括广度优先搜索和深度优先搜索，它们是遍历图的基础，并且通常是许多其他类型分析的第一步。

路径搜索（Pathfinding）算法建立在图搜索算法的基础上，并探索节点之间的路径。这些路径从一个节点开始，遍历关系，直到到达目的地。路径搜索算法识别最优路径，用于物流规划，最低成本呼叫或者叫IP路由问题，以及游戏模拟等。

下图是路径搜索类算法的分类：

DFS & BFS

图算法中最基础的两个遍历算法：广度优先搜索（Breadth First Search，简称 BFS）和深度优先搜索（Depth First Search，简称 DFS）。BFS 从选定的节点出发，优先访问所有一度关系的节点之后再继续访问二度关系节点，以此类推。DFS 从选定的节点出发，选择任一邻居之后，尽可能的沿着边遍历下去，知道不能前进之后再回溯。

下面是两张同样的图，分别采用 BFS 和 DFS 进行图的遍历，图上节点的数字标识这遍历顺序。

对于我们数据科学的角色来说，我们很少真正需要使用 BFS 和 DFS。这两个图搜索算法更多地作为底层算法支持其他图算法。例如，最短路径问题和 Closeness Centrality （在后文会有介绍）都使用了 BFS 算法；而 DFS 可以用于模拟场景中的可能路径，因为按照 DFS 访问节点的顺序，我们总能在两个节点之间找到相应的路径。感兴趣的话，可以猜一猜，后文介绍的算法是否使用了图搜索算法，并且分别使用了 DFS 还是 BFS。

最短路径

最短路径（Shortest Paths）算法计算给定的两个节点之间最短（最小权重和）的路径。算法能够实时地交互和给出结果，可以给出关系传播的度数（degree），可以快速给出两点之间的最短距离，可以计算两点之间成本最低的路线等等。例如：

• 导航：谷歌、百度、高德地图均提供了导航功能，它们就使用了最短路径算法（或者非常接近的变种）；
• 社交网络关系：当我们在 LinkedIn、人人（暴露年龄了）等社交平台上查看某人的简介时，平台会展示你们之间有多少共同好友，并列出你们之间的关系。

最常见的最短路径算法来自于 1956 年的 Edsger Dijkstra。Dijkstra 的算法首先选择与起点相连的最小权重的节点，也就是 “最临近的” 节点，然后比较 起点到第二临近的节点的权重 与 最临近节点的下一个最临近节点的累计权重和 从而决定下一步该如何行走。可以想象，算法记录的累计权重和 如同地理的 “等高线” 一样，在图上以 “波” 的形式传播，直到到达目的地节点。

最短路径算法有两个常用的变种：A （可以念作 A Star）algorithm和 Yen’s K-Shortest Paths。A algorithm 通过提供的额外信息，优化算法下一步探索的方向。Yen’s K-Shortest Paths 不但给出最短路径结果，同时给出了最好的 K 条路径。

所有节点对最短路径（All Pairs Shortest Path）也是一个常用的最短路径算法，计算所有节点对的最短路径。相比较一个一个调用单个的最短路径算法，All Pairs Shortest Path 算法会更快。算法并行计算多个节点的信息，并且这些信息在计算中可以被重用。

本文不打算再深入了，下图是从A节点开始的计算过程，看懂这张图，你就明白了。

All Pairs Shortest Path 算法通常用于，当最短路径受限或者变成了非最优时，如何寻找替代线路。其实算法非常常用：

• 优化城市设施的位置和货物的分配：例如确定运输网格中不同路段上预期的交通负荷，例如快递线路设计，从而保证运输对突发事件的应对；
• 作为数据中心设计算法的一部分：查找具有最大带宽和最小延迟的网络。

最小生成树

最小生成树（Minimum Spanning Tree）算法从一个给定的节点开始，查找其所有可到达的节点，以及将节点与最小可能权重连接在一起，行成的一组关系。它以最小的权重从访问过的节点遍历到下一个未访问的节点，避免了循环。

最常用的最小生成树算法来自于 1957 年的 Prim 算法。Prim 算法与Dijkstra 的最短路径类似，所不同的是， Prim 算法每次寻找最小权重访问到下一个节点，而不是累计权重和。并且，Prim 算法允许边的权重为负。

上图是最小生成树算法的步骤分解，算法最终用最小的权重将图进行了遍历，并且在遍历的过程中，不产生环。

算法可以用于优化连接系统（如水管和电路设计）的路径。它还用于近似一些计算时间未知的问题，如旅行商问题。虽然该算法不一定总能找到绝对最优解，但它使得复杂度极高和计算密集度极大的分析变得更加可能。例如：

• 旅行计划：尽可能降低探索一个国家的旅行成本；
• 追踪流感传播的历史：有人使用最小生成树模型对丙型肝炎病毒感染的医院暴发进行分子流行病学调查

随机游走

随机游走（Random Walk）算法从图上获得一条随机的路径。随机游走算法从一个节点开始，随机沿着一条边正向或者反向寻找到它的邻居，以此类推，直到达到设置的路径长度。这个过程有点像是一个醉汉在城市闲逛，他可能知道自己大致要去哪儿，但是路径可能极其“迂回”，毕竟，他也无法控制自己~

随机游走算法一般用于随机生成一组相关的节点数据，作为后续数据处理或者其他算法使用。例如：

• 作为 node2vec 和 graph2vec 算法的一部分，这些算法可以用于节点向量的生成，从而作为后续深度学习模型的输入；这一点对于了解 NLP （自然语言处理）的朋友来说并不难理解，词是句子的一部分，我们可以通过词的组合（语料）来训练词向量。那么，我们同样可以通过节点的组合（Random Walk）来训练节点向量。这些向量可以表征词或者节点的含义，并且能够做数值计算。这一块的应用很有意思，我们会找机会来详细介绍；
• 作为 Walktrap 和 Infomap 算法的一部分，用于社群发现。如果随机游走总是返回同一组节点，表明这些节点可能在同一个社群；
• 其他机器学习模型的一部分，用于随机产生相关联的节点数据。

中心性算法

中心性算法（Centrality Algorithms）用于识别图中特定节点的角色及其对网络的影响。中心性算法能够帮助我们识别最重要的节点，帮助我们了解组动态，例如可信度、可访问性、事物传播的速度以及组与组之间的连接。尽管这些算法中有许多是为社会网络分析而发明的，但它们已经在许多行业和领域中得到了应用。

下图罗列了我们所有需要了解的中心性算法指标。

Degree Centrality

Degree Centrality （度中心性，以度作为标准的中心性指标）可能是整篇博文最简单的 “算法” 了。Degree 统计了一个节点直接相连的边的数量，包括出度和入度。Degree 可以简单理解为一个节点的访问机会的大小。例如，在一个社交网络中，一个拥有更多 degree 的人（节点）更容易与人发生直接接触，也更容易获得流感。

一个网络的平均度（average degree），是边的数量除以节点的数量。当然，平均度很容易被一些具有极大度的节点 “带跑偏” （skewed）。所以，度的分布（degree distribution）可能是表征网络特征的更好指标。

如果你希望通过出度入度来评价节点的中心性，就可以使用 degree centrality。度中心性在关注直接连通时具有很好的效果。应用场景例如，区分在线拍卖的合法用户和欺诈者，欺诈者由于尝尝人为太高拍卖价格，拥有更高的加权中心性（weighted centrality）。

Closeness Centrality

Closeness Centrality（紧密性中心性）是一种检测能够通过子图有效传播信息的节点的方法。紧密性中心性计量一个节点到所有其他节点的紧密性（距离的倒数），一个拥有高紧密性中心性的节点拥有着到所有其他节点的距离最小值。

对于一个节点来说，紧密性中心性是节点到所有其他节点的最小距离和的倒数：

其中 u 是我们要计算紧密性中心性的节点，n 是网络中总的节点数，d(u,v) 代表节点 u 与节点 v 的最短路径距离。更常用的公式是归一化之后的中心性，即计算节点到其他节点的平均距离的倒数，你知道如何修改上面的公式吗？对了，将分子的 1 变成 n-1 即可。

理解公式我们就会发现，如果图是一个非连通图，那么我们将无法计算紧密性中心性。那么针对非连通图，调和中心性（Harmonic Centrality）被提了出来（当然它也有归一化的版本，你猜这次n-1应该加在哪里？）：

Wasserman and Faust 提出过另一种计算紧密性中心性的公式，专门用于包含多个子图并且子图间不相连接的非连通图：

其中，N 是图中总的节点数量，n 是一个部件（component）中的节点数量。

当我们希望关注网络中传播信息最快的节点，我们就可以使用紧密性中心性。

Betweenness Centrality

中介中心性（Betweenness Centrality）是一种检测节点对图中信息或资源流的影响程度的方法。它通常用于寻找连接图的两个部分的桥梁节点。因为很多时候，一个系统最重要的 “齿轮” 不是那些状态最好的，而是一些看似不起眼的 “媒介”，它们掌握着资源或者信息的流动性。

中间中心性算法首先计算连接图中每对节点之间的最短（最小权重和）路径。每个节点都会根据这些通过节点的最短路径的数量得到一个分数。节点所在的路径越短，其得分越高。计算公式：

其中，p 是节点 s 与 t 之间最短路径的数量，p(u) 是其中经过节点 u 的数量。下图给出了对于节点 D 的计算过程：

当然，在一张大图上计算中介中心性是十分昂贵的。所以我们需要更快的，成本更小的，并且精度大致相同的算法来计算，例如 Randomized-Approximate Brandes。我们不会对这个算法继续深入，感兴趣的话，可以去了解一下，算法如何通过随机（Random）和度的筛选（Degree）达到近似的效果。

中介中心性在现实的网络中有广泛的应用，我们使用它来发现瓶颈、控制点和漏洞。例如，识别不同组织的影响者，他们往往是各个组织的媒介，例如寻找电网的关键点，提高整体鲁棒性。

PageRank

在所有的中心性算法中，PageRank 是最著名的一个。它测量节点传递影响的能力。PageRank 不但节点的直接影响，也考虑 “邻居” 的影响力。例如，一个节点拥有一个有影响力的 “邻居”，可能比拥有很多不太有影响力的 “邻居” 更有影响力。PageRank 统计到节点的传入关系的数量和质量，从而决定该节点的重要性。

PageRank 算法以谷歌联合创始人拉里·佩奇的名字命名，他创建了这个算法来对谷歌搜索结果中的网站进行排名。不同的网页之间相互引用，网页作为节点，引用关系作为边，就可以组成一个网络。被更多网页引用的网页，应该拥有更高的权重；被更高权重引用的网页，也应该拥有更高权重。原始公式：

其中，u 是我们想要计算 PageRank 的网页，T1 到 Tn 是引用的网页。d 被称为阻尼系数（damping factor），代表一个用户继续点击网页的概率，一般被设置为 0.85，范围 0~1。C(T) 是节点 T 的出度。

从理解上来说，PageRank 算法假设一个用户在访问网页时，用户可能随机输入一个网址，也可能通过一些网页的链接访问到别的网页。那么阻尼系数代表用户对当前网页感到无聊，随机选择一个链接访问到新的网页的概率。那么 PageRank 的数值代表这个网页通过其他网页链接过来（入度，in-degree）的可能性。那你能如何解释 PageRank 方程中的 1-d 呢？实际，1-d 代表不通过链接访问，而是随机输入网址访问到网页的概率。

PageRank 算法采用迭代方式计算，直到结果收敛或者达到迭代上限。每次迭代都会分两步更新节点权重和边的权重，详细如下图：

当然，上图的计算并没有考虑阻尼系数，那为什么一定要阻尼系数呢？除了我们定义的链接访问概率，有没有别的意义呢？从上图的过程中，我们可能会发现一个问题，如果一个节点（或者一组节点），只有边进入，却没有边出去，会怎么样呢？按照上图的迭代，节点会不断抢占 PageRank 分数。这个现象被称为 Rank Sink，如下图：

解决 Rank Sink 的方法有两个。第一个，假设这些节点有隐形的边连向了所有的节点，遍历这些隐形的边的过程称为 teleportation。第二个，使用阻尼系数，如果我们设置 d 等于 0.85，我们仍然有 0.15 的概率从这些节点再跳跃出去。

尽管阻尼系数的建议值为 0.85，我们仍然可以根据实际需要进行修改。调低阻尼系数，意味着访问网页时，更不可能不断点击链接访问下去，而是更多地随机访问别的网页。那么一个网页的 PageRank 分数会更多地分给他的直接下游网页，而不是下游的下游网页。

PageRank 算法已经不仅限于网页排名。例如：

• 寻找最重要的基因：我们要寻找的基因可能不是与生物功能联系最多的基因，而是与最重要功能有紧密联系的基因；
• who to follow service at twitter：Twitter使用个性化的 PageRank 算法（Personalized PageRank，简称 PPR）向用户推荐他们可能希望关注的其他帐户。该算法通过兴趣和其他的关系连接，为用户展示感兴趣的其他用户；
• 交通流量预测：使用 PageRank 算法计算人们在每条街道上停车或结束行程的可能性；
• 反欺诈：医疗或者保险行业存在异常或者欺诈行为，PageRank 可以作为后续机器学习算法的输入。

社群发现算法

社群的形成在各种类型的网络中都很常见。识别社群对于评估群体行为或突发事件至关重要。对于一个社群来说，内部节点与内部节点的关系（边）比社群外部节点的关系更多。识别这些社群可以揭示节点的分群，找到孤立的社群，发现整体网络结构关系。社群发现算法（Community Detection Algorithms）有助于发现社群中群体行为或者偏好，寻找嵌套关系，或者成为其他分析的前序步骤。社群发现算法也常用于网络可视化。

下图是社群发现算法的分类。

Measuring Algorithm

三角计数（Triangle Count）和聚类系数（Clustering Coefficient）经常被一起使用。三角计数计算图中由节点组成的三角形的数量，要求任意两个节点间有边（关系）连接。聚类系数算法的目标是测量一个组的聚类紧密程度。该算法计算网络中三角形的数量，与可能的关系的比率。聚类系数为 1 表示这个组内任意两个节点之间有边相连。

有两种聚类系数：局部聚类系数（Local Clustering Coefficient）和全局聚类系数（Global Clustering Coefficient）。

局部聚类系数计算一个节点的邻居之间的紧密程度，计算时需要三角计数。计算公式：

其中，u 代表我们需要计算聚类系数的节点，R(u) 代表经过节点 u 和它的邻居的三角形个数，k(u) 代表节点 u 的度。下图是三三角计数聚类系数计算示意图：

全局聚类系数是局部聚类系数的归一化求和。

当需要计算一个组的稳定性或者聚类系数时，我们可以使用三角计数。三角计数在社交网络分析中有广泛的应用，通航被用来检测社区。聚类系数可以快速评估特定组或整个网络的内聚性。这些算法可以共同用于特定网络结构的寻找。例如，探索网页的主题结构，基于网页之间的相互联系，检测拥有共同主题的 “网页社群”。

Components Algorithm

强关联部件（Strongly Connected Components，简称 SCC）算法寻找有向图内的一组一组节点，每组节点可以通过关系 互相 访问。在 “Community Detection Algorithms” 的图中，我们可以发现，每组节点内部不需要直接相连，只要通过路径访问即可。

关联部件（Connected Components）算法，不同于 SCC，组内的节点对只需通过一个方向访问即可。

关联类算法作为图分析的早期算法，用以了解图的结构，或确定可能需要独立调查的紧密集群十分有效。对于推荐引擎等应用程序，也可以用来描述组中的类似行为等等。许多时候，算法被用于查找集群并将其折叠成单个节点，以便进一步进行集群间分析。对于我们来说，先运行以下关联类算法查看图是否连通，是一个很好的习惯。

Label Propagation Algorithm

标签传播算法（Label Propagation Algorithm，简称 LPA）是一个在图中快速发现社群的算法。在 LPA 算法中，节点的标签完全由它的直接邻居决定。算法非常适合于半监督学习，你可以使用已有标签的节点来种子化传播进程。

LPA 是一个较新的算法，由 Raghavan 等人于 2007 年提出。我们可以很形象地理解算法的传播过程，当标签在紧密联系的区域，传播非常快，但到了稀疏连接的区域，传播速度就会下降。当出现一个节点属于多个社群时，算法会使用该节点邻居的标签与权重，决定最终的标签。传播结束后，拥有同样标签的节点被视为在同一群组中。

下图展示了算法的两个变种：Push 和 Pull。其中 Pull 算法更为典型，并且可以很好地并行计算：

我们不再继续深入，看完上图，你应该已经理解了算法的大概过程。其实，做过图像处理的人很容易明白，所谓的标签传播算法，不过是图像分割算法的变种，Push 算法是区域生长法（Region Growing）的简化版，而 Pull 更像是分割和合并（divide-and-merge，也有人称 split-merge）算法。确实，图像（image）的像素和图（graph）的节点是十分类似的。

Louvain Modularity Algorithm

Louvain Modularity 算法在给节点分配社群是，会比较社群的密度，而不仅仅是比较节点与社群的紧密程度。算法通过查看节点与社群内关系的密度与平均关系密度的比较，来量化地决定一个节点是否属于社群。算法不但可以发现社群，更可以给出不同尺度不同规模的社群层次，对于理解不同粒度界别的网络结构有极大的帮助。

算法在 2008 年被提出以后，迅速成为了最快的模块化算法之一。算法的细节很多，我们无法一一覆盖，下图给出了一个粗略的步骤，帮助我们理解算法如何能够多尺度地构建社群：

Louvain Modularity 算法非常适合庞大网络的社群发现，算法采用启发式方式从而能够克服传统 Modularity 类算法的局限。算法应用：

• 检测网络攻击:该算可以应用于大规模网络安全领域中的快速社群发现。一旦这些社群被发现，就可以用来预防网络攻击；
• 主题建模：从 Twitter 和 YouTube 等在线社交平台中提取主题，基于文档中共同出现的术语，作为主题建模过程的一部分；

结论

本文更像是一篇综述，算法很干，我们会在后续继续分享图分析相关内容，敬请期待。

从 Yes&NoSQL 说起

在文章开始之前，先解释下为什么文章标签是 “Yes&NoSQL”。不同于传统的关系型数据库，NoSQL 是 “not only SQL” 的缩写，特指不以 SQL 为中心的任何非关系型数据库。比较常见的错误是，把 “NoSQL” 理解为 “NO SQL”，所以使用 “Yes&NoSQL” 代表关系型及非关系型数据库，关注所有数据库知识。

NoSQL 包含图数据库 (Graph DBMS)，时间序列数据库(Time Series DBMS)，宽列存储(Wide Column Stores，也称基于 Big Table 的存储)等等。典型的 NoSQL 数据库比如 Redis，MongoDB，HBase等等。

本期，我们关注图数据库。图数据库，不是存储图片的数据库，而是存储节点与他们之间关系的数据库。根据DB-Engines数据显示，图数据库是近五年来成长最快的数据库分类。 由于很早开始被Twitter，Facebook和Google在内的公司采用，图已经演变成当今各行各业所使用的主流技术。

什么是图

图广泛存在于现实世界之中，从社交网络到金融关系，都会涉及大量的高度关联数据。这些数据构成了庞大的图，图数据库就是呈现和查询这些关联的做好的方式。

图，形式上是节点 (vertex，或者 node) 和边 (edge) 的集合。在一张图中，一个节点代表一个实体，例如某个人，某个城市，某家公司等等。边，就是关联这些节点的关系 (relation) ，例如“王健林”是“王思聪”的父亲，“我”生活在“上海”。

如图，JanusGraph 官网教程中给了一个希腊神话的人物及罗马神殿关系图，是一个典型的带标签的属性图 （Labeled-Property Graph）。

我们可以从图中容易发现：

• 赫拉克勒斯（Hercules）的父亲是丘比特（Jupiter，对应希腊神话中的宙斯），母亲是阿尔克墨涅（Alcmene）；
• 阿尔克墨涅（Alcmene）是一个凡人（human），所以赫拉克勒斯（Hercules）是一个半神（demigod）；
• 尼普顿（Neptune，海神）住在海洋中，因为喜欢海浪的声音。
• ……

然后我们就很容易理解以下概念：

• 节点拥有一个（也可以是多个）标签（label），例如神（god）、半神（demigod）、凡人（human）等等；
• 节点可以拥有很多属性（property），例如姓名、年龄等等，以键值对（key-value pair）的形式表示，并且属性值也可以是键值对；
• 边也有标签，标签可以是“住在”、“是他的父亲”等等；
• 边有方向，不同图数据库对方向的约束可能不一样，例如JanusGraph只接受单向边，如果需要表达双向关系，则需要再添加一条反向的边；
• 边也有属性，例如某人“住在”某地的关系上存在“原因”的属性；

当然，实际场景中的图要比上图复杂的多的多，图数据库就是处理这种数据的工具。

为什么需要图数据库

其实这个问题可以这么问：为什么传统关系型数据库不能很好处理图？

有人曾做过一个测试：在一个包含100w人，每人约有50个朋友的社交网络中找到最大深度为5的朋友的朋友。下图为图数据库Neo4J和关系型数据库在寻找扩展朋友时的性能对比。

从图中可以发现，当我们需要寻找朋友的朋友（深度为 2）时，关系型数据库（RDBMS）与 Neo4j 性能差距并不明显；深度为 4 时，关系型数据库需要近半个小时才能返回结果；当深度到达 5 时，关系型数据库已无法返回结果。从中我们可以很容易看出，对于图数据库来说，数据量越大，查询需要涉及的关系越复杂，图数据库的性能优势越大。

为什么关系型数据库不行

我们来复盘一下上面的实验。对于关系型数据库来说，朋友的朋友意味着两张表的 join， 会很容易产生笛卡尔积的中间数据，数据量随着深度呈幂增长。这就是为什么性能随着查询深度，下降如此之快。

再举一个例子，假设刚才我们在寻找“ A 的朋友是谁”，我们的数据表针对此类查询进行了特殊表设计，查询一般会比较快。但是，如果我们需要查询“谁的朋友是 A ”，我们可能需要遍历整个关系表，查询效率就会瞬间降低。

同样的，在商品数据库中，我们查询某个客户买了哪些商品通常效率比较高，但是我们要查询”那些客户买了这个商品”甚至是“有哪些买了这个商品的客户也买了那个商品”的这种多层关系的时候，关系型数据库通常就显得力不从心了。实际上，关系型数据库在处理反向查询以及多层次关系查询的时候通常开销较大。

为什么图数据库可以

原理上的解释，看完下个章节，可能你就会有答案。这里，先介绍下图数据库的特点：

1. 使用图的方式表达现实世界很多事物更为直接、易于理解，自然也易于建模。你可以喜欢一部电影，也可以和好朋友建立密切的关系，也可以创作一些文章，均可以用节点和边的方式表达；

2. 图数据库可以高效插入大量数据。从应用的角度来说，知识图谱、社交关系、风控关系等，数据量在亿级别。图数据库在十亿级别的数据量时，能保持较好的性能；

3. 图数据库可以高效进行关联查询、数据插入，并且提供了针对图查询的语言。我们已在上一小结说明，关系型数据库针对关联查询效率下降严重。图数据库通过针对性的优化，在数据建模，存储形式上支持高效的关联查询。图模型提供了固有的索引数据结构，因此它不需要为给定条件的查询加载或接触不相关的数据。目前比较主流的图查询语言是 Gremlin 和 Cypher，都可以用模式匹配的方式，去寻找图上的路径。例如，使用 JanusGraph 寻找我的 2 度朋友关系：

   1	g.V().has('name','gupeng').out('friend').out('friend')

   使用 Cypher 寻找我和我的好朋友的共同好友：

   1 2 3

   MATCH (a:Person {name:'gupeng'}) -[:KNOWS]-> (b) -[:KNOWS]-> (c) (a) -[:KNOWS]-> (c) RETURN b,c

   并且，在查询节点之间的关系通常可以做到常数级别。

4. 图数据库提供专业的分析算法或者工具。分析算法例如 PageRank、ShortestPath 等等。大部分图数据库也会提供可视化的图显示，使得查询和分析十分直观。

图数据库应用

图数据库拥有广泛的适用场景，因为实体和关系的建模方式能很好地抽象自然和社会的很多事物。下面举例最常使用的场景。

1. 社交网络

   在社交网络中使用图数据库可以方便得识别人/群组和他们交流的事物之间的直接或间接的联系，使用户能够高效地对其他人或事物进行打分、评论、发现彼此存在的关系和共同关系的事情。可以更加直观得了解社交网络中人与人之间如何互动、如何关联、如何以群组的形式来做事情或选择。

2. 实时推荐

   推荐算法通过用户的购买、生产、消费、打分或评论等行为，建立人和商品之间的联系。推荐算法可以识别出某些资源会吸引特定个人或群体，或者某些个人或群体可能对特定资源感兴趣。用图数据库存储和查询这些数据使得应用程序可以为最终用户呈现实时结果，反映数据最新的变化，进行实时的商品推荐。

3. 知识图谱

   最早起源于Google Knowledge Graph。知识图谱本质上是一种语义网络 。其结点代表实体（entity）或者概念（concept），边代表实体/概念之间的各种语义关系。所以知识图谱可以很好地用图来表达。建立知识图谱，可以为后续应用提供基础，例如问答系统，商品推荐，信息检索等等。

4. 反欺诈和风控

   例如，近年来的消费金融行业快速发展，相比于传统商业银行，拥有自己独特的优势：填写字段少、在线操作、审核速度快、放贷及时。这类申请人群通常因缺乏征信信息而给消费金融企业带来了巨大的信用和欺诈风险。而图分析结合传统机器学习算法，可以在有限信用记录甚至是“零”信用记录下进行更准确的风险控制和欺诈识别。

此外，图数据库产品还广泛用在地理空间和物流应用，路由计算，电商和社交类产品防机器人作弊，网络和数据中心管理，授权和访问控制等领域。

数据模型 & 图计算引擎

我们从使用图数据库的角度入手，一个完善的图数据系统至少应该包括图存储和查询，图处理和计算，数据导入导出，可能还有可视化，对于商业化产品还需要高可用及容灾备份。下面对主要部分进行介绍。

图存储 & 数据模型

图数据如何存储图，对存储效率和查询效率都至关重要。我们称数据库表达数据的方式为图模型（Data Model），是一种对图的建模方式。

目前使用的图模型有3种，分别是属性图（Property Graph）、资源描述框架（RDF，Resource Description Framework）和超图（HyperGraph）。

1. 属性图（Property Graph）：目前主流图数据库选择的数据模型，更确切的说是带标签的属性图（Labeled-Property Graph）。除了图所共有节点和边的概念，我们已经在上面介绍了属性和标签的概念。我们可以用一个属性图来表达属性图各元素的关系：

   

2. 资源描述框架（RDF，Resource Description Framework）：在一个 RDF 中，增加的信息都以单独的节点表示。RDF由节点和边组成，节点表示实体/资源或者属性，边则表示了实体和实体之间的关系以及实体和属性的关系。相较于属性图，对属性的处理方式不一样。例如，如果要为某个”人“节点增加”name“属性，对于属性图来说，在这个”人“的”name“属性上设置名字，而在 RDF 中，直接通过一条”hasName“的边指向了设置名字。RDF 形式上表示为SPO（Subject - Predicte - Object）三元组，有时候也称为一条语句（Statement）。RDF 比较多地被使用在知识图谱中，那我们也通常称一条语句为一条知识。许多图数据库是基于RDF实现的，包括：AllegroGraph，Virtuoso，Blazegraph和Stardog。

3. 超图（HyperGraph）：不同于属性图和 RDF，超图的边可以连接任意数量（不能为 0）的节点，超图的边又称为超边（hyperedges）。如图是一个典型的超图：

   

主流的开源图数据库 Neo4j 和 JanusGraph 都采用属性图的数据模型。不同的是，Neo4j 使用原生图存储，JanusGraph 使用非原生图存储，将图结构序列化存储到基于 BigTable Model 的数据库（例如 Cassandra，HBase）中。原生图存储为存储和使用图做了更多的优化，遍历查询性能更高，但非遍历类的查询则不占优势，且为了全局搜索还会占用大量内存。

图查询和图计算 / OLTP 和 OLAP

图查询和图计算都是对图的遍历。图数据库主要提供两种与遍历图的方式：OLTP （Online Transaction Processing）和 OLAP （Online Analytical Processing）。

• OLTP：实时返回，涉及少量数据，随机的数据访问，串行运行，用于查询，偏向深度优先的计算引擎，不需要太大的内存；
• OLAP：长时间运行，涉及几乎整个图，串行地访问数据，并行运行，批量处理，偏向广度优先的计算引擎，需要更大的内存。

图查询指支持对图数据模型的增、删、改、查（CRUD）方法，更关注 OLTP。有的图数据库也继承了少量的图计算能力，但真正的大型系统还是需要单独的计算框架。

图计算引擎技术，偏重于全局查询，通常都对与批处理大规模数据做过优化。只有一部分图计算引擎有自己的存储层，其他的都只关注与如果处理外部传入的数据，然后返回结果到其他地方保存。图计算引擎，或者说图的并行计算框架，包括 Google 的 Pregel，基于 Spark 的 GraphX，Apache 下的 Giraph / HAMA 以及 GraphLab，其中Giraph 是 Pregel 的开源实现。

图数据库产品

Neo4j

Neo4j 是老牌的图数据代表（2007）。其功能强大，性能也不错，单节点的服务器可承载上亿级的节点和关系，单节点性能不够时也可进行分布式集群部署。

Neo4j有自己的后端存储，不必如同 JanusGraph 等一样依赖另外的数据库存储。Neo4j 在每个节点中存储了每个边的指针，因而遍历时效率相当高。Neo4j分为社区版和企业版，社区版功能受限，另外其提供可视化的客户端感觉很不错。

据neo4j的中国合作方的社区中描述，主要区别如下：

1、容量：社区版最多支持 320 亿个节点、320 亿个关系和 640 亿个属性，而企业版没有这个限制；

2、并发：社区版只能部署成单实例，不能做集群。而企业版可以部署成高可用集群或因果集群，从而可以解决高并发量的问题；

3、容灾：由于企业版支持集群，部分实例出故障不会影响整个系统正常运行；

4、热备：社区版只支持冷备份，即需要停止服务后才能进行备份，而企业版支持热备，第一次是全量备份，后续是增量备份；

5、性能：社区版最多用到 4 个内核，而企业能用到全部内核，且对性能做了精心的优化；

6、支持：企业版客户能得到 5X10 电话支持（Neo4j 美国电话、邮件，微云数聚电话、微信、邮件）；

考虑到这些限制，要选开源免费大容量分布式的图数据库的可以跳过了，研究图论及小型应用或不差钱的项目则选其的支持服务则另当别论。另外 Neo4j 的协议为 GPLv3，这个也不适合选用。

JanusGraph

JanusGraph（2017） 基于 Titan（2012）发展而来，包含其所有功能，采用 Tikerpop 的 Gremlin 图查询语言，有单独的后端存储，支持 Cassandra / HBase 等做存储，支持 Solr / ElasticSearch / Lucence 等做图索引。支持Spark GraphX / Giraph等图分析计算引擎及Hadoop分布式计算框架。原生支持集成了 Tinkerpop 系列组件：Gremlin 查询语言，Gremlin-Server 及 Gremlin applications。

采用很友好的 Apache2.0 协议，支持对接可视化组件如 Cytoscape，Gephi plugin for Apache TinkerPop，Graphexp，KeyLines by Cambridge Intelligence，Linkurious 等。

结语

总体来说，图数据和图分析还处在方兴未艾的阶段，很多现有的产品都相当的“实验室”，性能提升空间十分巨大。图数据库的价值，还需要更多的开发工程师、数据分析师来实现。

关于图数据库的未来，引用一段知乎作者 bop 的一段话：

图的本质难题是什么？是数据的高度关联带来的严重的随机访问。所以，传统的关系型数据库解决不了这个问题，因为他们仍然是面向磁盘优化，尽可能利用磁盘顺序读写的优势。Neo4j 这种数据结构在数据落到磁盘上的时候，随机访问比关系型数据库多更多，性能衰减想当厉害。那么分布式 NoSQL 的路子呢？网络是瓶颈。完美的最小割图分区算法是 NP 难题，而且在数据写入的情况下还要面临动态调整的难题。如果使用naive的分区算法，网络通讯的开销是想当大的。

所以，个人浅见，只有靠新硬件来解决问题。更廉价的大内存、NVRAM、RDMA高速网络、随机读写更强的SSD磁盘、有硬件事务支持的CPU等。

技术世界就是这样，封装封装再封装，重构重构造新轮。

Reference

1. 图数据库入门概览，作者：AirCloud，https://zhuanlan.zhihu.com/p/32856981
2. 一起学图数据库之一：图数据库介绍，作者：王二铁，https://zhuanlan.zhihu.com/p/32857155
3. 一起学图数据库之三：图数据库市场格局，作者：Yu Xu，翻译：王二铁，https://zhuanlan.zhihu.com/p/33112533
4. 知乎答案：类似 Neo4j 这样的图数据库在国内会兴起么？，作者 javeme，https://www.zhihu.com/question/19999933/answer/550019788
5. 图数据库基础，作者：温正湖，https://zhuanlan.zhihu.com/p/50171330
6. 20180818图数据库概览，作者：朱金华，https://zhuanlan.zhihu.com/p/42351039
7. 知乎答案：图论数据库未来的发展方向？，作者：bop，https://www.zhihu.com/question/31819867/answer/237043857
8. WIKIPEDIA Graph_database， https://en.wikipedia.org/wiki/Graph_database

欢迎来到我的博客，我来自 Teradata，是一名 Data Scientist。作为数据科学从业者，深知数据库知识、计算机知识、数据分析能力，当然还有算法知识，都是不可或缺的。

博客会针对这四个方面的内容，记录工作中的探索和心得。当然，我也会关注”如何快速成长为数据科学家“这一主题，提供一系列的课程，但这不会是本博客的主要内容。

主要内容

所有文章将可以在此页面进行索引和跳转，新的文章也可能在此页面进行预告~

Yes&NoSQL

主要关注数据库知识，了解㓊类型的数据是如何存储和取用的。包括但不限于传统关系型数据库的原理和使用、图片等非结构化数据如何存储、有什么好的工具提供完整的平台解决方案；

1. 图数据库：概览
2. 图数据库：JanusGraph 简介（TODO）

GeekStyle

主要关注计算机知识，对于一个 Data Scientist 来说，我会更关注如何高效工作。包括但不限于如何选择生产工具、如何自动化建立机器学习模型、如何高效利用多台计算机建立模型；

1. 开源 AI 分布式框架 Ray （TODO）

AnalyzeAnything

主要关注数据分析、数据挖掘，了解如何让数据说话，让数据真正产生价值。包括但不限于如何可视化你的数据、如何进行数学建模的过程、怎样去解决你的业务问题；

1. 可视化工具概览（TODO）

Algorithm

关注算法知识，了解最前沿的算法和工具。包括但不限于算法的原理和案例、如何理解算法的超参和算的局限性。

1. 图算法：概览