图形神经网络（GNN）已成为一种学习关系数据的强大技术。由于他们执行的消息传递步骤数量相对有限 - 因此一个较小的接收领域，人们对通过结合基础图的结构方面来提高其表现力引起了极大的兴趣。在本文中，我们探讨了亲和力措施作为图形神经网络中的特征，特别是由随机步行引起的措施，包括有效的阻力，击球和通勤时间。我们根据这些功能提出消息传递网络，并评估其在各种节点和图形属性预测任务上的性能。我们的体系结构具有较低的计算复杂性，而我们的功能对于基础图的排列不变。我们计算的措施使网络可以利用图表的连接性能，从而使我们能够超过相关的基准，用于各种任务，通常具有更少的消息传递步骤。在OGB-LSC-PCQM4MV1的最大公共图形回归数据集之一中，我们在编写时获得了最著名的单模验证MAE。

近年来，基于Weisfeiler-Leman算法的算法和神经架构，是一个众所周知的Graph同构问题的启发式问题，它成为具有图形和关系数据的机器学习的强大工具。在这里，我们全面概述了机器学习设置中的算法的使用，专注于监督的制度。我们讨论了理论背景，展示了如何将其用于监督的图形和节点表示学习，讨论最近的扩展，并概述算法的连接（置换 - ）方面的神经结构。此外，我们概述了当前的应用和未来方向，以刺激进一步的研究。

图形神经网络（GNNS）的表现力量受到限制，具有远程交互的斗争，缺乏模拟高阶结构的原则性方法。这些问题可以归因于计算图表和输入图结构之间的强耦合。最近提出的消息通过单独的网络通过执行图形的Clique复合物的消息来自然地解耦这些元素。然而，这些模型可能受到单纯复合物（SCS）的刚性组合结构的严重限制。在这项工作中，我们将最近的基于常规细胞复合物的理论结果扩展到常规细胞复合物，灵活地满满SCS和图表的拓扑物体。我们表明，该概括提供了一组强大的图表“提升”转换，每个图形是导致唯一的分层消息传递过程。我们集体呼叫CW Networks（CWNS）的结果方法比WL测试更强大，而不是比3 WL测试更强大。特别是，当应用于分子图问题时，我们证明了一种基于环的一个这样的方案的有效性。所提出的架构从可提供的较大的表达效益于常用的GNN，高阶信号的原则建模以及压缩节点之间的距离。我们展示了我们的模型在各种分子数据集上实现了最先进的结果。

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.

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.

我们提出了一个食谱，讲述了如何建立具有线性复杂性和最先进的结果的一般，功能可扩展的（GPS）图形变压器，并在各种基准测试基准上。 Graph Transformers（GTS）在图形表示学习领域中获得了多种近期出版物的知名度，但它们对构成良好的位置或结构编码的共同基础以及与众不同的区别。在本文中，我们总结了具有更清晰的定义的不同类型的编码，并将其分类为$ \ textit {local} $，$ \ textit {global} $或$ \ textit {fextit {ferseal} $。此外，GTS仍被限制在具有数百个节点的小图上，我们提出了第一个具有复杂性线性的体系结构对节点和边缘$ O（n+e）$的数量，通过将局部实质汇总从完全 - 连接的变压器。我们认为，这种解耦并不会对表现性产生负面影响，而我们的体系结构是图形的通用函数近似器。我们的GPS配方包括选择3种主要成分：（i）位置/结构编码，（ii）局部消息通讯机制和（iii）全局注意机制。我们构建和开源一个模块化框架$ \ textit {graphgps} $，该{GraphGps} $支持多种类型的编码，并且在小图和大图中提供效率和可扩展性。我们在11个基准测试上测试了我们的体系结构，并对所有这些基准显示出非常具竞争力的结果，展示了由模块化和不同策略组合获得的经验益处。

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.

图形神经网络（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在所有基准数据集中都取得了竞争成果。

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),

我们提出了一个新的图形神经网络，我们称为AgentNet，该网络专为图形级任务而设计。 AgentNet的灵感来自子宫性算法，具有独立于图形大小的计算复杂性。代理Net的体系结构从根本上与已知图神经网络的体系结构不同。在AgentNet中，一些受过训练的\ textit {神经代理}智能地行走图，然后共同决定输出。我们提供了对AgentNet的广泛理论分析：我们表明，代理可以学会系统地探索其邻居，并且AgentNet可以区分某些甚至3-WL无法区分的结构。此外，AgentNet能够将任何两个图形分开，这些图在子图方面完全不同。我们通过在难以辨认的图和现实图形分类任务上进行合成实验来确认这些理论结果。在这两种情况下，我们不仅与标准GNN相比，而且与计算更昂贵的GNN扩展相比。

在本文中，我们提供了一种使用图形神经网络（GNNS）的理论，用于多节点表示学习（我们有兴趣学习一组多个节点的表示）。我们知道GNN旨在学习单节点表示。当我们想学习涉及多个节点的节点集表示时，先前作品中的常见做法是直接将GNN学习的多节点表示与节点集的关节表示。在本文中，我们显示了这种方法的基本限制，即无法捕获节点集中节点之间的依赖性，并且认为直接聚合各个节点表示不会导致多个节点的有效关节表示。然后，我们注意到，以前的一些成功的工作作品用于多节点表示学习，包括密封，距离编码和ID-GNN，所有使用的节点标记。这些方法根据应用GNN之前的与目标节点集的关系，首先标记图中的节点。然后，在标记的图表中获得的节点表示被聚合到节点集表示中。通过调查其内部机制，我们将这些节点标记技术统一到单个和最基本的形式，即标记技巧。我们证明，通过标记技巧，可以获得足够富有表现力的GNN学习最具表现力的节点集表示，因此原则上可以解决节点集的任何联合学习任务。关于一个重要的双节点表示学习任务，链接预测，验证了我们理论的实验。我们的工作建立了使用GNN在节点集上使用GNN进行联合预测任务的理论基础。

我们表明，没有图形特异性修改的标准变压器可以在理论和实践中都带来图形学习的有希望的结果。鉴于图，我们只是将所有节点和边缘视为独立的令牌，用令牌嵌入增强它们，然后将它们馈入变压器。有了适当的令牌嵌入选择，我们证明这种方法在理论上至少与不变的图形网络（2-ign）一样表达，由等效线性层组成，它已经比所有消息传播的图形神经网络（GNN）更具表现力）。当在大规模图数据集（PCQM4MV2）上接受训练时，与具有精致的图形特异性电感偏置相比，与GNN基准相比，与GNN基准相比，与GNN基准相比，与GNN基准相比，我们创造的令牌化图形变压器（Tokengt）取得了明显更好的结果。我们的实施可从https://github.com/jw9730/tokengt获得。

大多数图形神经网络（GNNS）无法区分某些图形或图中的某些节点。这使得无法解决某些分类任务。但是，在这些模型中添加其他节点功能可以解决此问题。我们介绍了几种这样的增强，包括（i）位置节点嵌入，（ii）规范节点ID和（iii）随机特征。这些扩展是由理论结果激励的，并通过对合成子图检测任务进行广泛测试来证实。我们发现位置嵌入在这些任务中的其他扩展大大超过了其他扩展。此外，位置嵌入具有更好的样品效率，在不同的图形分布上表现良好，甚至超过了地面真实节点位置。最后，我们表明，不同的增强功能在既定的GNN基准中都具有竞争力，并建议何时使用它们。

图形神经网络（GNN）在许多基于图的学​​习任务中表现出很大的优势，但通常无法准确预测基于任务的节点集，例如链接/主题预测等。最近，许多作品通过使用随机节点功能或节点距离特征来解决此问题。但是，它们的收敛速度缓慢，预测不准确或高复杂性。在这项工作中，我们重新访问允许使用位置编码（PE）技术（例如Laplacian eigenmap，deepwalk等）的节点的位置特征。 。在这里，我们以原则性的方式研究了这些问题，并提出了一种可证明的解决方案，这是一类用严格数学分析的钉子的GNN层。 PEG使用单独的频道来更新原始节点功能和位置功能。 PEG施加置换量比W.R.T.原始节点功能并施加$ O（P）$（正交组）均值W.R.T.位置特征同时特征，其中$ p $是二手位置特征的维度。在8个现实世界网络上进行的广泛链接预测实验证明了PEG在概括和可伸缩性方面的优势。

通过定向消息传递通过方向消息通过的图形神经网络最近在多个分子特性预测任务上设置了最先进的技术。然而，它们依赖于通常不可用的原子位置信息，并获得它通常非常昂贵甚至不可能。在本文中，我们提出了合成坐标，使得能够使用高级GNN而不需要真正的分子配置。我们提出了两个距离作为合成坐标：使用个性化PageRank的对称变体指定分子配置的粗糙范围和基于图的距离的距离界限。为了利用距离和角度信息，我们提出了一种将正常图形神经网络转换为定向MPNN的方法。我们表明，通过这种转变，我们可以将正常图形神经网络的误差减少55％在锌基准。我们还通过在SMP和DimeNet ++模型中纳入合成坐标，在锌和自由QM9上设定了最新技术。我们的实现可在线获取。

图表可以模拟实体之间的复杂交互，它在许多重要的应用程序中自然出现。这些应用程序通常可以投入到标准图形学习任务中，其中关键步骤是学习低维图表示。图形神经网络（GNN）目前是嵌入方法中最受欢迎的模型。然而，邻域聚合范例中的标准GNN患有区分\ EMPH {高阶}图形结构的有限辨别力，而不是\ EMPH {低位}结构。为了捕获高阶结构，研究人员求助于主题和开发的基于主题的GNN。然而，现有的基于主基的GNN仍然仍然遭受较少的辨别力的高阶结构。为了克服上述局限性，我们提出了一个新颖的框架，以更好地捕获高阶结构的新框架，铰接于我们所提出的主题冗余最小化操作员和注射主题组合的新颖框架。首先，MGNN生成一组节点表示W.R.T.每个主题。下一阶段是我们在图案中提出的冗余最小化，该主题在彼此相互比较并蒸馏出每个主题的特征。最后，MGNN通过组合来自不同图案的多个表示来执行节点表示的更新。特别地，为了增强鉴别的功率，MGNN利用重新注射功能来组合表示的函数w.r.t.不同的主题。我们进一步表明，我们的拟议体系结构增加了GNN的表现力，具有理论分析。我们展示了MGNN在节点分类和图形分类任务上的七个公共基准上表现出最先进的方法。

尽管（消息通话）图形神经网络在图形或一般关系数据上近似置换量等函数方面具有明显的局限性，但更具表现力的高阶图神经网络不会扩展到大图。他们要么在$ k $ - 订单张量子上操作，要么考虑所有$ k $ - 节点子图，这意味着在内存需求中对$ k $的指数依赖，并且不适合图形的稀疏性。通过为图同构问题引入新的启发式方法，我们设计了一类通用的，置换式的图形网络，与以前的体系结构不同，该网络在表达性和可伸缩性之间提供了细粒度的控制，并适应了图的稀疏性。这些体系结构与监督节点和图形级别的标准高阶网络以及回归体系中的标准高阶图网络相比大大减少了计算时间，同时在预测性能方面显着改善了标准图神经网络和图形内核体系结构。

消息传递神经网络（MPNNS）是由于其简单性和可扩展性而大部分地进行图形结构数据的深度学习的领先架构。不幸的是，有人认为这些架构的表现力有限。本文提出了一种名为Comifariant Subgraph聚合网络（ESAN）的新颖框架来解决这个问题。我们的主要观察是，虽然两个图可能无法通过MPNN可区分，但它们通常包含可区分的子图。因此，我们建议将每个图形作为由某些预定义策略导出的一组子图，并使用合适的等分性架构来处理它。我们为图同构同构同构造的1立维Weisfeiler-Leman（1-WL）测试的新型变体，并在这些新的WL变体方面证明了ESAN的表达性下限。我们进一步证明，我们的方法增加了MPNNS和更具表现力的架构的表现力。此外，我们提供了理论结果，描述了设计选择诸如子图选择政策和等效性神经结构的设计方式如何影响我们的架构的表现力。要处理增加的计算成本，我们提出了一种子图采样方案，可以将其视为我们框架的随机版本。关于真实和合成数据集的一套全面的实验表明，我们的框架提高了流行的GNN架构的表现力和整体性能。

Deploying graph neural networks (GNNs) on whole-graph classification or regression tasks is known to be challenging: it often requires computing node features that are mindful of both local interactions in their neighbourhood and the global context of the graph structure. GNN architectures that navigate this space need to avoid pathological behaviours, such as bottlenecks and oversquashing, while ideally having linear time and space complexity requirements. In this work, we propose an elegant approach based on propagating information over expander graphs. We leverage an efficient method for constructing expander graphs of a given size, and use this insight to propose the EGP model. We show that EGP is able to address all of the above concerns, while requiring minimal effort to set up, and provide evidence of its empirical utility on relevant graph classification datasets and baselines in the Open Graph Benchmark. Importantly, using expander graphs as a template for message passing necessarily gives rise to negative curvature. While this appears to be counterintuitive in light of recent related work on oversquashing, we theoretically demonstrate that negatively curved edges are likely to be required to obtain scalable message passing without bottlenecks. To the best of our knowledge, this is a previously unstudied result in the context of graph representation learning, and we believe our analysis paves the way to a novel class of scalable methods to counter oversquashing in GNNs.

在过去十年中，图形内核引起了很多关注，并在结构化数据上发展成为一种快速发展的学习分支。在过去的20年中，该领域发生的相当大的研究活动导致开发数十个图形内核，每个图形内核都对焦于图形的特定结构性质。图形内核已成功地成功地在广泛的域中，从社交网络到生物信息学。本调查的目标是提供图形内核的文献的统一视图。特别是，我们概述了各种图形内核。此外，我们对公共数据集的几个内核进行了实验评估，并提供了比较研究。最后，我们讨论图形内核的关键应用，并概述了一些仍有待解决的挑战。