链接预测是图形上非常基本的任务。在本文中受到传统路径的方法的启发,我们提出了一种基于链路预测路径的一般和灵活的表示学习框架。具体地,我们将一对节点的表示定义为所有路径表示的广义和,每个路径表示为路径中的边缘表示的广义乘积。通过贝尔曼-Ford算法来解决最短路径问题,我们表明,所提出的路径配方可以通过广义的Bellman-Ford算法有效地解决。为了进一步提高路径制构的能力,我们提出了神经贝尔曼 - 福特网络(NBFNET),这是一种全图神经网络框架,其解决了通过广义Bellman-Ford算法中的学习运算符的路径制定。 NBFNET使用3个神经元件,即指示器,消息和聚合函数参数,即分别对应于边界条件,乘法运算符和求和运算符。 NBFNET非常一般,涵盖许多传统的基于路径的方法,并且可以应用于转导和归纳设置的同质图和多关系图(例如,知识图表)。两个均匀图表和知识图表的实验表明,所提出的NBFNET在转换和归纳设置中的大幅度优于现有方法,实现了新的最先进的结果。
translated by 谷歌翻译
基于分解的模型(FMS),例如Distmult,在知识图完成(KGC)任务中享有持久的成功,通常优于图形神经网络(GNNS)。但是,与GNN不同,FMS难以合并节点特征并概括在归纳环境中看不见的节点。我们的工作通过提出重构GNN来弥合FMS和GNN之间的差距。这种新的体系结构借鉴了两种建模范式,以前在很大程度上被认为是不结合的。具体地说,使用消息通讯的形式主义,我们通过将梯度下降程序重新定义为消息传播操作来展示如何将FMS施加为GNN,这构成了我们重构GNN的基础。在众多成熟的KGC基准测试中,我们的重构GNN可以实现与FMS相当的转导性能以及最先进的归纳性能,同时使用较少的参数阶数。
translated by 谷歌翻译
Formulating and answering logical queries is a standard communication interface for knowledge graphs (KGs). Alleviating the notorious incompleteness of real-world KGs, neural methods achieved impressive results in link prediction and complex query answering tasks by learning representations of entities, relations, and queries. Still, most existing query answering methods rely on transductive entity embeddings and cannot generalize to KGs containing new entities without retraining the entity embeddings. In this work, we study the inductive query answering task where inference is performed on a graph containing new entities with queries over both seen and unseen entities. To this end, we devise two mechanisms leveraging inductive node and relational structure representations powered by graph neural networks (GNNs). Experimentally, we show that inductive models are able to perform logical reasoning at inference time over unseen nodes generalizing to graphs up to 500% larger than training ones. Exploring the efficiency--effectiveness trade-off, we find the inductive relational structure representation method generally achieves higher performance, while the inductive node representation method is able to answer complex queries in the inference-only regime without any training on queries and scales to graphs of millions of nodes. Code is available at https://github.com/DeepGraphLearning/InductiveQE.
translated by 谷歌翻译
在本文中,我们提供了一种使用图形神经网络(GNNS)的理论,用于多节点表示学习(我们有兴趣学习一组多个节点的表示)。我们知道GNN旨在学习单节点表示。当我们想学习涉及多个节点的节点集表示时,先前作品中的常见做法是直接将GNN学习的多节点表示与节点集的关节表示。在本文中,我们显示了这种方法的基本限制,即无法捕获节点集中节点之间的依赖性,并且认为直接聚合各个节点表示不会导致多个节点的有效关节表示。然后,我们注意到,以前的一些成功的工作作品用于多节点表示学习,包括密封,距离编码和ID-GNN,所有使用的节点标记。这些方法根据应用GNN之前的与目标节点集的关系,首先标记图中的节点。然后,在标记的图表中获得的节点表示被聚合到节点集表示中。通过调查其内部机制,我们将这些节点标记技术统一到单个和最基本的形式,即标记技巧。我们证明,通过标记技巧,可以获得足够富有表现力的GNN学习最具表现力的节点集表示,因此原则上可以解决节点集的任何联合学习任务。关于一个重要的双节点表示学习任务,链接预测,验证了我们理论的实验。我们的工作建立了使用GNN在节点集上使用GNN进行联合预测任务的理论基础。
translated by 谷歌翻译
Graph neural networks (GNNs) have received remarkable success in link prediction (GNNLP) tasks. Existing efforts first predefine the subgraph for the whole dataset and then apply GNNs to encode edge representations by leveraging the neighborhood structure induced by the fixed subgraph. The prominence of GNNLP methods significantly relies on the adhoc subgraph. Since node connectivity in real-world graphs is complex, one shared subgraph is limited for all edges. Thus, the choices of subgraphs should be personalized to different edges. However, performing personalized subgraph selection is nontrivial since the potential selection space grows exponentially to the scale of edges. Besides, the inference edges are not available during training in link prediction scenarios, so the selection process needs to be inductive. To bridge the gap, we introduce a Personalized Subgraph Selector (PS2) as a plug-and-play framework to automatically, personally, and inductively identify optimal subgraphs for different edges when performing GNNLP. PS2 is instantiated as a bi-level optimization problem that can be efficiently solved differently. Coupling GNNLP models with PS2, we suggest a brand-new angle towards GNNLP training: by first identifying the optimal subgraphs for edges; and then focusing on training the inference model by using the sampled subgraphs. Comprehensive experiments endorse the effectiveness of our proposed method across various GNNLP backbones (GCN, GraphSage, NGCF, LightGCN, and SEAL) and diverse benchmarks (Planetoid, OGB, and Recommendation datasets). Our code is publicly available at \url{https://github.com/qiaoyu-tan/PS2}
translated by 谷歌翻译
在知识图上回答复杂的一阶逻辑(FOL)查询是多跳推理的基本任务。传统的符号方法穿越完整的知识图来提取答案,从而为每个步骤提供良好的解释。最近的神经方法学习复杂查询的几何嵌入。这些方法可以推广到不完整的知识图,但是它们的推理过程很难解释。在本文中,我们提出了图形神经网络查询执行器(GNN-QE),这是一种神经符号模型,享有两全其美的优势。 GNN-QE将复杂的数据分解为模糊集的关系预测和逻辑操作,这为中间变量提供了解释性。为了理解丢失的链接,GNN-QE从知识图完成中调整了图神经网络以执行关系预测,并使用产品模糊逻辑对逻辑操作进行建模。 3个数据集的实验表明,GNN-QE在回答FOL查询时显着改善了先前的最新模型。同时,GNN-QE可以在没有明确监督的情况下预测答案的数量,并为中间变量提供可视化。
translated by 谷歌翻译
链接预测是图神经网络(GNN)的重要应用。链接预测的大多数现有GNN基于一维Weisfeiler-Lehman(1-WL)测试。 1-wl-gnn首先通过迭代的相邻节点特征来计算中心,然后通过汇总成对节点表示来获得链接表示。正如先前的作品所指出的那样,这两步过程会导致较低的区分功能,因为自然而然地学习节点级表示而不是链接级别。在本文中,我们研究了一种完全不同的方法,该方法可以基于\ textit {二维WEISFEILER-LEHMAN(2-WL)测试直接获得节点对(链接)表示。 2-WL测试直接使用链接(2个小说)作为消息传递单元而不是节点,因此可以直接获得链接表示。我们理论上分析了2-WL测试的表达能力以区分非晶状体链接,并证明其优越的链接与1-WL相比。基于不同的2-WL变体,我们提出了一系列用于链路预测的新型2-WL-GNN模型。在广泛的现实数据集上进行的实验证明了它们对最先进的基线的竞争性能以及优于普通1-WL-GNN的优势。
translated by 谷歌翻译
Knowledge graph (KG) link prediction aims to infer new facts based on existing facts in the KG. Recent studies have shown that using the graph neighborhood of a node via graph neural networks (GNNs) provides more useful information compared to just using the query information. Conventional GNNs for KG link prediction follow the standard message-passing paradigm on the entire KG, which leads to over-smoothing of representations and also limits their scalability. On a large scale, it becomes computationally expensive to aggregate useful information from the entire KG for inference. To address the limitations of existing KG link prediction frameworks, we propose a novel retrieve-and-read framework, which first retrieves a relevant subgraph context for the query and then jointly reasons over the context and the query with a high-capacity reader. As part of our exemplar instantiation for the new framework, we propose a novel Transformer-based GNN as the reader, which incorporates graph-based attention structure and cross-attention between query and context for deep fusion. This design enables the model to focus on salient context information relevant to the query. Empirical results on two standard KG link prediction datasets demonstrate the competitive performance of the proposed method.
translated by 谷歌翻译
图表可以表示实体之间的关系信息,图形结构广泛用于许多智能任务,例如搜索,推荐和问题应答。然而,实际上大多数图形结构数据都遭受了不完整性,因此链路预测成为一个重要的研究问题。虽然提出了许多模型来用于链路预测,但以下两个问题仍然仍然较少:(1)大多数方法在不利用相关链路中使用丰富的信息,大多数方法都独立模型,并且(2)现有型号主要基于关联设计学习并没有考虑推理。通过这些问题,在本文中,我们提出了图表协作推理(GCR),它可以使用邻居与逻辑推理视角的关系中的关系推理。我们提供了一种简单的方法来将图形结构转换为逻辑表达式,以便链路预测任务可以转换为神经逻辑推理问题。我们应用逻辑受限的神经模块根据逻辑表达式构建网络架构,并使用反向传播以有效地学习模型参数,这在统一架构中桥接可分辨率的学习和象征性推理。为了展示我们工作的有效性,我们对图形相关任务进行实验,例如基于常用的基准数据集的链路预测和推荐,我们的图表合作推理方法实现了最先进的性能。
translated by 谷歌翻译
Pre-publication draft of a book to be published byMorgan & Claypool publishers. Unedited version released with permission. All relevant copyrights held by the author and publisher extend to this pre-publication draft.
translated by 谷歌翻译
最近提出了基于子图的图表学习(SGRL)来应对规范图神经网络(GNNS)遇到的一些基本挑战,并在许多重要的数据科学应用(例如链接,关系和主题预测)中证明了优势。但是,当前的SGRL方法遇到了可伸缩性问题,因为它们需要为每个培训或测试查询提取子图。扩大规范GNN的最新解决方案可能不适用于SGRL。在这里,我们通过共同设计学习算法及其系统支持,为可扩展的SGRL提出了一种新颖的框架Surel。 Surel采用基于步行的子图表分解,并将步行重新形成子图,从而大大降低了子图提取的冗余并支持并行计算。具有数百万个节点和边缘的六个同质,异质和高阶图的实验证明了Surel的有效性和可扩展性。特别是,与SGRL基线相比,Surel可以实现10 $ \ times $ Quad-Up,具有可比甚至更好的预测性能;与规范GNN相比,Surel可实现50%的预测准确性。
translated by 谷歌翻译
归纳链路预测(ILP)是考虑到新兴知识图(kgs)中未见实体的联系,考虑到KGS的发展性质。一个更具挑战性的场景是,新兴的kg仅由看不见的实体组成,被称为已断开新兴kgs(DEKGS)。 DEKGS的现有研究仅专注于预测封闭链接,即预测新兴KG内部的联系。到目前为止,先前的工作尚未对将进化信息从原始KG到DEKG进行进化信息。为了填补空白,我们提出了一个名为DEKG-ILP的新型模型(由以下两个组成部分组成的dekg-ilp(断开新兴知识图形的归纳链路预测)。 (1)模块CLRM(基于对比的关系特定特征特征建模)是为了提取基于全球关系的语义特征而开发的,它们在原始KGS和DEKGS之间以新颖的采样策略共享。 (2)提出了模块GSM(基于GNN的子图建模),以提取围绕KGS中每个链接的局部子图拓扑信息。在几个基准数据集上进行的广泛实验表明,与最新方法相比,DEKG-ILP具有明显的性能改进,用于封闭和桥接链路预测。源代码可在线获得。
translated by 谷歌翻译
Link prediction is a key problem for network-structured data. Link prediction heuristics use some score functions, such as common neighbors and Katz index, to measure the likelihood of links. They have obtained wide practical uses due to their simplicity, interpretability, and for some of them, scalability. However, every heuristic has a strong assumption on when two nodes are likely to link, which limits their effectiveness on networks where these assumptions fail. In this regard, a more reasonable way should be learning a suitable heuristic from a given network instead of using predefined ones. By extracting a local subgraph around each target link, we aim to learn a function mapping the subgraph patterns to link existence, thus automatically learning a "heuristic" that suits the current network. In this paper, we study this heuristic learning paradigm for link prediction. First, we develop a novel γ-decaying heuristic theory. The theory unifies a wide range of heuristics in a single framework, and proves that all these heuristics can be well approximated from local subgraphs. Our results show that local subgraphs reserve rich information related to link existence. Second, based on the γ-decaying theory, we propose a new method to learn heuristics from local subgraphs using a graph neural network (GNN). Its experimental results show unprecedented performance, working consistently well on a wide range of problems.
translated by 谷歌翻译
Learning node embeddings that capture a node's position within the broader graph structure is crucial for many prediction tasks on graphs. However, existing Graph Neural Network (GNN) architectures have limited power in capturing the position/location of a given node with respect to all other nodes of the graph. Here we propose Position-aware Graph Neural Networks (P-GNNs), a new class of GNNs for computing position-aware node embeddings. P-GNN first samples sets of anchor nodes, computes the distance of a given target node to each anchor-set, and then learns a non-linear distance-weighted aggregation scheme over the anchor-sets. This way P-GNNs can capture positions/locations of nodes with respect to the anchor nodes. P-GNNs have several advantages: they are inductive, scalable, and can incorporate node feature information. We apply P-GNNs to multiple prediction tasks including link prediction and community detection. We show that P-GNNs consistently outperform state of the art GNNs, with up to 66% improvement in terms of the ROC AUC score.Node embedding methods can be categorized into Graph Neural Networks (GNNs) approaches (Scarselli et al., 2009),
translated by 谷歌翻译
图形神经网络(GNNS)最流行的设计范例是1跳消息传递 - 反复反复从1跳邻居聚集特征。但是,1-HOP消息传递的表达能力受Weisfeiler-Lehman(1-WL)测试的界定。最近,研究人员通过同时从节点的K-Hop邻居汇总信息传递到K-HOP消息。但是,尚无分析K-Hop消息传递的表达能力的工作。在这项工作中,我们从理论上表征了K-Hop消息传递的表达力。具体而言,我们首先正式区分了两种k-hop消息传递的内核,它们在以前的作品中经常被滥用。然后,我们通过表明它比1-Hop消息传递更强大,从而表征了K-Hop消息传递的表现力。尽管具有较高的表达能力,但我们表明K-Hop消息传递仍然无法区分一些简单的常规图。为了进一步增强其表现力,我们引入了KP-GNN框架,该框架通过利用每个跳跃中的外围子图信息来改善K-HOP消息。我们证明,KP-GNN可以区分几乎所有常规图,包括一些距离常规图,这些图无法通过以前的距离编码方法来区分。实验结果验证了KP-GNN的表达能力和有效性。 KP-GNN在所有基准数据集中都取得了竞争成果。
translated by 谷歌翻译
最近,图形神经网络(GNNS)在各种现实情景中获得了普及。尽管取得了巨大成功,但GNN的建筑设计严重依赖于体力劳动。因此,自动化图形神经网络(Autopmn)引起了研究界的兴趣和关注,近年来显着改善。然而,现有的autopnn工作主要采用隐式方式来模拟并利用图中的链接信息,这对图中的链路预测任务不充分规范化,并限制了自动启动的其他图表任务。在本文中,我们介绍了一个新的Autognn工作,该工作明确地模拟了缩写为autogel的链接信息。以这种方式,AutoGel可以处理链路预测任务并提高Autognns对节点分类和图形分类任务的性能。具体地,AutoGel提出了一种新的搜索空间,包括层内和层间设计中的各种设计尺寸,并采用更强大的可分辨率搜索算法,以进一步提高效率和有效性。基准数据集的实验结果展示了自动池上的优势在几个任务中。
translated by 谷歌翻译
时间图代表实体之间的动态关系,并发生在许多现实生活中的应用中,例如社交网络,电子商务,通信,道路网络,生物系统等。他们需要根据其生成建模和表示学习的研究超出与静态图有关的研究。在这项调查中,我们全面回顾了近期针对处理时间图提出的神经时间依赖图表的学习和生成建模方法。最后,我们确定了现有方法的弱点,并讨论了我们最近发表的论文提格的研究建议[24]。
translated by 谷歌翻译
事实证明,信息提取方法可有效从结构化或非结构化数据中提取三重。以(头部实体,关系,尾部实体)形式组织这样的三元组的组织称为知识图(kgs)。当前的大多数知识图都是不完整的。为了在下游任务中使用kgs,希望预测kgs中缺少链接。最近,通过将实体和关系嵌入到低维的矢量空间中,旨在根据先前访问的三元组来预测三元组,从而对KGS表示不同的方法。根据如何独立或依赖对三元组进行处理,我们将知识图完成的任务分为传统和图形神经网络表示学习,并更详细地讨论它们。在传统的方法中,每个三重三倍将独立处理,并在基于GNN的方法中进行处理,三倍也考虑了他们的当地社区。查看全文
translated by 谷歌翻译
大型知识图(KGS)提供人类知识的结构化表示。然而,由于不可能包含所有知识,KGs通常不完整。基于现有事实的推理铺平了一种发现缺失事实的方法。在本文中,我们研究了了解完成缺失事实三胞胎的知识图表的推理的学习逻辑规则问题。学习逻辑规则将具有很强的解释性的模型以及概括到类似任务的能力。我们提出了一种称为MPLR的模型,可以改进现有模型以完全使用培训数据,并且考虑多目标方案。此外,考虑到缺乏评估模型表现和开采规则的质量,我们进一步提出了两名新颖的指标来帮助解决问题。实验结果证明我们的MPLR模型在五个基准数据集中优于最先进的方法。结果还证明了指标的有效性。
translated by 谷歌翻译
近年来,异构图形神经网络(HGNNS)一直在开花,但每个工作所使用的独特数据处理和评估设置会让他们的进步完全了解。在这项工作中,我们通过使用其官方代码,数据集,设置和超参数来展示12个最近的HGNN的系统再现,揭示了关于HGNN的进展的令人惊讶的结果。我们发现,由于设置不当,简单的均匀GNN,例如GCN和GAT在很大程度上低估了。具有适当输入的GAT通常可以匹配或优于各种场景的所有现有HGNN。为了促进稳健和可重复的HGNN研究,我们构建异构图形基准(HGB),由具有三个任务的11个不同数据集组成。 HGB标准化异构图数据分割,特征处理和性能评估的过程。最后,我们介绍了一个简单但非常强大的基线简单 - HGN - 这显着优于HGB上以前的所有模型 - 以加速未来HGNN的进步。
translated by 谷歌翻译