图模式匹配的软约束模型及其符号推理研究

Graph matching techniques are widely used in biological information analysis, chemical analysis, social network analysis, image recognition, document processing and other fields. These application areas are facing the big challenges in both increasing size and diverse forms. Graph matching is an NP-complete problem. For improving the efficiency of graph pattern matching and relieving its combinatorial complexity problem, a novel symbolic model based on soft constraint satisfaction problem (soft CSP) and decision diagrams for graph matching is proposed, which is more general and descriptive. Based on this model and decision diagram symbolic technique, constraints description for graph edit operations together with constraint solving symbolic algorithms for maximum clique problem and maximum common subgraph are proposed. Constraint reasoning symbolic algorithms for graph edit distance is studied, and constraint solving symbolic techniques with tree-decomposition technique, soft arc consistency, and heuristic search for graph matching are developed. For the dynamic graph matching, dynamic soft arc consistency symbolic technique and local modification technique are studied, and then symbolic algorithms based on minimal spanning tree and shortest path are proposed. In order to further improve efficiency of the soft constraint solving technique, variables and values symmetries of soft CSP is detected. It is hopeful that an effective and unified methodology for graph matching will be presented.

图匹配技术已广泛应用于生物信息分析、化学分析、社交网络分析、图像识别、文本分析等领域，这些应用正面临着规模快速增长和形式复杂多样的巨大挑战。图匹配问题是一个NP完全问题，本项目着力于提高图模式匹配算法的求解效率及缓减图匹配问题所面临的组合复杂性问题，提出一种新的更具通用性和描述力的图匹配问题的软约束满足问题（soft CSP）符号模型。基于此模型，结合决策图（DDs）符号技术，给出图编辑操作的约束描述、最大团问题和最大公共子图的约束求解符号算法；研究图编辑距离的约束推理符号算法，及基于树分解技术、软弧一致性技术和启发式搜索的图匹配约束求解符号技术。针对动态图匹配问题，研究动态软弧一致性符号技术和局部修改符号技术，给出基于最小生成树和最短路径的动态图匹配的符号算法。为进一步提高图匹配问题的软约束求解效率，研究soft CSP中变量和值的对称性检测，以期为图匹配领域提供新的理论、方法和技术。

图匹配技术已广泛应用于生物信息分析、化学分析、社交网络分析、图像识别、文本分析等领域，这些应用正面临着规模快速增长和形式复杂多样的巨大挑战。图匹配问题是一个NP完全问题，本项目着力于提高图模式匹配算法的求解效率及缓减图匹配问题所面临的组合复杂性问题，建立了更具通用性和描述力的图匹配问题的CSP符号模型，并基于此模型开展图匹配问题的搜索和推理技术研究。结合决策图（DDs）符号技术，建立了最大公共子图的软约束满足问题（Soft CSP）模型，提出基于代数决策图（ADD）的最大公共子图的约束求解符号算法。研究了soft CSP中变量和值的对称性，提出了基于对称性破坏的子图同构问题的约束求解算法。研究了图结构的空间信息，结合图卷积神经网络，给出一种基于邻居信息聚合的子图同构问题的约束求解算法，提出了深度图匹配的一种新的体系结构。研究了精确图编辑距离和近似图编辑距离的相关算法，总结了图编辑距离存在的一些问题，给出了基于BP算法的图编辑距离求解的p-FBP算法和D-FBP算法，图编辑距离的加权约束模型及其求解技术。研究了动态图匹配问题的相关算法，给出了基于最短路径的动态图模式匹配的符号算法。针对图数据中噪音对图匹配精确度的影响，提出了一种基于卡方统计的近似子图匹配改进算法。进一步地，将图匹配技术应用于蛋白质复合物识别，提出了XGBP算法、DCRA算法和graph2vec-SVM识别算法，与目前流行的ClusterOne、CMC、HC-PIN和COACH四种非监督学习算法和三种监督学习算法SCI-BN、SCI-SVM和RM进行比较，在精准度、敏感度和F-measure三项指标中都显示出了良好的性能。本项目为图匹配研究领域提供了新的方法和技术。