本文研究了用同构映射技术对图结构进行分析的方法，并通过引入颜色细化的广义，推广到了超图的结构分析。通过顶点彩色处理将超图和它的关联图中的同构映射联系起来，我们证明了当且仅当任何连通 Berig - 无圈超图 B 上的同构映射在两个超图 G 和 H 中的数量相同时，这种颜色细化的方法无法区分两个超图的结构。

Mar, 2019

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

Mar, 2024

本研究介绍了如何利用图重构技术来解决图神经网络架构存在的理论和实践问题，从而提高其表现力并实现应用于现实世界中的性能提升。

Oct, 2021

通过引导学习过程的精确同构求解器技术，我们的算法使消息传递图神经网络具有通用性，通过从根到叶子节点的搜索树中采样多个路径，并结合粒子滤波更新来学习更具辨别性的表示，从而在运行时间仅线性增加的情况下，在同构检测的合成基准和真实世界数据集上始终优于领先的图神经网络模型。

Jan, 2024

通过采用颜色精炼技术，结合线性规划，证明了图形同构的难题可在多项式时间内解决，该技术适用于大量的紧凑图，并且给了这一类图的识别复杂性的下界。

Feb, 2015

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

Nov, 2023

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

Aug, 2022

本文提出了关于图同构问题的方法，其中包括跟颜色精细算法和基于 Weisfeiler-Leman 算法的 k 维泛化相关的一些理论。我们证明了，如果对于所有树 T，T 到 G 的同态数量（Write out as Hom (T,G)）等于 T 到 H 的同态数量，那么颜色精细算法无法区分二者。而如果我们放弃非负性约束，在二者具有相同长度的路径时，寻找任意实数解的算法存在，且两个图形在分数同构时，颜色精细算法无法区分它们。最后，我们提出了一个几乎线性时间的算法来判定对于给定的图 G 和 H，是否存在一棵树 T 满足 Hom (T,G) = Hom (T,H)。

Feb, 2018

给定一个具有 n 个顶点和 m 条边的图，我们给出了一个算法来找到稳定着色的规范版本，具有最少的颜色，并且该算法的时间复杂度为 O ((m+n) log n)。该算法被广泛用于图同构测试算法的子程序中。

Sep, 2015

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

Dec, 2019