4

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

对于度数规则图等情况，这显然会产生误报。我希望找到另一种廉价可实现（时间和空间受限）的启发式方法，它可以跨越 WL 算法的极端情况。本质上，我正在寻找一对易于实施的启发式方法，它们之间会产生边际误报。

除了 WL 算法，我还应该研究哪种启发式算法？

谢谢！

4

4 回答 4

1

我发现该算法属于 k 维 Weisfeiler-Lehman 算法的类别，并且它在常规图上失败。更多信息：

http://dabacon.org/pontiff/?p=4148

原帖如下：

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

简而言之，该算法使用幂迭代方法创建图的哈希。可能存在误报哈希冲突，但这种可能性非常小（我没有与数万张图发生任何此类冲突）。

该算法的工作方式是这样的：

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

  • 对节点邻居的哈希进行排序
  • 散列连接的排序散列
  • 用新计算的哈希替换节点的哈希

第一步，一个节点的哈希值受到它的直接邻居的影响。第二步，一个节点的哈希值受到距离它 2 跳的邻居的影响。在第 N 步，节点的哈希值将受到其周围 N 跳的邻域影响。所以你只需要继续运行 N = graph_radius 步骤的 Powerhash。最终，图中心节点的哈希值将受到整个图的影响。

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

这里有更多背景：

https://plus.google.com/114866592715069940152/posts/fmBFhjhQcZF

你可以在这里找到它的源代码：

https://github.com/madgik/madis/blob/master/src/functions/aggregate/graph.py

于 2017-04-30T15:39:53.897 回答
0

Another invariant that could be relatively cheap to calculate is the list of cycles that a vertex is part of. Of course, that requires finding the cycles in your graph, but there are many algorithms to do that.

于 2015-04-19T13:48:15.413 回答
0

也许考虑本文中讨论的颜色最少的最短路径不变量：http ://www.academia.edu/5111652/A_new_refinement_procedure_for_graph_isomorphism_algorithms ？

于 2015-04-19T06:56:07.797 回答