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