Gori Marco, Maggini Marco, Sarti Lorenzo
DII-Università degli Studi di Siena, Via Roma, 56-53100 Siena, Italy.
IEEE Trans Pattern Anal Mach Intell. 2005 Jul;27(7):1100-11. doi: 10.1109/tpami.2005.138.
In this paper, we propose a general framework for graph matching which is suitable for different problems of pattern recognition. The pattern representation we assume is at the same time highly structured, like for classic syntactic and structural approaches, and of subsymbolic nature with real-valued features, like for connectionist and statistic approaches. We show that random walk based models, inspired by Google's PageRank, give rise to a spectral theory that nicely enhances the graph topological features at node level. As a straightforward consequence, we derive a polynomial algorithm for the classic graph isomorphism problem, under the restriction of dealing with Markovian spectrally distinguishable graphs (MSD), a class of graphs that does not seem to be easily reducible to others proposed in the literature. The experimental results that we found on different test-beds of the TC-15 graph database show that the defined MSD class "almost always" covers the database, and that the proposed algorithm is significantly more efficient than top scoring VF algorithm on the same data. Most interestingly, the proposed approach is very well-suited for dealing with partial and approximate graph matching problems, derived for instance from image retrieval tasks. We consider the objects of the COIL-100 visual collection and provide a graph-based representation, whose node's labels contain appropriate visual features. We show that the adoption of classic bipartite graph matching algorithms offers a straightforward generalization of the algorithm given for graph isomorphism and, finally, we report very promising experimental results on the COIL-100 visual collection.
在本文中，我们提出了一种适用于不同模式识别问题的图匹配通用框架。我们假设的模式表示同时具有高度结构化，类似于经典的句法和结构方法，并且具有像连接主义和统计方法那样的带有实值特征的亚符号性质。我们表明，受谷歌网页排名启发的基于随机游走的模型产生了一种谱理论，该理论在节点层面很好地增强了图的拓扑特征。由此直接得出，在处理马尔可夫谱可区分图（MSD）的限制下，我们为经典的图同构问题推导了一种多项式算法，MSD 是一类似乎不容易简化为文献中提出的其他类别的图。我们在 TC - 15 图数据库的不同测试平台上得到的实验结果表明，所定义的 MSD 类“几乎总是”覆盖该数据库，并且所提出的算法在相同数据上比得分最高的 VF 算法效率显著更高。最有趣的是，所提出的方法非常适合处理例如从图像检索任务中衍生出的部分和近似图匹配问题。我们考虑了 COIL - 100 视觉集合中的对象，并提供了一种基于图的表示，其节点标签包含适当的视觉特征。我们表明，采用经典的二分图匹配算法可以直接推广用于图同构的算法，最后，我们在 COIL - 100 视觉集合上报告了非常有前景的实验结果。
