云上高博会

基于社区结构的快速子图匹配方法

1.痛点问题随着图在各领域的广泛应用，对图上相关高效查询方法的需求也与日俱增，特别是在社交网络、金融、电商、安全和航天等众多领域具有重要作用的子图匹配查询。然而，现有子图匹配方法在实际使用中速度均较慢，当数据量较大时，现有方法的时间开销巨大，难以满足具体匹配过程中的时效性需求。同时，这些方法没有充分利用图数据的本质结构特点进行剪枝，在运行效率上仍有较大的改进空间。 2.解决方案本技术提出一种基于社区结构的子图匹配方法，基于社区结构在匹配过程中进行剪枝从而加快子图匹配的速度。流程图如图1所示。图1 本技术子图匹配计算流程首先，本技术识别数据图中的社区结构，将数据图划分为若干“内部紧密关联、相互之间连接松散”的社区。接着，基于社区结构，提出三种优化策略对子图匹配过程进行优化，并实现了相关技术。具体地，这三种优化策略包括两阶段破对称策略、基于社区路径的剪枝策略和基于社区结构的边界剪枝策略。其中，两阶段破对称策略利用模式图中的自同构映射，根据已得到的若干匹配结果推断出新的匹配结果，从而减少匹配过程中的计算量；基于社区路径的剪枝策略根据数据图中的跨社区的路径构建索引，在匹配过程中提前发现无法产生匹配结果的匹配尝试，减少匹配开销；基于社区结构的边界剪枝则考虑各社区的边界节点，即那些和其他社区的节点间有边关联的节点，根据边界节点的邻居情况进行剪枝，减小搜索空间，加快子图匹配速度。基于上述优化策略，本技术提出的基于社区结构的高效子图匹配方法能根据给出的数据图和模式图快速返回子图匹配结果。该技术可以作为模块嵌入金融、电商和航天等已有软件系统，也可作为单独软件工具并支持二次开发。 3.合作需求 1）应用场景：在图数据中快速查找满足某种特定结构的子图结构，进而作为查询结果返回或用于后续深入分析。可用于包括但不限于社交网络、金融、电商、安全和航天等众多场景中。 2）资源对接：对图查询、图分析有需求且对其高效性有要求的个人、单位和企业等。

清华大学 2022-12-05