Abstract: In the field of graph-based pattern recognition, the existing graph kernels can’t mine the node features that reflect graph’s topology sufficiently. To solve this problem, the present study proposes new graph kernels based on space syntax and shortest path. This paper takes advantage of the space syntax theory in architecture and urban planning to make up quantitative description of the graph’s topological features and proposes the space syntax kernel and the space syntax kernel based on shortest path. These graph kernels are expressible, positive definite, computable and applicable to most graphs, and then are used to implement the inexact graph matching using SVM. Differ from other graph kernel methods, the proposed method can render the graph’s topology adequately and has a favorable universality. Experimental results show that such graph kernels can achieve superior results in classification compared to shortest path kernel.

Key words: graph-based pattern recognition, inexact graph matching, space syntax, shortest path, graph kernel

摘要： 针对图模式识别领域中现有图核方法对反映图本身拓扑结构的节点特征挖掘不够充分的问题，提出了基于空间句法和最短路径的图核。借鉴建筑学与城市规划学科中的空间句法理论构造分布于图节点上的拓扑特征的量化描述，基于此提出了可表示、计算，正定、适用范围较广的空间句法核和基于最短路径的空间句法核，进而借助支持向量机实现了非精确图匹配。不同于其他图核方法，该方法对图的拓扑特征表达能力强，通用性较好。实验结果表明，所设计的图核在分类精度方面相较于最短路径核有较显著的改善。

关键词: 图模式识别, 非精确图匹配, 空间句法, 最短路径, 图核