最近几年来，有大量的研究专注于扩展图神经网络（GNNs）的表达能力，超越 Weisfeiler-Lehman (1-WL) 框架。在这项研究中，我们从图搜索的角度探讨了 GNNs 的表达能力，提出了一种新的顶点着色方案，并证明经典的搜索算法可以高效地计算超越 1-WL 的图表示。我们展示了这种着色方案从图搜索中继承的有用特性，可以帮助解决图的双连通性问题。此外，我们还展示了在某些条件下，GNNs 的表达能力随着搜索邻域的半径逐层递增。为了进一步研究所提出的方案，我们基于广度优先搜索和深度优先搜索开发了一种新类型的 GNN，突出了它们在 1-WL 之上所能捕捉到的图属性。

Mar, 2024

图分区神经网络（GPNNs）是一种新颖的 GNN 架构，通过对图进行分区以及顶点集和子图之间的结构相互作用的探索，提高了 GNN 的表达能力，并在各种图基准任务中展示了超越现有 GNN 模型的卓越性能。

Dec, 2023

该研究探讨了基于图神经网络的表达能力，提出了一种连续化的方法来反映图之间的相似程度并给出了各种拓扑特征的理论框架来描述基于树距离的图表达能力。

Jun, 2023

本研究提出了一种通过置换组捕捉相邻节点间的成对相关性的高效置换敏感聚合机制，证明我们的方法比 2-WL 图同构测试更强大且不逊于 3-WL 测试，并证明我们的方法可以实现线性采样复杂度。多个数据集的综合实验证明了我们模型的优越性。

May, 2022

本文通过引入颜色编码的方法，改进了消息传递神经网络（MPNNs）的表达能力，提出了一种使用颜色消除相同节点属性的图神经网络，名为 Colored Local Iterative Procedure (CLIP)，证明该方法是连续函数的通用逼近器，并实验验证了 CLIP 能够捕捉传统 MPNN 无法区分的结构特征，并且在基准图分类数据集中表现最佳。

Dec, 2019

通过在图结构数据中学习，物理启发图神经网络在解决常见图神经网络挑战（如平滑过度、压缩过度和异质适应）方面取得了显著的性能。本文通过在传播过程中引入额外的节点和重新连接具有正负权重的连接来丰富图结构，在理论上验证了通过我们的方法增强的图神经网络可以有效地解决平滑过度问题，并对压缩过度具有鲁棒性。此外，我们对重连后的图进行谱分析，证明相应的图神经网络可以适应同质化和异质化的图。在同质化、异质化图以及长期图数据集的基准验证中，我们通过我们的方法增强的图神经网络显著优于原始版本。

Jan, 2024

本研究提出了符合物理对称性的几何图卷积神经网络测试 GWL，并使用 GWL 研究了符合物理对称性的几何图卷积神经网络的表达能力，发现等变层扩展了局部邻域之外的几何信息，高阶张量和标量化使几何图卷积神经网络具有最大的表达能力。

Jan, 2023

本文探讨了图同构、图神经网络的表达能力及其应用。作者提出了 k - 阶不变 / 本质等变图神经网络，并将此网络应用于图分类的任务中。实验表明，模型在数据集上表现的优异，证明了本文所提出的模型是有实用价值的。

May, 2019

通过引入颜色分离集的新概念，我们解决了通过持久化同调识别属性图的问题，并建立了区分图的必要和充分条件。基于这些理论洞察力，我们提出了一种称为 RePHINE 的方法，它有效地结合了顶点和边的持久化同调，证明了其在学习图的拓扑特征方面比标准持久化同调更强大，并在多个图分类基准测试中取得了优势。

Nov, 2023

本研究分析了现有图嵌入神经网络（GNN）在图着色问题中的表现差异主要是由于其无法应对节点异质性以及其局部性；通过研究聚集 - 合并 GNN（AC-GNN）的性能以及其基于局部搜索的特性，我们得出了一系列在实践中使 GNN 在图着色问题中更具有等变性和强大性的规则，并提出了一个简单的 AC-GNN 变体以验证我们的理论，并实现了比现有启发式算法更高质量和更快速运行的结果。

Aug, 2022