Abstract
Measuring graph similarity is a key issue in many applications. We propose a new constraint-based modeling language for defining graph similarity measures by means of constraints. It covers measures based on univalent matchings, such that each node is matched with at most one node, as well as multivalent matchings, such that a node may be matched with a set of nodes. This language is designed on top of Comet, a programming language supporting both Constraint Programming (CP) and Constraint-Based Local Search (CBLS). Starting from the constraint-based description of the measure, we automatically generate a Comet program for computing the measure. Depending on the measure characteristics, this program either uses CP —which is better suited for computing exact measures such as (sub)graph isomorphism— or CBLS —which is better suited for computing error-tolerant measures such as graph edit distances. First experimental results show the feasibility of our approach.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
McKay, B.D.: Practical graph isomorphism. Congressus Numerantium 30, 45–87 (1981)
Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: Performance evaluation of the vf graph matching algorithm. In: ICIAP, pp. 1172–1177 (1999)
Umeyama, S.: An eigendecomposition approach to weighted graph matching problems. IEEE Transactions on Pattern Analysis and Machine Intelligence 10(5), 695–703 (1988)
Almohamad, H., Duffuaa, S.: A linear programming approach for the weighted graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence 15(5), 522–525 (1993)
Zaslavskiy, M., Bach, F., Vert, J.: A path following algorithm for the graph matching problem. In: Elmoataz, A., Lezoray, O., Nouboud, F., Mammass, D. (eds.) ICISP 2008. LNCS, vol. 5099, pp. 329–337. Springer, Heidelberg (2008)
Cross, A., Wilson, R., Hancock, E.: Inexact graph matching using genetic search. Pattern Recognition 30, 953–970 (1997)
Champin, P.A., Solnon, C.: Measuring the similarity of labeled graphs. In: Ashley, K.D., Bridge, D.G. (eds.) ICCBR 2003. LNCS, vol. 2689, pp. 80–95. Springer, Heidelberg (2003)
Sorlin, S., Solnon, C.: Reactive tabu search for measuring graph similarity. In: Brun, L., Vento, M. (eds.) GbRPR 2005. LNCS, vol. 3434, pp. 172–182. Springer, Heidelberg (2005)
Sammoud, O., Solnon, C., Ghedira, K.: Ant Algorithm for the Graph Matching Problem. In: Raidl, G.R., Gottlieb, J. (eds.) EvoCOP 2005. LNCS, vol. 3448, pp. 213–223. Springer, Heidelberg (2005)
Monette, J.N., Deville, Y., Van Hentenryck, P.: AEON: Synthesizing scheduling algorithms from high-level models. In: Proceedings of 2009 INFORMS Computing Society Conference (2009)
Vosselman, G.: Relational Matching. LNCS, vol. 628. Springer, Heidelberg (1992)
Bunke, H.: On a relation between graph edit distance and maximum common subgraph. Pattern Recognition Letters 18, 689–694 (1997)
Zaslavskiy, M., Bach, F., Vert, J.P.: A path following algorithm for graph matching. In: Elmoataz, A., Lezoray, O., Nouboud, F., Mammass, D. (eds.) ICISP 2008 2008. LNCS, vol. 5099, pp. 329–337. Springer, Heidelberg (2008)
Ambauen, R., Fischer, S., Bunke, H.: Graph Edit Distance with Node Splitting and Merging. In: Hancock, E.R., Vento, M. (eds.) GbRPR 2003. LNCS, vol. 2726, pp. 95–106. Springer, Heidelberg (2003)
Tsang, E.: Foundations of Constraint Satisfaction. Academic Press, London (1993)
Sorlin, S., Solnon, C.: A parametric filtering algorithm for the graph isomorphism problem. Constraints 13(4), 518–537 (2008)
Zampelli, S., Deville, Y., Solnon, C., Sorlin, S., Dupont, P.: Filtering for Subgraph Isomorphism. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 728–742. Springer, Heidelberg (2007)
Van Hentenryck, P., Michel, L.: Constraint-Based Local Search. The MIT Press, Cambridge (2005)
Quimper, C., Golynski, A., Lopez-Ortiz, A., van Beek, P.: An efficient bounds consistency algorithm for the global cardinality constraint. Constraints 10(1), 115–135 (2005)
Larrosa, J., Valiente, G.: Constraint satisfaction algorithms for graph pattern matching. Mathematical. Structures in Comp. Sci. 12(4), 403–422 (2002)
Barabasi, A.L.: Linked: How Everything Is Connected to Everything Else and What It Means. Plume (2003)
De Santo, M., Foggia, P., Sansone, C., Vento, M.: A large database of graphs and its use for benchmarking graph isomorphism algorithms. Pattern Recogn. Lett. 24(8), 1067–1079 (2003)
Bunke, H., Foggia, P., Guidobaldi, C., Sansone, C., Vento, M.: A comparison of algorithms for maximum common subgraph on randomly connected graphs. In: Caelli, T.M., Amin, A., Duin, R.P.W., Kamel, M.S., de Ridder, D. (eds.) SPR 2002 and SSPR 2002. LNCS, vol. 2396, pp. 123–132. Springer, Heidelberg (2002)
Sorlin, S.: Mesurer la similarité de graphes. PhD thesis, Université Claude Bernard, Lyon I, France (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
le Clément, V., Deville, Y., Solnon, C. (2009). Constraint-Based Graph Matching. In: Gent, I.P. (eds) Principles and Practice of Constraint Programming - CP 2009. CP 2009. Lecture Notes in Computer Science, vol 5732. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04244-7_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-04244-7_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04243-0
Online ISBN: 978-3-642-04244-7
eBook Packages: Computer ScienceComputer Science (R0)