最近,引入了亚图增强图神经网络(SGNN),以增强图形神经网络(GNN)的表达能力,事实证明,该功能不高于一维Weisfeiler-Leman同构测试。新的范式建议使用从输入图中提取的子图提高模型的表现力,但是额外的复杂性加剧了GNNS中本来可以具有挑战性的问题:解释其预测。在这项工作中,我们将PGEXPlainer(GNNS的最新解释者之一)改编为SGNN。拟议的解释器解释了所有不同子图的贡献,并可以产生人类可以解释的有意义的解释。我们在真实和合成数据集上执行的实验表明,我们的框架成功地解释了SGNN在图形分类任务上的决策过程。
translated by 谷歌翻译
消息传递神经网络(MPNNS)是由于其简单性和可扩展性而大部分地进行图形结构数据的深度学习的领先架构。不幸的是,有人认为这些架构的表现力有限。本文提出了一种名为Comifariant Subgraph聚合网络(ESAN)的新颖框架来解决这个问题。我们的主要观察是,虽然两个图可能无法通过MPNN可区分,但它们通常包含可区分的子图。因此,我们建议将每个图形作为由某些预定义策略导出的一组子图,并使用合适的等分性架构来处理它。我们为图同构同构同构造的1立维Weisfeiler-Leman(1-WL)测试的新型变体,并在这些新的WL变体方面证明了ESAN的表达性下限。我们进一步证明,我们的方法增加了MPNNS和更具表现力的架构的表现力。此外,我们提供了理论结果,描述了设计选择诸如子图选择政策和等效性神经结构的设计方式如何影响我们的架构的表现力。要处理增加的计算成本,我们提出了一种子图采样方案,可以将其视为我们框架的随机版本。关于真实和合成数据集的一套全面的实验表明,我们的框架提高了流行的GNN架构的表现力和整体性能。
translated by 谷歌翻译
Graph Neural Networks (GNNs) are a powerful tool for machine learning on graphs. GNNs combine node feature information with the graph structure by recursively passing neural messages along edges of the input graph. However, incorporating both graph structure and feature information leads to complex models and explaining predictions made by GNNs remains unsolved. Here we propose GNNEXPLAINER, the first general, model-agnostic approach for providing interpretable explanations for predictions of any GNN-based model on any graph-based machine learning task. Given an instance, GNNEXPLAINER identifies a compact subgraph structure and a small subset of node features that have a crucial role in GNN's prediction. Further, GNNEXPLAINER can generate consistent and concise explanations for an entire class of instances. We formulate GNNEXPLAINER as an optimization task that maximizes the mutual information between a GNN's prediction and distribution of possible subgraph structures. Experiments on synthetic and real-world graphs show that our approach can identify important graph structures as well as node features, and outperforms alternative baseline approaches by up to 43.0% in explanation accuracy. GNNEXPLAINER provides a variety of benefits, from the ability to visualize semantically relevant structures to interpretability, to giving insights into errors of faulty GNNs.
translated by 谷歌翻译
子图GNNS是最近表达的图形神经网络(GNN)的一类,它们将图形图形为子图的集合。到目前为止,可能的子图GNN体系结构的设计空间及其基本理论属性仍然在很大程度上尚未探索。在本文中,我们研究了子图方法的最突出形式,该方法采用了基于节点的子图选择策略,例如自我网络或节点标记和删除。我们解决了两个中心问题:(1)这些方法的表达能力的上限是什么? (2)在这些子图集上传递层的模棱两可的消息家族是什么?我们回答这些问题的第一步是一种新颖的对称分析,该分析表明,建模基于节点的子图集的对称性需要比以前的作品中所采用的对称组明显小。然后,该分析用于建立子图GNN和不变图网络(IGNS)之间的联系。我们通过首先通过3-WL来界定子图方法的表达能力,然后提出一个通用子图方法的一般家族,以将所有先前基于节点的子图GNN泛化。最后,我们设计了一个新颖的子图Gnn称为Sun,从理论上讲,该子gnn统一了以前的体系结构,同时在多个基准上提供了更好的经验性能。
translated by 谷歌翻译
最近出现了许多子图增强图神经网络(GNN),可证明增强了标准(消息通话)GNN的表达能力。但是,对这些方法之间的相互关系和weisfeiler层次结构的关系有限。此外,当前的方法要么使用给定尺寸的所有子图,要随机均匀地对其进行采样,或者使用手工制作的启发式方法,而不是学习以数据驱动的方式选择子图。在这里,我们提供了一种统一的方法来研究此类体系结构,通过引入理论框架并扩展了亚图增强GNN的已知表达结果。具体而言,我们表明,增加子图的大小总是会增加表达能力,并通过将它们与已建立的$ k \ text { - } \ Mathsf {Wl} $ hierArchy联系起来,从而更好地理解其局限性。此外,我们还使用最近通过复杂的离散概率分布进行反向传播的方法探索了学习对子图进行采样的不同方法。从经验上讲,我们研究了不同子图增强的GNN的预测性能,表明我们的数据驱动体系结构与非DATA驱动的亚图增强图形神经网络相比,在标准基准数据集上提高了对标准基准数据集的预测准确性,同时减少了计算时间。
translated by 谷歌翻译
在这项工作中,我们开发了一种新的方法,名为局部排列的图形神经网络,它为建立在本地节点邻域,通过子图形的构建图形神经网络的框架,同时使用置换等值更新功能。消息传递神经网络的消息被认为是有效应功率的限制,并且最近过度的方法缺乏可扩展性或需要将结构信息被编码为特征空间。这里呈现的一般框架克服了通过通过受限制表示在子图上操作的与全局排列等值相关的可扩展性问题。此外,我们证明了通过使用限制的陈述没有丧失表情。此外,所提出的框架仅需要选择$ k $-hops,用于创建用于为每层使用的子图和选择的表示空间,这使得该方法在一系列基于图形的域中可以容易地适用。我们通过实验验证了一系列图形基准分类任务的方法,在所有基准上展示了最先进的结果或非常竞争力的结果。此外,我们证明使用本地更新函数的使用在全球方法上提供了GPU存储器的显着改进。
translated by 谷歌翻译
在高措施应用中大量部署图神经网络(GNNS)对对噪声的强大解释产生了强烈的需求,这些解释与人类的直觉很好。大多数现有方法通过识别与预测有很强相关性的输入图的子图来生成解释。这些解释对噪声并不强大,因为独立优化单个输入的相关性很容易过分拟合噪声。此外,它们与人类直觉并不十分吻合,因为从输入图中删除已识别的子图并不一定会改变预测结果。在本文中,我们提出了一种新颖的方法,可以通过在类似的输入图上明确建模GNNS的共同决策逻辑来生成对GNN的强大反事实解释。我们的解释自然对噪声是强大的,因为它们是由控制许多类似输入图的GNN的共同决策边界产生的。该解释也与人类的直觉很好地吻合,因为从输入图中的解释中删除了一组边缘,从而显着改变了预测。许多公共数据集上的详尽实验证明了我们方法的出色性能。
translated by 谷歌翻译
我们研究了图神经网络(GNN)的解释性,作为阐明其工作机制的一步。尽管大多数当前方法都集中在解释图节点,边缘或功能上,但我们认为,作为GNNS的固有功能机制,消息流对执行解释性更为自然。为此,我们在这里提出了一种新颖的方法,即FlowX,以通过识别重要的消息流来解释GNN。为了量化流量的重要性,我们建议遵循合作游戏理论中沙普利价值观的哲学。为了解决计算所有联盟边际贡献的复杂性,我们提出了一个近似方案,以计算类似沙普利的值,作为进一步再分配训练的初步评估。然后,我们提出一种学习算法来训练流量评分并提高解释性。关于合成和现实世界数据集的实验研究表明,我们提出的FlowX导致GNN的解释性提高。
translated by 谷歌翻译
Recently, graph neural networks (GNNs) have revolutionized the field of graph representation learning through effectively learned node embeddings, and achieved state-of-the-art results in tasks such as node classification and link prediction. However, current GNN methods are inherently flat and do not learn hierarchical representations of graphs-a limitation that is especially problematic for the task of graph classification, where the goal is to predict the label associated with an entire graph. Here we propose DIFFPOOL, a differentiable graph pooling module that can generate hierarchical representations of graphs and can be combined with various graph neural network architectures in an end-to-end fashion. DIFFPOOL learns a differentiable soft cluster assignment for nodes at each layer of a deep GNN, mapping nodes to a set of clusters, which then form the coarsened input for the next GNN layer. Our experimental results show that combining existing GNN methods with DIFFPOOL yields an average improvement of 5-10% accuracy on graph classification benchmarks, compared to all existing pooling approaches, achieving a new state-of-the-art on four out of five benchmark data sets.
translated by 谷歌翻译
With the increasing use of Graph Neural Networks (GNNs) in critical real-world applications, several post hoc explanation methods have been proposed to understand their predictions. However, there has been no work in generating explanations on the fly during model training and utilizing them to improve the expressive power of the underlying GNN models. In this work, we introduce a novel explanation-directed neural message passing framework for GNNs, EXPASS (EXplainable message PASSing), which aggregates only embeddings from nodes and edges identified as important by a GNN explanation method. EXPASS can be used with any existing GNN architecture and subgraph-optimizing explainer to learn accurate graph embeddings. We theoretically show that EXPASS alleviates the oversmoothing problem in GNNs by slowing the layer wise loss of Dirichlet energy and that the embedding difference between the vanilla message passing and EXPASS framework can be upper bounded by the difference of their respective model weights. Our empirical results show that graph embeddings learned using EXPASS improve the predictive performance and alleviate the oversmoothing problems of GNNs, opening up new frontiers in graph machine learning to develop explanation-based training frameworks.
translated by 谷歌翻译
图形神经网络(GNNS)正在快速成为在多个域中学习图形结构化数据的标准方法,但它们在其决策中缺乏透明度。已经开发了几种基于扰动的方法,以提供对GNN的决策过程的见解。由于这是一个早期研究区域,用于评估生成的解释的方法和数据缺乏成熟。我们探索了这些现有的方法,并识别三个主要领域的普通缺陷:(1)合成数据生成过程,(2)评估指标,以及(3)最终呈现解释。为此目的,我们执行一个实证研究,以探索这些陷阱以及他们意外的后果,并提出补救措施来减轻它们的效果。
translated by 谷歌翻译
近年来,基于Weisfeiler-Leman算法的算法和神经架构,是一个众所周知的Graph同构问题的启发式问题,它成为具有图形和关系数据的机器学习的强大工具。在这里,我们全面概述了机器学习设置中的算法的使用,专注于监督的制度。我们讨论了理论背景,展示了如何将其用于监督的图形和节点表示学习,讨论最近的扩展,并概述算法的连接(置换 - )方面的神经结构。此外,我们概述了当前的应用和未来方向,以刺激进一步的研究。
translated by 谷歌翻译
许多现代神经架构的核心的卷积运算符可以有效地被视为在输入矩阵和滤波器之间执行点产品。虽然这很容易适用于诸如图像的数据,其可以在欧几里德空间中表示为常规网格,延伸卷积操作者以在图形上工作,而是由于它们的不规则结构而被证明更具有挑战性。在本文中,我们建议使用图形内部产品的图形内核,即在图形上计算内部产品,以将标准卷积运算符扩展到图形域。这使我们能够定义不需要计算输入图的嵌入的完全结构模型。我们的架构允许插入任何类型和数量的图形内核,并具有在培训过程中学到的结构面具方面提供一些可解释性的额外益处,类似于传统卷积神经网络中的卷积掩模发生的事情。我们执行广泛的消融研究,调查模型超参数的影响,我们表明我们的模型在标准图形分类数据集中实现了竞争性能。
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 谷歌翻译
对于学习图表表示,并非图中的所有详细结构都与给定的图形任务相关。与任务相关的结构可以是$本地化的$或$稀疏$,仅参与子图或以子图的交互作用(层次结构的角度)。图神经网络应该能够有效提取与任务相关的结构并与无关的部分不变,这对于通用消息传递GNN来说是具有挑战性的。在这项工作中,我们建议从原始图的一系列子图中学习图表表示,以更好地捕获与任务相关的子结构或分层结构,并跳过$ noisy $零件。为此,我们设计了软遮罩GNN层,以通过掩模机制提取所需的子图。软遮罩是在连续空间中定义的,以维持不同部分的重量并表征不同部分的权重。与现有的子图或分层表示方法和图形合并操作相比,软掩模GNN层不受固定样品或降低比率的限制,因此更灵活地提取具有任意尺寸的子图。公共图基准测试的广泛实验表明,软罩机制可以提高性能。它还提供了可解释性,使每个层中掩码的值可视化,使我们能够深入了解模型所学的结构。
translated by 谷歌翻译
图表神经网络(GNNS)最近提出了用于处理图形结构数据的神经网络结构。由于他们所采用的邻国聚合策略,现有的GNNS专注于捕获节点级信息并忽略高级信息。因此,现有的GNN受到本地置换不变性(LPI)问题引起的代表性限制。为了克服这些限制并丰富GNN捕获的特征,我们提出了一种新的GNN框架,称为两级GNN(TL-GNN)。这与节点级信息合并子图级信息。此外,我们提供了对LPI问题的数学分析,这表明子图级信息有利于克服与LPI相关的问题。还提出了一种基于动态编程算法的子图计数方法,并且该具有时间复杂度是O(n ^ 3),n是图的节点的数量。实验表明,TL-GNN优于现有的GNN,实现了最先进的性能。
translated by 谷歌翻译
尽管近期图形神经网络(GNN)进展,但解释了GNN的预测仍然具有挑战性。现有的解释方法主要专注于后性后解释,其中采用另一种解释模型提供培训的GNN的解释。后HOC方法未能揭示GNN的原始推理过程的事实引发了建立GNN与内置解释性的需求。在这项工作中,我们提出了原型图形神经网络(Protgnn),其将原型学习与GNNS相结合,并提供了对GNN的解释的新视角。在Protgnn中,解释自然地从基于案例的推理过程衍生,并且实际在分类期间使用。通过将输入与潜伏空间中的一些学习原型的输入进行比较来获得ProtGnn的预测。此外,为了更好地解释性和更高的效率,结合了一种新颖的条件子图采样模块,以指示输入图的哪个部分与ProtGnn +中的每个原型最相似。最后,我们在各种数据集中评估我们的方法并进行具体的案例研究。广泛的结果表明,Protgnn和Protgnn +可以提供固有的解释性,同时实现与非可解释对方的准确性有关的准确性。
translated by 谷歌翻译
在本文中,我们提供了一种使用图形神经网络(GNNS)的理论,用于多节点表示学习(我们有兴趣学习一组多个节点的表示)。我们知道GNN旨在学习单节点表示。当我们想学习涉及多个节点的节点集表示时,先前作品中的常见做法是直接将GNN学习的多节点表示与节点集的关节表示。在本文中,我们显示了这种方法的基本限制,即无法捕获节点集中节点之间的依赖性,并且认为直接聚合各个节点表示不会导致多个节点的有效关节表示。然后,我们注意到,以前的一些成功的工作作品用于多节点表示学习,包括密封,距离编码和ID-GNN,所有使用的节点标记。这些方法根据应用GNN之前的与目标节点集的关系,首先标记图中的节点。然后,在标记的图表中获得的节点表示被聚合到节点集表示中。通过调查其内部机制,我们将这些节点标记技术统一到单个和最基本的形式,即标记技巧。我们证明,通过标记技巧,可以获得足够富有表现力的GNN学习最具表现力的节点集表示,因此原则上可以解决节点集的任何联合学习任务。关于一个重要的双节点表示学习任务,链接预测,验证了我们理论的实验。我们的工作建立了使用GNN在节点集上使用GNN进行联合预测任务的理论基础。
translated by 谷歌翻译
我们提出了一个新的图形神经网络,我们称为AgentNet,该网络专为图形级任务而设计。 AgentNet的灵感来自子宫性算法,具有独立于图形大小的计算复杂性。代理Net的体系结构从根本上与已知图神经网络的体系结构不同。在AgentNet中,一些受过训练的\ textit {神经代理}智能地行走图,然后共同决定输出。我们提供了对AgentNet的广泛理论分析:我们表明,代理可以学会系统地探索其邻居,并且AgentNet可以区分某些甚至3-WL无法区分的结构。此外,AgentNet能够将任何两个图形分开,这些图在子图方面完全不同。我们通过在难以辨认的图和现实图形分类任务上进行合成实验来确认这些理论结果。在这两种情况下,我们不仅与标准GNN相比,而且与计算更昂贵的GNN扩展相比。
translated by 谷歌翻译
深度学习方法正在实现许多人工智能任务上的不断增长。深层模型的一个主要局限性是它们不适合可解释性。可以通过开发事后技术来解释预测,从而产生解释性领域,从而规避这种限制。最近,关于图像和文本的深层模型的解释性取得了重大进展。在图数据的领域,图形神经网络(GNN)及其解释性正在迅速发展。但是,既没有对GNN解释性方法的统一处理,也没有标准的基准和测试床。在这项调查中,我们提供了当前GNN解释性方法的统一和分类观点。我们对这一主题的统一和分类治疗对现有方法的共同性和差异阐明了灯光,并为进一步的方法论发展奠定了基础。为了促进评估,我们生成了一组专门用于GNN解释性的基准图数据集。我们总结了当前的数据集和指标,以评估GNN的解释性。总的来说,这项工作提供了GNN解释性和评估标准化测试床的统一方法论。
translated by 谷歌翻译