图何以嵌入

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

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



图(Graph)是由顶点集合(Vertex)及顶点间的关系集合(Edge)组成的一种数据结构,即由点和边联结而成的网络,是现实生活中关联数据的自然表示

由用户和用户之间的关注点赞转发等构成的社交网络,由学者、论文和他们之间的合作、引用关系构成的学术网络,由买卖双方、商品构成的电商网络等等,其数据特征都可以用图结构进行描述。
 
对于图结构的分析可以获得关于网络丰富的信息,但传统的研究方法大多伴随着较高的计算成本和空间存储成本。

针对这些问题,一部分学者提出了分布式图数据处理框架,或是有效利用空间进行图存储等方法;还有一部分学者转换思维方式,提出了将非结构化的高维图数据,“嵌入”到相对低维数据空间中的解决方案,即进行图嵌入(Graph Embedding)


01. 什么是图嵌入


一般而言,对于图,V是顶点的非空有限集合,E是顶点之间关系的有穷集合,也叫边集合。
 
所谓图嵌入,即给定一个作为输入的图,和事先定义好的嵌入维度d(满足),在最大限度保留图中信息的前提下,将图G转换至d维空间进行表示的过程。

按照表示粒度的不同,可以对整张图或图中的元素(例如节点、边、子图等)进行上述的转换过程,最终将图结构表示为一个d维向量或一组d维向量的集合,如下图所示。

图1.不同粒度的图嵌入

 

图嵌入研究可以说隶属于两个范围更广的研究领域——图分析和表示学习

一方面,图嵌入的本质就是对图进行分析,目的是从图数据中挖掘出有用的信息。
 
另一方面,图嵌入也是表示学习的一个细分领域,对数据进行特征表示(向量化)后,可以作为其他机器学习算法的前置输入,进一步进行分类、预测等任务。

两者的不同在于,图嵌入要求嵌入维度d远小于输入样本的特征维度,同时不依赖于基于专家知识的特征工程;而表示学习对最后生成的特征向量维度没有限制,同时包含有监督和无监督的特征工程,是一个更大的范畴。

图嵌入具有十分广泛的应用场景。按照图的粒度,可以大致作如下区分:
   1、与节点相关的应用,例如节点分类、节点聚类、节点的推荐或排序等。
   2、与边相关的应用,例如链路预测、关系重构等。
   3、与图相关的应用,例如图的分类、可视化等。
 
其他的应用场景还包括:基于知识图谱的网页搜索问答,寻找网络传播中的关键节点,社交网络之间实体的对齐等等。
 
总之,图嵌入算法为图的分析研究提供了一种全新的思路。

通过将图中的信息转换至相对低维的数据空间中进行向量表示,一方面可以对向量进行数学运算,实现对图数据的深度挖掘;另一方面也完成了对图数据的特征加工,在非结构化的图数据与机器学习算法之间搭建了一座桥梁


02. 图嵌入算法有哪些


上文中提到,图嵌入过程是一个将图中的元素嵌入到相对低维空间中,获得低维稠密向量表示的过程。在这个转换过程中,算法需要最大限度地保留图中原有的信息。

具体来说,用什么样的指标来衡量图中元素的相似性(即刻画元素的相对位置),以及用怎样的方法来将这些图中原有的信息最大程度的保留下来,体现在低维的嵌入空间中,则构成了不同的图嵌入算法
 
我们可以按照图嵌入的具体方法,大致将部分主流的图嵌入算法分为六类:矩阵分解算法、深度学习算法、边重构算法、图的核方法、生成模型、混合模型及其他。
 
2.1  矩阵分解算法
 
基于矩阵分解的图嵌入方法中,通常将需要保留的图中信息用矩阵来进行表示,例如由原始数据获得节点之间的相似性矩阵,作为模型的输入;接着对矩阵做分解并获得节点的嵌入向量。

根据目标函数的不同,可以进一步将这类方法分为,对图的拉普拉斯特征映射进行分解和直接分解节点相似性矩阵的方法。常见的算法有MDS、Isomap、GraRep、RESCAL等。


图2.矩阵分解
 
2.2  深度学习算法
 

深度学习的研究方法在计算机视觉、语言建模等领域已经取得了丰硕的成果。学者们开始尝试将一些现有的深度学习模型进行拓展并应用于图嵌入,或是根据图的特征,设计出为图数据“量身定制”的新模型。


根据是否基于随机游走在图中作路径采样的工作,可以将基于深度学习的图嵌入方法进一步分类。常见的算法有DeepWalk、node2vec、metapath2vec、SDNE、GCN等。


DeepWalk算法是词嵌入算法word2vec在图上的拓展。将节点类比为单词,(等概率)随机游走得到的节点序列作为句子,能够刻画节点的共现关系。


图3.DeepWalk
 
Node2vec模型是对DeepWalk模型的改进,实现了非等概率的随机游走。假设上一步节点为t,当前处于节点v,则下一步游走概率??满足:

其中d表示x与t的距离。

图4. Node2vec
 
通过调节p、q能够控制游走的广度优先(BFS)和深度优先(DFS)搜索,分别实现周边局部结构的远端整体结构的优先捕捉。

图5. BFS和DFS

图卷积神经网络是一般卷积神经网络在图数据上的推广,能同时对节点特征信息与结构信息进行端对端学习,适用于任意拓扑结构的图网络。

图6.GCN(图卷积神经网络)

2.3 边重构算法
 
基于边重构的图嵌入算法,其核心思想是:通过节点嵌入向量重构的边要与输入的图数据尽可能的一致。因此这类算法的目标函数有两种设计方向,一是最大化边重构的概率,二是最小化边重构的损失。代表性的模型有LINE、TranE、TransR等。


图7.TransE模型的优化目标是让,其中h、r、t分别代表头节点(head)、关系(relation)和尾节点(tail)的向量。
 
 2.4  核方法
 
图的核方法则尝试用一些原子结构来对整张图的结构进行分解,图嵌入向量的每一维表示相应原子结构的“成分比例”。当需要对两张图进行比较分析时,可以直接对嵌入向量做内积等运算。

常见的图核有:小图(Graphlet)、子树(Subtree Patterns)和随机游走路径等。

图8.三元Graphlet示例
 
2.5  生成模型
 
给定一组参数,生成模型可以用一系列输入特征和类别标签的条件联合分布来进行定义。
   
潜在狄利克雷分布(LDA)就是一个典型的生成模型,它将一段文本的生成过程解释为:以一定概率选取某个主题,再以一定概率选取该主题下的某个单词,重复上述两个步骤则最终可生成一篇完整的文章。

图9.LDA示例

由此联想到,文章可以“嵌入”到主题空间中,用主题向量来进行表示,文章中出现的词语重合度越高,文章的主题向量越相似。

例如,可以将某个与位置有关的社交网络设计成类似LDA的模型,输入一组位置(文章),每个位置都包含了曾访问过这里的用户(组成文章的单词);用户访问某个地址的行为可能基于某些特定的活动(主题),最终可以将用户和位置都表示为“活动空间”中的向量,实现图的嵌入。

2.6  混合算法及其他
 
有些图嵌入算法是多种算法模型的融合。

例如设计用于推荐系统的CKE(Collaborative Knowledge Base Embedding)模型中,作者首先采用TransR模型对用户和推荐对象构成的电商网络进行图嵌入,接着用自编码器(AE)对文本和图像信息进行向量化,以此来将网络、文本和图像三方面的对象信息整合为推荐对象的语义表示向量,最后实现了一个协同过滤的总体框架,有效地提升了推荐系统的质量。
 
还有一些算法例如:KR-EAR在知识图谱中用不同的模型方法刻画了实体之间由属性构成的关系和由关系边构成的关系;struc2vec模型则提出了一个能够捕捉节点所处结构特征的嵌入算法,等等。



03. 写在最后



不同的图嵌入算法各有优缺点,需要根据应用场景的不同合理选用或改进相应的模型。
 
矩阵分解考虑了全局的节点相似性,但对时间和空间资源消耗非常大。

深度学习模型往往是有效且具有鲁棒性的,但无论是基于随机游走的模型存在的“局部最优”问题,还是不基于随机游走的全图嵌入模型中,高计算代价的问题,实际使用时都应纳入考虑。

边重构方法在模型训练过程中是相对高效的,但也存在一定的“局部最优解”问题。

图的核方法效率较高,缺点在于子结构的非独立性和嵌入维度的指数增长。

对于生成模型来说,其嵌入结果具有可解释性,但模型的训练需要大量的样本,可能不适用于小规模的图,同时也很难验证分布选择的正确性。
 
总之,图嵌入算法还有非常巨大的研究潜力和空间。如何提高模型训练效率,创新模型构造方法,将图嵌入的思想应用于更多的学科领域和生产实践,唯有通过更进一步的研究,才能找到更好的答案。
 



参考资料:
1.A Comprehensive Survey of GraphEmbedding: Problems, Techniques and Applications
2.Deepwalk: Online learning of socialrepresentations
3.Node2vec: Scalable feature learning fornetworks
4.Translating embeddings for modelingmulti-relational data
5.Learning from your network of friends: Atrajectory representation learning model based on online social ties
6.A Survey on Graph Kernels

延伸阅读:

原创:从复杂网络看新冠疫情

原创:沉默的那些数

原创:战“疫”中的统计分析模型

原创:隔离期,我在家想了两件事

原创:从疫情看智慧城市






   微信扫一扫,关注我


              点击“在看”,

武汉加油,中国加油!

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

类似文章