论文精讲 | 图嵌入的综合调查:问题、技术和应用

admin 2023年2月2日14:59:30评论10 views字数 4483阅读14分56秒阅读模式

本次论文研读系列推文来自知识图谱硕士课程课堂展示。其中来自数据科学、管理科学与工程、保密管理等专业13位同学选择了知识图谱相关的前沿论文进行精读。我们将从KG construction,KG representation以及综述三个专题进行成果展示。本期展示主题为综述


摘要:

图形是一种重要的数据表示形式,它出现在各种各样的现实世界场景中。有效的图形分析使用户能够更深入地了解数据背后的内容,从而可以使许多有用的应用程序受益,例如节点分类,节点推荐,链接预测等。然而,大多数图形分析方法都面临着高昂的计算和空间成本图嵌入是解决图分析问题的一种有效而高效的方法。它将图数据转换为低维空间,其中图结构信息和图属性得到最大程度的保留。在本次调查中,我们对图嵌入的文献进行了全面回顾。我们首先介绍图嵌入的正式定义以及相关概念。之后,我们提出了两种图嵌入分类法,它们对应于不同图嵌入问题设置中存在的挑战以及现有工作如何在其解决方案中解决这些挑战。最后,总结了图嵌入在计算效率、问题设置、技术和应用场景等方面的四个未来研究方向。



关键词:分类学;任务分析;电子邮件;玩具制造业;二维显示;机器学习


论文精讲 | 图嵌入的综合调查:问题、技术和应用


论文标题:

A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications


会议:

IEEEE2018


论文地址:

Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications | IEEE Journals & Magazine | IEEE Xplore


———————————————————————————————


01定义


图可以理解为一个代数系统,本文对图及其不同的特点加以介绍。
1. 图
系统G(V, E),节点v∈V,边e∈E,节点类型映射fv: V→Tv, 边类型映射fe: E→Te。
2. 同质图
系统Ghomo(V, E),在图的定义基础上增加约束:| Tv | = | Te | = 1。
3. 异质图
系统Ghete(V, E),在图的定义基础上增加约束:| Tv | + | Te | > 2。
4. 知识图谱
系统Gknow(V, E),在图的定义基础上增加约束:有向图,对于一条知识三元组,节点表示实体h和t,边代表h→t方向的一条关系r。在图嵌入的过程当中,两个节点之间的一阶相似度和二阶相似度常被用作图嵌入属性的量化描述。
5. 一阶相似度
s(1)ij,表示节点vi和vj之间边eij的权重,即Aij(A为邻接矩阵),权重越高节点间越相似。
6. 二阶相似度
s(2)ij,表示vi的邻居节点s(1)i和vj的邻居节点s(1)j的相似度。s(2)ij=cosine(s(1)i , s(1)j)。

02图嵌入的输入输出问题

2.1 研究问题概述
1. 考虑图嵌入的输入及输出。
2. 不同种类的图在嵌入的方法上会有所差异。
    (1) 同质图;
    (2) 异质图;
    (3) 属性图;
    (4) 由非关系结构数据构造的图。

2.2 输入

2.2.1 同质图
节点只有一种类型,边也只有一种类型。
根据节点是否带权,是否有向,输入的方式会有些不同。带权:节点间权重越大,嵌入时距离越近。
研究难点:
1. 同质图中只有图的结构信息,如何保留连接中的模式信息;
2. 包含更多语义信息的高阶关系。

论文精讲 | 图嵌入的综合调查:问题、技术和应用


2.2.2 异质图
节点或/和,边有多种类型。
应用场景:社区问答、多模态网络、知识图谱、通用异质图结构。
研究难点:
1. 不同类型的信息的全局一致性;
2. 不同类型信息之间的平衡问题。

2.2.3 辅助信息图
节点/边带有辅助信息。
常见辅助信息类型:标签、属性、节点特征、信息传播路径信息、知识库。
研究难点:
1. 对辅助信息的整合方式,使嵌入时同时学习到;
2. 图结构特征;辅助信息特征。
下图为辅助信息的含义:
论文精讲 | 图嵌入的综合调查:问题、技术和应用

2.2.3 根据非结构化输入数据构建的图
前提:输入数据在相对低维流型(manifold)中节点/边带有辅助信息。
特征矩阵X∈R|V|×N,并得到(Xi, Xj)之间相似度矩阵S,利用S构造图。
1. 方法1:直接将S视作邻接矩阵A;
2. 方法2:S → K邻近图 → A。
研究难点:
1. 对样本之间的成对关系进行编码;
2. 生成节点的邻接矩阵嵌入时保持图的结构(其它所有图的类型共有的问题)。
Note:如何理解“低维流型”?人工智能领域的一个基本想法就是:自然界中同一类别的高维数据(例如图像),往往集中在某个低维流形附近——流型分布定律。所谓“流型结构”是来自拓扑几何和微分几何的基本概念,本质上就是很多的欧式空间粘贴在一起构成的抽象空间。从非结构化数据进行输入的过程中,由于特征矩阵的样本点空间R|V|×N就只有这两个维度,因此输入数据需要基于“包含有效信息的维度不能太高”这一假设,否则人工进行降维的过程中,极可能丢失一些有意义的信息。


2.3 输出
够表征图整体或局部的一系列低维向量
任务驱动(因具体任务的不同,输出嵌入的形式会有所不同)
嵌入类型:节点嵌入;嵌入;混合嵌入;张图嵌入。
论文精讲 | 图嵌入的综合调查:问题、技术和应用

2.3.1 基于节点嵌入的输出
论文精讲 | 图嵌入的综合调查:问题、技术和应用
将节点表示为低维空间中的向量。
核心观点:节点越接近,嵌入得到的向量相似度越高。
量化“相似度”的指标:一阶相似度、二阶相似度。
研究难点:如何对成对节点相似性进行定义、学习和抽取。


2.3.2 基于边嵌入的输出

论文精讲 | 图嵌入的综合调查:问题、技术和应用

将边表示为低维空间中的向量。
方法:
1. 知识图谱:三元组同时嵌入;
2. 将“节点对”特征嵌入,对比节点对之间的特性 / 预测边的存在性。
研究难点:
1. 边相似度的定义、学习和抽取;
2. 边的不对称特性建模(有向结构)。

2.3.3 基于混合嵌入的输出
将图的不同类型子结构组合在一起嵌入。
方法:
1. 节点+边(子图)嵌入;
2. 节点+社区嵌入。
研究难点:
1. 目标子结构的生成方式;
2. 嵌入不同子结构的方式。
Note: 下图给出了“社区嵌入”的一个示意(来源:Cavallari S, Zheng V W, Cai H, et al. Learning community embedding with community detection and node embedding on graphs[C]//Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. 2017: 377-386.)
论文精讲 | 图嵌入的综合调查:问题、技术和应用

所谓“社区”,是表示的彼此之间有密集连接的一系列节点簇,社区嵌入就是把这些密接节点嵌入到低维空间中来。
混合嵌入的输出目标是很灵活的,由于不同的子结构具有异质性,嵌入不同种类的子结构到同一个空间里面去的时候,异质信息的融合就又是一个问题了。

2.3.4 整张图嵌入的输出

论文精讲 | 图嵌入的综合调查:问题、技术和应用

将整张图作为一个整体嵌入到低维向量空间中。
两个图越相近,嵌入空间上距离越近。
常见于规模较小的图:蛋白质特征、分子特征。
研究难点: 在效率和表达能力上折中。
1. 耗时问题;
2. 尽可能多地保存图中蕴含的信息。



03图嵌入技术/方法

下图给出了图嵌入的5类技术方法,每种方法各有利弊。
论文精讲 | 图嵌入的综合调查:问题、技术和应用

3.1 基于矩阵分解的技术方法(MF)
输入:非结构化数据。
前提:低维流型空间。
输出:节点嵌入。
矩阵分解方法:
1. 拉普拉斯特征映射;
2. 节点相似度矩阵分解。
优点:考虑全局节点相似度。
不足:时间、空间消耗巨大。

3.1.1 拉普拉斯特征映射
思想:
1. 要保留的图的属性可以被解释为成对的节点相似性;
2. 因此,相似性较大而节点嵌入距离远的情形出现,会进行惩罚。
目标函数:
论文精讲 | 图嵌入的综合调查:问题、技术和应用

3.1.2 基于相似度的矩阵分解法
思想:
1. 矩阵分解可近似表示节点在低维空间的相似度
2. 尽量减少近似时的损失
目标函数:
论文精讲 | 图嵌入的综合调查:问题、技术和应用


3.2 基于深度学习的技术方法
输入:采样路径集合或完整的图。
分类:
1. 基于随机游走;
2. 不基于随机游走。
优势:高效性、健壮性、不用特征工程。
不足:基于随机游走的算法每次只能考虑一条路径的上下文信息,而且采样比较麻烦;
随机游走方法运算的时间复杂度较高。

3.2.1 基于随机游走的方法
思想:
1. 给定某一节点的前提下,最大化其邻居的概率分布;
2. 可在嵌入时保持图的二阶近似度特征。
目标函数:
论文精讲 | 图嵌入的综合调查:问题、技术和应用
(来源:Xu M. Understanding graph embedding methods and their applications[J]. SIAM Review, 2021, 63(4): 825-853.)
相关研究:
论文精讲 | 图嵌入的综合调查:问题、技术和应用

3.2.2 不使用随机游走
思想:
1. 用多层神经网络结构对图进行编码;
2. 编码后解码应尽量减少与输入相比时的损失。
举例:
1. AutoEncoder
2. 其它深度神经网络
相关研究:
论文精讲 | 图嵌入的综合调查:问题、技术和应用


3.3 基于边的重构优化方法
整体思想:
1. 以节点嵌入为基础;
2. 构建出来的边应尽量与给定原图相似。
具体方法:
1. 边生成预测概率的最大化
2. 距离损失函数的最小化
优势:训练较为高效
不足:观测的信息相对有限
相关研究:
论文精讲 | 图嵌入的综合调查:问题、技术和应用

3.3.1 思路1:生成边的概率最大化
思想:点嵌入得足够好时,图中原本有边的地方,生成边概率越大。
目标函数:
论文精讲 | 图嵌入的综合调查:问题、技术和应用

3.3.2 思路2:距离损失最小化
思想:节点嵌入后计算得到的相似度,接近于原始节点计算出来的相似度。
目标函数:
论文精讲 | 图嵌入的综合调查:问题、技术和应用



3.4 图内核(Graph-kernel)的思想方法
主要用于对整个图做嵌入。
思想:个复杂的图可以被拆成各种基础子结构(原子结构)。
原子结构:
1. Graphlet (图当中非同构的不可再分单元);
2. 子树模式 (认为图当中的某个序列可能反映在一棵抽象的树结构上,从而将计算节点概率分布的时间复杂度降低);
3. 随机游走路径 (将错综复杂的网络结构平铺成一系列包含潜在语义的序列状结构)。



3.5 其他方法简述
成式模型:
1. 考虑节点语义,图的结构直接用嵌入节点的距离表示;
2. 节点的语义信息,可通过生成式模型,从节点属性中检测。
3. 常见于异质图或者属性图的嵌入任务中;
混合技术:述的多种技术的综合使用。



04应用与展望

4.1 图嵌入的应用

4.1.1 基于节点嵌入的应用

1. 节点分类;

2. 节点聚类;

3. 节点推荐/提取/评分。


4.1.2 基于边嵌入的应用

1. 边的预测;

2. 三元组分类。


4.1.3 基于边嵌入的应用基于整图或者子结构嵌入的应用

1. 图的分类;

2. 可视化

Note: 这里说的可视化,并不仅仅是指学习使用echarts等这样的工具可视化,而是将嵌入后的结果凸显在一个低维可视空间(如二维、三维图,或者通过在二维图上引入节点颜色深浅、节点大小等方面,在二维图上反映更多信息),通过这种可视化,直观地辅助人理解图嵌入的效果,协助人进行数据分析。



4.2 图嵌入的未来研究

1. 运算效率问题

2. 输入、输出方面进一步的探讨

3. 图嵌入技术方法的进一步研究

4. 图结构在更多基础上的应用问题

Note第1点“运算效率”,不仅仅是在于对图嵌入的算法进行优化,还在于计算设备在处理图结构的时候,能够更加高效进行处理(例如:硬件层面合理组织存储空间,减少因图矩阵稀疏性带来的存储碎片空间)



THE END


指导老师:洪亮

图文:杜文添

编辑:龙雨荷

原文始发于微信公众号(珞珈大数据):论文精讲 | 图嵌入的综合调查:问题、技术和应用

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2023年2月2日14:59:30
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   论文精讲 | 图嵌入的综合调查:问题、技术和应用http://cn-sec.com/archives/1532932.html

发表评论

匿名网友 填写信息