知识图谱的增强CP分解链接预测方法

CP分解作为知识图谱链接预测的方法之一,能够对一些包含常规数据的知识图谱进行链接预测补全。但当知识图谱存在大量稀疏数据及可逆关系时,该方法不能体现两个实体间具有的隐藏联系,无法对此类数据进行处理。为解决上述问题,提出增强CP分解方法,对三元组中前实体和后实体的两个嵌入向量分别进行学习,并在训练过程中使用概率方法生成更高质量的负例三元组,引入ELU损失函数和AMSGrad优化器,有效对可逆关系和稀疏数据进行处理。在通用数据集上的实验结果表明,所提方法可以有效提升链接预测精度,与对比模型相比取得了5%的性能提升,同时应用在汽车维修知识图谱数据集补全中,取得83.2%正确率的实体补全结果。     

Mobile link prediction: Automated creation and crowdsourced validation of knowledge graphs

Building trustworthy knowledge graphs for cyber–physical social systems (CPSS) is a challenge. In particular, current approaches relying on human experts have limited scalability, while automated approaches are often not validated by users resulting in knowledge graphs of questionable quality. This paper introduces a novel pervasive knowledge graph builder for mobile devices that brings together automation, experts’ and crowdsourced citizens’ knowledge. The knowledge graph grows via automated link predictions using genetic programming that are validated by humans for improving transparency and calibrating accuracy. The knowledge graph builder is designed for pervasive devices such as smartphones and preserves privacy by localizing all computations. The accuracy, practicality, and usability of the knowledge graph builder is evaluated in a real-world social experiment that involves a smartphone implementation and a Smart City application scenario. The proposed methodology of knowledge graph building outperforms a baseline method in terms of accuracy while demonstrating its efficient calculations on smartphones and the feasibility of the pervasive human supervision process in terms of high interactions throughput. These findings promise new opportunities to crowdsource and operate pervasive reasoning systems for cyber–physical social systems in Smart Cities.     

融合链接预测相似度矩阵的属性网络嵌入算法

在属性网络中,与节点相关联的属性信息有助于提升网络嵌入各种任务的性能,但网络是一种图状结构,节点不仅包含属性信息还隐含着丰富的结构信息。为了充分融合结构信息,首先通过定义节点的影响力特性、空间关系特征;然后根据链接预测领域基于相似度的定义构建相似度矩阵,将节点二元组中的关联向量映射到相似度矩阵这一关系空间中,从而保留与节点相关的结构向量信息;再基于图的拉普拉斯矩阵融合属性信息和标签特征,将上述三类信息集成到一个最优化框架中;最后,通过二阶导数求局部最大值计算投影矩阵获取节点的特征表示进行网络嵌入。实验结果表明,提出的算法能够充分利用节点二元组的邻接结构信息,相比于其他基准网络嵌入算法,本模型在节点分类任务上取得了更好的结果。     

HSEM: highly scalable node embedding for link prediction in very large-scale social networks

World Wide Web - Very large-scale social networks are typically sparse and dynamic and often have millions of nodes and billions of links. Link prediction in very large-scale networks is a...     

面向知识图谱链接预测任务的解释子图生成模型

近年来图神经网络（GNN）发展迅速,相关模型在知识图谱链接预测任务上的性能显著提升。为解释性能提升的原因,研究人员需要提取GNN学习到的子图模式。然而现有GNN解释器在知识图谱这类典型多关系（multi-relation）图数据场景下的解释准确性尚未被验证,且相关工具尚未实现,导致解释子图提取困难。针对该问题,提出一种将多关系的知识图谱转换为单关系（uni-relational）图的知识图谱链接预测模型,该模型通过将知识图谱中的实体组合为新的节点,并将关系作为新节点的特征,生成只有单一关系的新图,并在新图上训练去噪自编码器使其获得链接预测能力,最后使用GNN解释器生成子图解释。在三个基准数据集上的实验表明,与不进行转换的GraIL相比,所提基于单关系转换的链接预测模型的相对AUC指标提升显著。最后,该模型选取FB15K-237数据集进行解释子图提取实验,验证了模型在直接提取链接预测解释方面的有效性。     

基于知识图谱嵌入和补全的电梯故障预测

为及早预测电梯发生的常见故障,提高电梯设备的维保质量和效率,提出基于规则推理、知识图谱嵌入技术和知识图谱补全技术实现电梯故障预测的方法,在构建电梯故障知识图谱后,通过改进的组合模型将三元组中的实体和关系训练为连续的低维向量空间,实现三元组对于故障预测相关运算的兼容,通过组合模型实现电梯实体、关系和故障实体三元组的预测....     

Ring embedding in faulty pancake graphs

In this paper, we consider the fault hamiltonicity and the fault hamiltonian connectivity of the pancake graph P_n. Assume that F⊆V(P_n)∪E(P_n). For n?4, we prove that P_n−F is hamiltonian if |F|?(n−3) and P_n−F is hamiltonian connected if |F|?(n−4). Moreover, all the bounds are optimal.     

Building k-connected neighborhood graphs for isometric data embedding

Isometric data embedding using geodesic distance requires the construction of a connected neighborhood graph so that the geodesic distance between every pair of data points can be estimated. This paper proposes an approach for constructing k-connected neighborhood graphs. The approach works by applying a greedy algorithm to add each edge, in a nondecreasing order of edge length, to a neighborhood graph if end vertices of the edge are not yet k-connected on the graph. The k-connectedness between vertices is tested using a network flow technique by assigning every vertex a unit flow capacity. This approach is applicable to a wide range of data. Experiments show that it gives better estimation of geodesic distances than other approaches, especially when the data are undersampled or nonuniformly distributed.     

Capturing and incorporating expert knowledge into machine learning models for quality prediction in manufacturing

Journal of Intelligent Manufacturing - Increasing digitalization enables the use of machine learning (ML) methods for analyzing and optimizing manufacturing processes. A main application of ML is...     

一种改进的自适应知识图谱嵌入式表示方法

知识图谱的嵌入式表示方法以基于翻译的TransE最为经典,但在处理复杂关系时存在局限;使用欧氏距离作为得分函数中的度量,每个特征维度以相同的权重参与计算,准确性会受到无关维度的影响,灵活性不高。因此,针对这两个缺陷,提出一种自适应的知识图谱嵌入式表示方法TransAD。利用自适应度量方法更换度量函数,在得分函数中引入对角权重矩阵,为每一个特征维分别赋予权重,增加模型的表示能力。同时受TransD方法的启发,将实体与关系通过动态映射矩阵建立空间投影模型,来增强模型对复杂关系的处理能力,最后将两种优化集成在一个模型中。实验结果表明,新方法TransAD优于Trans(E,H,R,D),在链路预测和三元组分类任务的各项指标上均有提升,有一定的先进性。     

Constraint models for graceful graphs

We present three constraint models of the problem of finding a graceful labelling of a graph, or proving that the graph is not graceful. An experimental comparison of the models applied to different classes of graph is given. The first model seems a natural way to represent the problem, but explores a much larger search tree than the other models. The second model does much less search, by making the most constrained decisions first, but is slow because the constraints are time-consuming to propagate. The third model combines the best features of the others, doing little more search than the second model while being much the fastest of the three. The comparison of the three models provides a useful case-study of modelling problems as constraint satisfaction problems. In addition, we show that constraint programming can be a useful tool for the study of graceful graphs; the models presented here have contributed many new results.     

Graph relation embedding network for click-through rate prediction

Knowledge and Information Systems - Most deep click-through rate (CTR) prediction models utilize a mainstream framework, which consists of the embedding layer and the feature interaction layer....     

Hybrid modelling for real-time prediction of the sulphur content during ladle furnace steel refining with embedding prior knowledge

Real-time prediction of the sulphur content of steel is of great importance for operation guidance during ladle furnace (LF) steel refining. For seeking an accurate prediction, this paper proposes to establish sulphur content prediction model in a hybrid way, where a simplified first principle model is introduced and fine tuned by data-driven modelling methods. The derived hybrid model employs optimization approach to optimize its data representation part, while prior knowledge is embedded in the form of linear constraints. An innovation of the proposed methodology is the full exploitation of prior knowledge about the process for determining reasonable process parameters. Moreover, a novel optimization approach is developed for ensuring accuracy and improving solution efficiency by the integration of genetic algorithm and successive approximation method. The proposed hybrid model possesses flexible interpretable structure and adaptive learning ability. As a result, it ensures the extrapolation property for real-time prediction and is able to provide an in-depth understanding of practical desulphurization process, making it very suitable for process monitoring and operations optimization during LF steel refining. Finally, this hybrid model is validated on recorded data from an industrial LF plant.     

Efficient algorithms for minimum congestion hypergraph embedding in a cycle

The minimum congestion hypergraph embedding in a cycle (MCHEC) problem is to embed the hyperedges of a hypergraph as paths in a cycle with the same node set such that the maximum congestion (the maximum number of paths that use any single edge in the cycle) is minimized. The MCHEC problem has many applications, including optimizing communication congestions in computer networks and parallel computing. The problem is NP-hard. In this paper, we give a 1.8-approximation algorithm for the MCHEC problem. This improves the previous 2-approximation results. Our algorithm has the optimal time complexity O(mn) for a hypergraph with m hyperedges and n nodes. We also propose an algorithm which finds an embedding with the optimal congestion L* for the MCHEC problem in O(n(nL*)/sup L*/) time. This improves the previous O((mn)/sup L*+1/) time algorithm.     

Systematic and deterministic graph minor embedding for Cartesian products of graphs

The limited connectivity of current and next-generation quantum annealers motivates the need for efficient graph minor embedding methods. These methods allow non-native problems to be adapted to the target annealer’s architecture. The overhead of the widely used heuristic techniques is quickly proving to be a significant bottleneck for solving real-world applications. To alleviate this difficulty, we propose a systematic and deterministic embedding method, exploiting the structures of both the specific problem and the quantum annealer. We focus on the specific case of the Cartesian product of two complete graphs, a regular structure that occurs in many problems. We decompose the embedding problem by first embedding one of the factors of the Cartesian product in a repeatable pattern. The resulting simplified problem comprises the placement and connecting together of these copies to reach a valid solution. Aside from the obvious advantage of a systematic and deterministic approach with respect to speed and efficiency, the embeddings produced are easily scaled for larger processors and show desirable properties for the number of qubits used and the chain length distribution. We conclude by briefly addressing the problem of circumventing inoperable qubits by presenting possible extensions of our method.     

Efficient parallel algorithms for path problems in directed graphs

In this paper we describe a technique for finding efficient parallel algorithms for problems on directed graphs that involve checking the existence of certain kinds of paths in the graph. This technique provides efficient algorithms for finding dominators in flow graphs, performing interval and loop analysis on reducible flow graphs, and finding the feedback vertices of a digraph. Each of these algorithms takesO(log² n) time using the same number of processors needed for fast matrix multiplication. All of these bounds are for an EREW PRAM.     

Efficient MapReduce algorithms for triangle listing in billion-scale graphs

This paper addresses the classical triangle listing problem, which aims at enumerating all the tuples of three vertices connected with each other by edges. This problem has been intensively studied in internal and external memory, but it is still an urgent challenge in distributed environment where multiple machines across the network can be utilized to achieve good performance and scalability. As one of the de facto computing methodologies in distributed environment, MapReduce has been used in some of existing triangle listing algorithms. However, these algorithms usually need to shuffle a huge amount of intermediate data, which seriously hinders their scalability on large scale graphs. In this paper, we propose a new triangle listing algorithm in MapReduce, FTL, which utilizes a light weight data structure to substantially reduce the intermediate data transferred during the shuffle stage, and also is equipped with multiple-round techniques to ease the burden on memory and network bandwidth when dealing with graphs at billion scale. We prove that the size of the intermediate data can be well bounded near to the number of triangles in the graph. To further reduce the shuffle size and memory cost, we also propose improved algorithms based on a compact data structure, and present several optimization techniques to accelerate the computation and reduce the memory consumption. The extensive experimental results show that our algorithms outperform existing competitors by several times on both synthetic graphs and real world graphs.     

Efficient approximation algorithms for shortest cycles in undirected graphs

We describe a simple combinatorial approximation algorithm for finding a shortest (simple) cycle in an undirected graph. Given an adjacency-list representation of an undirected graph G with n vertices and unknown girth k, our algorithm returns with high probability a cycle of length at most 2k for even k and 2k+2 for odd k, in time . Thus, in general, it yields a approximation. For a weighted, undirected graph, with non-negative edge weights in the range {1,2,…,M}, we present a simple combinatorial 2-approximation algorithm for a minimum weight (simple) cycle that runs in time O(n²logn(logn+logM)).     

Representing temporal knowledge in conceptual graphs

This study was motivated by some difficulties encountered by the authors when trying to express temporal knowledge using Sowa's conceptual graph (CG) approach. An overview of Sowa's approach is given and the difficulties encountered when trying to model temporal knowledge are outlined: the disparity of notations allowed by CG theory for expressing temporal information; the ambiguity and incompleteness of tense sspecification; the difficulty of harmonizing tenses and intergraph temporal relations. Various approaches suggested for representing time both in artificial intelligence and linguistics are presented, and an extension to Sowa's approach is proposed in which temporal and nontemporal knowledge are differentiated. In this model points in time are represented as well as time intervals. A semantic interpretation of verbs is provided based on an extension of Reichenbach's model of temporal markers. The authors show how their approach enables the representation of tenses as well as the aspectual properties of natural language sentences.