经典的Weisfeiler-Leman算法（又称颜色的细化是图形学习的基础，对于成功的图形内核和图形神经网络至关重要。该算法最初是用于图形同构测试的，它迭代地完善了顶点颜色。在许多数据集中，经过一些迭代后，可以达到稳定的着色，并且机器学习任务的最佳迭代数量通常更低。这表明颜色差异太快，定义了一个太粗糙的相似性。我们概括了颜色改进的概念，并提出了一个逐步邻里改进的框架，该框架使收敛较慢，从而提供了更细粒度的完善层次结构和顶点相似性。我们通过聚类顶点邻域来分配新颜色，从而替换原始的注射颜色分配功能。我们的方法用于得出现有图形内核的新变体，并通过有关顶点相似性的最佳分配来近似图表编辑距离。我们表明，在这两个任务中，我们的方法的表现都优于原始颜色的细化，只有在运行时间中逐渐增加，才能提高最新技术状态。

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

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

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

Weisfeiler-Lehman（WL）测试已广泛应用于图内核，指标和神经网络。但是，它仅考虑图的一致性，从而导致结构信息的描述能力较弱。因此，它限制了应用方法的性能提高。另外，WL检验定义的图之间的相似性和距离是粗略的测量。据我们所知，本文首次阐明了这些事实，并定义了我们称为Wasserstein WL子树（WWLS）距离的指标。我们将WL子树引入节点附近的结构信息，并将其分配给每个节点。然后，我们定义一个基于$ l_1 $ - 应用的树编辑距离（$ l_1 $ - ted）的新图嵌入空间：$ l_1 $ norm of noce noce node node nord noce node fartial farture varter vectors in space上的差异为$ l_1 $ - 节点。我们进一步提出了一种用于图嵌入的快速算法。最后，我们使用Wasserstein距离来反映$ L_1 $的图形级别。 WWL可以捕获传统指标困难的结构的小变化。我们在几个图形分类和度量验证实验中演示了其性能。

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

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

最近出现了许多子图增强图神经网络（GNN），可证明增强了标准（消息通话）GNN的表达能力。但是，对这些方法之间的相互关系和weisfeiler层次结构的关系有限。此外，当前的方法要么使用给定尺寸的所有子图，要随机均匀地对其进行采样，或者使用手工制作的启发式方法，而不是学习以数据驱动的方式选择子图。在这里，我们提供了一种统一的方法来研究此类体系结构，通过引入理论框架并扩展了亚图增强GNN的已知表达结果。具体而言，我们表明，增加子图的大小总是会增加表达能力，并通过将它们与已建立的$ k \ text { - } \ Mathsf {Wl} $ hierArchy联系起来，从而更好地理解其局限性。此外，我们还使用最近通过复杂的离散概率分布进行反向传播的方法探索了学习对子图进行采样的不同方法。从经验上讲，我们研究了不同子图增强的GNN的预测性能，表明我们的数据驱动体系结构与非DATA驱动的亚图增强图形神经网络相比，在标准基准数据集上提高了对标准基准数据集的预测准确性，同时减少了计算时间。

许多现代神经架构的核心的卷积运算符可以有效地被视为在输入矩阵和滤波器之间执行点产品。虽然这很容易适用于诸如图像的数据，其可以在欧几里德空间中表示为常规网格，延伸卷积操作者以在图形上工作，而是由于它们的不规则结构而被证明更具有挑战性。在本文中，我们建议使用图形内部产品的图形内核，即在图形上计算内部产品，以将标准卷积运算符扩展到图形域。这使我们能够定义不需要计算输入图的嵌入的完全结构模型。我们的架构允许插入任何类型和数量的图形内核，并具有在培训过程中学到的结构面具方面提供一些可解释性的额外益处，类似于传统卷积神经网络中的卷积掩模发生的事情。我们执行广泛的消融研究，调查模型超参数的影响，我们表明我们的模型在标准图形分类数据集中实现了竞争性能。

In recent years, graph neural networks (GNNs) have emerged as a promising tool for solving machine learning problems on graphs. Most GNNs are members of the family of message passing neural networks (MPNNs). There is a close connection between these models and the Weisfeiler-Leman (WL) test of isomorphism, an algorithm that can successfully test isomorphism for a broad class of graphs. Recently, much research has focused on measuring the expressive power of GNNs. For instance, it has been shown that standard MPNNs are at most as powerful as WL in terms of distinguishing non-isomorphic graphs. However, these studies have largely ignored the distances between the representations of nodes/graphs which are of paramount importance for learning tasks. In this paper, we define a distance function between nodes which is based on the hierarchy produced by the WL algorithm, and propose a model that learns representations which preserve those distances between nodes. Since the emerging hierarchy corresponds to a tree, to learn these representations, we capitalize on recent advances in the field of hyperbolic neural networks. We empirically evaluate the proposed model on standard node and graph classification datasets where it achieves competitive performance with state-of-the-art models.

近年来，在平衡（超级）图分配算法的设计和评估中取得了重大进展。我们调查了过去十年的实用算法的趋势，用于平衡（超级）图形分区以及未来的研究方向。我们的工作是对先前有关该主题的调查的更新。特别是，该调查还通过涵盖了超图形分区和流算法来扩展先前的调查，并额外关注并行算法。

Graph神经网络（GNN）最近已成为使用图的机器学习的主要范式。对GNNS的研究主要集中于消息传递神经网络（MPNNS）的家族。与同构的Weisfeiler-Leman（WL）测试类似，这些模型遵循迭代的邻域聚合过程以更新顶点表示，并通过汇总顶点表示来更新顶点图表。尽管非常成功，但在过去的几年中，对MPNN进行了深入的研究。因此，需要新颖的体系结构，这将使该领域的研究能够脱离MPNN。在本文中，我们提出了一个新的图形神经网络模型，即所谓的$ \ pi $ -gnn，该模型学习了每个图的“软”排列（即双随机）矩阵，从而将所有图形投影到一个共同的矢量空间中。学到的矩阵在输入图的顶点上强加了“软”顺序，并基于此顺序，将邻接矩阵映射到向量中。这些向量可以被送入完全连接或卷积的层，以应对监督的学习任务。在大图的情况下，为了使模型在运行时间和记忆方面更有效，我们进一步放松了双随机矩阵，以使其排列随机矩阵。我们从经验上评估了图形分类和图形回归数据集的模型，并表明它与最新模型达到了性能竞争。

In this article, we propose a family of efficient kernels for large graphs with discrete node labels. Key to our method is a rapid feature extraction scheme based on the Weisfeiler-Lehman test of isomorphism on graphs. It maps the original graph to a sequence of graphs, whose node attributes capture topological and label information. A family of kernels can be defined based on this Weisfeiler-Lehman sequence of graphs, including a highly efficient kernel comparing subtree-like patterns. Its runtime scales only linearly in the number of edges of the graphs and the length of the Weisfeiler-Lehman graph sequence. In our experimental evaluation, our kernels outperform state-of-the-art graph kernels on several graph classification benchmark data sets in terms of accuracy and runtime. Our kernels open the door to large-scale applications of graph kernels in various disciplines such as computational biology and social network analysis.

这篇综述的目的是将读者介绍到图表内，以将其应用于化学信息学中的分类问题。图内核是使我们能够推断分子的化学特性的功能，可以帮助您完成诸如寻找适合药物设计的化合物等任务。内核方法的使用只是一种特殊的两种方式量化了图之间的相似性。我们将讨论限制在这种方法上，尽管近年来已经出现了流行的替代方法，但最著名的是图形神经网络。

近年来，图形神经网络（GNNS）被出现为一个强大的神经结构，以学习在监督的端到端时尚中的节点和图表的矢量表示。到目前为止，只有经验评估GNNS - 显示有希望的结果。以下工作从理论的角度调查了GNN，并将它们与1美元 - 二维韦斯美犬 - Leman Graph同构Heuristic（1美元-WL）相关联。我们表明GNNS在区分非同义（子）图表中，GNN具有与1美元-WL相同的表现力。因此，这两种算法也具有相同的缺点。基于此，我们提出了GNN的概括，所谓的$ k $ -dimensional gnns（$ k $ -gnns），这可以考虑多个尺度的高阶图结构。这些高阶结构在社交网络和分子图的表征中起重要作用。我们的实验评估证实了我们的理论调查结果，并确认了更高阶信息在图形分类和回归的任务中有用。

图形神经网络（GNNS）是图形处理的广泛连接主义模型。它们对每个节点及其邻居进行迭代消息传递操作，以解决分类/群集任务 - 在某些节点或整个图表上 - 无论其订单如何，都会收集所有此类消息。尽管属于该类的各种模型之间的差异，但大多数基于本地聚合机制和直观地采用相同的计算方案，并直观地，本地计算框架主要负责GNN的表现力。在本文中，我们证明了Weisfeiler - Lehman测试在恰好对应于原始GNN模型上定义的展开等价的图表节点上引起了等效关系。因此，原始GNN的表现力的结果可以扩展到一般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.

即使机器学习算法已经在数据科学中发挥了重要作用，但许多当前方法对输入数据提出了不现实的假设。由于不兼容的数据格式，或数据集中的异质，分层或完全缺少的数据片段，因此很难应用此类方法。作为解决方案，我们提出了一个用于样本表示，模型定义和培训的多功能，统一的框架，称为“ Hmill”。我们深入审查框架构建和扩展的机器学习的多个范围范式。从理论上讲，为HMILL的关键组件的设计合理，我们将通用近似定理的扩展显示到框架中实现的模型所实现的所有功能的集合。本文还包含有关我们实施中技术和绩效改进的详细讨论，该讨论将在MIT许可下发布供下载。该框架的主要资产是其灵活性，它可以通过相同的工具对不同的现实世界数据源进行建模。除了单独观察到每个对象的一组属性的标准设置外，我们解释了如何在框架中实现表示整个对象系统的图表中的消息推断。为了支持我们的主张，我们使用框架解决了网络安全域的三个不同问题。第一种用例涉及来自原始网络观察结果的IoT设备识别。在第二个问题中，我们研究了如何使用以有向图表示的操作系统的快照可以对恶意二进制文件进行分类。最后提供的示例是通过网络中实体之间建模域黑名单扩展的任务。在所有三个问题中，基于建议的框架的解决方案可实现与专业方法相当的性能。

图形神经网络（GNNS）具有有限的表现力量，无法正确代表许多图形类。虽然更具表现力的图表表示学习（GRL）替代方案可以区分其中一些类，但它们明显难以实现，可能不会很好地扩展，并且尚未显示在现实世界任务中优于经过良好调整的GNN。因此，设计简单，可扩展和表现力的GRL架构，也实现了现实世界的改进仍然是一个开放的挑战。在这项工作中，我们展示了图形重建的程度 - 从其子图重建图形 - 可以减轻GRL架构目前面临的理论和实际问题。首先，我们利用图形重建来构建两个新的表达图表表示。其次，我们展示了图形重建如何提升任何GNN架构的表现力，同时是一个（可证明的）强大的归纳偏见，用于侵略性的侵略性。凭经验，我们展示了重建如何提高GNN的表现力 - 同时保持其与顶点的排列的不变性 - 通过解决原始GNN的七个图形属性任务而无法解决。此外，我们展示了如何在九世界基准数据集中提升最先进的GNN性能。

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.