jmlr jmlr2006 jmlr2006-25 jmlr2006-25-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Thomas Kämpke
Abstract: Similarity of edge labeled graphs is considered in the sense of minimum squared distance between corresponding values. Vertex correspondences are established by isomorphisms if both graphs are of equal size and by subisomorphisms if one graph has fewer vertices than the other. Best fit isomorphisms and subisomorphisms amount to solutions of quadratic assignment problems and are computed exactly as well as approximately by minimum cost flow, linear assignment relaxations and related graph algorithms. Keywords: assignment problem, best approximation, branch and bound, inexact graph matching, model data base
Ravindra, K. Ahuja, Thomas L. Magnanti and James Orlin. Network Flows. Prentice Hall, Englewood Cliffs, 1993. 2084 D ISTANCE PATTERNS IN S TRUCTURAL S IMILARITY Endika Bengoetxea. Inexact graph matching using estimation of distribution algorithms. Ph.D. dissertation, University of the Basque Country, San Sebastian, 2002. Tiberio S. Caetano, Terry Caelli, Dale Schuurmanns and Dante A.C Barone. Graphical models and point pattern matching. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI, forthcoming. Pierre-Antoine Champin and Christine Solnon. Measuring the similarity of labeled graphs. In Proceedings of the Fifth International Conference on Case-Based Reasoning, pages 80-95, Springer, LNCS 2689, Berlin, 2003. Richard Desper and Martin Vingron. Tree fitting: topological reconstruction from ordinary leastsquares edge length estimates. Journal of Classification, 19:87-112, 2002. Ian Foster and Carl Kesselman, editors. The Grid: Blueprint to a new Computing Infrastructure. 2nd ed., Elsevier, Amsterdam, 2004. Satoru Fujishige. Submodular Functions and Optimization. North Holland, Amsterdam, 1991. Michael R. Garey and David S. Johnson. Computers and Intractability. Freeman, San Francisco, 1981. Steven Gold and Anand Rangarajan. A graduated assignment algorithm for graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence. 18:377-388, 1996. Gene H. Golub and Charles F. van Loan. Matrix Computations. 4th printing, John Hopkins University Press, Baltimore, 1985. Godefrey H. Hardy, John E. Littlewood and George Polya. Inequalities. Cambridge University Press, Cambridge, 1948. Adel Hlaoui and Shengrui Wang. A new algorithm for inexact graph matching. In Proceedings of the International Conference on Pattern Recognition ICPR’02, pages 180-183, Quebec, 2002. Thomas K¨ mpke. Scalable distance similarity of chemical structures. Combinatorial Chemistry and a High Throughput Screening. 7:11-21, 2004. Sergey Melnik, Hector Garcia-Molina and Erhard Rahm. Similarity flooding: a versatile graph matching algorithm and its application to schema matching. In Proceedings of the 16th International Conference on Data Engineering ICDE, 12 pages, San Diego, 2002. Kurt Mehlhorn and Stephan N¨ her. LEDA A Platform for Combinatorial and Geometric Computing. a Cambridge University Press, Cambridge, 2000. Bruno T. Messmer and Horst Bunke. A new algorithm for error-tolerant subgraph isomorphism detection. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI, 20:493-504, 1998. Bruno T. Messmer and Horst Bunke. A decision tree approach to graph and subgraph isomorphism detection. Pattern Recognition 32:1979-1998, 1999. 2085 ¨ K AMPKE Apostolos N. Papadopoulos and Yannis Manolopoulos. Structure-based similarity search with graph histograms. In Proceedings of the 10th International Workshop on Database and Expert System Applications DEXA, pages 174-178, 1999. Arthur R. Pope and David G. Lowe. Learning appearance models for object recognition. In Proceedings of International Workshop on Object Representation for Computer Vision, pages 201-219, Springer, Berlin, 1996. Dennis Shasha, Jason T.L. Wang and Rosalba Giugno. Algorithmics and applications of tree and graph searching. In Proceedings of the Symposium on Principles of Database Systems, pages 39-52, 2002. Steven S. Skiena and Gopalakrishnan Sundaram. A partial digest approach to restriction site mapping. Bulletin of Mathematical Biology, 56:275-294, 1994. Jason T.L. Wang, Bruce A. Shapiro, Dennis Shasha, Kaizhong Zhang and Kathleen M. Currey. An algorithm for finding the largest approximately common substructures of two trees. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20:889-895, 1998. ¨ Laurenz Wiskott, Jean-Marc Fellous, Norbert Kruger, Christoph Malsburg. Face recognition by elastic bunch graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI, 19:775-779, 1997. Laurenz Wiskott and Christoph Malsburg. Labeled bunch graphs for image analysis. US patent no. 6,356,659, 2002. 2086