基于解耦概要图的大规模图数据高效分布式挖掘算法

频繁封闭子图挖掘被证明是NP-难问题.多年来,虽然已有许多算法被提出用于解决该问题,但在挖掘大规模图数据时,却面临着共同的计算效率问题.特别是,当图中节点的平均度数增加时,挖掘效率更是急剧下降.现在已有的面向图数据库的分布式频繁子图挖掘算法大多采用基于水平划分的分布式计算框架,且都聚焦在挖掘所有频繁子图的问题上.基于水平划分的分布式计算框架是对原始数据进行水平分片,完成分布式挖掘过程.在计算效率方面,该框架存在一些不足.同时,由于封闭子图模式需要对频繁子图进行封闭性检测,如果直接将现有的分布式频繁子图挖掘算法用于闭图模式挖掘可能导致各节点间频繁的通讯,或大量的子图同构检测.针对以上问题,本文提出一种面向大规模图数据的高效分布式挖掘算法Desu-FSM.与现有基于水平分解的分布式挖掘框架不同,该算法首次采用了基于垂直分解的分布式挖掘框架.其基本思想可概括为“快速抵近,双向搜索”.首先,通过τ-邻域核图合并,获得概要图集,跨越式地快速抵近较大尺寸子图的聚集区域.在此基础上,通过对概要图的缩减和扩展发现所有被概要图包含和包含概要图的闭图模式.相较于原始图数据,概要图的尺寸和平均节点度数更小.而且,基于概要图的双向搜索可在分布式环境下同时独立完成,不存在耦合.与基于水平划分的框架采用的“数据物理分治”方式不同,该框架采用“任务逻辑分治”.前者减少了各节点处理的图数据量,后者将原始图数据中的挖掘任务分解为一系列具有更小尺寸和平均节点度数的子图限定的子任务.因此,计算效率大幅提升.本文还提出一组高效的优化策略来减少概要图之间存在公共子图导致的大量重复计算.大量真实和人工数据集上的测试结果表明,在大规模图数据封闭子图挖掘中,基于垂直分解框架的挖掘效率相较于水平分解框架的效率可提升一个数量级.同时,具有更少的内存空间占用.