IEEE Transactions on Pattern Analysis and Machine Intelligence · 2005 · 160 citations · 21 references
ComputingComputer ScienceAlgorithmsData MiningInformation RetrievalGraph AlgorithmsGraph AnalyticsGraph MiningGraph TheoryPattern RecognitionGraph IsomorphismGraph MatchingGraph-based Pattern RecognitionMatching AlgorithmsSpectral Graph AlgorithmsSpectral Graph TheorySubgraph IsomorphismTopological Features
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.
21
The PageRank Citation Ranking : Bringing Order to the Web
Lawrence M. Page, Sergey Brin, Rajeev Motwani et al. · 1999 · 12.7K citations
The Hungarian method for the assignment problem
Harold W. Kuhn · Naval Research Logistics Quarterly · 1955 · 12.6K citations
An Algorithm for Subgraph Isomorphism
J. R. Ullmann · Journal of the ACM · 1976 · 2.3K citations · Full text
Columbia Object Image Library (COIL100)
S.K. Nayar · Medical Entomology and Zoology · 1996 · 1.4K citations