有图有真相

  • 关注新蜂数字金融,ID:gh_c5ca7eb11df4

  • 这是新蜂数字金融的第86篇原创首发文章


许多大数据都是以大规模网络的形式呈现,数据中存在着大量的关联关系。作为表示和处理关系的最佳方式,图和图计算已经成为研究热点和业界关注的重点,被广泛应用于欺诈识别、社交网络分析、个性化推荐等领域。


在本文中,笔者将从图的表示、存储、查询以及分析等维度,介绍图计算的整体框架


1


什么是图?

1.1 图


在图论中,图是表示节点与节点之间关系的数学对象。图由两个要素组成:


1.节点,又称顶点,可以用来表示数据中的实体,节点上可以有属性;

2.边,表示节点之间的联系,可以用来描述数据中实体之间的关系,边上也可以有属性。


一个图G可以由一个有序二元组(V,E)来定义。其中V表示顶点的集合,E表示边的集合。边有方向的图称为有向图,边没有方向的图称为无向图,无向图可以看作每条边都有两个方向的有向图。


1.2 图的存储表示


图有两种标准的存储表示方法:邻接矩阵和邻接表


邻接矩阵的行和列表示图的顶点,矩阵中第i行第j列的元素表示从顶点vi到顶点vj的边上的信息(可以是1表示有边0表示没有边,也可以表示边的权重或者其他属性)。


邻接表是对图的每一个顶点,以列表的形式记录所有以该顶点为起点的边,每一条边需要存储的信息为终点和其他属性。


邻接矩阵的优点是可以快速判断两个顶点之间是否存在边,可以快速添加边或者删除边,但是占据的空间较多,多用于图的计算。邻接表的优点是节省空间,只存储实际存在的边,多用于图的存储。



1.3 图遍历


图遍历是指从图的一个顶点出发,沿着边的方向访问图中的其他顶点。一般分为深度优先遍历和广度优先遍历。


2


用什么存储和访问图数据?



图本质上是用来表示节点之间的关系,因此图数据的存储也就是节点和关系的存储。一个复杂的图,可能包含多种不同类型的节点,例如个人节点、公司节点等,节点之间又有不同类型的关系,例如朋友关系、同事关系、股权关系等。


这一节讨论如何用关系型数据库和图数据库实现含有多种节点和关系的图的存储和查询,并比较两类数据库的优缺点。


2.1使用关系型数据库


关系型数据库用表存储数据。存储图数据时,对于图中的每一类节点,关系型数据库分别用一张表来保存其主键和其他属性。对于图中的每一类关系,也可以用一张表来保存。


但是,不论是邻接表还是邻接矩阵,新的边的加入可能会造成其横向扩展,而这种类型的数据不适合用表来存储。


因此,关系型数据库通常不会直接存储邻接表或邻接矩阵,而是将其序列化,用表的每一行记录图中的每一条边,字段依次为起点主键、终点主键、其他属性。这种结构能防止关系表的横向扩展,并以纵向扩展的形式实现边的增减。


同时,数据分析工具可以很方便地将这种结构的关系表转换为邻接表或邻接矩阵,用于图的计算。为了防止产生数据的冗余,关系表中一般不记录或记录少部分起点和终点的属性。


关系型数据库可以用表的关联(join)操作实现图的遍历以及不同关系的合并。例如,寻找朋友的朋友,就需要对朋友关系表进行自关联;寻找同事的朋友,就需要对同事关系表和朋友关系表进行关联。如果还需要查询朋友的详细属性,则再与个人节点表关联。


2.2 使用图数据库


图数据库以图论为基础,以图结构来组织节点和关系数据。图数据库底层数据的存储方式有原生图存储和非原生图存储两种方式。


非原生图存储方式将的图数据存储在非关系型数据库(如HBase)甚至关系型数据库(如MySQL)中,在此基础上设计一套图模型,JanusGraph、HugeGraph等图数据库使用的是非原生图存储方式。


原生图存储方式将图的节点、边、属性数据直接存在本地,与图结构保持一致,这类存储经过优化,是专门为存储和管理图而设计的,Neo4j等图数据库使用的是原生图存储方式。


原生图存储在性能表现上优于非原生图存储,但在稳定性和运维上不如非原生图存储。本文讨论的图数据库主要是原生图存储的图数据库。


在图数据库中,图数据通常以邻接表的形式存储,每个节点都有指向相邻节点的指针,这有利于提高图遍历的速度。不同于关系型数据库将每一类节点和关系各存成一张表,图数据库通常以每个节点为中心,存储与该节点相连的边。


这样,进行图遍历时,只有与起点相邻的边会被访问到,减小了图遍历的查询量。图数据库数据是非关系型数据库,有自己的查询语言,用户可以用其进行图的遍历和查询,但不支持join操作。


不同的图数据库使用的查询语言不同,目前并没有类似于SQL的标准查询语言。图数据库可以将查询的结果,通过HTTP/RESTful 等API接口,为分析工具提供数据,通常提供json的格式的数据,易于转化为邻接表或者邻接矩阵。

 

2.3 图数据库的优点


与关系型数据库相比,图数据库主要的优点来源于用图结构替代了关系型数据库中低效的join操作。


1.图遍历效率高。关系型数据库使用join进行图遍历操作,对于从单个顶点出发的图遍历,关系型数据库需要对关系表进行筛选和关联,关联时会遍历整个关系表,需要过滤很多无关的数据,产生不必要的运算。


图数据库以节点为核心组织数据,进行图遍历时,只涉及与起点相关的边,进行的是局部的搜索;同时,由于每个节点都有指向相邻节点的指针,可以沿着边的方向快速访问到相邻节点。


因此,图数据库从查询数量和查询速度两方面优化了图遍历的效率,相对于关系型数据库有了显著提升。


2.擅长复杂关联。复杂关联包括多关系类型的关联、多度的关联以及两者的混合。例如查询一些公司的员工的亲属和朋友。在关系型数据库中,此类查询都会涉及大量的join操作,运行效率很低,甚至无法计算出结果。而图数据库基于局部搜索的机制,能快速完成此类查询。


3.实时查询计算。图数据库对图遍历查询可以做到秒级的实现,并通过HTTP/RESTful API进行供数,实现实时计算。


4.对图算法的支持。图数据库通常都能支持一些经典的图算法,例如最短路径、中心度指标、社区发现等。关于图算法,本文将在第四节详细展开。


2.4 图数据库的缺点


与关系型数据库相比,图数据库主要的缺点来源于节点和关系高度耦合。图数据库可以看作将关系型数据库中的一部分关系提前进行了关联,在对这些关系进行查询的时候,效率会得到极大的提高;但对没有建立边的关系进行查询时,图数据库则会显得力不从心。此外,图数据库作为新技术存在一些成熟度上的缺点。


1.非遍历查询困难。图数据库进行图遍历查询时效率高,但进行非遍历查询,即不是通过边进行关联的查询,则会很困难。例如图中并没有同乡关系的边,需要根据个人节点中的身份证号这个属性查询同乡好友。


由于没有join操作,在图数据库中实现这种查询需要对全量个人节点进行循环,会占用很大内存,而且效率低于关系型数据库。


2.全量查询没有优势。对于部分数据的查询,图数据库由于具有局部搜索的特性,能减少搜索量提升效率。而对于全量搜索,例如对某一类节点或者某一类边的所有数据进行查询计算,图数据库相对于关系型数据库没有效率上的优势,甚至更慢。


3.数据修改牵一发而动全身。在图数据库中,对已有的数据进行重构会比较复杂。例如,在个人节点中,发现有两个节点表示的是同一个人,这两个节点各记录了此人的部分关系,需要将这两个节点进行合并。


这个操作涉及到关系迁移,实现起来很复杂且易错。而在关系型数据库中,由于节点和关系用不同的表存储,处于松耦合的状态,只需要修改节点表的数据,并修改关联时的筛选条件就能实现。


4.难以保存中间结果。在进行查询时,有时候需要保存中间结果用于后续的多个查询,避免重复运行这一步查询。在关系型数据库中,可以很方便地建立一个中间表来保存。而在图数据库中,可能需要通过新增节点属性或者新增边的方式实现中间结果的保存,但这会造成对原图的修改,并不合理。


5.对内存容量要求高。原生图存储的图数据库在运行时会将部分图数据加载到内存中,这样做可以提高计算效率,但会造成内存的大幅占用。再加上需要为运行查询预留内存,图数据库对内存容量的要求远高于关系型数据库。


6.API接口少。数据库一个重要的功能就是接收来自数据分析工具、可视化工具等的查询请求并提供查询结果。很多新的图数据库都只能提供HTTP/RESTful接口,相对关系型数据库。


7.没有标准的查询语言。每一种图数据库都有自己的查询语言,没有类似关系型数据库的SQL。导致图数据库的学习成本高。


3


 如何在图数据库构建一个图?



图的构建包括图模式(Schema)设计和数据导入两部分。


3.1图模式设计


图模式类似于关系型数据库的E-R图。图模式定义了图所包含的节点、节点属性、边以及边的属性。部分图数据库支持Schemaless的方式,可以不事先设计图模式,直接在导入数据时生成图结构。


这种方式提升了图的灵活性,但是对图的维护增加了难度。此外,图的schema设计对图的查询以及计算效率有直接影响,因此建议在导入数据前进行schema设计。


进行图模式设计时,首先从数据出发,提取出其中的实体以及实体间的关系。将实体设计为图中的点,定义节点的类型、主键和其他属性。


例如个人节点,主键为身份证号,其他属性有姓名、性别等。然后将实体间的关系设计为图中的边,定义边的类型、起点类型、终点类型以及其他属性。例如股权关系,定义为从个人到企业的边,边上还可以有股权占比等属性。


这样,图模式的设计已经基本完成,然后,为了提升图查询的效率,可以结合数据分布、图的应用场景从以下三个方面进行优化:


1.建议将常查到的属性设计成单独的节点。例如将个人的省份属性设计成节点,然后将个人节点与对应的省份节点以边相连。这种处理方式可以减少查询的起点数。


2.可以根据某一属性将一类节点拆分成多类节点。例如将借记卡节点拆分成转账卡节点、专用卡节点和储值卡节点。这种处理的效果与上一种方法类似,但不会新增节点和边,多用于拆分后的几类节点所包含的关系有较大差异的情况。


3.可以根据某一属性将一类关系拆分成多类关系。例如将交易关系拆分成转账关系和消费关系。如果有较多的应用场景使用的是拆分后的其中几种关系,这种处理方式可以提升查询效率。


4.需要结合所使用的图数据库的特性对图模式设计进行优化。例如某些图数据库不支持对属性进行索引,则需要考虑上述前两条优化方式。有些图数据库区分有向边和无向边,需要结合业务逻辑以及数据情况进行有向边和无向边的选择。


3.2数据导入


数据导入的流程可以参考所使用的图数据库的文档。通常节点数据来源于关系型数据库中的节点表,关系数据来源于关系型数据库中的关系表。


图数据库修改数据牵一发而动全身,而且图数据库通常带有前端展示界面,能直观地展现数据中的错误,因此图数据库对数据的质量要求很高,需要对数据进行仔细检验。

 

4


图数据怎么分析?



图数据的分析通常基于邻接矩阵或者邻接表,关系型数据库和图数据库都可以提供相应的数据,因此图数据的分析不依赖于底层数据库的选择。


但是,使用图数据库将带来两个方面的提升:1. 图数据库由于优化了图的存储和遍历查询,可以直接使用其查询语言实现部分基于图遍历的图算法;2. 图数据库能够进行复杂关联,可以为建模提供更多种类的查询结果。


本节介绍图数据的分析和挖掘,讨论算法和模型的原理、应用场景、优缺点、以及图数据库的作用。


4.1 最短路径


最短路径是计算一个节点到目标节点的最短路径。原理是以起始点为中心向外层层遍历,直到扩展到终点为止。


4.1.1 Dijkstra算法


计算最短路径常用的方法为Dijkstra算法,它按照特定的顺序计算每个节点与起点之间的最短距离,直至找到目标节点。对于所有边的权重为非负值的图,它能够得到最优解。


4.1.2 Bellman-Ford算法/SPFA算法


Dijkstra算法无法用于带有负权重的边的图。对于这类图,在没有负回路的情况下,可以使用Bellman-Ford算法计算最短路径。SPFA算法是Bellman-Ford算法的队列优化版本。


4.1.3 A*算法


Dijkstra算法的另一个问题是遍历的范围较大,效率低。A*算法加入了当前节点与目标节点最短路径的估计函数,优化目标为g(n)+h(n),其中g(n)为当前节点与起点的距离,h(n)为当前节点与目标节点的最短路径的估计。h(n)的存在能减少与目标节点背道而驰的搜索,减少搜索的范围,提高效率。A*算法的难点在于h(n)的设计和优化。


4.1.4 Floyd-Warshall算法


Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。通常可以在任何图中使用,包括有向图、带负权边的图。这种算法计算量很大,不建议在规模较大的图中使用。


最短路径常用于计算关系的远近,或者作为部分图指标的基础。最短路径算法可以在图数据库中通过图遍历查询实现(其中A*算法需要保证h(n)能在图遍历查询时可计算)。


4.2 图指标


图指标指的是根据图的结构计算得到的节点或边的值,可用于量化节点或边的重要程度,也可以以变量的形式作为机器学习模型的输入。


4.2.1 节点的度


度(Degree)是最简单的图指标,分为出度和入度,一个节点的出度是以该节点为起点的边的数量,一个节点的入度是以该节点为终点的边的数量。出度和入度可以作为评价节点重要性的指标,可以用于识别超级节点,也可以用于图遍历查询的计算量评估。图数据库通常都有计算出度和入度的函数。


4.2.2 基于路径的图指标


1.接近中心度(ClosenessCentrality):接近中心度计算的是一个节点与其他所有节点的最短路径的平均值的倒数。接近中心度是节点的图指标,它可以用于衡量某一节点与其他所有节点之间的接近程度。


2.中介中心度(BetweennessCentrality):中介中心度计算的是经过某个节点的最短路径的数量。中介中心度也是节点的图指标,用于衡量某一节点在图的路径中的重要程度。


这两类中心度算法可以在图数据库中通过图遍历查询实现。


4.2.3 基于图传播算法的图指标


图传播算法是根据图结构进行图指标自我更新迭代的一类算法。它的原理是根据业务逻辑和经验假设,利用相邻节点和边循环更新图指标,最终收敛到稳定值。这类算法中最经典、最简单的就是PageRank算法。

 

PageRank算法


PageRank算法计算的目标是每个网页节点的排名值PageRank。根据业务逻辑,它的经验假设是:


  • 被更多网页链接到的网页更重要

  • 被重要的网页链接到的网页更重要

  • 有更少外链的网页将会传递更高的权重


根据这三条经验假设,PageRank值的循环更新函数是,即网页的PageRank值等于所有连接到该网页的PageRank值的加权和,其中权重反比于网页的外链数。初始时设所有网页节点的PageRank值都相等且和为1,每一次循环遍历全图更新每个网页节点的PageRank值,直至稳定。


PageRank算法为了提高收敛稳定性还加入了随机跳转,计算PageRank值时也有不同的优化算法。PageRank的核心是图传播算法,而且是图传播算法中最简单的一种。


复杂的图传播算法可以同时计算多个图指标,包括节点的图指标和边的图指标。图传播算法为图指标的计算提供了一种体系化的方法。


它的优点是算法遵循业务逻辑和经验假设,可解释性强,并且可以为边计算图指标,为某种关系进行量化


缺点是对于规模较大的图,全量循环迭代需要很长的计算时间,即便是最简单的PageRank算法,由于互联网的网站节点规模巨大,谷歌也是隔一段时间更新一版,因此不建议在规模较大的图中使用。


图传播算法的难点是业务逻辑和经验假设的抽取,以及构建的循环更新函数需要符合经验假设且循环更新时能稳定收敛,这需要业务专家和模型专家的共同努力。


图传播算法可以在图数据库中实现,但是建议复杂的图传播算法在数据分析工具中实现,因为可以使用邻接矩阵对计算方式进行优化,且图传播算法通常涉及的节点和关系类型不多,使用图数据库没有优势。


4.3 社区检测


社区检测指的是把图分为多个社区,将各个节点划分到其中一个社区的算法,可以看作是基于图结构的聚类算法。


社区检测算法的一般模式是,先将每个节点视为一个独立的社区,然后根据某种方式,将每个节点分配到相邻节点所在的社区,直至所有节点所分配到的社区不再变化。经典的社区检测算法包括Label Propagation和Louvain算法。


1.Label Propagation算法采用投票的方式进行节点的分配,将每个节点分配到其相邻节点中出现最多次的社区,如果出现并列第一,则随机选择一个社区赋给该节点。这个算法简单高效,但是存在随机性,导致每次运行结果可能有差异,利用边上的权重信息进行投票可以改善这个问题。


2.Louvain算法定义了模块度Q,表示社区内连边数与随机期望值的差,这个值用于衡量社区划分的好坏。Louvain算法在进行节点的分配时,会依次尝试将某个节点分配到其相邻节点所在的社区,计算分配前后的的Q值变化,如果分配后Q值变大,则说明这个节点与这个社区联系紧密。


因此,Louvain算法将每个节点分配到Q值变大最多的社区,如果没有一种分配能使Q值变大,则不改变原来的划分。Louvain算法的计算速度也比较快。


社区检测算法适合使用图数据库实现,它可以有效地识别节点的群体性特征,也可以用于为后续的图计算和建模进行数据的筛选,缩小分析范围。


4.4 图数据辅助机器学习


机器学习是数据分析领域的一个热点。图数据可以为机器学习带来三个方面的帮助:


1.搜索特殊的图结构,为监督学习提供正样本。在一些应用场景例如反套现中,确定为套现客户的数量很少,这会降低机器学习的准确性。


利用图数据库以及图遍历查询,可以根据特定的规则,即特定的图结构,来识别疑似套现客户和疑似套现行为,这些疑似套现客户和疑似套现行为会被进一步确认是否属于套现,从而为机器学习的分类模型提供正样本。


2.利用图指标,为机器学习提供基于图特征的变量。使用上文的算法计算出图指标后,可以将图指标与节点的其他属性结合,输入机器学习模型。


3.对图数据进行机器学习。例如融合节点的图结构信息与其他特征信息,进行节点分类。典型的代表为图卷积神经网络GCN。


4.4.1 图卷积神经网络


GCN的输入包括:

1.节点的图结构信息,通常是稍作变换的邻接矩阵A;

2.节点的其他特征,可以写成节点数*特征数的矩阵H。


GCN的目标是对图的节点进行分类。

GCN的为多层神经网络,每一层的传播规则为:

其中为D节点度的对角矩阵,A为主对角线变为1的邻接矩阵,H为第l层特征矩阵,W为第l层的系数矩阵,f为非线性激活函数。  


一层内部的操作可以理解为:首先进行图结构的标准化,然后将标准化后的图结构与特征矩阵相乘(称为卷积),在将卷积后的特征矩阵与系数相乘,并用非线性函数激活,作为下一层的特征矩阵。


GCN模型的特点包括:1. 卷积核不需要训练,直接由图的邻接矩阵变化得到;2. 将节点的图结构与其他特征相乘的操作称为卷积,这个操作的本质为将相邻节点的特征加到自身的特征中;3. 第一层利用了一度邻居的特征,第二层利用了二度邻居的特征,以此类推。


GCN的优点是适用于任意拓扑结构的节点与图,能同时学习到节点的结构信息和特征信息,适合图数据的学习。GCN的缺点与其他的神经网络一样,即可解释性差。


笔者认为,图卷积的思想可以延申到其他的机器学习模型。例如将图卷积后的特征矩阵作为逻辑回归、随机森林等模型的输入。


由于图卷积后的特征矩阵具备可解释性(例如个人节点卷积后的年龄变量表示此人关系圈的平均年龄),这类模型的可解释性较好,可以作为应用的选择。


4.5 图数据与推荐系统


经典的协同过滤推荐系统都是基于用户-商品矩阵进行建模,而用户-商品偏好矩阵可以看作一种关系的邻接矩阵。


用户-商品矩阵的构建上存在两个难点:1.只有用户与商品存在直接关系的情况下,矩阵的相应位置非零,导致矩阵极为稀疏,对于新用户还存在冷启动问题;2.用户和商品的关系中需要包含能够反映用户对商品偏好的信息。


利用图数据,可以基于全图的信息来量化用户对商品的偏好,解决上述两个难点。常用的有两种方法:


1.基于路径量化用户对商品的偏好,例如通过用户-朋友关系-朋友-购买关系-商品这类路径对偏好进行建模;


2.基于图的结构量化用户对商品的偏好,例如通过用户至少有十个朋友都购买某商品这类图结构对偏好进行建模。


偏好矩阵建议使用图数据库进行构建,因为图数据库可以通过图遍历快速定位到指定模式的路径或图结构。针对新用户的冷启动问题,可以基于图的信息量化其对商品的偏好后直接进行推荐,也可以进一步在协同过滤建模后进行推荐。


5


写在最后



写到最短路径的时候,笔者想起自己以前为了用A*算法玩滑块拼图,从零开始自学了Python,在无意中掌握了一项在日后的学习和工作中所需的重要技能。


这篇文章是笔者对最近所学的整理,希望能给各位读者带来一些思考和启发,各位未来若能用到文中知识,岂不妙哉!



延伸阅读:

原创:今天到银行“存款”,明天会到银行“存数”吗?

原创:GFT的成功与错误

原创:普惠金融与数字化风控

原创:聊一聊上海楼市的真实现状

原创:知否知否应是卫私驭数




     

   微信扫一扫,关注我


              觉得好,请点“好看”

文章转载自微信公众号:新蜂数字金融

类似文章