卷积神经网络（CNN）已通过卷积和汇总实现了图像分类的重大进展。特别是，图像池将连接的离散网格转换为具有相同连接性的还原网格，并允许还原功能考虑图像的所有像素。但是，对于图形而不存在满足此类属性的合并。实际上，某些方法基于一个顶点选择步骤，该步骤会导致重要信息丢失。其他方法学习了顶点集的模糊聚类，该聚类几乎诱导了几乎完全减少的图形。我们建议使用名为MivSpool的新合并方法克服这两个问题。该方法基于使用最大独立顶点集（MIV）和将其余顶点分配给幸存者的最大独立顶点集（MIV）的选择的顶点。因此，我们的方法不会丢弃任何顶点信息，也不会人为地增加图的密度。实验结果表明，各种标准数据集上的图形分类的精度有所提高。

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.

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

在处理大规模网络和关系数据时，降低图是基本的。它们可以通过在粗糙的结构中求解它们来缩小高度计算影响的尺寸。同时，图减少起着在图神经网络中合并层的作用，从结构中提取多分辨率表示。在这些情况下，还原机制保留距离关系和拓扑特性的能力似乎是基本的，以及可扩展性，使其能够应用于实际大小的问题。在本文中，我们基于最大重量$ k $独立的集合的图理论概念引入了图形粗化机制，从而提供了一种贪婪的算法，该算法允许在GPU上有效地并行实现。我们的方法是常规数据（图像，序列）中的第一个图形结构化对应物。我们证明了在路径长度上的失真界限的理论保证，以及在污垢图中保留关键拓扑特性的能力。我们利用这些概念来定义我们在图形分类任务中经验评估的图表合并机制，表明它与文献中的合并方法进行了比较。

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.

Graph Neural Networks (GNNs) are deep learning models designed to process attributed graphs. GNNs can compute cluster assignments accounting both for the vertex features and for the graph topology. Existing GNNs for clustering are trained by optimizing an unsupervised minimum cut objective, which is approximated by a Spectral Clustering (SC) relaxation. SC offers a closed-form solution that, however, is not particularly useful for a GNN trained with gradient descent. Additionally, the SC relaxation is loose and yields overly smooth cluster assignments, which do not separate well the samples. We propose a GNN model that optimizes a tighter relaxation of the minimum cut based on graph total variation (GTV). Our model has two core components: i) a message-passing layer that minimizes the $\ell_1$ distance in the features of adjacent vertices, which is key to achieving sharp cluster transitions; ii) a loss function that minimizes the GTV in the cluster assignments while ensuring balanced partitions. By optimizing the proposed loss, our model can be self-trained to perform clustering. In addition, our clustering procedure can be used to implement graph pooling in deep GNN architectures for graph classification. Experiments show that our model outperforms other GNN-based approaches for clustering and graph pooling.

自引入以来，图形注意力网络在图表表示任务中取得了出色的结果。但是，这些网络仅考虑节点之间的成对关系，然后它们无法完全利用许多现实世界数据集中存在的高阶交互。在本文中，我们介绍了细胞注意网络（CANS），这是一种在图表上定义的数据上运行的神经体系结构，将图表示为介绍的细胞复合物的1个骨骼，以捕获高阶相互作用。特别是，我们利用细胞复合物中的下层和上层社区来设计两种独立的掩盖自我发项机制，从而推广了常规的图形注意力策略。罐中使用的方法是层次结构的，并结合了以下步骤：i）从{\ it node demantion}中学习{\ it Edge功能}的提升算法}; ii）一种细胞注意机制，可以在下层和上邻居上找到边缘特征的最佳组合； iii）层次{\ it Edge Pooling}机制，以提取一组紧凑的有意义的功能集。实验结果表明，CAN是一种低复杂性策略，它与基于图的学​​习任务的最新结果相比。

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.

在处理表格数据时，基于回归和决策树的模型是一个流行的选择，因为与其他模型类别相比，它们在此类任务上提供了高精度及其易于应用。但是，在图形结构数据方面，当前的树学习算法不提供管理数据结构的工具，而不是依靠功能工程。在这项工作中，我们解决了上述差距，并引入了图形树（GTA），这是一个新的基于树的学习算法，旨在在图形上操作。 GTA既利用图形结构又利用了顶点的特征，并采用了一种注意机制，该机制允许决策专注于图形的子结构。我们分析了GTA模型，并表明它们比平原决策树更具表现力。我们还在多个图和节点预测基准上证明了GTA的好处。在这些实验中，GTA始终优于其他基于树的模型，并且通常优于其他类型的图形学习算法，例如图形神经网络（GNNS）和图核。最后，我们还为GTA提供了一种解释性机制，并证明它可以提供直观的解释。

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

我们专注于使用图形神经网络（GNN）模型来分类的图形分类，该模型预先计算了使用并行排列的邻域聚合图操作员的Bank的节点功能。这些GNN模型具有降低培训和推理时间，由于预兆，而且还与流行的GNN变体不同，这些VNN变体通过训练期间通过顺序邻域聚合过程更新节点特征。我们提供了理论条件，其中具有平行邻域聚集（简称PA-GNN的PA-GNN）的通用GNN模型作为鉴别非同胞图的众所周知的Weisfeiler-Lehman（WL）曲线构同试验。虽然PA-GNN模型与WL测试没有明显的关系，但我们表明从这两种方法获得的图形嵌入是无标有关的。然后，我们提出了一个专门的PA-GNN模型，称为旋转，从而携带开发的条件。我们通过数值实验证明了开发的模型在许多不同的现实世界数据集上实现了最先进的性能，同时保持WL测试的辨别力和训练过程之前预处理图的计算优势。

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

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

在用于图形结构数据的几台机器学习任务中，所考虑的图形可以由不同数量的节点组成。因此，需要设计汇集方法，该方法将不同大小的图形表示聚合到固定大小的表示，其可以用于下游任务，例如图形分类。现有的图形池池方法没有关于图形表示的相似性和其汇总版的保证。在这项工作中，我们通过提出流池来解决这些限制，通过最小化其Wassersein距离，通过最佳地将图形表示的统计数据统计到其汇集的对应物。这是通过对汇集的图形表示来执行Wasserstein梯度流来实现的。我们提出了我们的方法，可以通过任何基础成本考虑表示空间的几何形状。该实施依赖于与最近提出的隐式差异化方案的Wasserstein距离的计算。我们的汇集方法可用于自动分化，可以集成在端到端的深度学习架构中。此外，流量池是不变的，因此可以与GNN中的置换设备提取层组合，以便获得与节点的排序无关的预测。实验结果表明，与现有在图形分类任务中的现有汇集方法相比，我们的方法导致性能增加。

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

尽管图形神经网络（GNNS）已成功地用于节点分类任务并在图中链接预测任务，但学习图级表示仍然是一个挑战。对于图级表示，重要的是要学习相邻节点的表示形式，即聚合和图形结构信息。为此目标开发了许多图形合并方法。但是，大多数现有的合并方法都使用K-HOP社区，而无需考虑图中的明确结构信息。在本文中，我们提出了使用先前的图形结构来克服限制的结构原型指导池（SPGP）。 SPGP将图形结构制定为可学习的原型向量，并计算节点和原型矢量之间的亲和力。这导致了一种新颖的节点评分方案，该方案在封装图形的有用结构的同时优先考虑信息性节点。我们的实验结果表明，SPGP的精度和可扩展性都优于图形分类基准数据集上的最先进的图形合并方法。

The goal of graph summarization is to represent large graphs in a structured and compact way. A graph summary based on equivalence classes preserves pre-defined features of a graph's vertex within a $k$-hop neighborhood such as the vertex labels and edge labels. Based on these neighborhood characteristics, the vertex is assigned to an equivalence class. The calculation of the assigned equivalence class must be a permutation invariant operation on the pre-defined features. This is achieved by sorting on the feature values, e. g., the edge labels, which is computationally expensive, and subsequently hashing the result. Graph Neural Networks (GNN) fulfill the permutation invariance requirement. We formulate the problem of graph summarization as a subgraph classification task on the root vertex of the $k$-hop neighborhood. We adapt different GNN architectures, both based on the popular message-passing protocol and alternative approaches, to perform the structural graph summarization task. We compare different GNNs with a standard multi-layer perceptron (MLP) and Bloom filter as non-neural method. For our experiments, we consider four popular graph summary models on a large web graph. This resembles challenging multi-class vertex classification tasks with the numbers of classes ranging from $576$ to multiple hundreds of thousands. Our results show that the performance of GNNs are close to each other. In three out of four experiments, the non-message-passing GraphMLP model outperforms the other GNNs. The performance of the standard MLP is extraordinary good, especially in the presence of many classes. Finally, the Bloom filter outperforms all neural architectures by a large margin, except for the dataset with the fewest number of $576$ classes.

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

学习图形结构与图形神经网络（GNN）的数据被涌现为一个重要领域，因为它在生物信息学，化疗，社交网络分析和数据挖掘中的广泛适用性。最近的GNN算法基于神经消息传递，这使得GNN能够递归地集成本地结构和节点特征。然而，基于1跳邻域神经消息传递的过去的GNN算法暴露于对局部结构和关系的信息丢失的风险。在本文中，我们提出了邻居边缘聚合器（近），这是通过边缘聚集在邻域中的节点之间的关系的框架。近的，可以与图同构网络（GIN）正交结合，提供描述邻域中的节点的集成信息。因此，接近可以在1跳邻域中反映每个节点的局部结构的局部结构的附加信息。多图分类任务的实验结果表明，我们的算法在基于GNN的其他基于GNN的基于GNN的算法中取得了良好的改进。