In this work a convex relaxation of a subgraph isomorphism problem is proposed, which leads to a new lower bound that can provide a proof that a subgraph isomorphism between two graphs can not be found. The bound is based on a semidefinite programming relaxation of a combinatorial optimisation formulation for subgraph isomorphism and is explained in detail. We consider subgraph isomorphism problem instances of simple graphs which means that only the structural information of the two graphs is exploited and other information that might be available (e.g., node positions) is ignored. The bound is based on the fact that a subgraph isomorphism always leads to zero as lowest possible optimal objective value in the combinatorial problem formulation. Therefore, for problem instances with a lower bound that is larger than zero this represents a proof that a subgraph isomorphism can not exist. But note that conversely, a negative lower bound does not imply that a subgraph isomorphism must be present and only indicates that a subgraph isomorphism can not be excluded. In addition, the relation of our approach and the reformulation of the largest common subgraph problem into a maximum clique problem is discussed. 1. Introduction The subgraph isomorphism problem is a well-known combinatorial optimization problem and often involves the problem of finding the appropriate matching too. It is also of particular interest in computer vision where it can be exploited to recognise objects. For example, if an object in an image is represented by a graph, the object could be identified as subgraph within a possibly larger scene graph. Several approaches have been proposed to tackle the subgraph isomorphism problem and we refer to a few [1–4] and their references therein. Error-correcting graph matching [5]—also known as error-tolerant graph matching—is a general approach to calculate an assignment between the nodes of two graphs. It is based on the minimisation of graph edit costs which result from some predefined edit operations when one graph is turned exactly into the other. Commonly introduced graph edit operations are deletion, insertion, and substitution of nodes and edges. Each graph-edit operation has a cost assigned to it which is application dependent. The minimal graph edit cost defines the so-called edit distance between two graphs. The idea to define such a distance for graph matching goes back to Sanfeliu and Fu [6] in 1983. Before that, the edit distance was mainly used for string matching. Several approaches for error correcting graph matching have been
References
[1]
J. R. Ullmann, “An algorithm for subgraph isomorphism,” Journal of the Association for Computing Machinery, vol. 23, no. 1, pp. 31–42, 1976.
[2]
H. G. Barrow and R. M. Burstall, “Subgraph isomorphism, matching relational structures and maximal cliques,” Information Processing Letters, vol. 4, no. 4, pp. 83–84, 1976.
[3]
B. T. Messmer and H. Bunke, “A new algorithm for error-tolerant subgraph isomorphism detection,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, no. 5, pp. 493–504, 1998.
[4]
D. Eppstein, “Subgraph isomorphism in planar graphs and related problems,” Journal of Graph Algorithms and Applications, vol. 3, no. 3, pp. 1–27, 1999.
[5]
H. Bunke, “Error correcting graph matching: on the influence of the underlying cost function,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21, no. 9, pp. 917–922, 1999.
[6]
A. Sanfeliu and K. S. Fu, “A distance measure between attributed relational graphs for pattern recognition,” IEEE Transactions on Systems, Man and Cybernetics, vol. 13, no. 3, pp. 353–362, 1983.
[7]
Y.-K. Wang, K.-C. Fan, and J.-T. Horng, “Genetic-based search for error-correcting graph isomorphism,” IEEE Transactions on Systems, Man, and Cybernetics, Part B, vol. 27, no. 4, pp. 588–597, 1997.
[8]
H. Wolkowicz, R. Saigal, and L. Vandenberghe, Eds., Handbook of Semidefinite Programming, Kluwer Academic Publishers, Boston, Mass, USA, 2000.
[9]
M. X. Goemans and D. P. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” Journal of the Association for Computing Machinery, vol. 42, no. 6, pp. 1115–1145, 1995.
[10]
J. Keuchel, C. Schn？rr, C. Schellewald, and D. Cremers, “Binary partitioning, perceptual grouping, and restoration with semidefinite programming,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no. 11, pp. 1364–1379, 2003.
[11]
C. Schellewald and C. Schn？rr, “Probabilistic subgraph matching based on convex relaxation,” in Proceedings of the 5th International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR '05), vol. 3757 of Lecture Notes in Computer Science, pp. 171–186, 2005.
[12]
H. Yu and E. R. Hancock, “Graph seriation using semi-definite programming,” in Proceedings of the 5th IAPR International Workshop on Graph-Based Representations in Pattern Recognition (GbRPR '05), vol. 3434 of Lecture Notes in Computer Science, pp. 63–71, 2005.
[13]
M. Agrawal and L. S. Davis, “Camera calibration using spheres: a semi-definite programming approach,” in Proceedings of the 9th IEEE International Conference on Computer Vision (ICCV '03), vol. 2, pp. 782–789, 2003.
[14]
I. M. Bomze, M. Budinich, P. M. Pardalos, and M. Pelillo, “The maximum clique problem,” in Handbook of Combinatorial Optimization, D.-Z. Du and P. M. Pardalos, Eds., pp. 1–74, Kluwer Academic, Boston, Mass, USA, 1999.
[15]
M. Pelillo, “Replicator equations, maximal cliques, and graph isomorphism,” Neural Computation, vol. 11, no. 8, pp. 1933–1955, 1999.
[16]
M. R. Garey and D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, San Francisco, Calif, USA, 1991.
[17]
P. M. Pardalos and S. A. Vavasis, “Quadratic programming with one negative eigenvalue is NP-hard,” Journal of Global Optimization, vol. 1, no. 1, pp. 15–22, 1991.
[18]
B. Borchers, “CSDP, a C library for semidefinite programming,” Optimization Methods and Software, vol. 11, no. 1, pp. 613–623, 1999.
[19]
S. J. Benson and Y. Ye, “DSDP3: dual scaling algorithm for general positive semidefinite programming,” Tech. Rep. ANL/MCS-P851-1000, Argonne National Labs, 2001.
[20]
M. Ko？vara and M. Stingl, “Pennon: a code for convex nonlinear and semidefinite programming,” Optimization Methods & Software, vol. 18, no. 3, pp. 317–333, 2003.
[21]
A. Graham, Kronecker Products and Matrix Calculus with Applications, Ellis Horwood and John Wiley & Sons, 1981.
[22]
Y. Ye, Interior Point Algorithms: Theory and Analysis, John Wiley & Sons Inc., New York, NY, USA, 1997.
[23]
H. D. Mittelmann, “An independent benchmarking of SDP and SOCP solvers,” Mathematical Programming Series B, vol. 95, no. 2, pp. 407–430, 2003.
[24]
C. Helmberg, F. Rendl, R. J. Vanderbei, and H. Wolkowicz, “An interior-point method for semidefinite programming,” SIAM Journal on Optimization, vol. 6, no. 2, pp. 342–361, 1996.
[25]
Brian Borchers. CSDP 4.8 User’s Guide, 2004.
[26]
M. Budinich, “Exact bounds on the order of the maximum clique of a graph,” Discrete Applied Mathematic, vol. 127, no. 3, pp. 535–543, 2003.
[27]
T. S. Motzkin and E. G. Straus, “Maxima for graphs and a new proof of a theorem of Turán,” Canadian Journal of Mathematics. Journal Canadien de Mathématiques, vol. 17, pp. 533–540, 1965.
[28]
L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, “Performance evaluation of the vf graph matching algorithm,” in Proceedings of the 10th International Conference on Image Analysis and Processing (ICIAP ’99), p. 1172, IEEE Computer Society, Washington, DC, USA, 1999.
