基于变压器的模型已在各个领域（例如自然语言处理和计算机视觉）中广泛使用并实现了最先进的性能。最近的作品表明，变压器也可以推广到图形结构化数据。然而，由于技术挑战，诸如节点数量和非本地聚集的技术挑战之类的技术挑战，因此成功限于小规模图，这通常会导致对常规图神经网络的概括性能。在本文中，为了解决这些问题，我们提出了可变形的图形变压器（DGT），以动态采样的键和值对进行稀疏注意。具体而言，我们的框架首先构建具有各种标准的多个节点序列，以考虑结构和语义接近。然后，将稀疏的注意力应用于节点序列，以减少计算成本，以学习节点表示。我们还设计简单有效的位置编码，以捕获节点之间的结构相似性和距离。实验表明，我们的新型图形变压器始终胜过现有的基于变压器的模型，并且与8个图形基准数据集（包括大型图形）的最新模型相比，与最新的模型相比表现出竞争性能。

近年来，图形变压器在各种图形学习任务上表现出了优势。但是，现有图形变压器的复杂性与节点的数量二次缩放，因此难以扩展到具有数千个节点的图形。为此，我们提出了一个邻域聚集图变压器（Nagphormer），该变压器可扩展到具有数百万节点的大图。在将节点特征馈送到变压器模型中之前，Nagphormer构造令牌由称为Hop2Token的邻域聚合模块为每个节点。对于每个节点，Hop2token聚合从每个跳跃到表示形式的邻域特征，从而产生一系列令牌向量。随后，不同HOP信息的结果序列是变压器模型的输入。通过将每个节点视为一个序列，可以以迷你批量的方式训练Nagphormer，从而可以扩展到大图。 Nagphormer进一步开发了基于注意力的读数功能，以便学习每个跳跃的重要性。我们在各种流行的基准测试中进行了广泛的实验，包括六个小数据集和三个大数据集。结果表明，Nagphormer始终优于现有的图形变压器和主流图神经网络。

图形神经网络（GNNS）显着改善了图形结构数据的表示功率。尽管最近GNN的成功，大多数GNN的图表卷积都有两个限制。由于图形卷积在输入图上的小本地邻域中执行，因此固有地无法捕获距离节点之间的远程依赖性。另外，当节点具有属于不同类别的邻居时，即，异常，来自它们的聚合消息通常会影响表示学习。为了解决图表卷积的两个常见问题，在本文中，我们提出了可变形的图形卷积网络（可变形GCNS），可在多个潜在空间中自适应地执行卷积并捕获节点之间的短/远程依赖性。与节点表示（特征）分开，我们的框架同时学习节点位置嵌入式嵌入式（坐标）以确定节点之间以端到端的方式之间的关系。根据节点位置，卷积内核通过变形向量变形并将不同的变换应用于其邻居节点。我们广泛的实验表明，可变形的GCNS灵活地处理异常的处理，并在六个异化图数据集中实现节点分类任务中的最佳性能。

The Transformer architecture has become a dominant choice in many domains, such as natural language processing and computer vision. Yet, it has not achieved competitive performance on popular leaderboards of graph-level prediction compared to mainstream GNN variants. Therefore, it remains a mystery how Transformers could perform well for graph representation learning. In this paper, we solve this mystery by presenting Graphormer, which is built upon the standard Transformer architecture, and could attain excellent results on a broad range of graph representation learning tasks, especially on the recent OGB Large-Scale Challenge. Our key insight to utilizing Transformer in the graph is the necessity of effectively encoding the structural information of a graph into the model. To this end, we propose several simple yet effective structural encoding methods to help Graphormer better model graph-structured data. Besides, we mathematically characterize the expressive power of Graphormer and exhibit that with our ways of encoding the structural information of graphs, many popular GNN variants could be covered as the special cases of Graphormer. The code and models of Graphormer will be made publicly available at https://github.com/Microsoft/Graphormer.

图形神经网络（GNN）已被广泛应用于各种领域，以通过图形结构数据学习。在各种任务（例如节点分类和图形分类）中，他们对传统启发式方法显示了显着改进。但是，由于GNN严重依赖于平滑的节点特征而不是图形结构，因此在链接预测中，它们通常比简单的启发式方法表现出差的性能，例如，结构信息（例如，重叠的社区，学位和最短路径）至关重要。为了解决这一限制，我们建议邻里重叠感知的图形神经网络（NEO-GNNS），这些神经网络（NEO-GNNS）从邻接矩阵中学习有用的结构特征，并估算了重叠的邻域以进行链接预测。我们的Neo-Gnns概括了基于社区重叠的启发式方法，并处理重叠的多跳社区。我们在开放图基准数据集（OGB）上进行的广泛实验表明，NEO-GNNS始终在链接预测中实现最新性能。我们的代码可在https://github.com/seongjunyun/neo_gnns上公开获取。

变压器架构已成为许多域中的主导选择，例如自然语言处理和计算机视觉。然而，与主流GNN变体相比，它对图形水平预测的流行排行榜没有竞争表现。因此，它仍然是一个谜，变形金机如何对图形表示学习表现良好。在本文中，我们通过提出了基于标准变压器架构构建的Gragemer来解决这一神秘性，并且可以在广泛的图形表示学习任务中获得优异的结果，特别是在最近的OGB大规模挑战上。我们在图中利用变压器的关键洞察是有效地将图形的结构信息有效地编码到模型中。为此，我们提出了几种简单但有效的结构编码方法，以帮助Gramemormer更好的模型图形结构数据。此外，我们在数学上表征了Gramemormer的表现力，并展示了我们编码图形结构信息的方式，许多流行的GNN变体都可以被涵盖为GrameRormer的特殊情况。

多模式的机器学习已被广​​泛研究以开发通用智能。最近，感知者和感知者IO出色的多模式算法对各种数据集域和任务显示了竞争结果。但是，最近的作品，感知者和感知者IO专注于异质模式，包括图像，文本和语音，并且对于图形结构化数据集的研究作品很少。图是最概括的数据集结构之一，我们可以代表其他数据集，包括图像，文本和语音作为图形结构化数据。图具有与其他数据集域（例如文本和图像）不同的邻接矩阵，并且处理拓扑信息，关系信息和规范的位置信息并不微不足道。在这项研究中，我们提供了图形感知器IO，即图形结构化数据集的感知器IO。我们将图形感知器IO的主要结构保留为感知器IO，因为除了图形结构化数据集外，感知器IO已经很好地处理了各种数据集。图形感知器IO是一种通用方法，它可以处理各种数据集，例如图形结构化数据以及文本和图像。比较图形神经网络，图感知器IO需要较低的复杂性，并且可以有效地合并局部和全局信息。我们表明，图形感知器IO显示了与图形相关任务的各种竞争结果，包括节点分类，图形分类和链接预测。

变压器架构最近在图表表示学习中引起了人们的注意，因为它自然地克服了图神经网络（GNN）的几个局限性，避免了它们严格的结构电感偏置，而仅通过位置编码来编码图形结构。在这里，我们表明，具有位置编码的变压器生成的节点表示不一定捕获它们之间的结构相似性。为了解决这个问题，我们提出了结构感知的变压器，这是一类简单而灵活的图形变压器，建立在新的自我发项机制的基础上。这一新的自我注意力通过在计算注意力之前提取植根于每个节点的子图表来结合结构信息。我们提出了几种自动生成子图表表示的方法，并从理论上说明结果表示至少与子图表一样表现力。从经验上讲，我们的方法在五个图预测基准上实现了最先进的性能。我们的结构感知框架可以利用任何现有的GNN提取子图表表示，我们表明它系统地改善了相对于基本GNN模型的性能，成功地结合了GNN和变形金刚的优势。我们的代码可在https://github.com/borgwardtlab/sat上找到。

Graph Neural Networks (GNNs) have shown great potential in the field of graph representation learning. Standard GNNs define a local message-passing mechanism which propagates information over the whole graph domain by stacking multiple layers. This paradigm suffers from two major limitations, over-squashing and poor long-range dependencies, that can be solved using global attention but significantly increases the computational cost to quadratic complexity. In this work, we propose an alternative approach to overcome these structural limitations by leveraging the ViT/MLP-Mixer architectures introduced in computer vision. We introduce a new class of GNNs, called Graph MLP-Mixer, that holds three key properties. First, they capture long-range dependency and mitigate the issue of over-squashing as demonstrated on the Long Range Graph Benchmark (LRGB) and the TreeNeighbourMatch datasets. Second, they offer better speed and memory efficiency with a complexity linear to the number of nodes and edges, surpassing the related Graph Transformer and expressive GNN models. Third, they show high expressivity in terms of graph isomorphism as they can distinguish at least 3-WL non-isomorphic graphs. We test our architecture on 4 simulated datasets and 7 real-world benchmarks, and show highly competitive results on all of them.

现代图形神经网络（GNNS）通过多层本地聚合学习节点嵌入，并在各种图形应用中取得巨大成功。但是，对辅音图的任务通常需要非局部聚合。此外，我们发现本地聚合对某些抵消图表甚至有害。在这项工作中，我们提出了一个简单但有效的非本地聚合框架，具有高效的GNN的关注排序。基于它，我们开发各种非本地GNN。我们进行彻底的实验，以分析Disasstative图数据集并评估我们的非本地GNN。实验结果表明，在模型性能和效率方面，我们的非本地GNN在七个基准数据集上显着优于七个基准数据集。

图形神经网络（GNNS）在各种基于图形的应用中显示了优势。大多数现有的GNNS假设图形结构的强大奇妙并应用邻居的置换不变本地聚合以学习每个节点的表示。然而，它们未能概括到异质图，其中大多数相邻节点具有不同的标签或特征，并且相关节点远处。最近的几项研究通过组合中央节点的隐藏表示（即，基于多跳的方法）的多个跳数来解决这个问题，或者基于注意力分数对相邻节点进行排序（即，基于排名的方法）来解决这个问题。结果，这些方法具有一些明显的限制。一方面，基于多跳的方法没有明确区分相关节点的大量多跳社区，导致严重的过平滑问题。另一方面，基于排名的模型不与结束任务进行联合优化节点排名，并导致次优溶液。在这项工作中，我们呈现图表指针神经网络（GPNN）来解决上述挑战。我们利用指针网络从大量的多跳邻域选择最相关的节点，这根据与中央节点的关系来构造有序序列。然后应用1D卷积以从节点序列中提取高级功能。 GPNN中的基于指针网络的Ranker是以端到端的方式与其他部件进行联合优化的。在具有异质图的六个公共节点分类数据集上进行了广泛的实验。结果表明，GPNN显着提高了最先进方法的分类性能。此外，分析还揭示了拟议的GPNN在过滤出无关邻居并减少过平滑的特权。

Optimization of directed acyclic graph (DAG) structures has many applications, such as neural architecture search (NAS) and probabilistic graphical model learning. Encoding DAGs into real vectors is a dominant component in most neural-network-based DAG optimization frameworks. Currently, most DAG encoders use an asynchronous message passing scheme which sequentially processes nodes according to the dependency between nodes in a DAG. That is, a node must not be processed until all its predecessors are processed. As a result, they are inherently not parallelizable. In this work, we propose a Parallelizable Attention-based Computation structure Encoder (PACE) that processes nodes simultaneously and encodes DAGs in parallel. We demonstrate the superiority of PACE through encoder-dependent optimization subroutines that search the optimal DAG structure based on the learned DAG embeddings. Experiments show that PACE not only improves the effectiveness over previous sequential DAG encoders with a significantly boosted training and inference speed, but also generates smooth latent (DAG encoding) spaces that are beneficial to downstream optimization subroutines. Our source code is available at \url{https://github.com/zehao-dong/PACE}

消息传递已作为设计图形神经网络（GNN）的有效工具的发展。但是，消息传递的大多数现有方法简单地简单或平均所有相邻的功能更新节点表示。它们受到两个问题的限制，即（i）缺乏可解释性来识别对GNN的预测重要的节点特征，以及（ii）特征过度混合，导致捕获长期依赖和无能为力的过度平滑问题在异质或低同质的下方处理图。在本文中，我们提出了一个节点级胶囊图神经网络（NCGNN），以通过改进的消息传递方案来解决这些问题。具体而言，NCGNN表示节点为节点级胶囊组，其中每个胶囊都提取其相应节点的独特特征。对于每个节点级胶囊，开发了一个新颖的动态路由过程，以适应适当的胶囊，以从设计的图形滤波器确定的子图中聚集。 NCGNN聚集仅有利的胶囊并限制无关的消息，以避免交互节点的过度混合特征。因此，它可以缓解过度平滑的问题，并通过同粒或异质的图表学习有效的节点表示。此外，我们提出的消息传递方案本质上是可解释的，并免于复杂的事后解释，因为图形过滤器和动态路由过程确定了节点特征的子集，这对于从提取的子分类中的模型预测最为重要。关于合成和现实图形的广泛实验表明，NCGNN可以很好地解决过度光滑的问题，并为半监视的节点分类产生更好的节点表示。它的表现优于同质和异质的艺术状态。

图形神经网络已成为从图形结构数据学习的不可缺少的工具之一，并且它们的实用性已在各种各样的任务中显示。近年来，建筑设计的巨大改进，导致各种预测任务的性能更好。通常，这些神经架构在同一层中使用可知的权重矩阵组合节点特征聚合和特征转换。这使得分析从各种跳过的节点特征和神经网络层的富有效力来挑战。由于不同的图形数据集显示在特征和类标签分布中的不同级别和异常级别，因此必须了解哪些特征对于没有任何先前信息的预测任务是重要的。在这项工作中，我们将节点特征聚合步骤和深度与图形神经网络分离，并经验分析了不同的聚合特征在预测性能中发挥作用。我们表明，并非通过聚合步骤生成的所有功能都很有用，并且通常使用这些较少的信息特征可能对GNN模型的性能有害。通过我们的实验，我们表明学习这些功能的某些子集可能会导致各种数据集的性能更好。我们建议使用Softmax作为常规器，并从不同跳距的邻居聚合的功能的“软选择器”;和L2 - GNN层的标准化。结合这些技术，我们呈现了一个简单浅的模型，特征选择图神经网络（FSGNN），并经验展示所提出的模型比九个基准数据集中的最先进的GNN模型实现了可比或甚至更高的准确性节点分类任务，具有显着的改进，可达51.1％。

图形神经网络（GNN）是用于建模图数据的流行机器学习方法。许多GNN在同质图上表现良好，同时在异质图上表现不佳。最近，一些研究人员将注意力转移到设计GNN，以通过调整消息传递机制或扩大消息传递的接收场来设计GNN。与从模型设计的角度来减轻异性疾病问题的现有作品不同，我们建议通过重新布线结构来从正交角度研究异质图，以减少异质性并使传统GNN的表现更好。通过全面的经验研究和分析，我们验证了重新布线方法的潜力。为了充分利用其潜力，我们提出了一种名为Deep Hertophilly Graph Rewiring（DHGR）的方法，以通过添加同粒子边缘和修剪异质边缘来重新线图。通过比较节点邻居的标签/特征 - 分布的相似性来确定重新布线的详细方法。此外，我们为DHGR设计了可扩展的实现，以确保高效率。 DHRG可以轻松地用作任何GNN的插件模块，即图形预处理步骤，包括同型和异性的GNN，以提高其在节点分类任务上的性能。据我们所知，这是研究图形的第一部重新绘图图形的作品。在11个公共图数据集上进行的广泛实验证明了我们提出的方法的优势。

Recent years have witnessed the emerging success of graph neural networks (GNNs) for modeling structured data. However, most GNNs are designed for homogeneous graphs, in which all nodes and edges belong to the same types, making them infeasible to represent heterogeneous structures. In this paper, we present the Heterogeneous Graph Transformer (HGT) architecture for modeling Web-scale heterogeneous graphs. To model heterogeneity, we design node-and edge-type dependent parameters to characterize the heterogeneous attention over each edge, empowering HGT to maintain dedicated representations for different types of nodes and edges. To handle dynamic heterogeneous graphs, we introduce the relative temporal encoding technique into HGT, which is able to capture the dynamic structural dependency with arbitrary durations. To handle Web-scale graph data, we design the heterogeneous mini-batch graph sampling algorithm-HGSampling-for efficient and scalable training. Extensive experiments on the Open Academic Graph of 179 million nodes and 2 billion edges show that the proposed HGT model consistently outperforms all the state-of-the-art GNN baselines by 9%-21% on various downstream tasks. The dataset and source code of HGT are publicly available at https://github.com/acbull/pyHGT.

Deep learning has revolutionized many machine learning tasks in recent years, ranging from image classification and video processing to speech recognition and natural language understanding. The data in these tasks are typically represented in the Euclidean space. However, there is an increasing number of applications where data are generated from non-Euclidean domains and are represented as graphs with complex relationships and interdependency between objects. The complexity of graph data has imposed significant challenges on existing machine learning algorithms. Recently, many studies on extending deep learning approaches for graph data have emerged. In this survey, we provide a comprehensive overview of graph neural networks (GNNs) in data mining and machine learning fields. We propose a new taxonomy to divide the state-of-the-art graph neural networks into four categories, namely recurrent graph neural networks, convolutional graph neural networks, graph autoencoders, and spatial-temporal graph neural networks. We further discuss the applications of graph neural networks across various domains and summarize the open source codes, benchmark data sets, and model evaluation of graph neural networks. Finally, we propose potential research directions in this rapidly growing field.

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.

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

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