图模型、图查询、图计算和图学习知识

本篇的内容主要从图模型、图查询以及图计算和图学习四个方面着手阐述，重点介绍对图的应用上的经验、思考，讨论关于图有哪些应用、为什么有用、怎么用以及哪些地方难用或无用、为什么没用等内容，避免复杂概念或公式以保证非技术人员也能充分理解，相信这篇文章能让大家开卷有益，也欢迎大家来一起讨论。

1 图模型

1.1 图的点、边、标签、属性与同异构

图论中，图（Graph）的符号往往用G表示，图被定义为一个多元组，核心元素为顶点（vertex）集V以及边（edge）集E，即G=（V，E）。从数据的角度，顶点可以理解为针对实体、对象的建模，边则是用于描述两个顶点间的关联或交互。给定两个顶点u,v, 用（u,v）表示两点间的边。此外，图的多元组中往往还有标签函数L（指向点边的标签）、属性函数P（指向点边的属性）以及点边类型函数T等等。比如，社交网络中异常的账号可能有色情、赌博等标签。账号可以有注册时长的属性，所属用户年龄属性等。而好友关系的边则可以有好友建立时间点的属性。

值得一提的是，点边均只有一种类型的图称为同构图，比如转账网络中只有用户账号一种点类型，并且只有转账关系这一种边类型，因此转账网络为同构图。除了同构图之外的图均为异构图。如微信支付的交易网络中，用户账号间的交易既可以转账，也可以是红包或者面对面，因此支付交易网络的边不仅有一种类型，微信支付的交易网络是异构图。

1.2 图形式简单，图问题复杂

图论起源于欧拉对哥尼斯堡七桥问题的研究。七桥问题是指如何能够不走重复路的情况下走遍哥尼斯堡的七座桥，其实就是现今大家熟知的一笔画的问题。形式很简单，但解决却不容易。欧拉通过将七桥问题形式化为点边的一笔画问题来解决。这种简洁的点边建模思路为后世的学者沿用发展，逐渐形成了图论体系。图论问题在高中数学联赛试题中很常见，这个点跟图模型的一个重要特性有或多或少的关联：图模型的形式足够简单，但图模型下提出的问题往往很复杂。

这个特点也引来不少对图饶有兴趣却不求甚解的同行，时常把简单问题复杂化以获取信息不对等优势进而行不实宣传，导致大量图的潜在使用者的时间浪费与业界对图的信心受挫。希望此篇能够澄清图的相关概念与作用，帮助大家在图应用上少走弯路。

1.3 高效的关联表达与分析能力

图的形式虽然简洁，但是对信息的表达能力却非常强。

复杂信息的建模与融合

人们每天获取的信息，不限任何主题或领域，大都可以一条或多条陈述句来表达。例如“拜登当选了美国总统”，“Twitter封杀了特朗普”。陈述句的主体大都可以表示为主谓宾，如三元组:以及。而图模型可以很好地建模主谓宾，即以主、宾为两个对象（顶点），以谓语表示对象间的关联或交互（边）。因此图模型能很好地建模主谓宾，进而建模陈述句、信息。而且，这里不对信息做任何主题或者领域的限制，因此图模型能以简洁的形式对复杂知识信息进行良好的建模和融合。

高效的关联发现与分析

图做关联分析的高效性来源于其本身对关联的存储与顶点的低冗余度。以“旅美物理学家吴健雄与中国近代权臣袁世凯有什么关系”这一问题为例，为了回答这一问题，在传统的关系数据库中，需要先在各种可能的关系表里定位“吴健雄”，而“吴健雄”在同一表中的出现可能相当冗余，因为每个“吴健雄”相关的关系实例中“吴健雄”均会出现一次，存在冗余的计算代价。而在图模型中，定位单个“吴健雄”的出现就能够同时定位其相关的所有关联关系，如邻接表。

更简洁地说，在传统关系数据库中，以上关联分析往往会在大量表上进行代价高昂的join过程，效率低下，尤其是多个join串联的计算。而在图模型中，由于图本身直接存储了部分关联，同时对顶点及其直接关联的定位能够足够高效（相比于join），进而使得图的关联发现与分析足够高效。

此外，在对传统关系数据多级join的优化过程，往往也将关系数据进行图模型化的过程。回到“吴健雄”与“袁世凯”关系的问题，这个问题在图模型中会以路径的形式来建模，而图算法中有大量针对路径的优化工作，这也是图模型关联高效性的一个来源。总的来说，图对关联的聚焦，带来了能够保证高效关联分析的相关方法论与技术手段，这点促进了图关联分析的高效。

1.4 图系统的三大类功能

目前图技术的应用主要通过三个技术点的支撑来实现，分别是图查询、图计算和图表示学习。

图查询主要是对图关联数据的基础查询，旨在直接获取关联信息，包括多阶邻居查询、路径查询与子图查询。此外图可视化也是辅助图查询结果的展示，是提高图关联分析效能的重要组件。图计算是指针对全图结构进行重组、抽象或者传播迭代得到点/边全局属性的过程，如图的聚类、分割、生成树、PageRank的计算等等。国际学术界常用Graph Processing System表示图计算系统，中文翻译过来是图处理系统，但中文语境下图计算这个词更为形象，也使用的更为普遍。

图学习主要是指图表示学习，将图中的顶点映射到低维向量空间，要求向量间的相对距离能够尽可能地反映原顶点在图结构关联强度上的相对大小，实现非欧图数据向欧式向量空间的转变（图数据无法满足欧式空间约束）。欧式的向量数据能够作为特征，更直接地支撑下游的业务需求。图的关联数据与用户属性数据有明显的不同，是业务瓶颈提升探索上的一个非常重要的新视角。

图学习经常被归入图计算范畴内讨论。其实两者内涵迥异。其中最大的不同点在于，图计算的结果仍然在图语义范围内有清晰的解释，如PageRank作为顶点的网络中心性度量，而图学习的结果是向量集，同图语义无交集。图计算和图学习在学术界也是较为不同的学者群体在各自研究。后文将以笔者在业务实践中，对图的三大类技术点的应用思考展开讨论。

2 图查询

图查询包括单点的多阶邻居查询、两点间的关联路径查询以及获取多点间关联的子图查询。除此之外我们也会讨论驱动图查询的图数据库的现状，腾讯公司图数据库Oteam的产品EasyGraph以及知识图谱等相关内容。

2.1 多阶邻居查询

同某个顶点v有关联边的所有顶点均为v的邻居，如图所示，以中心红色顶点v为源顶点，绿色顶点为v的邻居，也称为一阶邻居；绿色顶点的邻居集合里，去除v自身以及所有绿色顶点，剩下的顶点称为v的二阶邻居，如图中的蓝色顶点；依次类推得到v的三阶邻居，即图中的紫色顶点。

图查询应用点很多，这里介绍常见的四种应用点：多阶扩散、近邻分布、关联可视化展示、特定邻居搜索。

多阶扩散多阶扩散是较为常见的图查询操作。近邻往往同自身关系密切或属性相近，多阶扩散则是用来获取同自身属性一致或相近的人群。例如在特定标签的人群识别中，同类人群往往形成社区并且彼此间紧密关联，从已知的标签人群出发，通过相应标签场景的紧密的关联（如业界常见的共同设备）扩散出的人群往往能覆盖未知的标签人群。值得注意的是，扩散后的人群也往往也可能包括正常人群，因此扩散结果需要进一步的过滤处理。实践中，图的多阶查询效率比传统关系型系统的join操作在性能上高出2~3个数量级。

近邻分布多阶邻居查询也用来获取近邻分布，进而更精准地刻画用户自身特定属性。例如，程序员在社交网络关联的邻居里，具有程序员标签的用户密度会明显偏高。对于一个未知标签的用户，可以通过其社交网络或资金网络多阶邻居中已知的用户分布来辅助确定用户是否具有相应的属性。

关联画像对于给定的一个顶点，多阶邻居的全貌展示能够有助于对顶点更深刻的理解，即通过多阶邻居的关联来对顶点进行画像。这类应用的落地主要通过图可视化工具对多阶邻居的展示来完成，如天眼查等通过关联可视化落地的应用。

特定邻居搜索多阶邻居的查询也能获取特定的邻居进行强化关联。以社交网络为例，每个人的一阶好友关系为其可见的人脉集合，而二阶好友往往是每个人的人脉盲区，通过特定的二阶好友的查询能够精确定位到符合需求的人脉。举现实例子来说，假设一名患者想在赴诊前对某医院某科室医生提前进行健康咨询，而该患者一阶人脉并无覆盖该科室的任何一名医生，如果该患者能够找到同某个目标医生的公共好友，则可以通过公共好友同目标医生建立直接的关联关系，实现提前的健康咨询。

多阶查询往往最大阶数为3，因为4阶及以上查询结果将非常庞大难以处理。此外，高阶的邻居同源点的关联强度也随着阶数的增长而不断下降。因此，从经验的角度看，多阶邻居查询一般最多到3阶。

2.2 路径查询

路径的一般定义为：两点间能够连通起来的边的集合。如下图从史玉柱到深大，从深大到张维，从张维到高晓松的三条边的集合即构成了史玉柱到高晓松的一条路径。

路径聚焦两点间的间接关联关系。间接关联获取成本更大，更为隐蔽。在金融欺诈场景中，犯罪团伙往往将资金关联拉长以进行对抗，如将直接的资金往来通过多阶的转账来间接实现。传统的关系型数据平台因串联join的低效性导致路径查询成本高昂难以实现，而路径查询是图研究领域的经典问题，通过对路径的高效查询能够降低间接关联的发现成本，提高欺诈团伙的对抗门槛。

例如，在刑侦场景中，案件里的受害人与施害人的关联也是刑警首要关注的信息。如果能构建足够大的一张图，包括多种关联关系信息（图有很强的数据融合能力），则通过在该图中获取受害人与施害人之间的所有路径，就能清晰展现两者间的各种直接与间接的关联关系。高效地进行路径查询则有利于提高案件分析的效率。

亿级图上，路径查询的目标路径长度一般不会大于6（受限于计算能力），而实际需求往往不会大于4（关联信息衰减），查询过程往往是从两点分别向对方搜索，将两点各自的多阶邻居进行取交，实现路径的发现。每个顶点最多往外搜索的深度为3。正如前面多阶查询所说，搜索深度大于等于4时，搜索空间容易过于巨大。（以上数据经验之谈，仅供参考）

2.3 子图查询

子图的概念是相对一个更大的图来定义的。如果一个图的点集和边集都是另一个图的子集，则该图为另外一个图的子图。以微信支付月度转账网络为例，该月腾讯公司员工之间的转账关系则是构成了一个转账网络的子图。

子图查询最直接的优点就是对数据需求的表达能力很强。假设我们有一个查询需求：“在国务院工作并且家乡在安徽的博士有哪些？”已有的查询理解方式往往只是从查询中抽取关键字来进行，而子图的方式则更为精准，如下图所示。子图能够理解查询的目标是个顶点，顶点有三条关联的边，分别是对“国务院”的就职关系，对“安徽”的家乡定位关系以及对“博士学位”的学历关系。而通过子图同构的查询，则能够对查询需求进行更为精准地响应。

子图也可以用来构建通用的行为特征。例如针对顶点及其一阶或多阶的邻居构成的频繁子图（复杂网络领域定义为Motif，Wikipedia显示Motif的本质定义就是频繁子图），将对应频繁子图的频次定义成特定维的特征，这样的特征是对频繁子图的数值化描述，因此具有较强的稳定性和一定程度的可解释性。

子图的第三个优点，也是非常重要的优点就是描述多点多阶关联，如导出子图：给定图G及其点集V的某个子集V’，假设边集子集E’对应G中顶点同时属于V’的所有的边，则子图（V’，E’）为G在V’上的导出子图。即导出子图是给定点集子集的情况下，边集最大的子图。从数据的角度来说，给定一个顶点集，其导出子图能描述顶点集在原图上的所有的关联关系。在微信支付反欺诈中，经常会遇到做法手法高度一致的一批用户账号，即欺诈团伙。挖掘并打击团伙的关键在于分析出团伙是组织的，而导出子图的查询则能够对批量账号查询其间所有的相互关联。例如，我们曾发现一个典型的欺诈手法，欺诈分子以少女形象，通过网络同新认识的用户约定，如果该用户向“少女”的前男友发送48元转账（48为某不和谐用语谐音）并备注侮辱性用词，则“少女”将返现1000给到新认识的用户。

利用这一套路行骗的不同账号数超过一千，是我们重点打击的团伙。通过hive进行代价高昂的同设备、同证件、同地理位置等关联时，并没有发现特别的团伙痕迹。经过大量的高昂代价关联后，我们最终发现了欺诈分子真实的关联方式。如果我们构建支付欺诈场景下的多种关联形成大图，在遇到作案手法高度一致的批量账号时，直接在大图上进行导出子图查询，则能够高效且全面地获取账号团伙的蛛丝马迹并顺藤摸瓜打击所有欺诈账号。

2.4 图数据库

目前驱动以上查询的主要是图数据库，针对已有图数据库的最新详实的对比信息可以在DB-Engine(https://db-engines.com/en/ranking/graph+dbms) 上获取。图库的潜在使用者该如何选择图数据库？这一问题也等价于技术圈该如何发展图数据库。这里不得不提一个目前普遍存在的现象：技术圈对图数据库的发展同业务圈对图库的需求定位存在明显不一致。

技术与业务对图库定位的分歧已了解到的图应用场景中，对图数据库的功能与性能需求暂时没有到线上数据库的级别，对图数据库的读写要求大体是周期性地批量导入或写入之后，进行多次只读。因此与其说图数据库，不如说图分析平台更为贴切。而且，在图操作的事务管理方面，研究上都还有较大空白，进展寥寥，实际落地上更是困难重重。业务侧对图的需求重点仍然是数据分析为主，而技术圈以数据库视角去发展图系统的却是主流，已知的很多图数据产品团队在以性能为重点内容做宣传。而其实从业务的角度，性能只要达到一定程度（比如一秒内响应）就没有迫切的提高性能的需求（比如十毫秒级）。

再者，图数据库对属性数据的管理相比传统关系型数据库毫无优势。点边属性数据的获取与关联无关，考虑点属性或边属性的查询时，点、边均为孤立的存在，而孤立的点、边在图数据模型中意义相当有限。据说某大厂内部，有部分图数据库产品中的属性管理仍然交由传统关系型数据库管理。因此，技术圈与业务圈对图库定位存在分歧，不过随着越来越多的图库应用落地，这种分歧似乎在不断减少，图技术与实际业务更多的碰撞令人期待。

Easygraph（easygraph.oa.com）落地过程中遇到的数据导入图库的成本与思考

技术圈对数据导入图库过程中开发人员所消耗的时间成本其实存在明显的忽视。EasyGraph作为腾讯公司图数据库Oteam协同开源的一款产品，经历了微信支付欺诈业务场景下多次迭代优化，也是图库在技术和业务上的一次难得的结合。在微信支付欺诈场景下，同EasyGraph团队的合作过程中，笔者对图库在业务应用上的理解要加深了许多。例如，欺诈场景中非常关心的一点是欺诈分子之间或欺诈分子与受骗人之间的关联和交互，进而制定相应的策略或模型进行精准打击。核心点在于，关联数据的查找和可视化。传统的hive在关联数据的查找上效率低下，而已有的图数据库，虽然能够加速关联查询，却忽略了另一重大的成本：数据导入图库。当有一个图数据可视化需求时，往往需要先进行既定格式的数据出库（如HDFS），填写相应图库的配置文件，再启动图库导入。

不同的图库产品往往有不同的导入格式和流程。当可视化过程中需要对关联结果进行微调时，整个流程需要再进行一遍，过程繁琐费时。数据导入图库的成本高昂其实在VLDB 2018的best paper [1]里就重点提到，该论文的核心内容是关于加拿大滑铁卢大学的Semih针对图应用的调研分析。时隔两年，大量图数据库的数据导入成本仍然很高，以笔者所了解的情况，腾讯公司的EasyGraph图数据库对数据导入成本问题解决得较为完善。在EasyGraph落地微信支付场景的过程中，我们迭代了三个版本的图库导入。

①最开始的版本则是通过预处理组件，按既定格式出库数据到HDFS，并通过配置文件启动导入；②之后，我们推动了通过UI交互的方式直接对数据源进行相关配置的导入方式，如浏览器端的库表配置，从列名等字段到点边及其属性的映射等。避免了配置文件和数据预处理脚本开发的成本。但其实对构图成本解决仍不够彻底，因为可视化的数据源往往需要数据分析者先创建相应的临时表，占用存储和元数据开销。即便用视图来优化这一问题，随着时间的推进，图数据库中仍然需要定期清理相应的临时视图等。

基于此，EasyGraph团队又迭代了第三个版本，通过类sql-schema的逻辑，一行简洁的代码就能完成导入，具体导入语法此处不详述，而且第三版的导入方式很大地减少了图库使用者的数据导入成本。这里也给出一个笔者在支付场景下思考获得的一个图库导入设计，这个设计启发于hive create table as select x,x,x from t_xxxx的语法。数据分析者仅需要针对点边及其属性数据写select的查询来反应需求，由图库自身将SQL语法解析出对应的查询计划并从SQL数据库表中直接获取数据并完成相应schema构建和数据导入。数据分析者仅需要撰写寥寥几个其足够熟悉且通用的SQL语句，语句中可以通过SQL语法中的限制条件语句对数据需求进行详细定制。这点其实对技术来说，完全可以实现。

2.5 知识图谱

已有的知识图谱可以直观理解为知识+图谱，即用图的模型与方法对知识数据进行建模、存储与查询挖掘。知识很有用，图谱也有用，所以知识图谱肯定有用，但是大家肯定期待知识和图谱结合起来，有什么新的用处，诸如推理、纠错等强大的功能，也就是做两个减法：知识图谱-知识-图谱 所剩下的那部分功能到底有什么。我个人的看法是：还有待进一步观察。下文也针对这点展开讨论。

从搜索引擎到语义网知识图谱起源于搜索引擎的瓶颈：对查询需求与信息的理解不足。搜索引擎体系以关键字来理解查询需求。以“老家在安徽并且在国务院工作的博士是谁？”问题为例，当下的搜索引擎的主干技术均在于对语句分词，得到关键字后通过关键字对目标网页进行召回排序并反馈。而关键字序列的信息相比原句是有不少信息损失的。此外，搜索引擎所获取的信息也是非结构的复杂的数据，如无格式化的文本、表格等等。直接按排序提供给用户之后，用户需要另外浏览选择过滤得到目标的结果，用户可能在无关的网页中进行费时的筛选。因此以关键字理解查询需求存在不少信息损失，以网页文本集反馈用户，对用户来说其实也存在额外的信息获取成本。基于这个原因，WWW联盟的Tim Berners-Lee在1998年提出了语义网的概念。

语义网旨在将文档上的元素添加计算机能理解的语义，使得互联网成为一个通用的信息交换介质。语义网有两个非常重要的标准，分别是RDF和SPARQL。

RDF全称资源描述框架（Resource Description Framework），用来描述网络资源，这里可以粗浅地理解RDF的描述方式为三元组的方式，分别是主语、谓词以及宾语/字面量（如日期、金额等数值/数词类宾语）。或者更简单地说，RDF数据集就是一系列的三元组集合，三元组分别为主谓宾。基于图模型部分的内容，相信读者可以理解，三元组集合的RDF数据集对复杂数据的表达与融合能力非常出色。

SPARQL是针对RDF数据集的查询语言，全称是SPARQL Protocol and RDF Query Language。如上图所示，SPARQL查询的核心模块是where语句中的三元组集合，此处的三元组不同于RDF的三元组，一般每一个where语句中的三元组至少有一个元组是变量，例如图中的?p，若?p出现在select 的目标中，则是查询需要的对象，若不存在，?p则只是起到对查询结果的约束作用，表示查询结果中，?p出现的几个位置所匹配的实际元组必须完全一致。

这两个标准将精准语义的信息获取分成了三个阶段，第一个阶段是从复杂的网络资源中抽取出三元组集合，即RDF数据集。比如德国的马克思普朗克实验室输出的知名的Yago系列数据集。第二个阶段是将表达数据需求的自然语句转化成格式化的SPARQL查询语句，是NLP语义理解范畴的问题。前两个阶段高度依赖于NLP技术的发展，从学术的角度来看还有较大的发展空间，但在实际业务场景中其实影响有限，因为业务场景上报采集的数据格式相对稳定，查询的需求也相对确定，因此，基于业务经验能够较好地直接格式化出RDF三元组。

第三个阶段则是针对RDF数据集处理SPARQL查询，可行的方法众多，其中一种就是用子图匹配的方式，也就是我们接下来要提到的知识图谱的典型查询处理方式。笔者的导师邹磊教授是最早一批用子图匹配的方式处理SPARQL查询的学者，其相关工作形成的博士论文获CCF 优博提名奖。感兴趣的读者也可以去阅读其发表在VLDB 2011的关于子图匹配处理SPARQL查询的文章 [2] https://dl.acm.org/doi/pdf/10.14778/2002974.2002976。

从语义网到知识图谱

知识图谱一般可以理解为以图谱的方式驱动知识的管理，为知识数据建模、存储和查询挖掘。图模型能够很好地建模三元组集合的RDF数据集，同时也能够很好地将SPARQL的查询需求表达成子图（如下图所示），因此SPARQL查询可以转化成子图查询，而RDF数据集则可以转化成RDF图，SPARQL的查询处理自然就成了在RDF图上进行子图匹配的过程。因此，撇开挖掘不谈，如果只从建模、存储和查询三个方面，知识图谱仅仅是图数据库来管理知识数据并提供子图查询得到的功能，也就是说是知识+图谱。知识+图谱本身就有很大应用，针对知识的图查询本身就能解决很多应用问题，如天眼查的知识展示。而知识+图谱能否碰撞出更大的火花，就必须讨论知识图谱中的挖掘方面的技术成果，这也是广大对知识图谱感兴趣的人群最关心的地方。

而我的结论是：目前不要期望太高，有待进一步观察。图谱对知识本身并无在内涵上的增益，是对知识的一个管理工具。推理、纠错、监控种种在NLP角度发展所遇到的瓶颈，在知识图谱中仍然是瓶颈。以推理为例，给定四个顶点“吴健雄”，“袁家骝”，“袁克文”，“袁世凯“以及他们之间的关系：“吴健雄”与“袁家骝”的夫妻关系以及袁氏三父子的关系，知识图谱大致能基于规则推导出“吴健雄”和“袁世凯”的孙媳妇的关系。

整个过程里图谱其实起到的是数据建模和管理的作用，对数据内涵增益有限，甚至不需要图谱来完成推理，因此这个推理实质还是知识范畴的技术在起作用，并非是知识+图谱碰撞出的新信息。更具体地说，如果存在这么一个问题，知识范畴内无法解决而加了图谱就可以解决的话，目前来看基本可以确定解决这个问题的技术关键在于图谱自身独立存在的功能，如知识的高效关联可视化问题的技术关键在于图谱的可视化，与知识角度的NLP技术无关。反之亦然。

此外，NLP角度解决语义推理问题的一大瓶颈是常识逻辑的缺失，如鸟是天上飞的以及鱼是水里游的。因为逻辑推理的链条不能缺失任何一环，而常识逻辑难以全盘数字化，因此推理这一瓶颈难以突破，期冀知识图谱来解决这个问题，在目前来看困难重重，有待存储和计算能力的进一步发展。

3 图计算

图计算主要指基于全图结构计算点边或点边子集属性的过程。如PageRank描述点的中心性，点边介数（Betweenness）则是描述点边的连通重要性。图计算可以作为对图查询的一个补充，图查询是直接获取关联的信息，而图计算的目标则是计算出基于关联结构蕴藏在点边中的信息，而且，图计算结果本身可以再存储到图数据库中作为图查询的查询目标。对于希望借力图计算提升业务效果的同行来说，重点要关注两个方面，首先是图计算的结果怎么用，其次是如何高效算出图计算的结果。

对于图计算能起到多大作用问题，难以一概而论。鉴于图计算任务大都是计算和资源均密集型的，明确图计算对业务助力的效果应该优于图计算在计算效率上的提升。图计算算法可达数十种，每种有各自适用的场景。图计算的结果可以是点边具体的属性，如PageRank，Betweenness，置信度传播，聚集系数等等；也可以是点边子集所对应的属性或结构，如社区类的连通分量、图聚类、图分割、图染色等等，以及子图类的生成图、生成树、斯坦纳树、最大独立集、K-Core等等。图计算的结果确实在特定的场景下起到过非常关键的作用，如PageRank、斯坦纳树等，但在支付场景的欺诈人群识别实践中，基于资金网络得到的图计算结果对分类效果的支撑提升比较有限，离开特定的场景需求暴力使用图计算的结果难以达到预期的效果。

已有的图计算工作的宣传也侧重计算效率的提升，并没有很全面地解答图计算对业务的提升效果如何。例如，对于连通分量来说，作为经典的图计算的问题，在各大公司内部什么场景，起到多大的业务提升作用？如果存在图计算比较全面地、大幅地提升业务效果（不是效率）的案例，是不是应该有比较多关注图计算的同行已经周知？期待有相关经验的同行能够分享图计算针对业务大幅提升效果的成功案例，笔者也是在较长的一段时间里一直关注图计算在业务中的落地效果。结合自己的实践经验，确实看到过图计算对业务的一定程度的提升，但是提升幅度相比于图计算的投入成本而言，并未达到预期。因此，目前还在持续观察图计算是否能在业务上发挥更大的、更全面且更高效的作用。

图计算算法众多，但是大都可以通过传播迭代的方式实现目标的收敛计算。对于计算和资源均密集的图计算任务，如果直接计算精确的结果，对应的算法复杂度容易达到O(N^2) 甚至更高，在大规模图上计算的执行时间不可承受。已有的图计算系统主要是基于点中心框架的计算，通过定义单点的算子，来实现点粒度的并发，同时多次迭代来收敛至计算目标。类似于Hadoop/Spark生态对行的抽象：开发者只需要对行进行低代码量的开发就能够调度大规模的集群对大规模数据实现计算；点中心图计算则是对点的抽象：开发者仅需要开发基于点的低代码量的函数/算子，就能够调度大规模的集群对大规模图数据实现高效计算。

已有的图系统对图计算的效率提升到了相当的高度。自2010年谷歌首次提出点中心编程框架Pregel（开源对应Giraph系统）之后，GraphLab通过共享内存将Pregel的性能提升了2~3倍，PowerGraph随后基于图的幂率分布进行优化并提出GAS模型，又将GraphLab的性能提升了将近5倍。比较特殊的是随后出现的GraphX，立足于Spark生态的普及在RDD上开发图计算的框架，并直接承认性能弱于PowerGraph将近7倍。但是GraphX基于生态优势也能够大幅解放开发者在数据预处理（ETL）上的生产力，这点上被后来的GraphX的流行所验证。学术界目前最先进的图计算系统应该是清华大学发表在OSDI2016的Gemini。腾讯公司WXG也有基于Gemini原理开发的Plato，在Gemini之上做了很多充分的落地优化。腾讯公司TEG 的Angel图计算则另辟蹊径，通过PS驱动图计算，性能足够优秀的同时与腾讯公司内部TDW生态有非常好的结合。

值得注意的是，目前图计算对异构图的支持有限，针对异构图的计算优化与实际图数据的构图形式有较大的关联，因此难以有通用的图计算系统或算法，但实际业务中的图计算往往更关注异构图。笔者曾在腾讯CSIG开发过基于GraphCHI存储的分布式核外（即磁盘为主）异构图的图计算系统，但由于磁盘I/O效率过低，而业务中对内存的成本并无严苛的要求，该图计算系统实际应用性不足。笔者在异构图计算的开发过程中最大的体会是，具体的计算逻辑和构图形式对计算引擎的效率影响很大，所以通用且高效的异构图计算系统短期内可能难以实现。

4 图表示学习

图表示学习并没有形式化的定义，但基本原理大都为将图中顶点映射到低维向量空间，并且向量间的相对距离能够尽可能地反映顶点间在图上的相对关联强度，完成从非欧图模型到欧式向量空间的转换。而点向量则是可以作为特征无缝地支持下游深度学习任务，因此图学习也是在工业界落地最多，使用最普遍的图技术。鉴于网络上对图表示学习的文章众多，不乏全面详实的综述论文，本篇不在对表示学习已有工作进行过多的展开，直接讨论笔者在图表示学习落地过程中的经验。

图表示学习的核心本质在于表示学习，图只是作为数据源，因此图表示学习的技术部分主要在于表示学习，除了数据外，并没有图的语义，也没有图的算法，理解这点对如何使用、何时使用图表示学习至关重要。讨论这点需要从笔者之前开发的基于LINE算法的扩展版本WxPayLine++说起，算法细节未获授权对外，此处不再展开。

WxPayLine++是基于LINE的二阶无效性开发的LINE的优化版本，核心思路是基于笔者提出的传递增强算子，将多阶信息融合到一阶再进行表示学习。如图所示，WxpayLine++在转账网络学习得到的用户的向量特征，在多种异常人群识别中提升的效果显著。

但是有一点出乎了我们的意料，就是刷单和羊毛党两种标签的提升情况截然不同。这两类标签在各种场合常是同时被提起，并且粗浅理解起来是高度相似的两种标签。然而仔细推敲才发现两者其实非常不同。在微信支付场景中，刷单用户因为回款和佣金的原因往往通过中介形成了紧密的资金流关系，而羊毛党用户均是只有同商户的商业支付，羊毛党用户之间却不一定形成紧密的资金流关系。因此基于转账网络表示学习对刷单有明显的提升，而羊毛党则没有，反而引入了噪声导致效果下降。这点引发了针对图表示学习适用性问题的思考。这里向大家分享下思考的心得：构图关联对问题的指向性决定了表示学习的是否有效果。还是回到刚才的问题，即图表示学习有用时，是表示学习起了作用还是图起了作用。换句话说，当图表示学习对业务不起效果时，是表示学习环节出了问题，还是图本身无用？我倾向认为是后者。毕竟表示学习算法已经经过广大同行的检验。

关于构图关联指向性的讨论，再从一个简单的问题说起。假设以一个人向另一个人发起了微信转账，那是否能够说明以下三种情况成立：第①种：两者是微信好友。显然这点是充分成立的；第②种：两者是居住地同省。考虑到同省人之间更容易发生经济交流，这点上也是有一定概率成立的；第③种：两者身高差18公分。这点就毫无逻辑可言了。因此，转账关系对不同的问题，其指向性程度是不同的，转账对同为刷单用户的指向性要远大于同为羊毛党用户，这点应该可以解释WxPayLine++在两种标签下迥异的表现。

如何判断关联对问题具有指向性？如果可以提前判断关联与问题缺乏指向性，则可以避免代价高昂的图表示学习的计算，节约开发者时间。这里介绍两种方法。

首先是直观理解，即如果有关联的双方能够同时离目标较近，关联对问题则有较强的指向性。如对于两个用户，若一位用户是刷单用户的转账交易关联方，而另一位不是，则前者是刷单用户的概率相对要高于后者。一个有趣的案例则是微信支付场景中的非本人项目。非本人项目旨在挖掘实名证件同账号实际使用者并不一致的所有微信支付账号（如上图所示）。例如未成年人通过绑定父母的银行卡实现实名的微信支付账号则为非本人账号。该项目初期通过分类遇到较大的效果瓶颈，有同事提议使用图表示学习的介入来提升效果。图表示学习的计算代价高昂，经过详细评估之后判断图表示学习在该场景中难以发挥作用，核心的障碍在于无法构图。即基于非本人的语义，无论是人为顶点，抑或人证pair为点，均难以构建针对非本人有指向性意义的关联。这点不做详细的展开，欢迎读者一起讨论。

其次是低代价的统计分布。通过抽取相同数量的正负样本，分别组成对应的导出子图。可以比较两个导出子图的连通分量数、边数以及二阶路径数，如果差异明显，则关联对正负样本的区分具有指向性，反之则无指向性。

表示学习效果与画像特征可能的重叠一般来说，表示学习从数据还是方法的角度上，同画像特征都是相对独立的。但在支付场景的实践中我们发现一个有趣的现象：表示特征的提升效果在画像特征不断丰富后会出现下降。在微信支付反欺诈场景的恶意率建模中，交易网络表示学习的特征在第一版模型上效果提升明显，但随着模型特征工程的展开和优化，表示学习的提升效果明显下降，即画像等基础特征足够丰富时，交易的关联所带来的额外信息在减少。初步估计是交易关联的双方相比无交易关联的双方更容易画像相似，诸如消费地点、兴趣爱好或其它行为上的相似，通过画像工程体现在特征中。

这点上并没有形式化的证明，但有个有趣的真实例子可以供大家参考：笔者之前常去南山文体游泳馆游泳，游泳馆需要客户交现金做衣柜钥匙的押金，这里很容易出现某位客户忘了带现金向其他泳友求助现金并微信转账还款的情况，笔者自身就遇到过一次。这种情况下转账交易的双方往往出现在相同的地点，有相同的兴趣爱好和消费习惯（泳具）等等。

以上几点均是经验之谈，仅供参考，更准确的方法或更形式化的证明留待未来研究。

5 总结

• 图查询的关键在于可视化与即时关联分析的高效
• 图计算的核心作用再全局关联计算中的性能加速
• 图学习同目前业务需求关系最为紧密，作用最为明显
• 图的运用应该在遇到业务瓶颈之后
• 图的产品应该聚焦业务需求、使用体验而非图技术本身

参考文献

• [1] Sahu, Siddhartha, et al. “The ubiquity of large graphs and surprising challenges of graph processing.” Proceedings of the VLDB Endowment 11.4 (2017): 420-431.
• [2] Zou, Lei, et al. “gStore: answering SPARQL queries via subgraph matching.” Proceedings of the VLDB Endowment4.8 (2011): 482-493.
• 作者：youhuanli，腾讯 WXG 应用研究员