使用神经网络编码HyperGraphs的HyperGraph神经网络（HNNS）为建模数据中的高阶关系提供了一种有希望的方法，并进一步解决了基于此类高阶关系的相关预测任务。但是，实践中的高阶关系包含复杂的模式，通常是高度不规则的。因此，设计一个足以表达这些关系的HNN在保持计算效率的同时，通常是一项挑战。受到超图扩散算法的启发，这项工作提出了一种名为ED-HNN的新型HNN体系结构，该结构可证明可以代表任何可以建模广泛的高阶关系的连续均值超差扩散算子。 ED-HNN可以通过将超图的星形扩展与传递神经网络的标准消息相结合来有效地实现。 ED-HNN进一步在处理异性超图和建造深层模型方面表现出了极大的优势。我们评估了在9个现实世界中的HyperGraph数据集上进行节点分类的ED-HNN。 ED-HNN均匀地胜过这9个数据集的最佳基线，并在其中四个数据集中获得了超过2 \％$ \ uparrow $的预测准确性。

计算机视觉和机器学习中的许多问题都可以作为代表高阶关系的超图的学习。 HyperGraph Learning的最新方法基于消息传递扩展了图形神经网络，这在建模远程依赖性和表达能力方面很简单但根本上有限。另一方面，基于张量的模棱两可的神经网络具有最大的表现力，但是由于沉重的计算和对固定顺序超中件的严格假设，它们的应用受到了超图的限制。我们解决了这些问题，并目前呈现了模棱两可的HyperGraph神经网络（EHNN），这是实现一般超图学习最大表达性的层的首次尝试。我们还提出了基于超网（EHNN-MLP）和自我注意力（EHNN-TransFormer）的两个实用实现，这些实现易于实施，理论上比大多数消息传递方法更具表现力。我们证明了它们在一系列超图学习问题中的能力，包括合成K边缘识别，半监督分类和视觉关键点匹配，并报告对强烈消息传递基线的改进性能。我们的实施可从https://github.com/jw9730/ehnn获得。

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

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

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

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.

在这项工作中，我们开发了一种新的方法，名为局部排列的图形神经网络，它为建立在本地节点邻域，通过子图形的构建图形神经网络的框架，同时使用置换等值更新功能。消息传递神经网络的消息被认为是有效应功率的限制，并且最近过度的方法缺乏可扩展性或需要将结构信息被编码为特征空间。这里呈现的一般框架克服了通过通过受限制表示在子图上操作的与全局排列等值相关的可扩展性问题。此外，我们证明了通过使用限制的陈述没有丧失表情。此外，所提出的框架仅需要选择$ k $-hops，用于创建用于为每层使用的子图和选择的表示空间，这使得该方法在一系列基于图形的域中可以容易地适用。我们通过实验验证了一系列图形基准分类任务的方法，在所有基准上展示了最先进的结果或非常竞争力的结果。此外，我们证明使用本地更新函数的使用在全球方法上提供了GPU存储器的显着改进。

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

Deep learning-based approaches have been developed to solve challenging problems in wireless communications, leading to promising results. Early attempts adopted neural network architectures inherited from applications such as computer vision. They often yield poor performance in large scale networks (i.e., poor scalability) and unseen network settings (i.e., poor generalization). To resolve these issues, graph neural networks (GNNs) have been recently adopted, as they can effectively exploit the domain knowledge, i.e., the graph topology in wireless communications problems. GNN-based methods can achieve near-optimal performance in large-scale networks and generalize well under different system settings, but the theoretical underpinnings and design guidelines remain elusive, which may hinder their practical implementations. This paper endeavors to fill both the theoretical and practical gaps. For theoretical guarantees, we prove that GNNs achieve near-optimal performance in wireless networks with much fewer training samples than traditional neural architectures. Specifically, to solve an optimization problem on an $n$-node graph (where the nodes may represent users, base stations, or antennas), GNNs' generalization error and required number of training samples are $\mathcal{O}(n)$ and $\mathcal{O}(n^2)$ times lower than the unstructured multi-layer perceptrons. For design guidelines, we propose a unified framework that is applicable to general design problems in wireless networks, which includes graph modeling, neural architecture design, and theory-guided performance enhancement. Extensive simulations, which cover a variety of important problems and network settings, verify our theory and the effectiveness of the proposed design framework.

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

在本文中，我们通过图形函数的关键代数条件（称为\ textIt {置换兼容性}）完全回答上述问题，该函数将图形和图形的特征​​与功能约束相关联。我们证明：（i）GNN作为图形函数必然是兼容的； （ii）相反，当限制具有不同节点特征的输入图上时，任何置换兼容函数都可以由GNN生成； （iii）对于任意节点特征（不一定是不同），一个简单的功能增强方案足以生成GNN置换兼容函数； （iv）可以通过仅检查二次功能约束，而不是对所有排列的详尽搜索来验证置换兼容性； （v）GNN可以生成\ textIt {any}图形函数，一旦我们以节点身份增强节点特征，从而超越了图同构和置换兼容性。上面的表征铺平了正式研究GNN和其他算法程序之间复杂联系的路径。例如，我们的表征意味着许多自然图问题，例如最小值值，最大流量值，最大值尺寸和最短路径，可以使用简单的功能增强来生成GNN。相比之下，每当GNN无法生成具有相同特征的置换函数时，著名的Weisfeiler-Lehman图形测试就会失败。我们分析的核心是一种新的表示定理，它标识了GNN的基础函数。这使我们能够将目标图函数的属性转化为GNN聚合函数的属性。

子图GNNS是最近表达的图形神经网络（GNN）的一类，它们将图形图形为子图的集合。到目前为止，可能的子图GNN体系结构的设计空间及其基本理论属性仍然在很大程度上尚未探索。在本文中，我们研究了子图方法的最突出形式，该方法采用了基于节点的子图选择策略，例如自我网络或节点标记和删除。我们解决了两个中心问题：（1）这些方法的表达能力的上限是什么？ （2）在这些子图集上传递层的模棱两可的消息家族是什么？我们回答这些问题的第一步是一种新颖的对称分析，该分析表明，建模基于节点的子图集的对称性需要比以前的作品中所采用的对称组明显小。然后，该分析用于建立子图GNN和不变图网络（IGNS）之间的联系。我们通过首先通过3-WL来界定子图方法的表达能力，然后提出一个通用子图方法的一般家族，以将所有先前基于节点的子图GNN泛化。最后，我们设计了一个新颖的子图Gnn称为Sun，从理论上讲，该子gnn统一了以前的体系结构，同时在多个基准上提供了更好的经验性能。

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

群体模棱两可（例如，SE（3）均衡性）是科学的关键物理对称性，从经典和量子物理学到计算生物学。它可以在任意参考转换下实现强大而准确的预测。鉴于此，已经为将这种对称性编码为深神经网络而做出了巨大的努力，该网络已被证明可以提高下游任务的概括性能和数据效率。构建模棱两可的神经网络通常会带来高计算成本以确保表现力。因此，如何更好地折衷表现力和计算效率在模棱两可的深度学习模型的设计中起着核心作用。在本文中，我们提出了一个框架来构建可以有效地近似几何量的se（3）等效图神经网络。受差异几何形状和物理学的启发，我们向图形神经网络介绍了局部完整帧，因此可以将以给定订单的张量信息投射到框架上。构建本地框架以形成正常基础，以避免方向变性并确保完整性。由于框架仅是由跨产品操作构建的，因此我们的方法在计算上是有效的。我们在两个任务上评估我们的方法：牛顿力学建模和平衡分子构象的产生。广泛的实验结果表明，我们的模型在两种类型的数据集中达到了最佳或竞争性能。

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

图神经网络（GNN）是非欧盟数据的强大深度学习方法。流行的GNN是通信算法（MPNNS），它们在本地图中汇总并结合了信号。但是，浅的mpnns倾向于错过远程信号，并且在某些异质图上表现不佳，而深度mpnns可能会遇到过度平滑或过度阵型等问题。为了减轻此类问题，现有的工作通常会从欧几里得数据上训练神经网络或修改图形结构中借用归一化技术。然而，这些方法在理论上并不是很好地理解，并且可能会提高整体计算复杂性。在这项工作中，我们从光谱图嵌入中汲取灵感，并提出$ \ texttt {powerembed} $ - 一种简单的层归一化技术来增强mpnns。我们显示$ \ texttt {powerembed} $可以证明图形运算符的顶部 - $ k $引导特征向量，该算子可以防止过度光滑，并且对图形拓扑是不可知的；同时，它产生了从本地功能到全球信号的表示列表，避免了过度阵列。我们将$ \ texttt {powerembed} $应用于广泛的模拟和真实图表，并展示其竞争性能，尤其是对于异性图。

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

通常通过将许多输入张量汇总为单个表示形式来处理神经网络中神经网络中的处理集或其他无序的，潜在的变化大小的输入。尽管从简单的汇总到多头关注已经存在许多聚合方法，但从理论和经验的角度来看，它们的代表力都受到限制。在搜索主要功能更强大的聚合策略时，我们提出了一种基于优化的方法，称为平衡聚​​集。我们表明，许多现有的聚合方法可以作为平衡聚集的特殊情况恢复，并且在某些重要情况下，它效率更高。在许多现有的架构和应用中，平衡聚集可以用作置换式替换。我们在三个不同的任务上验证其效率：中值估计，班级计数和分子性质预测。在所有实验中，平衡聚集的性能都比我们测试的其他聚合技术更高。

Graph neural networks (GNNs), as the de-facto model class for representation learning on graphs, are built upon the multi-layer perceptrons (MLP) architecture with additional message passing layers to allow features to flow across nodes. While conventional wisdom largely attributes the success of GNNs to their advanced expressivity for learning desired functions on nodes' ego-graphs, we conjecture that this is \emph{not} the main cause of GNNs' superiority in node prediction tasks. This paper pinpoints the major source of GNNs' performance gain to their intrinsic generalization capabilities, by introducing an intermediate model class dubbed as P(ropagational)MLP, which is identical to standard MLP in training, and then adopt GNN's architecture in testing. Intriguingly, we observe that PMLPs consistently perform on par with (or even exceed) their GNN counterparts across ten benchmarks and different experimental settings, despite the fact that PMLPs share the same (trained) weights with poorly-performed MLP. This critical finding opens a door to a brand new perspective for understanding the power of GNNs, and allow bridging GNNs and MLPs for dissecting their generalization behaviors. As an initial step to analyze PMLP, we show its essential difference with MLP at infinite-width limit lies in the NTK feature map in the post-training stage. Moreover, though MLP and PMLP cannot extrapolate non-linear functions for extreme OOD data, PMLP has more freedom to generalize near the training support.

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