一种匹配全局结构的图相似性度量

Graph Similarity Measure by Matching Global Structure

相似性度量是许多机器学习方法的基础,由于包含难以量化的结构,衡量图的相似性成为一项困难的任务.现有的基于图结构的直接型度量着重于图顶点或边等局部信息进行局部结构匹配,大大降低了许多实际应用中度量的有效性.提出一种新的图相似性度量方法,通过匹配两个图的全局结构来衡量它们的相似性,称之为全局结构匹配法.新方法通过顶点匹配和路径匹配两个步骤分别捕捉顶点和边的信息并以此来刻画图的全局结构.结合近邻分类器,在实际应用图数据上对新方法的性能进行了评估,实验结果表明,该方法大幅提高了分类精度.

Similarity measure is the basis of many machine learning methods. Due to the difficulty of quantizing structure,measure graph similarity becomes a difficult task. The existing direct methods focus on local information such as vertex or edge to conduct local structure matching,which greatly reduces the effectiveness of the measure in many practical applications. In this paper,we propose a newgraph similarity measure,called Global Structural Matching method,to measure the similarity of two graphs through matching their global structure. The method captures the vertex and edge information through the vertex matching step and path matching step,respectively. Based on this,the global structure of the graph can be easily depicted. The performance of the proposed measure is evaluated in nearest-neighbor classification on the real-world graph dataset,which demonstrates that the proposed method significantly improves the accuracy.