1 前言

图是一种广泛存在的数据结构，广泛应用于社交网络、万维网、金融风控、人工智能等领域。图通常可以抽象地表达为点和边的集合G=(V,E)，其中 V是顶点（或者称为节点）集合，E是边集合。我们可以形式化地理解图是以某种方式关联的事物的集合。

图有很多种分类方式，如果按照基本性质分，根据边是否带有方向性，可以分为有向图和无向图；根据边上是否分配有一个数值，可以分为带权图和无权图；根据边是否稠密，又可以分为稠密图和稀疏图。如果按照应用场景分，可以分为社交网络，交易网络、知识图谱等。

通常来讲，关于图的研究可以分为两类，一类是研究如何高效地存储图结构的数据，以及如何进行快速的图查询和图检索，我们称之为图存储，图存储的典型例子是图数据库。一类是研究如何在图结构数据之上架构复杂的计算模式，例如在一个超大规模的交易网络中查询某笔交易是否触黑，这类计算模式我们称为图计算， 图计算又可以分为传统的图计算（例如PageRank，连通分量）和近年来兴起的图嵌入（Graph Embedding）和图神经网络（GNN）。本文将侧重于图存储和图查询技术的介绍。

2 历史

网易游戏从2018年开始开始调研图计算在游戏中的应用，主要有以下几个方面的考虑：

3 图数据库技术

从数据结构上来说，图可以用邻接表、邻接矩阵和十字链表等形式表示，这里我们不对这三种数据结构加以赘述，主要讨论目前主流的图数据库方案。目前主流的图数据库主要有三大阵营：

主流的图数据库一般都使用『带标签的属性图』（Labeled Property Graph，或者简称属性图）作为底层的数据模型，属性图由基本的节点和关系组成：

• 节点（Node）：节点是图数据库中的一个基本元素，用来表示一个实体记录，类似于关系型数据库中的一条记录（或者多条记录的联合），在 Neo4j 中，节点可以包含多个属性（Property）和多个标签（Label）。
  

• 关系（Relationship）：关系同样是图数据库中的基本元素。关系用来连接两个节点，从源节点指向目的节点。关系和节点一样，可以包含多个属性（Property），但是关系只能有一个类型（或者说标签，常用 Type）表示。
  

3.1 Neo4j 生态

Neo4j是图数据库生态的老牌劲旅，最初的构想起源于2000年，当时Neo4j的联合创始人们正在开发一个媒体管理系统，他们发现，现有的数据管理系统很难处理数据模型（Schema）经常变化的情况，为了支持这种灵活性，创始人之一的Peter希望将数据管理系统建模为一种互联的网络，另一位创始人Emil和印度理工孟买分校的一群研究生们花了一周的时间实现了这个系统的原型。这之后，为了性能考量，创始人之一的Johan又基于这个思路实现了一个原生的数据管理系统，这就是Neo4j的原型。起初，Neo4j作为内部项目进行研发，后来于2006年独立出去了，成为了一家独立公司的产品，并于2010年推了1.0版本，此后便一直活跃至今，被众多的企业采用。

Neo4j分为开源版和企业版，开源版支持单实例部署，并且具有数据总量的限制。企业版包含了HA（高可用方案）、Casual Clustering（因果集群）、容灾等诸多高级功能。Neo4j在3.5版本之前，企业版分支也维持着开放源码的状态，但是由于众多云厂商开始将Neo4j企业版包装成数据库云服务对外售卖，Neo4j从3.5版本开始，宣布企业版开始闭源。

Neo4j采用声明式的查询语言Cypher进行图查询，Cypher由于其类SQL的特性，受到了很多图数据分析师的青睐。Neo4j于2015年将Cypher开源为openCypher，推动Cypher能成为图数据库查询语言的标准。

截止到目前，Neo4j已经发展到4.x版本，并且在这一里程碑版本中引入了多数据库、分布式查询等诸多新特性。

3.2 TinkerPop 生态

Neo4j最初通过Java API来访问，随着NoSQL数据库的兴起，越来越多的数据库引擎开始采用Rest风格的API来访问数据库，受这个影响，Neo4j的联合创始人之一Peter找来了好友Marko来实现这个想法，Marko很快基于Groovy和XPath实现了这个想法。

Marko逐渐将这个想法发展成了后来的Gremlin，一种基于Groovy的图遍历语言和虚拟机，并在2009年底开发了出了V0.1版本，项目被命名为TinkerPop。

Gremlin和Cypher形成了两种主流的图遍历风格：以Gremlin为代表的类API过程式（Procedural）语言和以Cypher为代表的声明式（Declarative）语言。Gremlin由于更贴近底层的图访问API，需要研发人员对图的遍历过程有较为深刻的理解，例如如何优化查询查询语句，上手门槛相对困难，Cypher由于跟SQL类似，数据分析师一般能够比较快速地上手，在数据分析场景中更加流行。

TinkerPop项目于2016年成为了Apache顶级项目，众多的数据库都采用TinkerPop（Gremlin）作为图查询语言，比较有名的有Titan，JanusGraph和HugeGraph。

3.3 新兴的分布式图数据库

随着大数据的兴起，以Neo4j为代表的图数据库在面对越来越大的数据量和越来越高的访问性能要求的时候，开始显得力不从心。Neo4j最初的设计是单机模式，也就是整张图需要存储在单台机器，这种设计显然无法很好地满足当下动则百亿、千亿边规模的大图。正所谓长江后浪推前浪，近年来，一众基于高性能分布式技术的图数据库技术开始兴起，比较流行的有商业版的TigerGraph、开源的DGraph和Nebula Graph。

这里面，着重介绍下Nebula Graph，它是Facebook图数据库核心开发人员、蚂蚁金服GeaBase主要负责人叶小萌在2018年创业推出的重量级产品。Nebula Graph采用当下主流的分布式数据库采用的Share-nothing架构，并推出了自己的图查询语言nGQL，nGQL和Cypher类似，也是一种声明式的查询语言。Nebula Graph非常擅长处理千亿节点万亿条边的超大规模数据集，在微信、美团、Boss直聘都很多成功的落地场景。

4 网易游戏图计算平台

网易游戏从2018年开始投入图计算的调研和选型，并开始探索图计算技术在游戏中的落地场景。总的来说，分三个阶段：

• 图数据的建设

• 一站式图计算平台的搭建
  

• 不同业务场景的探索

4.1 图数据的建设

得益于网易游戏的丰富的玩法和场景，游戏数据往往具有丰富的异质性，这里的异质性是指：

• 数据源多样

• 数据模式灵活

• 数据种类丰富

一款流行的MMORPG（大型多人在线角色扮演游戏）可能会有一千多种不同场景下的用户行为，例如：

• 社交行为：聊天，组队，结拜，加好友，结婚等
  

• 交易行为：商城交易，摆摊交易，面对面交易，赠礼等

这些行为数据由于其天然的关联性，很适合用图模型去建模。基于这个背景，从2018年开始，我们开始陆续基于一些游戏的游戏日志和数据仓库建设图模型数据。首先面临的一个问题是：图模型如何存储和查询，也就是图数据库的选型问题。

我们先后对Neo4j，JanusGraph和HugeGraph进行了调研，最终选定了较新的HugeGraph，它是百度安全团队于2018年中旬开源的一款基于Apache TinkerPop框架的高性能、分布式的图数据库，选择HugeGraph主要有几个考量：

• Neo4j本身很成熟了， 但社区版仅支持单机模式，随着数据量的增加会遇到瓶颈。此外，Neo4j单实例在4.0版本前仅支持单图，无法很好的满足我们的多租户场景，多实例部署会给运维增加难度。
  

• JanusGraph的前身是Titan（已经不维护），作为Apache TinkerPop生态的主要成员，其设计理念最初是十分先进的，Gremlin API的实现也很完善，但JanusGraph开源社区近年来显得比较疲软，新特性的更新十分缓慢。此外，JanusGraph的易用性欠佳，缺乏高质量的文档和操作教程，很多需求（比如大数据量的导入，多节点部署）都需要开发人员自己去摸索。
  

• HugeGraph基于Titan，JanusGraph的源码进行了深度改造，从2018年开源以来，社区一直较为活跃，新特性的更新也比较频繁。此外，HugeGraph提供了丰富的组件来帮助用户快速上手，例如HugeGraph-Loader（数据导入工具）、HugeGraph-Tools（数据库运维工具） 等。

HugeGraph能支撑数十亿级别的点边规模，基本能满足我们单个游戏的建模需求。在数据模型设计上，我们将不同的关系根据主题抽象成不同的图，例如，社交图中包含如下类型的节点和关系：

• 节点：玩家、帮会等
  

• 关系：朋友关系、结拜关系、师徒关系、情侣关系、帮会同仁、家族关系等

建模的过程分为几步：

1. 通过Hive/Spark等大数据工具生成点边关系数据，将点根据标签分为不同的点表（例如玩家表，帮会表），根据不同的边类型组成不同的边表（例如好友关系表，师徒关系表），这一步一般叫做业务数据的加工。
   

2. 在HugeGraph中预初始化图，HugeGraph采用『插件化』的思路设计，其本身并不负责数据的存储，而是将数据存储在HBase，RocksDB，Cassandra这类数据库中。存储引擎的选择通常基于对可用性和性能的要求，一般情况下，Cassandra在可用性上相比HBase有优势，HBase对数据一致性的支持更好，RocksDB则性能更优。实际使用过程中，由于不同的图可以配置不同的存储引擎，我们一般将对数据冗余和可用性要求高的场景放在HBase，对于离线的图计算实验或ad-hoc图分析，则多使用RocksDB。
   

3. 利用HugeGraph-Loader将准备好的点、边数据导入到图实例中。

下图展示了社交关系图的一个局部（蓝色是玩家，红色是帮会），可以看到，游戏中大多数玩家都是围绕着帮会报团，同时，部分帮会间成员之间也存在紧密的关系。

除了社交关系图，我们还陆续构造了交易关系图，组队关系，聊天关系图等。这些图模型数据主要帮助解决了我们遇到几个问题：

• 图算法的数据源：随着图深度学习的兴起，将图深度学习方法引入到实际游戏业务中成为我们当时的一个重要关注点，算法同学可以用我们提供的图数据库很方便地批量拉取图数据。
  

• 图模式识别：MMORPG游戏中，存在着大量的交易行为，一些不法的工作室，会创建一批角色进行薅羊毛，然后将资产通过中间账号最终汇集给金主号，这种薅羊毛的行为可以抽象成图上的模式匹配。
  

• 好友推荐：利用社交关系图，图数据库可以充当好友推荐功能的核心召回链路，例如，我们可以推荐玩家的同帮会好友，两个玩家的共同好友等。

4.2 一站式图计算平台的搭建

随着业务的发展，我们发现算法同学慢慢有了更多的图数据需求，同时，工程同学同时运维多个图数据库实例会面临比较大的运维压力，为了更好地适应不同业务方的需求，我们开始着手搭建一站式的图计算平台。结合业务现状，我们制定了几个方向：

• 一站式的平台：打通用户从数据建模，数据导入，交互式查询到图分析、图计算的全链路。
  

• 云原生架构：容器化地管理系统的各模块和资源，解放运维的生产力。
  

• 多租户架构：不同租户能够通过平台自助地创建图存储实例，实例间做到资源隔离，同时支持动态扩缩容。

我们将系统拆解为了三部分：

• 图存储：支持图数据的一站式建模，导入
  

• 交互式查询：支持图存储中图数据的交互式查询
  

• OpenAPI：支持通过OpenAPI将图存储和交互式查询的能力透出给外部应用和系统

4.2.1 图存储模块

图存储模块底层基于图数据库搭建，支持实例创建，图数据建模，数据导入，交互式查询，便捷查询，图版本管理等功能。

使用图存储模块分为几个步骤：

• 数据接入：图数据一般有两种数据来源，一种是游戏数据仓库中的数据，业务方需要将数据仓库中的数据通过ETL任务加工成点、边表，然后通过平台将数据导入到图数据库实例中。第二种是外部收集的数据，例如算法同学会通过算法将收集的数据进行知识化处理，加工成实体和关系数据存储在不同的文件中，这种情况可以通过平台提供上传文件的功能，将实例和关系文件手工上传然后进行建模和导入。
  

• 数据建模：数据导入之前首先要进行数据建模，数据建模分为两部分：点建模和边建模。下图是数据建模的界面截图，用户点击添加点/添加边的按钮来创建不同类型的点边标签，每一种点和边都包含一系列的属性，对于属性还可以创建相应的索引，目前支持的索引包括二级索引、范围索引和全文检索。

• 数据导入：不同业务方对于数据导入的方式有不同的诉求，有的是离线批量导入，有的实时写入，有的希望通过平台，有的希望能够将任务部署在外部调度系统或流程中。为此我们提供了不同的导入工具：

• 通过平台导入：通过平台进行点边建模的时候，可以指定对应的图数据文件（上传或存在数据仓库），完成数据建模后在平台直接启动导入任务。
  

• 通过离线导入工具导入：平台提供了图数据导入工具（基于Java开发），业务同学可以在平台完成数据建模，不指定对应的数据文件，然后通过离线导入工具本地将数据导入到平台的图存储实例中。
  

• 通过API接口：通过OpenAPI模块的点边BatchAPI接口，用户可以将数据实时写入到图存储实例中，这种方式比较适合数据峰值流量不高，但需要频繁插入新数据的场景。

4.2.2 交互式查询

在图数据应用中，业务同学经常需要通过可视化探索的方式来查询图数据来验证查询和实验的合理性，这种场景有点类似于OLAP中的ad-hoc查询。例如，在异常交易检测场景中，经常需要检测多层级交易薅羊毛的行为，这种交易通过是从一批节点出发，通过若干中间玩家，最终汇集到金主号；又例如，玩家a通过中间玩家b，将银两转移给同伙玩家c，三个节点之间就形成了一个明显的环路。

通过交互式查询，能够很方便地探索这种模式，也可以通过这种方式来验证风控计算是否合理或者算法抓到的可疑玩家是否真的存在作弊的行为。在实际落地场景中，我们发现交互式查询是用户会频繁用到的一个功能，可视化的交互式查询也是目前世面上主流的图数据库或云服务厂商都会提供的一个核心功能。

除了上述几个主要功能，平台还提供了便捷查询来帮助用户快速配置常用的图查询（例如最短路径查询），此外，还支持图版本的管理，在实际场景中，经常存在需要对图的数据模型或建模思路进行大幅调整的情况，图版本管理能够很好的支持这种模型的演进。

4.2.3 OpenAPI

OpenAPI 通过Rest API的方式，将图存储和交互式分析的能力透出给业务方，业务同学可以根据需要将图查询的能力集成到系统中。常见的使用场景有：

• 集成到数据流，通过调度平台定时更新图数据
  

• 集成到平台，将图数据库作为后端数据库
  

• 集成到图分析程序中，离线开展各类图计算实验

  
  

目前，我们的OpenAPI模块日均处理约10万+的ad-hoc查询，基本能够满足业务方不同的图计算需求，OpenAPI也成为了一站式图计算平台的一个主要使用入口。

4.3 不同业务场景的探索

4.3.1 游戏知识图谱

知识图谱是人工智能时代很重要的一个研究分支，被广泛地应用于智能机器人、证券投资、医疗诊断和推荐系统等场景。AI在游戏中一个很重要的应用是智能问答，比如游戏内的闲聊机器人、自动客服或NPC都会用NLP的技术。知识图谱的建设是智能问答类应用不可或缺的一环，可以说知识图谱充当了智能问答机器人的『大脑』。

有灵AI是网易伏羲研发的一款文娱AI平台，有灵AI的核心能力之一有灵机器人使用图数据库来存储知识图谱，同时，通过OpenAPI接入了图相关的操作接口。用户可以在平台上在线构建知识图谱，例如创建实体和关系类型，批量上传实体和关系数据，查询实体数据等，同时还可以将定制好的知识图谱接入到智能机器人中。

4.3.2 舆情传播链

风言舆情是网易游戏的舆情风控平台，覆盖了网易100多款端手游和国内外200+渠道，平台采用先进的NLP技术，为游戏决策者提供实时、自动化的、可视化的舆情服务。平台采用了图计算技术来分析舆情传播链，目前主要的落地场景是对微博的转发链进行分析。通过指定相关话题或微博，平台能够实时计算出话题下的所有微博或单条微博被转发的关键路径，给游戏策划、运营和营销同学提供数据洞见。

4.3.3 异常交易检测

风控是图数据库最典型的一类应用，其中比较重要的一环是异常交易检测。网易伏羲智能用户画像平台集成了图计算的能力来分析玩家之间的交易链路，能够有效抓取循环交易、层级交易等作弊行为。交易图中，玩家被抽象成为图中的点，玩家之间的各种交易行为（正常的面对面交易、摆摊、玩家商店交易、红包、赠予等）被抽象成为图中的边，然后基于游戏日志进行数据加工并导入到图数据库中进行分析，分析支持指定时间区间，支持基于单层交易网络或多层交易网络进行展开。除了通过探索的方式抓取作弊行为，该工具还可以用来进行算法效果的验证，例如，算法同学通过机器学习的方法抓到一批疑似玩家，游戏策划同学可以从中选择几个玩家并通过这个工具来分析其交易链路，判断算法的效果。

5 总结和展望

目前，一站式图计算平台已经在网易游戏多个业务场景落地，业务方能够在平台上自助地创建图存储实例，进行数据建模，数据导入以及交互式的图查询。同时，多个项目和平台还通过OpenAPI的方式集成了图计算的能力，来探索更多基于图的应用。

未来我们主要计划从几个方面来优化这个平台：

• 持续优化图计算引擎，提升系统的稳定性和性能。
  

• 提升图计算平台的易用性，尤其是可视化交互式分析功能。
  

• 和业务、算法同学探索更多的图计算离在线落地场景。