algorithm - 大量图集中指导常见子结构的挖掘

Question

我有一大组(> 1000)有向无环图，每组有一个大(> 1000)顶点。顶点被标记，标签的基数较小(<30)

我想识别(挖掘)在整个图集中经常出现的子结构。

子结构是至少两个具有特定标签的直接连接的顶点的图形。这样的子结构可以在一个或多个给定的输入图中出现一次或多次。例如“在图U中出现了两次[在图U中出现了两次，并在图V中出现了一次，在图2中出现了一个[标记为A的顶点，带有两个直接相连的子项，标记为B]”。

我们正在寻找的子结构必须遵守一组预先设定的规则，这些规则会过滤顶点的标签。例如:如果子图是“一个标记为A的顶点，它具有至少一个直接标记为B的子代，而不是一个标记为U或V的顶点的同级兄弟”，则包含一个标记为A的顶点的子结构将很有趣。 。不符合这些规则的子结构可能会出现在输入图中，但对于搜索不感兴趣。

我们正在寻找的输出是给定图中的子结构及其(数量)外观的列表。

我试图研究问题，并且(似乎总是伴随我发生)这个问题是NP完全的。据我所知，gSpan是解决此问题的最常用算法。但是，如上所述，我不是在图中寻找任何常见的子结构，而只是在遵循某些规则的结构中寻找。为了减少搜索空间，应该可以使用它。

对如何解决此问题有任何见解？

更新:我可能应该补充一点，上述规则可以在一定程度上递归。例如“标记为A的顶点，其中至少有两个子代为B，每个子代至少有一个子代为A”。最大递归深度在1到10之间。

更新II:指出我们不是在搜索已知或首选的子结构，而是对其进行挖掘。没有汤匙针。

Answer 1

我在回答中假设您正在尝试最小化运行时间，并且不想花费过多的时间编写代码来做到这一点。起初，我在学习编写高效算法时遇到的一件事是有时多次通过可能会更有效。在这种情况下，我要说的是，从根本上讲，您希望获得两遍:

首先，创建一个过滤器，使您可以忽略大多数(如果不是全部)非重复模式。为了做到这一点:

分配两个位数组(这样做时要考虑缓存大小)。第一个将是一个简单的Bloom过滤器。第二个将是重复的布隆过滤器。

在第一次遍历该结构时，对于每个可索引结构，请计算一个哈希值。在第一个Bloom过滤器中选择适当的位并进行设置。如果该位已被设置，则还要在重复布隆过滤器中设置相应的位。

在第二遍时，您将需要执行“更重”的过程以实际确认匹配。为了做到这一点:

再次扫描图形并记录与第一遍中生成的重复Bloom过滤器匹配的任何结构。

将匹配的那些放在哈希表中(理想情况下，使用与计算得出的哈希不同的位)

当检测到重复项时，将该信息存储在您希望收集的地方。

该算法将在大型数据集上非常快速地运行，因为它将大大减少适当缓存级别上的压力。您还可以进行一些增强，以使其在不同的情况下表现更好。

为了提高多线程系统上的性能，并行执行第一步实际上是安全的。为此，请为每个线程(或群集中的计算机)分配一张图表。每个人都应计算自己的两个大花色副本。然后可将大方坯结合成最终的大方坯。约简函数为(存在，重复)=(present1或present2，重复1或重复2或(present1和present2))。这一步非常快。

并行执行第二步也是完全安全的，但是必须稍加修改。为此，您将从第一步开始使用重复的bloom过滤器，并将其用作第二步中的过滤器，与之前相同。但是，您无法轻松完成最终比较。相反，您必须将潜在的重复项放入哈希存储桶中。然后，在将每个数据碎片写入其自己的潜在重复哈希表列表之后，将数据按哈希桶划分，然后在第三步中找到重复项。每个哈希存储桶(来自第二步中的任何输出)必须由同一工作人员处理。

如果您要索引的结构很多，则可以通过递归应用上述算法来提高性能。所做的调整是，对于上述算法的输出，将每个匹配类别用作递归遍历的输入。例如，如果在算法的第一次运行中仅索引最多包含5个项目的结构，则可以在递归时获取每组重复的子图，并仅对那些子图运行算法。显然，只有大量数据才需要这样做。

如果图形很大，您可能会考虑的另一种调整是为了迭代算法，以提高Bloom Bloom过滤器的效率。例如，在第一遍中，您可能只考虑具有第一个标签的子图作为子图的基础。这将减少Bloom筛选器所需的大小，并且/或者允许您在第一次通过时筛选出更多的子图。

关于上述内容的一些注意事项:

考虑缓存大小。例如，在Intel Haswell芯片上，每个内核在L1缓存中具有32K，在L2缓存中具有256K。每条缓存行将包含512位，因此，如果您填充1％的Bloom过滤器，则将触摸大多数缓存行。根据算法其他部分的运行速度以及其他内容使用这些缓存的情况，您可以安全地创建一个布隆过滤器，该过滤器最多包含512 * 1024个条目(在超线程系统上，每个过滤器每位8个条目= 128k，是您获得的L2数量)，并且仍然保留L2缓存中的大部分数据集以及L1中真正活跃的内容。对于较小的数据集，请减小此数字，因为没有必要增大它。如果您仅将特征标记为不少于1％的潜在重复项，那就完全可以了。

再次并行化仅在拥有大量数据的情况下才真正有用。我假设你可以。如果进行并行化，则应考虑几何形状。使用此算法可以在每台计算机上放置部分数据集。然后，您可以在每台计算机上运行每个迭代(版本4)。如果您拥有庞大的数据集，则可以避免将所有数据传输到所有计算机。

无论如何，总结一下运行时复杂性，我会说这确实取决于。许多人忽略了以下事实:增加数据的工作集将导致内存访问的成本不均等。从根本上讲，上述算法虽然性能良好，但如果对其进行了适当的调整，将可以在较小的数据集上非常快速地运行，但是对于更大的数据集，它确实非常有用，因为它允许以高效的方式将工作数据集保持在任何缓存级别合适的方法(L1，L2，L3，RAM，本地磁盘，本地网络等)。算法的复杂性取决于数据，但是我不认为可以创建更快的算法。我确实省略了如何表示子图，并且在那里要做一些工作来实现最佳算法，但是在不了解更多信息的情况下，我无法确定存储该信息的最佳方法。

一种算法的运行速度不能比我所介绍的算法快得多的原因是，第一遍将比第二遍运行所需的工作少得多，因为它不需要分支，并且进行按位运算的工作也较少。因此，我们可以说，它对我们正在进行的总体工作没有多大作用。第二阶段也要尽可能地高效。您必须(用有限的位集合来完美地描述每种可能性的方法，我将在后面解释)，然后实际比较每个图形特征并将信息写入某处。唯一的变量是检查您是否需要执行此操作的工作量。尽可能多地检查一下您可以将错误率缩放到0％的程度。

对于较小的数据集，两次通过对您有利的原因是，您可以在更少量的内存中拥有大量的布隆基数。但是，对于非常小的数据集，您最好只使用第二步，而忽略第一步。但是，至少，您需要为每个哈希目标存储一个指针。这意味着对于相同级别的过滤，您将需要写入32或64倍的数据。对于足够小的数据集，这无关紧要，因为读取是读取，写入是写入，但是对于较大的数据集，这可以允许您完成相同级别的过滤，同时保留给定的缓存级别。在必须跨多台计算机或多线程工作的情况下，此算法提供的机制将更加高效，因为可以更快地合并数据，并且可以交换有关潜在匹配的更多信息。

现在，最后，正如我提到的，如果进一步减少每次迭代中要检查的功能数量，则可能会稍微好一些。例如，如果您仅检查32个可能的标签以及每次通过中具有特定标签的子代的数量(且该标签的上限为1024)，则可以用15位完美地表示。如果将计数限制为255，则可以使用32K完美存储此信息。为了实现这一点，您需要使用我上面提到的迭代，递归和分片策略，然后还需要跟踪源图和其他一些信息。老实说，我怀疑除非在非常有限的情况下，否则这种方法是否会奏效，但出于完整性考虑，我将其包括在内。

无论如何，这是我对Stack Overflow的第一个答案，所以不要对我太在意。我希望这可以帮到你!