猜歌名论⽂研读-图嵌⼊-2018综述
图嵌⼊综述论⽂研读
⼀、论⽂概述
这是⼀篇2018年发表在IEEE知识与数据⼯程汇刊上的图嵌⼊的综述,论⽂题⽬为A Comprehensive Survey of Graph
Embedding:Problems, Techniques, and Applications。如题⽬所⽰,主要对图嵌⼊问题中存在的挑战、现有的⼀些技术和应⽤场景进⾏了总结。
1 ⽂章摘要
图是⼀种重要的数据表⽰形式,它出现在各种现实场景中。有效的图分析可以让⽤户更深⼊地了解数据背后的内容,从⽽受益于许多有⽤的应⽤,如节点分类、节点推荐、链接预测等。然⽽,⼤多数图分析⽅法都有很⾼的计算和空间成本。图嵌⼊是解决图分析问题的⼀种有效⽽⾼效的⽅法。它将图形数据转换成⼀个能最⼤限度地保留图形结构信息和图形属性的低维空间。在这项调查中,我们对图嵌⼊的⽂献进⾏了全⾯的回顾。
1. ⾸先介绍了图嵌⼊的形式化定义及其相关概念。
2. 在此之后,我们提出了图嵌⼊的两种分类,它们对应于在不同的图嵌⼊问题设置中存在哪些挑战,以及现有的⼯作如何在它们的解决
⽅案中解决这些挑战。
3. 最后,从计算效率、问题设置、技术和应⽤场景四个⽅⾯总结了图嵌⼊的应⽤,并提出了未来的研究⽅向。
2 关键词
图嵌⼊:Graph embedding
图分析: graph analytics
图嵌⼊调查:graph embedding survey
⽹络嵌⼊: network embedding
王者荣耀特殊名字
同构图:homogeneous graph
异构图:heterogeneous graph
带有辅助信息的图:graph with auxiliary information
由⾮关系数据构造的图:graph constructed from non-relational data
知识图:knowledge graph
3 ⽂章脉络
1. 理解图嵌⼊问题所需的基本概念的定义,并给出了图嵌⼊问题的形式化定义,提供了图嵌⼊的两个分类。
2. ⽐较了基于问题设置的相关⼯作,并总结了在每个设置中所⾯临的挑战。
3. 根据嵌⼊技术对⽂献进⾏分类。每⼀种技术背后的见解都被抽象出来,并在最后提供了不同技术的详细⽐较。
4. 介绍图形嵌⼊⽀持的应⽤。
5. 讨论了四个潜在的未来研究⽅向.
6. 总结了本研究。
烧猪肉的家常做法4 ⽂章贡献
1. 基于问题设置将图嵌⼊分成两类,并总结了在两类问题中所⾯临的挑战。
2. 详细的分析了图嵌⼊技术,对图嵌⼊⼯作进⾏了全⾯的调查,⽽且给出了每个技术背后的知识,回答了为什么图形嵌⼊可以以某种⽅
式解决的问题。
3. 系统地对图嵌⼊的应⽤进⾏了分类,并将其划分为与节点相关、与边相关和与图相关的应⽤。对于每个类别,提供了详细的应⽤场景
免费听睡前故事作为参考。
4. 从计算效率、问题设置、求解技术和应⽤四个⽅⾯提出了未来在图嵌⼊领域的研究⽅向和⽬前⼯作中的不⾜之处。
⼆、图嵌⼊是什么
1 简单概念
解决问题:⼀种解决图分析问题的有效⽅法
概念:图嵌⼊将⼀个图转换成⼀个低维空间,其中的图信息被保留。通过将⼀个图表⽰为⼀个(或⼀组)低维向量,可以有效地计算图算法。
输⼊:由于图的类型不同(如同构图、异构图、属性图等),在不同的场景下,图嵌⼊的输⼊也不同。
输出:图嵌⼊的输出是表⽰图的⼀部分(或整个图)的低维向量。
单板公园关于不同类型的图嵌⼊输⼊和输出的更多细节在⽂章第3节中提供。
2 形式化定义
同构图(homogeneous graph):节点和边都只有⼀个类型。
异构图(heterogeneous graph):节点和边都有两种及以上的类型。
知识图(knowledge graph):⼀个有向图,节点是实体,边是⼀个三元组。每条边的形式为头实体、关系、尾实体,记为< h,r,t >,指从实体h到实体t中有关系r。
知识图中的实体和关系通常是不同类型的。因此,知识图可以看作是异构图的⼀个实例。
如何量化嵌⼊空间中要保留的图属性
1. ⼀阶邻近度是指仅由边连接的节点之间的局部成对相似度,它⽐较⼀个节点对之间的直接连接强度。在形式上,如果两个节点之间的
边具有较⼤的权值,则两个节点之间的关系更相似。
vi与vj的⼀阶邻近度为图G的邻接矩阵中的第i⾏第j列的元素,即边eij的权重。
vi与其他节点之间的⼀阶邻近度为图G邻接矩阵A的第i⾏
2. ⼆阶邻近度⽐较节点的邻近结构的相似性。两个节点的邻域越相似,它们之间的⼆阶邻近值越⼤。在形式上,vi与vj的⼆阶邻近度为vi
与vj的与其他节点⼀阶邻近度的相似度。
3. ⾼阶邻近度,类似的,vi与vj的k阶邻近度为vi和vj的与其他节点的k-1阶邻近度的相似度。也可以使⽤Katz Index, Rooted
PageRank, Adamic Adar等来度量。
注:在⼀些⼯作中,⼀阶近似和⼆阶近似是根据两个节点的联合概率和条件概率经验计算的。
图嵌⼊问题的形式化定义:
给定⼀个图的输⼊G = (V,E),并预先定义了嵌⼊的维度d (d << |V|)。图嵌⼊问题是将G转换成⼀个d维空间,在这个空间中尽可能保留图的属性。图属性可以使⽤邻近度量,如⼀阶和⾼阶邻近度来量化。每个图可以表⽰为⼀个d维向量(对于整个图)或⼀组d维向量,每个向量表⽰图的⼀部分(如节点、边、⼦结构)的嵌⼊。
3 图嵌⼊发展
21世纪初,图嵌⼊算法主要是通过假设数据处于低维流形中来降低⾮关系型数据的⾼维特征。(降维)
从2010年开始,图的嵌⼊研究开始以图为输⼊,利⽤辅助信息(如果有的话)来⽅便嵌⼊。(图嵌⼊)
1)有些算法关注于将图的⼀部分(如节点、边、⼦结构)(图1b、1c和1d)表⽰为⼀个向量。
怎么写观后感实现⽅法:最先进的深度学习技术(章节4.2);设计⼀个⽬标函数来优化边缘重建概率(章节4.3)。
2)也有⼀些⼯作集中于将整个图嵌⼊为⼀个向量(图1e)的图级应⽤。
图的嵌⼊问题与两个传统的研究问题有关,即图分析[8]和表⽰学习[9]。
投影仪安装方法三、图嵌⼊问题设置
图嵌⼊的挑战取决于问题设置,问题设置包括嵌⼊输⼊和嵌⼊输出。本⽂基于问题设置将图嵌⼊分成两类,并总结了在两类问题中所⾯临的挑战。
1 嵌⼊输⼊
图嵌⼊的输⼊是⼀个图。
在本研究中,我们将图嵌⼊输⼊分为四类:同构图、异构图、带辅助信息的图和构造图。不同类型的嵌⼊输⼊需要在嵌⼊空间中保留不同的信息,从⽽对图嵌⼊问题提出了不同的挑战。接下来,我们将介绍这四种类型的输⼊图,并总结在每种输⼊设置中⾯临的挑战。
同构图
第⼀类输⼊图是同构图(Homogeneous Graph),其中节点和边都只有⼀个类型。同构图可以进⼀步分为有权(或有向)图和⽆权(或⽆向)图。
⽆向⽆权同构图是最基本的图嵌⼊输⼊设置。很多研究都是在这种背景下进⾏的。它们平等地对待所有节点和边,因为只有输⼊图的基本结构信息是可⽤的。
从直观上看,边的权值和⽅向提供了更多关于图形的信息,可以帮助在嵌⼊空间中更准确地表⽰图形。这些信息丢失在⽆权⽆向图中。图嵌⼊群体注意到利⽤图边的权值和⽅向特性的优点,开始探索权值图和/或有向图。
有些只关注⼀个图属性,即边权值或边⽅向。⼀⽅⾯考虑图,由权重较⾼的边连接的节点嵌⼊得更近。然⽽,他们的⼯作仍然局限于⽆向图。另⼀⽅⾯,有些作品在嵌⼊过程中获取边缘的⽅向,并在嵌⼊空间中保留⽅向信息。
最近,提出了⼀种更通⽤的图嵌⼊算法,该算法同时考虑了权值和⽅向属性。换句话说,这些算法既可以处理有向图,也可以处理⽆向图,也可以处理加权图和未加权图。
挑战:如何捕捉图中观察到的连接模式的多样性?由于同构图中只有结构信息可⽤,同构图嵌⼊的挑
战在于如何保留嵌⼊过程中在输⼊图中观察到的连通性模式。
异构图
第⼆类输⼊是异构图(Heterogeneous Graph),它主要存在于以下三个场景中。
以社区为基础的问答(cQA)⽹站。直观地说,cQA图中有不同类型的节点,例如,问题、答案、⽤户。现有的cQA图嵌⼊⽅法在利⽤的链接⽅⾯存在差异,其中(i,j,k,o,p)表⽰,对于问题i,⽤户k提供的第j个答案⽐⽤户p提供的第o个答案获得更多的投票(即点赞)。
多媒体⽹络。多媒体⽹络是包含多媒体数据(如图像、⽂本等)的⽹络。某些⽂献嵌⼊了包含两种类型节点(图像和⽂本)和三种类型链接(图像-图像、⽂本-⽂本和图像-⽂本)的图形。有些⼯作利⽤⽤户图像链接将⽤户和图像嵌⼊到同⼀个空间中,从⽽可以直接⽐较它们,进⾏图像推荐。有的⼯作中考虑了⼀个包含图像和⽂本查询的点击图。图像查询的边表⽰给定查询的图像的点击,边权重为点击次数。
知识图谱。在知识图中,实体(节点)和关系(边)通常是不同类型的。例如,在电影相关知识图中,实体的类型可以是“导演”、“演员”、“电影”等。关系的类型可以是“创作”、“导演”、“扮演”。在知识图的嵌⼊⽅⾯已经做了⼤量的⼯作。
其他的异构图。例如,有些⼯作是流动数据图,其中站点(s)、⾓⾊( r )和公司( c)节点通过三种链路(s-
s、s-r、s-c)连接。还有⼯作嵌⼊了⼀个包含三种节点实体(e),类别( c)和词(w)和三种边(e-e, e-c, w-w)的维基百科图。除上述图外,还有⼀些⼀般的异构图,其中节点和边的类型没有明确定义。
挑战。如何探索不同类型对象之间的全局⼀致性,以及如何处理不同类型对象之间的不平衡(如果存在的话)?在异构图嵌⼊中,不同类型的对象(如节点、边)被嵌⼊到同⼀个空间中。如何探索它们之间的全局⼀致性是⼀个问题。此外,不同类型的对象之间可能存在不平衡。这种数据偏倚应该在嵌⼊时加以考虑。
带辅助信息的图
第三类输⼊图除了包含节点的结构关系(即E)外,还包含节点/边/全图的辅助信息。⼀般有五种不同类型的辅助信息。
标签。带有不同标签的节点应该彼此远离地嵌⼊。为此,[47]和[48]结合分类器函数共同优化嵌⼊⽬标函数。Shervashidze等⼈[49]对具有不同标签的节点之间的相似性进⾏惩罚。Nikolentzos等⼈[50]在计算不同的图核时考虑了节点标签和边缘标签。Guo等⼈的
[51]和[52]嵌⼊了⼀个知识图,其中的实体(节点)有⼀个语义类别。Xie等[53]以层次结构的实体类别嵌⼊了更为复杂的知识图谱,
如“图书”类别有两个⼦类别“作者”和“书⾯⼯作”。
属性。与标签不同,属性值可以是离散的,也可以是连续的。例如,[54]嵌⼊了⼀个带有离散节点属性值(例如,分⼦中的原⼦序数)的图。⽽[4]则将节点属性表⽰为⼀个连续的⾼维向量(如社交⽹络中的⽤户属性特征)。Niepert等⼈[55]处理节点和边的离散和连续属性。
节点特征。⼤多数节点特征都是⽂本,⽂本可以作为每个节点[56]、[57]的特征向量提供,也可以作为⽂档[58]、[59]、[60]提供
[61]。对于后者,对⽂档进⾏进⼀步处理,使⽤词袋[58]、主题建模[59]、[60]等技术提取特征向量,或将“word”作为⼀种节点
[61]。其他类型的节点特征,如图像特征[33],也是如此。
信息传播。信息传播的⼀个例⼦是Twitter上的“retweet”。在[63]中,给定数据图G¼ðV;EÞ,对每个级联c构造⼀个级联图Gc¼ðVc;EcÞ,其中Vcare是Vc中采⽤c的节点,care是Vc中两端的边。然后嵌⼊Gcto来预测级联⼤⼩的增量。不同的是,[64]的⽬的是嵌⼊⽤户和内容信息,他们嵌⼊的相似性表明扩散概率。Topo-LSTM[65]认为级联不仅是节点序列,⽽且是动态的有向⽆环图,⽤于嵌⼊。
知识库。流⾏的知识库包括Wikipedia[66]、Freeba[37]、YAGO[67]、DBpedia[68]等。以Wikipedia
为例,概念是⽤户提出的实体,⽂本是与实体相关联的⽂章。Yang等[66]通过将每个社会⽹络⽤户连接到⼀组给定的知识概念,利⽤知识库学习⼀个社会知识图。Xiong等⼈[69]在实体空间(由知识库提供)中表⽰查询和⽂档,使学术搜索引擎能够在查询中理解研究概念的含义。
其他类型的辅助信息包括⽤户签到数据(ur-location)[70]、⽤户项⽬偏好排名列表[71]等。
注意,辅助信息不仅限于⼀种类型。例如,[62]和[72]同时考虑标签和节点特征信息。Pan等[73]利⽤节点内容和标签来辅助图形嵌⼊过程。
挑战:如何整合丰富的⾮结构化信息,使学习到的嵌⼊既能表⽰拓扑结构,⼜能区分辅助信息?除了图结构信息外,辅助信息还有助于定义节点相似性。嵌⼊辅助信息图的挑战是如何结合这两个信息源来定义要保留的节点相似度。
构造图
最后⼀类输⼊图是通过不同的策略从⾮关系的输⼊数据中构造⽽成。这通常发⽣在假设输⼊数据位于低维流形中时。
基于节点间两两相似度构造节点之间的边。
根据节点的共现建⽴节点之间的边。
还针对不同的⽬的设计了其他的图构建策略。
1. 构建了⼀个内在图来捕获类内紧性,和⼀个惩罚图来刻画类间可分离性。前者是通过将每个数据点与同类的相邻数据点连接起来构建
的,⽽后者是通过连接不同类的边缘点构建的。
2. 构造了⼀个有符号的图来利⽤标签信息。如果两个节点属于同⼀个类,则⽤⼀条正边连接;如果它们来⾃两个类,则⽤⼀条负边连
接。
3. 将所有具有共同标签的实例包含到⼀个超边中,以捕获它们的共同相似性。
4. 构造了两个反馈图,在嵌⼊后将相关的对聚集在⼀起,将不相关的对隔离。在正图中,如果两个节点都相关,则两个节点是连接的。
在负图中,只有当⼀个节点是相关的,另⼀个节点是不相关的,两个节点才连接起来。
挑战。如何构造⼀个对实例之间的关系进⾏编码的图,以及如何在嵌⼊空间中保留⽣成的节点邻近矩
阵?嵌⼊由⾮关系数据构造的图所⾯临的第⼀个挑战是如何计算⾮关系数据之间的关系并构造这样的图。在构造图之后,问题与其他输⼊图相同,即如何在嵌⼊空间中保持构造图的节点邻近性。
2 嵌⼊输出
图嵌⼊的输出是表⽰⼀个图的(部分)低维向量的(集合)。
根据输出粒度,我们将图嵌⼊输出分为节点嵌⼊、边缘嵌⼊、混合嵌⼊和全图嵌⼊四种类型。不同类型的嵌⼊⽅便不同的应⽤。与固定给定的嵌⼊输⼊不同,嵌⼊输出是任务驱动的。例如,节点嵌⼊可以使各种与节点相关的图分析任务受益。然⽽,图分析任务并不总是在在某些场景中,任务可能与图的更⾼粒度相关,例如节点对、⼦图,甚⾄整个图。因此,在嵌⼊输出⽅⾯的第⼀个挑战是如何找到⼀种适合的嵌⼊输出类型,以满⾜特定的应⽤任务的需要。
节点嵌⼊
作为最常见的嵌⼊输出设置,节点嵌⼊将每个节点表⽰为低维空间中的向量。图中“接近”的节点被嵌⼊以具有类似的向量表⽰。不同的图嵌⼊⽅法的区别在于它们如何定义两个节点之间的“紧密性”。⼀阶邻近度和⼆阶邻近度是两种常⽤的节点相似性计算指标。在⼀些⼯作中,也在⼀定程度上探讨了⾼阶邻近性。
挑战。如何在各种类型的输⼊图中定义成对的节点邻近度,以及如何在学习的嵌⼊中编码邻近度?节点嵌⼊的挑战主要来⾃于定义输⼊图中的节点邻近度。
选树是什么意思边嵌⼊
与节点嵌⼊不同,边嵌⼊的⽬的是将边表⽰为⼀个低维向量。边嵌⼊在以下两个场景中很有⽤。
⾸先,知识图嵌⼊学习节点和边。每条边都是三元组的定义。通过学习嵌⼊,将r保留在嵌⼊空间的h和t之间,从⽽在的其他两个分量下,能够正确预测缺失的实体/关系。
其次,⼀些⼯作将节点对嵌⼊为向量特征,以使节点对与其他节点具有可⽐性或预测两个节点之间是否存在链路。
综上所述,边缘嵌⼊有利于边(/节点对)相关图分析,如链接预测、知识图实体/关系预测等。
挑战。如何定义边级相似度,如何对边的⾮对称属性建模,如果有的话?边缘接近不同于节点接近,因为⼀条边包含⼀对节点,通常表⽰成对的节点关系。此外,与节点不同的是,边可以是有向的。这种不对称性质应该被编码在学习到的边缘表⽰中。