InterTris:三元交互的领域知识图谱表示学习

在新事物不断涌现,且事物之间联系不断丰富的时代背景下,作为一项新生技术,知识图谱旨在对现实世界中概念或实体及其之间的联系进行建模.由于直接来自于现实世界,知识图谱中的实体和关系往往以符号化形式表示.要实现进一步的价值挖掘,进行知识图谱计算,就需要将符号化表示转换为数值形式.知识图谱表示学习技术应运而生.目前,知识图谱表...     

基于符号语义映射的知识图谱表示学习算法

图的分布式表示对于知识图谱的构建与应用任务至关重要.通过对当前流行的图表示学习模型进行比较,分析了现有模型存在的不合理之处,据此提出了一个基于符号语义映射的神经网络模型用于学习图的分布式表示,基本思想是依据知识图谱中已有的实体关系数据,采用循环神经网络对符号组合(实体-关系组合)进行语义编码,并将其映射到目标符号(实体)上.此外,通过为图中的每个关系类型引入一个逆关系镜像,解决了关系的非对称性问题,使模型能够适应多种不同类型的(同构或异构)网络的关系推理任务.该模型适用于大规模知识图谱的表示学习任务.在公开数据集上的实验结果表明,该模型在知识图谱扩容任务和基于图的多标签分类任务上的性能表现优于相关工作.     

基于图上下文的知识表示学习

在知识图谱的知识表示学习中,绝大多数方法都是将知识图谱中实体和关系映射到低维的连续向量空间中,但数据的稀疏和信息的不足仍会导致实体和关系语义表示的不完整性.针对这个问题,提出基于图上下文的知识表示学习模型(Context_RL).将知识图谱中实体和关系的上下文信息作为可靠数据来源和输入.通过计算实体和关系的语义相似度,...     

类型增强的时态知识图谱表示学习模型

知识图谱表示学习旨在将知识图谱中的元素（实体和关系）表示在低维的连续向量空间中，可以有效地实现知识图谱补全并提高计算效率，是贯穿知识图谱构建和应用全过程的重要问题.现有的知识图谱表示学习模型大多基于静态的结构化三元组，忽略了知识的时间动态性和实体的类型特征，限制了它们在知识图谱补全和语义计算中的表现.针对这一问题，提出一种类型增强的时态知识图谱表示学习模型（type-enhanced temporal knowledge graph representation learning model,T-Temp），基于经典的张量分解技术，将不同形式的时间信息显式融合到知识图谱表示学习过程中.同时，利用实体与关系间的类型兼容性，充分挖掘隐含在实体中的类型特征，进一步提升表示学习的准确性.此外，证明T-Temp模型具有完全表达性，且与同类模型相比，具有较低的时空复杂度.在多个真实的时态知识图谱上进行的详细实验说明了T-Temp模型的有效性和先进性.     

基于链接实体回放的多源知识图谱终身表示学习

知识图谱存储大量的结构化知识和丰富的语义信息,已被广泛应用于知识驱动的智能软件.随着智能应用的不断发展,它们对知识图谱的需求也在发生变化.而单一知识图谱往往具有数据不完备等缺点,难以满足需求.因此,支持新数据来源、融合多源知识已经成为迫切需求.传统的知识图谱表示学习和应用范式只考虑单一图谱,忽视了不同图谱间的知识迁移.多源知识图谱联合训练虽然可以带来性能提升,但不支持新增知识图谱的拓展表示学习.鉴于此,提出了多源知识图谱终身表示学习的新范式.给定一个知识图谱序列,终身表示学习的目标是在学习新知识图谱的同时,从已学习的知识图谱与模型中获得知识迁移.为实现这一目标,提出了一个基于链接实体回放的多源知识图谱终身表示学习框架.首先,设计一个以Transformer为编码器的知识图谱表示学习模型作为框架核心,利用关系相关性进行实体的链接预测.其次,提出链接子图构造方法,基于实体对齐构建并回放新增知识图谱和已有知识图谱之间的链接子图进行终身学习和知识迁移.最后,采用动态结构方法,为每个知识图谱存储相应的模型参数快照来避免灾难性遗忘.多个链接预测基准数据集上的实验结果表明,所提出的表示学习模型可以取得最先进的性能,且提出的终身表示学习框架可以实现有效的知识迁移.     

融合实体概念描述与图像特征的知识图谱表示学习研究

知识图谱表示学习将实体和关系映射到一个连续的低维空间.传统学习方法是从结构化的三元组学习知识表示,忽略了三元组之外与实体相关的丰富多源信息.针对该问题,提出一种将实体概念描述和图像特征与事实三元组相结合的知识图谱表示学习模型DIRL.首先,利用BERT模型进行实体概念描述的语义表示;其次,使用CNN编码器对图像总体特征进行提取,然后通过基于注意力的方法表示图像特征;最后,将基于概念描述的表示和基于图像特征的表示与翻译模型TransR结合起来进行知识图谱表示学习.通过实验验证,DIRL模型优于现有方法,提高了多源信息知识图谱表示的有效性.     

一种融合关系路径与实体描述信息的知识图谱表示学习方法

知识图谱表示学习旨在通过学习的方法将知识图谱中的实体和关系映射到一个连续的低维向量空间而获得其向量表示.已有的知识图谱表示学习方法大多仅从三元组角度考虑实体间的单步关系,未能有效利用多步关系路径及其实体描述等重要信息,从而影响性能.针对上述问题,提出了一种融合关系路径与实体描述的知识图谱表示学习模型.首先,对知识图谱中的多步关系路径进行联合表示,将路径上的所有关系和实体相加,得到关系路径信息的表示;其次,使用BERT(bidirectional encoder representations from transformers)模型对实体描述信息进行编码,得到相对应的语义表示;最后,对知识图谱中的三元组表示、实体描述的语义表示以及关系路径的表示进行融合训练,得到融合向量表示.在FB15K,WN18,FB15K-237,WN18RR数据集上,对提出的模型和基准模型进行链接预测和三元组分类任务,实验结果表明,与现有的基准模型相比,该模型在2项任务中均具有更高的准确性,证明了方法的有效性和优越性.     

融合实体类别信息的知识图谱表示学习

知识图谱表示学习通过将实体和关系嵌入连续低维的语义空间中,获取实体和关系的语义关联信息.设计一种融合实体类别信息的类别增强知识图谱表示学习(CEKGRL)模型,构建基于结构与基于类别的实体表示,通过注意力机制捕获实体类别和三元组关系之间的潜在相关性,结合不同实体类别对于某种特定关系的重要程度及实体类别信息进行知识表示学...     

融合实体描述与路径信息的知识图谱表示学习模型

知识图谱表示学习方法是将知识图谱中的实体和关系通过特定规则表示成一个多维向量的过程。现有表示学习方法多用于解决单跳知识图谱问答任务,其多跳推理能力无法满足实际需求,为提升多跳推理能力,提出一种融合实体描述与路径信息的知识图谱表示学习模型。首先通过预训练语言模型RoBERTa得到融合实体描述的实体、关系表示学习向量;其次利用OPTransE将知识图谱转化成融入有序关系路径信息的向量。最后构建总能量函数,将针对实体描述和路径信息的向量进行融合。通过实验分析与对比该模型在链路预测任务上与主流知识图谱表示学习模型的性能,验证了该模型的可行性与有效性。     

基于贝叶斯网的开放世界知识图谱补全

知识图谱中实体所涉及的关系之间通常具有相互依赖的性质,基于这种依赖性可利用数据中的新实体来构造更多的三元组从而补全知识图谱.贝叶斯网(BN)是一种表示和推理变量之间相互依赖关系和不确定性知识的有效模型,将BN作为模型框架,研究基于BN的开放世界知识图谱补全方法.提出知识图谱中关系之间依赖性的表示模型构建方法,构建过程包...     

动态图划分算法研究综述

图划分是大规模分布式图处理的首要工作,对图应用的存储、查询、处理和挖掘起基础支撑作用.随着图数据规模的不断扩大,真实世界中的图表现出动态性.如何对动态图进行划分,已成为目前图划分研究的热点问题.从不同动态图划分算法的关注点和特点出发,系统性地介绍当前可用于解决动态图划分问题的各类算法,包括流式图划分算法、增量式图划分算法和图重划分算法.首先介绍图划分的3种不同的划分策略及问题定义、图的两种不同的动态性来源以及动态图划分问题;然后介绍3种不同的流式图划分算法,包括基于Hash的划分算法、基于邻居分布的划分算法以及基于流的优化划分算法;其次介绍单元素增量式划分和批量增量式划分这两种不同的增量式图划分算法;再次,分别介绍针对图结构动态的重划分算法和针对图计算动态的重划分算法;最后,在对已有方法分析和比较的基础上,总结目前动态图划分面临的主要挑战,提出相应的研究问题.     

一种基于GN算法的动态图划分方法

随着图规模的急剧增长,对动态图进行实时处理的需求日益增加。大多现有的算法针对静态图划分是有效的,直接用其处理动态图会带来较大的通信开销。针对该问题,提出一种基于GN算法的动态图划分方法。首先收集一段时间内加入动态图中的顶点;然后,利用GN算法对这些新加入的顶点进行预划分,产生若干个内部联系紧密的社区;最后,将预划分产生的社区结果插入到已经划分好的当前图中。实验从交叉边数和负载均衡度两方面将该方法与传统流式划分方法进行比较,结果表明,在公开数据集上,该方法的交叉边数降低了13%,负载均衡度减少了42.3%。由此可见,该方法的划分质量明显优于传统的流式划分方法。     

大图结构特征对划分效果的影响

针对大图结构特征如何影响划分效果这一问题,提出一种通过顶点度分布特征来描述大图结构特征的方法。首先,基于真实的图数据产生若干顶点数和边数相同、但结构特征不同的仿真数据集,通过实验计算真实图与仿真图之间的相似度,证明该方法对描述真实大图结构特征的有效性。然后,通过Hash和点对交换划分算法,验证图结构特征与划分效果之间的关系。当点对交换划分算法执行到5万次时,划分一个有6301个顶点和20777条边的真实图其交叉边数比Hash划分算法降低了54.32%,划分仿真图数据集中结构特征差异明显的两个图时,交叉边数分别为6233和316。实验结果表明,点对交换划分算法能够减少交叉边数,图的顶点度分布差异越大,划分后交叉边数越少,划分效果越好,因此大图结构特征影响其划分效果,这为建立图的结构特征与划分效果之间的关系模型研究奠定了基础。     

基于顶点组重分配的动态增量图划分算法

图划分是分布式图计算中的一项基础工作, 其作用是将大规模图进行划分并分配到集群中的不同机器上. 图划分的质量对分布式图计算的性能有很大的影响, 其目标是降低负载平衡和最小化边割. 如今, 现实中的图数据通常呈动态增长态势, 这就需要一种能够处理动态增量图的划分方法, 在图数据动态增长的过程中确保划分的质量不受影响. 目前虽然有一些动态图划分算法被提出, 但它们不能同时专注于实时处理动态变化和获得高质量的划分结果. 提出基于顶点组重分配的动态增量图划分算法(ED-IDGP)来解决大规模动态增量图的划分问题. 在ED-IDGP算法中, 设计实时处理4种不同单元更新类型的动态处理器, 并在每次处理完单元更新后通过在分区发生动态变化的附近执行局部优化器进一步提高图划分的质量. 在ED-IDGP的局部优化器中, 利用基于改进标签传播算法的顶点组搜索策略搜索顶点组, 并利用提出的顶点组移动增益公式衡量最有益的顶点组, 将该顶点组移动到目标分区中做优化. 在真实数据集上从不同的角度和度量指标评估了ED-IDGP算法的性能和效率.     

基于通信负载均衡的社交网络图分割方法

海量社交网络数据中蕴含着丰富的信息,图论是挖掘这些信息的重要方法之一。面对日益增多的图数据,分布式计算成为处理大规模图数据的有效手段。在分布式图计算中,通信所消耗的时间占有很大的比例,通过图分割算法的设计可以有效地降低通信量并实现负载均衡,从而提高分布式图计算的效率,典型的例子包括Metis图分割算法。但是,用现有的图分割算法处理非均衡图数据会造成各个子图之间通信量不均衡,从而影响了计算效率。为了解决这一问题,提出一种新的图分割方法：通信均衡标签交换方法。该方法在保持子图规模一致的基础上,既降低了全图计算所需的通信量,又使各个子图之间的通信量达到均衡。实验结果表明,与Metis等典型的图分割算法相比,提出的图分割方法在各种数据集和集群配置情况下,能降低6%~30%的图计算时间,充分显示了该方法的有效性。     

Multilevelk-way Partitioning Scheme for Irregular Graphs

In this paper, we present and study a class of graph partitioning algorithms that reduces the size of the graph by collapsing vertices and edges, we find ak-way partitioning of the smaller graph, and then we uncoarsen and refine it to construct ak-way partitioning for the original graph. These algorithms compute ak-way partitioning of a graphG= (V,E) inO(|E|) time, which is faster by a factor ofO(logk) than previously proposed multilevel recursive bisection algorithms. A key contribution of our work is in finding a high-quality and computationally inexpensive refinement algorithm that can improve upon an initialk-way partitioning. We also study the effectiveness of the overall scheme for a variety of coarsening schemes. We present experimental results on a large number of graphs arising in various domains including finite element methods, linear programming, VLSI, and transportation. Our experiments show that this new scheme produces partitions that are of comparable or better quality than those produced by the multilevel bisection algorithm and requires substantially smaller time. Graphs containing up to 450,000 vertices and 3,300,000 edges can be partitioned in 256 domains in less than 40 s on a workstation such as SGI's Challenge. Compared with the widely used multilevel spectral bisection algorithm, our new algorithm is usually two orders of magnitude faster and produces partitions with substantially smaller edge-cut.     

基于城市安全知识图谱的多关键词流式并行检索算法

我国智慧城市安全概念的普及和建设的逐渐落地,以及大数据在智慧城市安全建设方面的深度应用,对关键词检索的处理响应速度提出了更高的要求。针对这一问题,提出了基于城市安全知识图谱的流式知识图谱多关键词并行检索算法(MKPRASKG),该算法能够根据用户输入的查询关键字,通过关联类图的构建、剪枝和融合操作实时构建基于知识图谱实体的查询子图集,再结合评分函数,以高评分的查询子图为指引,在知识图谱实例数据中进行并行搜索,最终返回Top-k查询结果。实验结果证明,该算法在实时搜索、响应时间、搜索效果以及可扩展性等方面均具有较大的优势。     

An asynchronous traversal engine for graph-based rich metadata management

Rich metadata in high-performance computing (HPC) systems contains extended information about users, jobs, data files, and their relationships. Property graphs are a promising data model to represent heterogeneous rich metadata flexibly. Specifically, a property graph can use vertices to represent different entities and edges to record the relationships between vertices with unique annotations. The high-volume HPC use case, with millions of entities and relationships, naturally requires an out-of-core distributed property graph database, which must support live updates (to ingest production information in real time), low-latency point queries (for frequent metadata operations such as permission checking), and large-scale traversals (for provenance data mining).Among these needs, large-scale property graph traversals are particularly challenging for distributed graph storage systems. Most existing graph systems implement a “level-synchronous” breadth-first search algorithm that relies on global synchronization in each traversal step. This performs well in many problem domains; but a rich metadata management system is characterized by imbalanced graphs, long traversal lengths, and concurrent workloads, each of which has the potential to introduce or exacerbate stragglers (i.e., abnormally slow steps or servers in a graph traversal) that lead to low overall throughput for synchronous traversal algorithms. Previous research indicated that the straggler problem can be mitigated by using asynchronous traversal algorithms, and many graph-processing frameworks have successfully demonstrated this approach. Such systems require the graph to be loaded into a separate batch-processing framework instead of being iteratively accessed, however.In this work, we investigate a general asynchronous graph traversal engine that can operate atop a rich metadata graph in its native format. We outline a traversal-aware query language and key optimizations (traversal-affiliate caching and execution merging) necessary for efficient performance. We further explore the effect of different graph partitioning strategies on the traversal performance for both synchronous and asynchronous traversal engines. Our experiments show that the asynchronous graph traversal engine is more efficient than its synchronous counterpart in the case of HPC rich metadata processing, where more servers are involved and larger traversals are needed. Moreover, the asynchronous traversal engine is more adaptive to different graph partitioning strategies.     

基于启发策略的动态平衡图划分算法

随着计算技术的发展以及大数据时代的来临,分布式计算已成为研究的热点,其中大图迭代计算作为其研究的重点,降低划分后子图之间的通信边规模是改善计算性能的关键.传统算法很难在切割率最小化与负载均衡上同时满足.由于图划分属于NP组合优化问题,提出了一种动态平衡算法来解决图的平衡划分,确保在子图边界点划分最优的基础上引入扰动策略使其跳出局部最优扩大搜索空间,最后在真实世界图上验证算法的可行性,分别从平衡系数、切割边规模与传统算法进行了比较.在指定的扰动次数下,此算法比常见的算法hash,Chunk,Metis在割边率上分别降低了近40%,30%,5%.与Metis相比,平衡系数也更加地优化,实验结果证明了该算法的有效性.     

基于图压缩的k可达查询处理

研究了基于图压缩的k可达查询处理,提出了一种支持k可达查询的图压缩算法k-RPC及无需解压缩的查询处理算法,k-RPC算法在所有基于等价类的支持k-reach查询的图压缩算法中是最优的.由于k-RPC算法是基于严格的等价关系,因此进一步又提出了线性时间的近似图压缩算法k-GRPC.k-GRPC算法允许从原始图中删除部分边,然后使用k-RPC获得更好的压缩比.提出了线性时间的无需解压缩的查询处理算法.真实数据上的实验结果表明,对于稀疏的原始图,两种压缩算法的压缩比分别可以达到45%,对于稠密的原始图,两种压缩算法的压缩比分别可以达到75%和67%;与在原始图上直接进行查询处理相比,两种基于压缩图的查询处理算法效率更好,在稀疏图上的查询效率可以提高2.5倍.