我们专注于使用图形神经网络(GNN)模型来分类的图形分类,该模型预先计算了使用并行排列的邻域聚合图操作员的Bank的节点功能。这些GNN模型具有降低培训和推理时间,由于预兆,而且还与流行的GNN变体不同,这些VNN变体通过训练期间通过顺序邻域聚合过程更新节点特征。我们提供了理论条件,其中具有平行邻域聚集(简称PA-GNN的PA-GNN)的通用GNN模型作为鉴别非同胞图的众所周知的Weisfeiler-Lehman(WL)曲线构同试验。虽然PA-GNN模型与WL测试没有明显的关系,但我们表明从这两种方法获得的图形嵌入是无标有关的。然后,我们提出了一个专门的PA-GNN模型,称为旋转,从而携带开发的条件。我们通过数值实验证明了开发的模型在许多不同的现实世界数据集上实现了最先进的性能,同时保持WL测试的辨别力和训练过程之前预处理图的计算优势。
translated by 谷歌翻译
Graph Neural Networks (GNNs) are an effective framework for representation learning of graphs. GNNs follow a neighborhood aggregation scheme, where the representation vector of a node is computed by recursively aggregating and transforming representation vectors of its neighboring nodes. Many GNN variants have been proposed and have achieved state-of-the-art results on both node and graph classification tasks. However, despite GNNs revolutionizing graph representation learning, there is limited understanding of their representational properties and limitations. Here, we present a theoretical framework for analyzing the expressive power of GNNs to capture different graph structures. Our results characterize the discriminative power of popular GNN variants, such as Graph Convolutional Networks and GraphSAGE, and show that they cannot learn to distinguish certain simple graph structures. We then develop a simple architecture that is provably the most expressive among the class of GNNs and is as powerful as the Weisfeiler-Lehman graph isomorphism test. We empirically validate our theoretical findings on a number of graph classification benchmarks, and demonstrate that our model achieves state-of-the-art performance. * Equal contribution. † Work partially performed while in Tokyo, visiting Prof. Ken-ichi Kawarabayashi.
translated by 谷歌翻译
图表可以模拟实体之间的复杂交互,它在许多重要的应用程序中自然出现。这些应用程序通常可以投入到标准图形学习任务中,其中关键步骤是学习低维图表示。图形神经网络(GNN)目前是嵌入方法中最受欢迎的模型。然而,邻域聚合范例中的标准GNN患有区分\ EMPH {高阶}图形结构的有限辨别力,而不是\ EMPH {低位}结构。为了捕获高阶结构,研究人员求助于主题和开发的基于主题的GNN。然而,现有的基于主基的GNN仍然仍然遭受较少的辨别力的高阶结构。为了克服上述局限性,我们提出了一个新颖的框架,以更好地捕获高阶结构的新框架,铰接于我们所提出的主题冗余最小化操作员和注射主题组合的新颖框架。首先,MGNN生成一组节点表示W.R.T.每个主题。下一阶段是我们在图案中提出的冗余最小化,该主题在彼此相互比较并蒸馏出每个主题的特征。最后,MGNN通过组合来自不同图案的多个表示来执行节点表示的更新。特别地,为了增强鉴别的功率,MGNN利用重新注射功能来组合表示的函数w.r.t.不同的主题。我们进一步表明,我们的拟议体系结构增加了GNN的表现力,具有理论分析。我们展示了MGNN在节点分类和图形分类任务上的七个公共基准上表现出最先进的方法。
translated by 谷歌翻译
Graph classification is an important area in both modern research and industry. Multiple applications, especially in chemistry and novel drug discovery, encourage rapid development of machine learning models in this area. To keep up with the pace of new research, proper experimental design, fair evaluation, and independent benchmarks are essential. Design of strong baselines is an indispensable element of such works. In this thesis, we explore multiple approaches to graph classification. We focus on Graph Neural Networks (GNNs), which emerged as a de facto standard deep learning technique for graph representation learning. Classical approaches, such as graph descriptors and molecular fingerprints, are also addressed. We design fair evaluation experimental protocol and choose proper datasets collection. This allows us to perform numerous experiments and rigorously analyze modern approaches. We arrive to many conclusions, which shed new light on performance and quality of novel algorithms. We investigate application of Jumping Knowledge GNN architecture to graph classification, which proves to be an efficient tool for improving base graph neural network architectures. Multiple improvements to baseline models are also proposed and experimentally verified, which constitutes an important contribution to the field of fair model comparison.
translated by 谷歌翻译
近年来,基于Weisfeiler-Leman算法的算法和神经架构,是一个众所周知的Graph同构问题的启发式问题,它成为具有图形和关系数据的机器学习的强大工具。在这里,我们全面概述了机器学习设置中的算法的使用,专注于监督的制度。我们讨论了理论背景,展示了如何将其用于监督的图形和节点表示学习,讨论最近的扩展,并概述算法的连接(置换 - )方面的神经结构。此外,我们概述了当前的应用和未来方向,以刺激进一步的研究。
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能够递归地集成本地结构和节点特征。然而,基于1跳邻域神经消息传递的过去的GNN算法暴露于对局部结构和关系的信息丢失的风险。在本文中,我们提出了邻居边缘聚合器(近),这是通过边缘聚集在邻域中的节点之间的关系的框架。近的,可以与图同构网络(GIN)正交结合,提供描述邻域中的节点的集成信息。因此,接近可以在1跳邻域中反映每个节点的局部结构的局部结构的附加信息。多图分类任务的实验结果表明,我们的算法在基于GNN的其他基于GNN的基于GNN的算法中取得了良好的改进。
translated by 谷歌翻译
Most graph neural network models rely on a particular message passing paradigm, where the idea is to iteratively propagate node representations of a graph to each node in the direct neighborhood. While very prominent, this paradigm leads to information propagation bottlenecks, as information is repeatedly compressed at intermediary node representations, which causes loss of information, making it practically impossible to gather meaningful signals from distant nodes. To address this issue, we propose shortest path message passing neural networks, where the node representations of a graph are propagated to each node in the shortest path neighborhoods. In this setting, nodes can directly communicate between each other even if they are not neighbors, breaking the information bottleneck and hence leading to more adequately learned representations. Theoretically, our framework generalizes message passing neural networks, resulting in provably more expressive models, and we show that some recent state-of-the-art models are special instances of this framework. Empirically, we verify the capacity of a basic model of this framework on dedicated synthetic experiments, and on real-world graph classification and regression benchmarks, and obtain state-of-the-art results.
translated by 谷歌翻译
图形内核是历史上最广泛使用的图形分类任务的技术。然而,由于图的手工制作的组合特征,这些方法具有有限的性能。近年来,由于其性能卓越,图形神经网络(GNNS)已成为与下游图形相关任务的最先进的方法。大多数GNN基于消息传递神经网络(MPNN)框架。然而,最近的研究表明,MPNN不能超过Weisfeiler-Lehman(WL)算法在图形同构术中的力量。为了解决现有图形内核和GNN方法的限制,在本文中,我们提出了一种新的GNN框架,称为\ Texit {内核图形神经网络}(Kernnns),该框架将图形内核集成到GNN的消息传递过程中。通过卷积神经网络(CNNS)中的卷积滤波器的启发,KERGNNS采用可训练的隐藏图作为绘图过滤器,该绘图过滤器与子图组合以使用图形内核更新节点嵌入式。此外,我们表明MPNN可以被视为Kergnns的特殊情况。我们将Kergnns应用于多个与图形相关的任务,并使用交叉验证来与基准进行公平比较。我们表明,与现有的现有方法相比,我们的方法达到了竞争性能,证明了增加GNN的表现能力的可能性。我们还表明,KERGNNS中的训练有素的图形过滤器可以揭示数据集的本地图形结构,与传统GNN模型相比,显着提高了模型解释性。
translated by 谷歌翻译
图形神经网络已成为从图形结构数据学习的不可缺少的工具之一,并且它们的实用性已在各种各样的任务中显示。近年来,建筑设计的巨大改进,导致各种预测任务的性能更好。通常,这些神经架构在同一层中使用可知的权重矩阵组合节点特征聚合和特征转换。这使得分析从各种跳过的节点特征和神经网络层的富有效力来挑战。由于不同的图形数据集显示在特征和类标签分布中的不同级别和异常级别,因此必须了解哪些特征对于没有任何先前信息的预测任务是重要的。在这项工作中,我们将节点特征聚合步骤和深度与图形神经网络分离,并经验分析了不同的聚合特征在预测性能中发挥作用。我们表明,并非通过聚合步骤生成的所有功能都很有用,并且通常使用这些较少的信息特征可能对GNN模型的性能有害。通过我们的实验,我们表明学习这些功能的某些子集可能会导致各种数据集的性能更好。我们建议使用Softmax作为常规器,并从不同跳距的邻居聚合的功能的“软选择器”;和L2 - GNN层的标准化。结合这些技术,我们呈现了一个简单浅的模型,特征选择图神经网络(FSGNN),并经验展示所提出的模型比九个基准数据集中的最先进的GNN模型实现了可比或甚至更高的准确性节点分类任务,具有显着的改进,可达51.1%。
translated by 谷歌翻译
Graph神经网络(GNN)最近已成为使用图的机器学习的主要范式。对GNNS的研究主要集中于消息传递神经网络(MPNNS)的家族。与同构的Weisfeiler-Leman(WL)测试类似,这些模型遵循迭代的邻域聚合过程以更新顶点表示,并通过汇总顶点表示来更新顶点图表。尽管非常成功,但在过去的几年中,对MPNN进行了深入的研究。因此,需要新颖的体系结构,这将使该领域的研究能够脱离MPNN。在本文中,我们提出了一个新的图形神经网络模型,即所谓的$ \ pi $ -gnn,该模型学习了每个图的“软”排列(即双随机)矩阵,从而将所有图形投影到一个共同的矢量空间中。学到的矩阵在输入图的顶点上强加了“软”顺序,并基于此顺序,将邻接矩阵映射到向量中。这些向量可以被送入完全连接或卷积的层,以应对监督的学习任务。在大图的情况下,为了使模型在运行时间和记忆方面更有效,我们进一步放松了双随机矩阵,以使其排列随机矩阵。我们从经验上评估了图形分类和图形回归数据集的模型,并表明它与最新模型达到了性能竞争。
translated by 谷歌翻译
In the last few years, graph neural networks (GNNs) have become the standard toolkit for analyzing and learning from data on graphs. This emerging field has witnessed an extensive growth of promising techniques that have been applied with success to computer science, mathematics, biology, physics and chemistry. But for any successful field to become mainstream and reliable, benchmarks must be developed to quantify progress. This led us in March 2020 to release a benchmark framework that i) comprises of a diverse collection of mathematical and real-world graphs, ii) enables fair model comparison with the same parameter budget to identify key architectures, iii) has an open-source, easy-to-use and reproducible code infrastructure, and iv) is flexible for researchers to experiment with new theoretical ideas. As of December 2022, the GitHub repository has reached 2,000 stars and 380 forks, which demonstrates the utility of the proposed open-source framework through the wide usage by the GNN community. In this paper, we present an updated version of our benchmark with a concise presentation of the aforementioned framework characteristics, an additional medium-sized molecular dataset AQSOL, similar to the popular ZINC, but with a real-world measured chemical target, and discuss how this framework can be leveraged to explore new GNN designs and insights. As a proof of value of our benchmark, we study the case of graph positional encoding (PE) in GNNs, which was introduced with this benchmark and has since spurred interest of exploring more powerful PE for Transformers and GNNs in a robust experimental setting.
translated by 谷歌翻译
Advanced methods of applying deep learning to structured data such as graphs have been proposed in recent years. In particular, studies have focused on generalizing convolutional neural networks to graph data, which includes redefining the convolution and the downsampling (pooling) operations for graphs. The method of generalizing the convolution operation to graphs has been proven to improve performance and is widely used. However, the method of applying downsampling to graphs is still difficult to perform and has room for improvement. In this paper, we propose a graph pooling method based on selfattention. Self-attention using graph convolution allows our pooling method to consider both node features and graph topology. To ensure a fair comparison, the same training procedures and model architectures were used for the existing pooling methods and our method. The experimental results demonstrate that our method achieves superior graph classification performance on the benchmark datasets using a reasonable number of parameters.
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 谷歌翻译
尽管图形神经网络(GNNS)已成功地用于节点分类任务并在图中链接预测任务,但学习图级表示仍然是一个挑战。对于图级表示,重要的是要学习相邻节点的表示形式,即聚合和图形结构信息。为此目标开发了许多图形合并方法。但是,大多数现有的合并方法都使用K-HOP社区,而无需考虑图中的明确结构信息。在本文中,我们提出了使用先前的图形结构来克服限制的结构原型指导池(SPGP)。 SPGP将图形结构制定为可学习的原型向量,并计算节点和原型矢量之间的亲和力。这导致了一种新颖的节点评分方案,该方案在封装图形的有用结构的同时优先考虑信息性节点。我们的实验结果表明,SPGP的精度和可扩展性都优于图形分类基准数据集上的最先进的图形合并方法。
translated by 谷歌翻译
消息传递神经网络(MPNNS)是由于其简单性和可扩展性而大部分地进行图形结构数据的深度学习的领先架构。不幸的是,有人认为这些架构的表现力有限。本文提出了一种名为Comifariant Subgraph聚合网络(ESAN)的新颖框架来解决这个问题。我们的主要观察是,虽然两个图可能无法通过MPNN可区分,但它们通常包含可区分的子图。因此,我们建议将每个图形作为由某些预定义策略导出的一组子图,并使用合适的等分性架构来处理它。我们为图同构同构同构造的1立维Weisfeiler-Leman(1-WL)测试的新型变体,并在这些新的WL变体方面证明了ESAN的表达性下限。我们进一步证明,我们的方法增加了MPNNS和更具表现力的架构的表现力。此外,我们提供了理论结果,描述了设计选择诸如子图选择政策和等效性神经结构的设计方式如何影响我们的架构的表现力。要处理增加的计算成本,我们提出了一种子图采样方案,可以将其视为我们框架的随机版本。关于真实和合成数据集的一套全面的实验表明,我们的框架提高了流行的GNN架构的表现力和整体性能。
translated by 谷歌翻译
图形神经网络(GNN)是一个强大的工具,可以在图形上执行标准机器学习。为了在非欧几里德图形数据中的每个节点的欧几里德表示,GNN沿着图形的边缘递归地遵循邻域聚合和信息的组合。尽管文献中具有许多GNN变体,但没有模型可以处理具有间隔值的节点的图形。本文提出了一个间隔valuedPraph神经网络,这是一个新的GNN模型,在其中,首次放松了特征空间的限制。由于任何可数集始终是通用集合$ r ^ {n} $的子集,我们的模型比现有模型更为一般。这里,为了处理间隔值的特征向量,我们提出了一种新的间隔聚合方案,并表现出其捕捉不同间隔结构的表现力。我们通过将其性能与在多个基准网络和合成数据集上的最先进模型的性能进行比较,验证了我们对图形分类任务的模型的理论调查结果。
translated by 谷歌翻译
图形神经网络(GNN)已被证明具有强大的表示能力,可以利用该图形在图形结构数据(例如分子和社交网络)上的下游预测任务。他们通常通过从单个顶点的$ K $ - 霍普社区或图表中的枚举步行中汇总信息来学习表示形式。先前的研究表明,将加权方案纳入GNN的有效性。但是,到目前为止,这主要仅限于$ k $ hop的社区GNNS。在本文中,我们旨在设计一种将加权方案纳入步行式GNN并分析其效果的算法。我们提出了一种称为Aware的新型GNN模型,该模型使用注意方案汇总了有关图中的步行的信息。这导致了在标准设置中用于图形预测任务的端到端监督学习方法,其中输入是图形的邻接和顶点信息,并且输出是图形的预测标签。然后,我们对Aware进行理论,经验和解释性分析。我们在简化设置中的理论分析确定了可证明的保证的成功条件,证明了图表信息如何在表示中编码,以及意识中的加权方案如何影响表示和学习绩效。我们的实验表明,在分子财产预测和社交网络领域的标准设置中,在图形预测任务中意识到的强劲表现。最后,我们的解释研究表明,意识到可以成功捕获输入图的重要子结构。该代码可在$ \ href {https://github.com/mehmetfdemirel/aware} {github} $上获得。
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 谷歌翻译
本文研究了辍学图神经网络(DAVERGNNS),一种旨在克服标准GNN框架的局限性的新方法。在DAMPGNNS中,我们在输入图上执行多个GNN运行,其中一些节点随机且独立地在这些运行中丢弃。然后,我们将这些运行的结果结合起来获得最终结果。我们证明DAMPGNN可以区分无法通过GNN的消息分隔的各种图形邻域。我们导出了确保可靠分布辍学所需的运行数量的理论界限,我们证明了有关DACKGNNS的表现能力和限制的若干特性。我们在实验上验证了我们对表现力的理论结果。此外,我们表明DOWNNNS在已建立的GNN基准上表现得很竞争。
translated by 谷歌翻译