从图的集合中排除同构

Question

我有一个包含1500万（百万）个DAG（有向无环图 - 实际上是有向超立方体）的集合，我想从中删除同构。针对此问题，有哪些常见算法？每个图形都相当小，是N维的超立方体，其中N为3到6（目前为止），因此对于N = 6情况，每个图形有64个节点。

使用networkx和python，我像这样实现了它，对于像300k（千）这样的小数据集非常有效（在几天内运行得很好）。

def isIsomorphicDuplicate(hcL, hc):
    """checks if hc is an isomorphism of any of the hc's in hcL
    Returns True if hcL contains an isomorphism of hc
    Returns False if it is not found"""
    #for each cube in hcL, check if hc could be isomorphic
    #if it could be isomorphic, then check if it is
    #if it is isomorphic, then return True
    #if all comparisons have been made already, then it is not an isomorphism and return False

    for saved_hc in hcL:
        if nx.faster_could_be_isomorphic(saved_hc, hc):
            if nx.fast_could_be_isomorphic(saved_hc, hc):
                if nx.is_isomorphic(saved_hc, hc):
                    return True
    return False

更好的方法是将每个图转换为其规范顺序，对集合进行排序，然后删除重复项。这样可以避免通过二进制is_isomophic()测试来检查15M个图中的每一个。我相信上述实现类似于O(N!N)(不考虑同构时间)，而干净的转换为规范顺序并排序应该需要O(N)用于转换+O(log(N)N)用于搜索+O(N)用于去除重复项. O(N!N)>>O(log(N)N)

我在Canonical graph labeling的论文中找到了一些信息，但非常简洁，只有数学公式，没有伪代码："McKay's Canonical Graph Labeling Algorithm" - http://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf

tldr: 我需要通过二进制同构性检查来检查大量的图形，这几乎是不可能的。我相信通常通过规范顺序来解决这个问题。是否存在任何已打包的算法或已发表的易于实现的算法（即具有伪代码）？

- SwimBikeRun

Answer 1

以下是Hartke和Radcliffe在论文中提出的McKay的规范图标记算法的详细解析[链接到论文]。

首先，我要指出，这里有一个开源实现可供使用：nauty和Traces源代码。

好的，我们开始吧！不幸的是，这个算法涉及很多图论术语，所以我们需要一些定义。首先，我将从定义同构和自同构开始。

同构：

如果两个图形相同，但顶点的标签不同，则它们是同构的。下面是两个同构图形的示例。

自同构：

如果两个图形完全相同，包括顶点标记，则它们是自同构的。以下两个图形是自同构的。这似乎是微不足道的，但出于技术原因，这一点非常重要。

图哈希：

整个概念的核心思想是有一种方法将图哈希为一个字符串，然后对于给定的图形，计算与其同构的所有图的哈希字符串。字典序最大的同构哈希字符串称为“规范哈希”，生成它的图形称为“规范同构”或“规范标签”。

有了这个，要检查任何两个图是否同构，只需要检查它们的规范同构（或规范标签）是否相等（即它们是否互为自同构）。哇，术语！不幸的是，如果没有术语，这会更加令人困惑 :-(

我们将使用的哈希函数称为i(G)，其中G表示一个图形：通过按顶点标签的顺序查看G中每对顶点并放置“1”（如果这两个顶点之间存在一条边）或“0”（如果不存在），构建二进制字符串。这样，i(G)中的第j位表示该图中该边的存在或不存在。

麦凯的规范图标记算法

问题在于，对于一个有n个顶点的图，基于你如何标记这些顶点，可能会有O(n!)个同构哈希字符串，如果我们必须多次计算相同的字符串（即自同构），则会有更多。通常情况下，我们必须计算每个同构哈希字符串才能找到最大的那个，没有什么魔法可以简化此过程。麦凯算法是一种搜索算法，通过剪枝所有自同构来加速查找规范同构，强制规范同构中的顶点按照度数递增的顺序标记，并使用其他一些技巧来减少我们必须哈希的同构数量。

（1）第4节：麦凯算法的第一步是根据度数对顶点进行排序，这样可以剪枝掉大部分需要搜索的同构，但不能保证唯一的排序，因为可能会有多个具有相同度数的顶点。例如，以下图形有6个顶点；verts {1,2,3} 的度数为1，verts {4,5} 的度数为2，vert {6} 的度数为3。它按照顶点度数的部分排序是{1,2,3|4,5|6}。

(2) 第5节：对于那些顶点度数相同但不能区分的顶点，施加人工对称性；基本上我们取其中一个具有相同度数的顶点组，在总排序中依次选择一个来排在最前面（见论文中的图2），因此在我们上面的例子中，节点{1,2,3|4,5|6}将会有子节点{{1|2,3|4,5|6}，{2|1,3|4,5|6}}，{3|1,2|4,5|6}}，通过扩展组{1,2,3}，以及子节点{{1,2,3|4|5|6}，{1,2,3|5|4|6}}，通过扩展组{4,5}。这种分割可以一直进行到叶节点，叶节点是完整同构的总排序，如{1|2|3|4|5|6}，这使我们能够从（1）中按顶点度数获取部分排序，并建立列出规范同构的所有候选树 - 这比n！的组合已经少得多，例如，顶点6永远不会排在第一位。请注意，麦凯以深度优先方式评估子节点，从最小的组开始，这导致了更深但更窄的树，这对下一步的在线修剪更好。还要注意，每个总排序叶节点可能会出现在多个子树中，这就是修剪的地方！

（3）第6节：在搜索树时，寻找自同构并使用其来修剪树。这里的数学有点超出了我的理解范围，但我认为这个想法是，如果您发现树中的两个节点彼此是自同构的，则可以安全地修剪它们的一个子树，因为您知道它们都将产生相同的叶节点。

我只给出了McKay的高层描述，论文在数学上更加深入，构建实现需要对这种数学有所了解。希望我已经给了你足够的背景，以便你可以回去重新阅读论文或阅读实现的源代码。

- Mike Ounsworth

Answer 2

这确实是一个有趣的问题。

我会从邻接矩阵的角度来解决它。两个同构图将具有邻接矩阵，其中行/列的顺序不同。因此，我的想法是为每个图计算几个与行/列交换不变的矩阵属性，例如：

numVerts, min, max, sum/mean, trace（如果没有自反边可能没有用），norm, rank, min/max/mean column/row sums, min/max/mean column/row norm

任何一对同构图在所有属性上都将相同。

您可以创建一个哈希函数，它接受一个图形并输出哈希字符串，例如：

string hashstr = str(numVerts)+str(min)+str(max)+str(sum)+...

那么按哈希字符串对所有图形进行排序，你只需要对哈希相同的图形进行完整同构检查。

假设您有3600万个节点上的15百万个图形，我认为您正在处理加权图形，对于非加权无向图形，这种技术将不太有效。

- Mike Ounsworth

Answer 3

这是一个有趣的问题，我暂时还没有答案！以下是我的想法:

当你提到 15M，你是否指的是 1500 万个无向图？每个图的大小有多大？它们有什么特性（树形结构，平面图，k-树）？

您是否尝试过通过预先检测假阳性来最小化检查次数？这包括计算和比较数字，如顶点，边缘度和度序列等。除此之外，还可以使用其他启发式方法来测试给定的两个图是否不同构。另外，请检查nauty。它可能是您检查它们（并生成规范排序）的方式。

- Xline

---

“某些东西包括计算和比较数字，例如顶点、边缘度和度序列？” - 是的，那很棒。不幸的是，这就是faster_could_be_isomorphic()已经在做的:(哈哈。我的问题更多地针对N！N到logN*N部分。这有意义吗？将所有内容转换为规范形式，排序，然后删除重复项。否则，您必须逐个将每个项目与每个其他项目进行比较（在规范化之前无法排序）。 - SwimBikeRun

Answer 4

如果你的所有图形都是超立方体（就像你所说的），那么这很简单：相同维度的所有超立方体同构，不同维度的超立方体则不同构。因此，按照其节点数将每个图形在线性时间内放入一个桶中（对于超立方体来说：不同维度<=>不同节点数），并完成它。

- mastov

---

顺便说一句，我当然不期望因为这个琐碎的答案而获得赏金。我知道这不是SwimBikeRun想要的。我只是指出问题肯定有些地方出错了（可能是它们是超立方体的子图，或者他正在处理加权图而不是普通图等等）。 - mastov

有向超立方体哈哈。不过还是感谢您的评论！ - SwimBikeRun

Answer 5

也许你可以使用麦凯的实现？它现在可以在这里找到：http://pallini.di.uniroma1.it/ 你可以将你的15M个图形转换为紧凑的graph6格式（或sparse6），nauty使用这种格式，然后运行nauty工具labelg生成规范标签（也以graph6格式呈现）。

例如-从一组随机图中删除同构图：

#gnp.py
import networkx as nx
for i in range(100000):
    graph = nx.gnp_random_graph(10,0.1)
    print nx.generate_graph6(graph,header=False)


[nauty25r9]$ python gnp.py > gnp.g6
[nauty25r9]$ cat gnp.g6 |./labelg |sort |uniq -c |wc -l
>A labelg
>Z  10000 graphs labelled from stdin to stdout in 0.05 sec.
710

- Aric

Answer 6

自从您提到可以检查约300k个图的同构性，我建议将这1500万个图分成约300k个节点的组，并在每个组上运行同构性测试。

假设每个图Gi := VixEi（顶点x边缘）。

（1）创建图形桶，使第n个桶仅包含|V|=n的图形。

（2）对于在（1）中创建的每个桶，创建子桶，使第（n，m）个子桶仅包含|V|=n且|E|=m的图形。

（3）如果组仍然太大，请按其度数（即与节点相连的边数）对每个图中的节点进行排序，从中创建矢量并通过该矢量分发图形。

例子（3）：

假设有 4 个节点 V = {v1, v2, v3, v4}。令 d(v) 是节点 v 的度数，其中 d(v1)=3，d(v2)=1，d(v3)=5，d(v4)=4，那么找到 < := transitive hull ( { (v2,v1), (v1,v4), (v4,v3) } ) 并创建一个基于度数和顺序的向量，留下如下所示的结果：

(1,3,4,5) = (d(v2), d(v1), d(v4), d(v3)) = d( {v2, v1, v4, v3} ) = d(<)

现在你已经将 15M 个图分成了许多桶，每个桶都具有以下特征：

• n 个节点
• m 条边
• 该组中的每个图具有相同的“出度向量”

如果您不希望找到太多同构体，则我认为这已经足够细粒度了

到目前为止的成本：O(n) + O(n) + O(n*log(n))

(4) 现在，您可以假设每个桶内的成员很可能是同构的。您可以在该桶上运行同构检查，并且只需要将当前测试的图与您已经在此桶中找到的所有代表进行比较。根据假设，这些代表不应该太多，因此我认为这会非常便宜。

在步骤4中，您还可以愉快地将计算分配给多个计算节点，这应该真正加快了过程。

- Benj

---

同时，没有人阻止您将上述分割与Mike非常详细的描述相结合，这将为您留下最佳选择（并行化和快速同构检查器）。 - Benj