图同构启发式解决方案

Question

4

我正在尝试实现一种启发式解决方案，以从给定的图集中识别同构图类。目前我正在使用WL算法为每个节点标记其邻居度数的多重集。

显然，这会产生误判，例如对于度规则图的情况。我希望找到另一种便宜易行（在时间和空间上受限）的启发式方法，可以跨越WL算法的边缘情况。本质上，我正在寻找一对易于实现的启发式方法，它们之间给出了微小的误判率。

除了WL算法之外，还有哪些启发式算法应该考虑？

谢谢！

- Devaansh Samant

你的图表是否限制在特定的域内？ - phs

它们只是简单的图表，就这样。 - Devaansh Samant

4个回答

1

- krjampani

我不被允许使用库（课程作业）。将尝试自己实现。VF2是我一直在研究的东西。 - Devaansh Samant

0

- Edward Doolittle

0

另一个相对容易计算的不变量是顶点所属的循环列表。当然，这需要在图中找到循环，但有许多算法可以做到这一点。

- gilleain

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- estama · Accepted Answer

我发现该算法属于k维Weisfeiler-Lehman算法范畴，但在常规图中失败。更多信息请参见：

以下是原始帖子:

我在解决在图形数据库（包含化学成分）中查找同构图的问题。

简要来说，该算法使用幂迭代方法创建图形的哈希值。可能会有错误的哈希碰撞，但这种概率极小（我在数以万计的图形中没有遇到过这样的碰撞）。

算法的工作方式如下：

执行N次（其中N是图形半径）迭代。在每次迭代和每个节点上：

在第一步中，节点的哈希受其直接邻居的影响。在第二步中，节点的哈希受其2跳邻域的影响。在第N步中，节点的哈希将受到其周围N跳邻域的影响。因此，您只需要继续运行Powerhash N = graph_radius步即可。最终，图形中心节点的哈希将受到整个图形的影响。

为了生成最终的哈希值，需要对最后一步的节点哈希进行排序并将它们连接在一起。之后，您可以比较最终哈希值以查找两个图形是否同构。如果有标签，则在计算每个节点的内部哈希时（以及每个步骤），请将它们添加到其中。

这里还有更多背景信息：

您可以在此处找到它的源代码：