基于图数据的模式挖掘研究

• 作 者: 雷鸣涛
• 机 构: 北京邮电大学
• 出 处: 北京邮电大学
• 发表日期: 2020年01期
• 关键词: 图数据挖掘 序列模式挖掘 社团发现 子图匹配 子图同构

近年来,随着互联网技术的蓬勃发展,海量有价值的图或网络数据不断涌现。图中的节点或边之间普遍存在较强的关联性,例如,社交网络中用户间的消息传递,网络安全中网络节点间的攻防对抗,文献引用网络中文献间的引用等。该关联性可被表示为“序列模式”,针对其的挖掘研究具有重要的科学价值,不但能够总结出关联特性及分布规律,并用于分类、预测等实际应用场景;而且能够与图结构特征相结合,进而可提升图计算的效率与精度。基于以上背景,本文提出将图数据的结构特征与序列模式相结合,从基于图数据的序列模式的发现（discovery）、提炼（refinement）和实际应用（application）三个关键过程开展如下四项研究:1、图中前k项序列模式挖掘真实网络应用中,图节点往往关联了丰富的内容信息,导致已有方法在挖掘序列模式时存在存储困难、时间开销大、挖掘计算难等问题。基于此,本文首先提出一种全新的图模型——事务数据库图（transcation database graph）,并提出一种高效的两步采样框架,能够在保证挖掘准确度的同时显著改善挖掘效率。该框架设计了针对序列模式频率的无偏估计量,根据该估计量首先从图中均匀随机地采样路径,随后从每条采样得到的路径上均匀采样事务序列并赋权,最终在加权的序列集合中进行模式挖掘。通过证明可得该采样过程是均匀采样,且可给出采样数的联合上界。在合成和真实数据集进行的实验验证了该框架的有效性。2、图中前k项序列模式的快速近似前述问题设定仅考虑了丰富网络内容与节点相关联的情况,忽略了与连边相关联的情况。这导致了已有的方法不能直接处理事务数据库构建于连边的情况,且求解过程依然存在极大的时间开销。基于此,本文提出基于并行采样的快速近似方法。该方法主要应用了两项关键技术:一是基于序列平衡图划分策略的无偏序列采样技术;二是基于序列反单调性的新颖树型计算结构的高效挖掘技术。这两项技术能够在保证近似求解精确度的同时提高序列模式挖掘的效率。在合成和真实数据集的实验结果指出,本项工作所提出的方法能够以较高的效率和准确率近似得出前k项频繁序列。3、融合图结构信息的序列模式提炼已有的序列模式挖掘方法往往只考虑出现的频率等统计规律,导致所挖掘出的序列模式可用性不高。本工作将图的网络结构与序列模式相结合,提出在频繁序列模式的发现过程中实现提炼和过滤。基于此,首先给出具有图结构和序列模式时序性双重特征的新结构“轨迹热点”的结构定义,即由若干含有相同序列模式的轨迹所覆盖的紧密子图结构。为主动发现此类结构,本工作首先证明了该问题的计算复杂度,探索了轨迹热点的特征属性规律。在此基础上,提出了一种高效可扩展的主动发现方法,充分利用了轨迹热点结构和序列的反单调性,能够有效剪除不合规的序列模式,从而提高搜索效率。同时,为避免重复性发现和搜索造成的额外开销,设计并实现了高效的索引结构,支持轨迹热点的存储、更新和高效检索。在真实数据集上的实验指出,所提出的方法具有高可扩展性和有效性。4、基于序列模式的分布式子图匹配应用针对序列模式在实际业务场景中的应用问题,区别于以往其应用于分类与预测任务,提出将序列模式应用于子图匹配问题的剪枝优化操作上。本工作首先定义了一种“分解-组合”的分布式子图匹配框架,首先将查询图和数据图分解为子图,随后查询子图在数据子图中进行同构匹配形成中间解,最终中间解进行组合以应答原始查询图。其中,每个数据子图均可针对节点的邻居信息形成路径,从路径中可导出标签序列模式,与查询图中节点的标签序列模式进行比对和匹配后可对不合规的节点进行剪枝。实验结果证明,将序列模式用于剪枝过程中可有效降低计算的时间和空间开销。