大型图中常见子结构的引导挖掘

Question

我有一个大的(> 1000)有向无环图集,每个图都有一个大的(> 1000)顶点集.顶点被标记,标签的基数很小(<30)

我想识别(我的)在整个图表集中频繁出现的子结构.

1. 子结构是至少两个具有特定标签的直接连接顶点的图.这样的子结构可以在给定输入图中的一个或多个中出现一次或多次.例如,"a [带有两个直接连接的子标记为B的顶点A]在图U中出现两次,在图V中出现一次".
2. 我们正在寻找的子结构必须遵守一组预先给定的规则,这些规则在顶点的标签上进行过滤.作为示例:如果子图是"标记为A的顶点,其具有标记为B的至少一个直接连接的子节点并且不是标记为U或V的顶点的直接连接的兄弟节点",则包含标记为A的顶点的子结构是有趣的..不符合这些规则的子结构可能会出现在输入图中,但对搜索不感兴趣.

我们要查找的输出是给定图形中的子结构列表及其(出现次数).

我试图调查事物并且(因为它似乎总是发生在我身上)问题是NP完全的.据我所知,gSpan是解决这个问题最常用的算法.但是,如上所述,我不是在图中寻找任何常见的子结构,而只是那些遵守某些规则的子结构.人们应该能够如此使用它以减少搜索空间.

有关如何解决此问题的任何见解？

更新:我应该补充一点,上述规则可以在一定程度上递归.例如,"标记为A且具有至少两个标记为B的子节点的顶点,每个子节点具有至少一个标记为A的子节点".最大递归深度介于1到10之间.

更新II:指出我们不是在搜索已知或首选的子结构,而是在挖掘它们.没有勺针.

Answer 1

我在答案中假设您正在尝试最小化运行时间并且不想花费过多的时间来编写代码来执行此操作.在学习编写高效算法时,我最初努力解决的一件事是,有时多次传递会更有效率.在这种情况下,我会说,从根本上说,你想要两个通行证:

首先,创建一个过滤器,允许您忽略大多数(如果不是全部)非重复模式.为此:

1. 分配两个位数组(并在执行此操作时考虑高速缓存大小).第一个将是一个简单的布隆过滤器.第二个是重复布隆过滤器.
2. 在第一遍遍历结构时,对于每个可索引结构,计算哈希值.在第一个布隆过滤器中选择适当的位并进行设置.如果该位已设置,则还要设置重复布隆过滤器中的相应位.

在第二次通过时,您需要执行实际确认匹配的"更重"过程.为了实现这个目标:

1. 再次扫描图形并记录与第一遍中生成的重复布隆过滤器匹配的任何结构.
2. 将那些匹配的表放在哈希表中(理想情况下使用计算的哈希值中的不同位)
3. 检测到重复时,将该信息存储在您想要收集的位置.

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

1. 为了提高多线程系统的性能,并行化第一步实际上是安全的.为此,请为每个线程(或群集中的计算机)提供一个图形.每个人都应该计算自己的两个绽放的副本.然后可以将花朵组合成最终的花朵.减少函数只是(存在,重复)=(present1或present2,duplicate1或duplicate2 OR(present1 AND present2)).这一步非常快.
2. 并行化第二步也是完全安全的,但必须稍加修改.为此,您将从第一步开始使用重复布隆过滤器,并在第二步中将其用作过滤器,与之前相同.但是,您无法轻松完成最终比较.您必须将潜在的重复项放在散列桶中.然后,在将每个数据碎片写入其自己的潜在重复哈希表列表之后,将数据按哈希桶分开,并在第三步中找到重复项.每个哈希桶(来自第二步中的任何输出)必须由同一个工作程序处理.
3. 如果您有大量要编制索引的结构,则可以通过递归应用上述算法来提高性能.调整是您使用上述算法输出的每个匹配类别作为递归传递的输入.例如,如果仅对第一次运行算法中最多包含5个项目的结构进行索引,则可以在递归时获取每组重复的子图,并仅在这些子图上运行算法.显然,只有非常大的数据集才需要这样做.
4. 如果图形非常大以提高布隆过滤器的有效性,您可以考虑的另一个调整是迭代算法.例如,在第一遍中,您可能只考虑将第一个标签作为子图基础的子图.这将减少布隆过滤器所需的大小和/或允许您在第一次过程中过滤掉更多子图.

调整上述内容的几个注意事项:

1. 考虑缓存大小.例如,在Intel Haswell芯片上,每个内核在L1缓存中具有32K,在L2缓存中具有256K.每个缓存行将包含512位,因此如果填充1%的布隆过滤器,将触及大多数缓存行.根据算法的其他部分的速度以及其他内容使用这些缓存的情况,您可以安全地创建一个最多约512*1024个条目的布隆过滤器(每个过滤器每位8个条目= 128k,在超线程系统上,是你获得了多少L2,并且仍然维护L2缓存中的大部分数据集以及L1中真正活跃的东西.对于较小的数据集,请保持此数字,因为没有必要使它变大.如果你只是在不少于1%的时间内将功能标记为可能重复,那就完全没问题了.
2. 并行化这一点,只有在您拥有大量数据的情况下才真正有用.我假设你可能.如果进行并行化,则应考虑几何体.在每台计算机上放置部分数据集将适用于此算法.然后,您可以在每台计算机上运行每次迭代(在变体#4中).如果您拥有庞大的数据集,将无需将所有数据传输到所有计算机.

无论如何,总结一下关于运行时复杂性的陈述,我会说它确实取决于.很多人忽略了这样一个事实,即增加数据的工作集会导致内存访问的成本并不相同.从根本上说,上述算法尽管性能很好,但如果调整得适当,将在一个小型数据集上运行得非常快,但它确实能够用更大的数据集来实现,因为它允许高效的方式将数据的工作集保持在任何缓存级别是合适的(L1,L2,L3,RAM,本地磁盘,本地网络等)算法的复杂性将取决于数据,但我不相信可以更快地创建算法.我确实忽略了你如何表示子图,并且有一些工作要做,以实现最优算法,但不知道更多,我无法确定存储该信息的最佳方法.

算法运行速度不如我所提出的快得多的原因是第一遍要比第二遍运行要少得多,因为它不需要分支,并且执行按位运算的工作量较少.因此,我们可以说它对我们正在进行的整体工作几乎没有什么影响.第二阶段也尽可能高效.你必须(除非用一组有限的位来完美地描述每种可能性,我将解释一下)实际比较每个图形特征并在某处写入信息.唯一的变量是检查是否需要执行此操作需要做多少工作.检查一下你可以随意将错误率调整到0%的位置就可以获得.

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

现在,最后,正如我所提到的,如果在每次迭代中检查的功能数量进一步减少,您可能会稍微好一些.例如,如果您只检查32个可能的标签以及每个传递中具有特定标签的子节点数(并且这限制为1024),则可以用15位完美地表示这一点.如果将计数限制为255,则可以使用32K完美地存储此信息.为了在你的情况下解决这个问题,你需要使用我上面提到的迭代,递归和分片策略,然后你还需要跟踪源图和其他一些信息.老实说,我怀疑这种情况除非在非常有限的情况下才能正常工作,但我要把它包括在内以保证完整性.

无论如何,这是我在Stack Overflow上的第一个答案,所以不要太难对我说.我希望这可以帮到你!

Answer 2

编辑：这是我要开始的：

1. 构建 30x30 可能的父/子组合到相应节点的索引
2. 与给定子结构的匹配相交
3. 手动检查更多条件

（原帖）：

1. 找到一种为子结构构建哈希键的方法
2. 构建从子结构到对应节点的哈希映射
3. 使用哈希图查找候选者，手动检查详细条件