动态异质大图匹配模型及算法研究

Graph has been prevalently used in a wide range of application domains to model the complicated relationships between data objects. With a large number of graphs generated and accumulated, graph processing has attracted great interests from both research and industrial communities. Graph matching is an important research topic in graph processing, with the aim of finding the node correspondences in two graphs to maximize the common part between these two graphs. In many applications, graphs are heterogeneous，large, and changing dynamically. Current solutions for graph matching problem are targeted at static graphs with very high computational complexity. Thus they cannot handle heterogeneous graphs as described above. To solve this problem, we study three sub-problems in heterogeneous graph matching, including heterogeneous graph matching model construction, heterogeneous graph matching algorithms, and dynamic maintenance of heterogeneous graph matching. We will also implement a prototype system for large-scale dynamic heterogeneous graph matching to verify the proposed theories and techniques.This project will make significant contribution for the further development of graph processing techniques and solving the problem occurred in many application domains.

图结构被广泛应用于多种领域，以描述事物之间的复杂关系。随着图的大量产生和积累，图处理技术成为众多学者和业界人士的研究热点。图匹配问题是图处理技术中的重要研究内容，其目标是确定两个图顶点之间的对应关系，以尽可能地保留它们的公共部分。目前很多应用领域的图数据呈现异质、大规模、动态变化的特性，而现有的图匹配算法主要针对静态同质图且计算复杂度过高，无法解决具有上述特性的异质大图匹配问题，这给研究者带来新的挑战和机遇。为此，本项目围绕动态异质大图匹配问题，从语义模型、匹配算法、动态更新三个方面，采用逐步推进的方式，依次研究异质大图匹配语义模型、语义模型约束下异质大图分布式匹配算法、异质大图匹配结果的动态更新方法，并研制动态异质大图匹配原型系统以验证基础理论研究成果的有效性和可行性。本项研究对于推动图处理技术的进一步发展以及满足应用领域对动态异质大图匹配的需求，具有重要的科学意义和应用价值。

随着信息技术的产生和发展，越来越多的领域产生并积累了大量的图数据。图数据因其固有的结构复杂性，在计算上面临许多挑战，成为众多学者和业界人士的研究热点。图匹配以建立图顶点之间的对应关系且最大化其公共部分为目标，是图数据处理技术中的重要研究内容。针对目前应用领域中的图数据呈现的异质、大规模、动态变化的特性，本项目围绕动态异质大图匹配问题，从语义模型、匹配算法、动态更新三个方面，采用逐步推进地方式，依次研究异质大图匹配语义模型、语义模型约束下异质大图分布式匹配算法、异质大图匹配结果的动态更新方法，并将上述模型和算法在生物信息、社交网络等图数据上进行了测试，证明了我们提出的理论和方法的可行性和有效性。在本项目的执行过程中，我们培养了两名博士，一名硕士，并发表十余篇论文于ICDE、DASFAA、BIBM等重要的国际学术会议和期刊上。