图嵌入模型综述

图分析用于深入挖掘图数据的内在特征,然而图作为非欧几里德数据,传统的数据分析方法普遍存在较高的计算量和空间开销。图嵌入是一种解决图分析问题的有效方法,其将原始图数据转换到低维空间并保留关键信息,从而提升节点分类、链接预测、节点聚类等下游任务的性能。与以往的研究不同,同时对静态图和动态图嵌入文献进行全面回顾,提出一种静态图嵌入和动态图嵌入通用分类方法,即基于矩阵分解的图嵌入、基于随机游走的图嵌入、基于自编码器的图嵌入、基于图神经网络(GNN)的图嵌入和基于其他方法的图嵌入。其次,对静态图和动态图方法的理论相关性进行分析,对模型核心策略、下游任务和数据集进行全面总结。最后,提出了四个图嵌入的潜在研究方向。     

基于连续时间量子游走的链路预测方法研究*

链路预测是复杂网络研究的基础问题之一。目前研究者们已经提出了许多链路预测的方法,其中大量的链路预测方法是基于经典随机游走。量子游走是经典随机游走的量子模拟。大量研究表明,在诸如图匹配、搜索等很多领域,基于量子游走的量子算法的性能远优于其对应的经典随机游走算法。但目前关于基于量子游走的链路预测算法几乎没有研究报道。本文提出了一种基于连续时间量子游走的链路预测方法。实验结果表明,连续时间量子游走链路预测结果的AUC值和经典随机游走的结果非常接近。而在Precision和Recall指标上,远优于经典随机游走的链路预测结果。     

基于节点-属性二部图的网络表示学习模型

在图结构数据上开展推理计算是一项重大的任务,该任务的主要挑战是如何表示图结构知识使机器可以快速理解并利用图数据。对比现有表示学习模型发现,基于随机游走方法的表示学习模型容易忽略属性对节点关联关系的特殊作用,因此提出一种基于节点邻接关系与属性关联关系的混合随机游走方法。首先通过邻接节点间的共同属性分布计算属性权重,并获取节点到每个属性的采样概率;然后分别从邻接节点与含有共有属性的非邻接节点中提取网络信息;最后构建基于节点-属性二部图的网络表示学习模型,并通过上述采样序列学习得到节点向量表达。在Flickr、BlogCatalog、Cora公开数据集上,用所提模型得到的节点向量表达进行节点分类的Micro-F1平均准确率为89.38%,比GraphRNA（Graph Recurrent Networks with Attributed random walks）高出了2.02个百分点,比经典工作DeepWalk高出了21.12个百分点;同时,对比不同随机游走方法发现,提高对节点关联有促进作用的属性的采样概率可以增加采样序列所含信息。     

基于随机游走模型的物体识别

针对传统物体识别算法中只依赖于视觉特征进行识别的单一性缺陷,提出了一种结合先验关系的物体识别算法。在训练阶段,通过图模型结构化表示先验关系,分别构建了图像-图像、语义-语义两个子图以及两子图之间的联系,利用该图模型建立随机游走模型;在识别阶段,建立待识别图像与随机游走模型中的图像节点和语义节点的关系,在该概率模型上进行随机游走,将随机游走的结果作为物体识别的结果。实验结果证明了结合先验关系的物体识别算法的有效性;提出的物体识别算法具有较强的识别性能。     

基于染色随机游走的可重叠社区发现

社区发现是一个基础性的且被广泛研究的问题。现有的社区发现方法大多聚焦于网络拓扑结构,然而随着真实网络中实体可用属性的激增,捕获图中结构和属性的丰富交互关系来进行社区发现变得尤为必要。据此面向属性图提出了一种基于染色随机游走的可重叠社区发现算法OCDC,该算法解决了传统的基于随机游走的社区发现算法利用结构转移矩阵造成社区发现效果不佳的问题。具体地,首先利用经典的初始种子策略选出网络中差异度较大的节点,在此基础上设计种子替换策略,挖掘网络中质量更佳的种子替换路径集合对初始种子集合进行替换;其次构建结构-属性交互节点转移矩阵并执行染色随机游走过程得到高质量种子节点的染色分布向量;最后基于融合结构和属性的并行电导值对社区进行扩展。在人工网络和现实网络上的实验表明,本文提出的算法能够准确地识别属性社区并显著优于基准算法。     

基于随机游走与最优匹配的装配体相似性分析

为了提高利用拓扑信息进行装配体检索的能力,提出一种基于随机游走和最优匹配的相似性分析方法.首先用图节点表示装配体中的零件,将装配体转化为属性连接图并进行简化;然后分析零件连接装配关系的紧密程度并构建转移概率矩阵,利用随机游走模型分析各零件的拓扑特征;最后依据拓扑和属性特征进行零件的两两相似性评价,建立对比装配体的二分图并用最优匹配获得装配体的整体相似性.实例验证了文中方法是正确和有效的.     

一种基于节点嵌入表示学习的社区搜索算法

针对已有社区搜索算法采用高维稀疏向量表示节点时间复杂度高的问题,提出一种基于节点嵌入表示学习的社区搜索算法CSNERL.节点嵌入技术能够直接从网络结构中学习节点的低维实值向量表示,为社区搜索提供了新思路.首先,针对已有节点嵌入算法存在较高概率在最亲近邻居间来回游走的问题,提出基于最亲近邻居但不立即回访随机游走的节点嵌入模型NECRWNR,采用NECRWNR模型学习节点的特征向量表示;然后,采用社区内所有节点的向量均值作为社区的向量表示,通过选择与当前社区距离最近的节点加入社区的方法实现一种新的社区搜索算法.在真实网络和模拟网络数据集上分别与相关的社区搜索算法进行实验对比,结果表明所提出社区搜索算法CSNERL具有更高的准确性.     

融合结构-属性交互二部图随机游走的社区搜索方法

属性图中的社区搜索是一种局部社区发现方法,本质是基于用户提供的查询节点返回包含查询节点且在结构内聚的同时属性与查询属性相似的个性化子图.该任务有助于用户更好地理解社区是如何形成的以及社区形成的原因.提出了一种融合结构-属性交互二部图随机游走机制,有效地支持属性图中的社区搜索.具体地,首先基于网络拓扑结构构建结构概率转移...     

RAKING:一种高效的不确定图K-极大频繁模式挖掘算法

由于不确定图蕴含了指数级的可能图实例,基于确定图模型的频繁图模式挖掘算法通常难以在不确定图集合上高效运行.文中提出了一种不确定图数据集上的基于随机游走的K极大频繁子模式挖掘算法.首先,将每个不确定图转换为相应的确定图并挖掘候选频繁模式;然后,将候选频繁模式恢复为不确定图并生成极大频繁模式搜索空间;最后,通过随机游走以相同概率随机地选择K个极大频繁模式.理论分析和实验结果表明文中提出的算法能够高效地获得不确定图集合的K-极大频繁模式.     

结构-属性平衡图节点相似度测量算法

摘  要：节点相似度是图聚类算法的重要基础,在基于结构-属性图聚类现有方法中,由于传统图模型的限制,需要多次矩阵相乘来调整属性边的权值,算法执行效率低。为解决这一问题,提出了结构-属性平衡图的概念,并采用随机游走模型策略统一度量结构-属性平衡图GB中顶点间的相似度。与现有方法相比,该方法不但能测量直接相连的顶点之间的相似度,还可测量不直接相连而存在不同长度的路径的顶点之间的相似度,且没有增加原相似度矩阵的规模,节省了大量存储空间,提高了算法执行效率。     

基于Beta分布和半监督学习的非确定性知识图谱嵌入模型

近年来,面向确定性知识图谱的嵌入模型在知识图谱补全等任务中取得了长足的进展,但如何设计和训练面向非确定性知识图谱的嵌入模型仍然是一个重要挑战。不同于确定性知识图谱,非确定性知识图谱的每个事实三元组都有着对应的置信度,因此,非确定性知识图谱嵌入模型需要准确地计算出每个三元组的置信度。现有的非确定性知识图谱嵌入模型结构较为简单,只能处理对称关系,并且无法很好地处理假负(false-negative)样本问题。为了解决上述问题,该文首先提出了一个用于训练非确定性知识图谱嵌入模型的统一框架,该框架使用基于多模型的半监督学习方法训练非确定性知识图谱嵌入模型。为了解决半监督学习中半监督样本噪声过高的问题,我们还使用蒙特卡洛Dropout计算出模型对输出结果的不确定度,并根据该不确定度有效地过滤了半监督样本中的噪声数据。此外,为了更好地表示非确定性知识图谱中实体和关系的不确定性以处理更复杂的关系,该文还提出了基于Beta分布的非确定性知识图谱嵌入模型UBetaE,该模型将实体、关系均表示为一组相互独立的Beta分布。在公开数据集上的实验结果表明,结合该文所提出的半监督学习方法和UBetaE模型,不仅...     

基于一维三态量子游走的量子聚类算法

量子游走具有与经典随机游走不同的特性,因此它已经被用来解决包括元素区分、组合优化、图同构等问题。考虑量子游走和聚类两个领域,提出了一个基于一维三态离散量子游走的聚类算法。在该算法中,将数据点看作游走粒子;然后,这些粒子执行三态量子游走,接着根据粒子的测量结果更新数据点的属性值;最后,属于同一簇的数据点将会聚集,而属于不同簇的数据点将会分离。仿真实验结果表明了所提算法的有效性。     

基于多重异质图的恶意软件相似性度量方法

现有恶意软件相似性度量易受混淆技术影响,同时缺少恶意软件间复杂关系的表征能力,提出一种基于多重异质图的恶意软件相似性度量方法RG-MHPE （API relation graph enhanced multiple heterogeneous ProxEmbed）解决上述问题.方法首先利用恶意软件动静态特征构建多重异质图,然后提出基于关系路径的增强型邻近嵌入方法,解决邻近嵌入无法应用于多重异质图相似性度量的问题.此外,从MSDN网站的API文档中提取知识,构建API关系图,学习Windows API间的相似关系,有效减缓相似性度量模型老化速度.最后,通过对比实验验证所提方法RG-MHPE在相似性度量性能和模型抗老化能力等方面表现最好.     

基于属性嵌入与图注意力网络的实体对齐算法

实体对齐旨在找到位于不同知识图谱中的等效实体,是实现知识融合的重要步骤.当前主流的方法是基于图神经网络的实体对齐方法,这些方法往往过于依赖图的结构信息,导致在特定图结构上训练得到的模型不能拓展应用于其他图结构中.同时,大多数方法未能充分利用辅助信息,例如属性信息.为此,本文提出了一种基于图注意力网络和属性嵌入的实体对齐方法,该方法使用图注意力网络对不同的知识图谱进行编码,引入注意力机制从实体应用到属性,在对齐阶段将结构嵌入和属性嵌入进行结合实现实体对齐效果的提升.在现实世界的3个真实数据集上对本文模型进行了验证,实验结果表明提出的方法在很大程度上优于基准的实体对齐方法.     

知识图谱嵌入研究综述

随着互联网技术和应用模式的迅猛发展,表达方式丰富直观的知识图谱得到了大量关注,在知识表示学习方面积累了丰富研究成果,这些研究已在垂直搜索、智能问答等应用领域发挥了重要作用.在总结现有知识图谱嵌入研究基础之上,以面向的知识图谱数量为依据,将知识图谱嵌入模型分为面向单个知识图谱的链接预测模型和面向多个知识图谱的实体对齐模型...     

基于多通道图卷积自编码器的图表示学习

针对基于图卷积的自编码器模型对原始图属性和拓扑信息的保留能力有限、无法学习结构和属性之间深度关联信息等问题,提出基于多通道图卷积自编码器的图表示学习模型。设计拓扑和属性信息保留能力实验,验证了基于图卷积的自编码器模型具备保留节点属性和拓扑结构信息的能力。构建特定信息卷积编码器和一致信息卷积编码器,提取图的属性空间特征、拓扑空间特征以及两者关联特征,生成属性嵌入、拓扑嵌入和一致性嵌入,同时建立与编码器对称的卷积解码器,还原编码器过程。使用重构损失、局部约束和一致性约束,优化各编码器生成的低维嵌入表示。最终将蕴含不同图信息的多种嵌入进行融合,生成各节点的嵌入表示。实验结果表明,该模型在BlogCatalog和Flickr数据集上节点分类的Micro-F1和Macro-F1明显高于基线模型,在Citeseer数据集上节点聚类的精度和归一化互信息相比于表现最优的基线模型提升了11.84%和34.03%。上述实验结果证明了该模型采用的多通道方式能够在低维嵌入中保留更丰富的图信息,提升图机器学习任务的性能表现。     

基于量子漫步的图形匹配算法进展与展望

图形匹配是图形研究中的重要问题,目前的经典算法受限于存储资源和计算复杂度,未能提供有效的解决方法.基于量子效应,将图形信息存储于量子比特,不仅能够极大减少存储资源的消耗,而且对量子比特进行操作可实现对存储信息的并行计算,从而为有效解决图形匹配问题提供了新的可能.量子漫步作为量子计算中的重要模型,是分析研究图形问题的有效工具.总结了量子计算的特点,介绍了量子漫步的2种模型并对二者进行了比较.然后对目前已有的基于量子漫步的图形匹配算法进行了介绍,对其算法思想、计算过程和优缺点进行了描述,同时还提出了相应的改进思路.在总结分析目前研究存在问题的基础上,探讨了今后的研究方向.