基于符号决策图的图数据表示和匹配研究

Graph data are the abstract model for the emerging applications such as social network, world wide web and biological structure, which are facing the big challenges in both increasing size and diverse forms. Managing and treating graph data efficiently are urgent topics, have been attracting more and more attentions. Representing graph data compactly can not only reduce the storage space, but also improve the managing efficiency. Graph matching is the score of the similarity among graph (or subgraph) and graphs, and the core techniques supporting graph data query, mining and knowledge discovery. In terms of the large scale graph data applications, the mechanism to represent and operate graph using ordered binary decision digrams，their variants and K2 trees will be studied so that the symbolic decision diagrams gDD to represent succintly and operate efficiently graph data will be proposed. In the framework of algebraic decision diagram and its bisimulation with graph edit, the novel structure edit-DD to symbolically formulate the edit operations of graphs will be explored so as to develop the symbolic algorithms for the graph edit distance and the graph (or subgraph) matching. On the basis of symbolic operations of graph set, the combination of the verification-filtering procedure with symbolic heuristic searching will be probed in order to put forward the ef-DD techniques for the multi-graph matching. It is hopeful that an effective and unified methodology for the representation, operation and matching of the large-scale graph data applications will be presented.

图数据是社交网络、万维网和生物信息等应用的抽象数据模型，这些应用正面临着规模快速增长和形式复杂多样的巨大挑战,图数据的高效管理和分析研究具有重要的学术意义和实际价值。紧凑的图数据表示不仅可以降低图数据的存储空间,而且还可以支持图数据的快速处理。图数据匹配是图/子图与图之间的相似度评测，是图数据查询、挖掘和知识发现的核心支撑技术。本项目拟从大规模图数据应用的需求出发，研究有序二叉决策图及扩展形式和K2树的图表示和操作机制，建立能够高效支持图数据紧凑表示和多模式操作的符号决策图gDD表示方法；以代数决策图与图编辑操作的互模拟为基础，提出图数据编辑的新型符号决策图edit-DD，建立图编辑距离计算以及图/子图匹配的符号决策图算法；基于图集的符号决策图操作，研究“验证-过滤”和启发式搜索融合的符号操作技术，建立多图匹配的vf-DD方法。以期为大规模图数据的表示、操作和匹配提供新的理论、方法和技术。

图数据是社交网络、万维网和生物信息等应用的抽象数据模型，这些应用正面临着规模快速增长和形式复杂多样的巨大挑战，图数据的高效管理和分析研究具有重要的学术意义和实际价值。.从大规模图数据的应用需求出发，本项目对大规模图数据的聚类、紧凑表示及操作算法进行了研究，不仅可以降低图数据的存储空间，而且还可以支持图数据的快速处理；进一步地，对知识图谱嵌入模型进行了研究，提出了基于翻译、相似性负采样、自适应负采样等技术的知识图谱嵌入模型，在链路预测和三元组分类任务上取得了显著的性能改善；最后，将二叉决策图、模式挖掘、偏好学习等图数据相关理论与技术应用于信息安全、智慧旅游等领域，取得良好的效果。