每周学点大数据 | No.48 计算子图同构

No.48期

计算子图同构

Mr. 王：我们再来看一个例子——计算子图同构。这个问题给定（节点有标签）数据图G和查询图P，找到G 中和P 同构的子图。这是一个经典的NP 完全问题。

小可：那求解岂不是很困难？

Mr. 王：在实际情况下，虽然数据图G 会比较大，可能有上G 个节点，但查询图P 一般会比较小，因为查询图一般是由查询需求表现出来的，查询需求往往没有那么大。

小可：如果依然利用Pregel 平台的思想来解决问题，要怎么做呢？

Mr. 王：考虑到Pregel 平台具有面向节点编程的思想，我们就要考虑在比较大的图中较小的相邻结构。因为在每一轮迭代处理中，每一个节点也就只能和与其相邻的结构进行通信，所以我们使用一种叫作STwig 的结构，这种结构就是只有两层的一棵“小”树。

小可：嗯，只有两层的树的确可以很有效地表示某一个节点的所有邻居。

Mr. 王：我们要将整个大图拆分成Stwig 结构，这样做的效率比匹配点和边显然要高得多。然后我们按照P 中的STwig 到G 中去搜索相同的结构。经过数次迭代之后，将查询出的STwig 再重新join 成原来要查询的图结构就可以了。总结起来就是：拆分、查询、join。

小可：还是有点抽象，具体是怎么做的呢？

Mr. 王：好，我用一种具体的图模式来演示这种思想的具体步骤。

第1 步：划分。对查询图P 进行分解。比如上面的图abcdef 是想要查询的图模式。我们将其分解成多个STwig，也就是大小只有两层的树。当然，分解方法是不唯一的，而且求解最佳的分解方法也是NP 完全的，好在图模式的大小比较小，相对来讲比较容易求解。比如图中的q 和q’ 就是两种不同的划分方法，当我们完成划分之后，这一次查询Q（或者说查询图P）就可以表示成q1q2q3q4 或者q1’q2’q3’。

第2 步：搜索。在搜索时，我们先选取一种模式，比如q1，然后到数据图G 去搜索子模式q1。

这个搜索过程可以很好地利用Pregel 的思想。因为我们要寻找的模式都是两层的小树，所以在搜索q1 这种模式时，只需要让每一个节点检查自己是不是a，然后再让每一个a 去与其邻居联系，看看它们是不是b 和c，如果其邻居中同时有b 和c，那么就上报说明自己这里有q1。

小可：这样确实可以很好地利用“把自己当作一个节点”的思想。无须关注图的其他部分，也不用从整体上去寻找这种模式，而是每一个节点自己出发去检查其邻居是不是和自己构成了一个P 中存在的STwig 结构。

Mr. 王：这里还有一个小技巧。我们不难注意到，在要进行搜索的这些STwig 中，会存在一些公共的节点，比如q1 和q3 就有公共节点b。我们可以做一个缓存，记录下来在搜索q1 时找到的所有的b。当进行q3 搜索时，我们无须去搜索所有的b，而是只搜索q1 时找到的那些b就可以了。你想想看这是为什么？

小可想了一下，说：能够匹配模式P 的G 的子图必然同时匹配q1 和q3。如果进行q1 搜索时并没有将某一个b 搜索出来，则意味着符合q3 的子模式不符合q1，因为它的b 不连着a 或者它连着的a 不连着c。如果是这样，即使它真的能够匹配q3，那么到最后组合起来，也会由于不含q1 不可能构成P。

Mr. 王笑着说：非常好，你的逻辑思维很严谨。这样做的好处是，可以大大减少我们在每一轮搜索过程中需要处理的节点。

第3 步：对查找到的这些子模式进行一个join 操作，将小的STwig 合并成更加接近原图P的结构，以求能够返回最终结果。这个join 操作相对会麻烦一些，因为图的连接并不是一个符合“以节点为核心”思想的操作，这里就需要所涉及的每一台机器都要加载一些中间结果，让这些中间结果在自己这里进行连接。

下期精彩预告：

经过学习，我们学习了一个经典的NP 完全问题，计算子图同构。在下一期中，我们将了解众包算法。更多精彩内容，敬请关注灯塔大数据，每周五不见不散呦！

内容来源：灯塔大数据 文章编辑：柯一