User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Combining two structured domains for modeling various graph matching problems

Primary tabs

download
  • Open access
  • PDF
  • 143.97 K
Deville, Yves [UCL] Dooms, Grégoire [UCL] Zampelli, Stéphane [UCL]

Graph pattern matching is a central application in many fields. In various areas, the structure of the pattern can only be approximated and exact matching is then too accurate. We focus here on approximations declared by the user within the pattern (optional nodes and forbidden arcs), covering graph/subgraph mono/isomorphism problems. In this paper, we show how the integration of two domains of computation over countable structures, graphs and maps, can be used for modeling and solving various graph matching problems from the simple graph isomorphism to approximate graph matching. To achieve this, we extend map variables allowing the domain and range to be non-fixed and constrained. We describe how such extended maps are designed then realized on top of finite domain and finite set variables with specific propagators. We show how a single monomorphism constraint is sufficient to model and solve those multiples graph matching problems. Furthermore, our experimental results show that our CP approach is competitive with a state of the art algorithm for subgraph isomorphism.

Document type Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection
Access type Accès libre
Publication date 2008
Language Anglais
Conference "Recent Advances in Constraints. 12th Annual ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2007", Rocquencourt, France (7-8 June 2007)
Peer reviewed yes
Host document "Recent Advances in Constraints. 12th Annual ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2007"- 76-90 (ISBN : 978-3-540-89811-5)
Publisher Springer-verlag
Affiliation UCL - FSA/INGI - Département d'ingénierie informatique
Links
  1. Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. IJPRAI 18, 265–298 (2004)
  2. Larrosa, J., Valiente, G.: Constraint satisfaction algorithms for graph pattern matching. Mathematical Structures in Comp. Sci. 12, 403–422 (2002)
  3. Rudolf Michael, Utilizing Constraint Satisfaction Techniques for Efficient Graph Pattern Matching, Theory and Application of Graph Transformations (2000) ISBN:9783540672036 p.238-251, 10.1007/978-3-540-46464-8_17
  4. Wang, J.T.L., Zhang, K., Chirn, G.W.: Algorithms for approximate graph matching. Inf. Sci. Inf. Comput. Sci. 82, 45–74 (1995)
  5. Messmer B.T., Bunke H., A new algorithm for error-tolerant subgraph isomorphism detection, 10.1109/34.682179
  6. DePiero Fred, Krout David, An algorithm using length-r paths to approximate subgraph isomorphism, 10.1016/s0167-8655(02)00186-1
  7. Robles-Kelly A., Hancock E.R., Graph edit distance from spectral seriation, 10.1109/tpami.2005.56
  8. Giugno, R., Shasha, D.: Graphgrep: A fast and universal method for querying graphs. ICPR 2, 112–115 (2002)
  9. Zampelli Stéphane, Deville Yves, Dupont Pierre, Approximate Constrained Subgraph Matching, Principles and Practice of Constraint Programming - CP 2005 (2005) ISBN:9783540292388 p.832-836, 10.1007/11564751_74
  10. Sorlin Sébastien, Solnon Christine, A Global Constraint for Graph Isomorphism Problems, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (2004) ISBN:9783540218364 p.287-301, 10.1007/978-3-540-24664-0_20
  11. Puget Jean-Fran�ois, Symmetry Breaking Revisited, 10.1007/s10601-004-5306-8
  12. Mamoulis Nikos, Stergiou Kostas, Constraint Satisfaction in Semi-structured Data Graphs, Principles and Practice of Constraint Programming – CP 2004 (2004) ISBN:9783540232414 p.393-407, 10.1007/978-3-540-30201-8_30
  13. Dooms Gregoire, Deville Yves, Dupont Pierre, CP(Graph): Introducing a Graph Computation Domain in Constraint Programming, Principles and Practice of Constraint Programming - CP 2005 (2005) ISBN:9783540292388 p.211-225, 10.1007/11564751_18
  14. Gervet, C.: New structures of symbolic constraint objects: sets and graphs. In: Third Workshop on Constraint Logic Programming (WCLP 1993), Marseille (1993)
  15. Chabrier Alain, Danna Emilie, Le Pape Claude, Perron Laurent, Solving a Network Design Problem, 10.1023/b:anor.0000032577.81139.84
  16. Gervet Carmen, Interval propagation to reason about sets: Definition and implementation of a practical language, 10.1007/bf00137870
  17. Flener Pierre, Hnich Brahim, Kiziltan Zeynep, Compiling High-Level Type Constructors in Constraint Programming, Practical Aspects of Declarative Languages (2001) ISBN:9783540417682 p.229-244, 10.1007/3-540-45241-9_16
  18. Beldiceanu N, Contejean E, Introducing global constraints in CHIP, 10.1016/0895-7177(94)90127-9
  19. Pesant Gilles, Gendreau Michel, Potvin Jean-Yves, Rousseau Jean-Marc, An Exact Constraint Logic Programming Algorithm for the Traveling Salesman Problem with Time Windows, 10.1287/trsc.32.1.12
  20. Puget, J.F.: Pecos a high level constraint programming language. In: Proceedings of Spicis 1992 (1992)
  21. Beldiceanu Nicolas, Flener Pierre, Lorca Xavier, The tree Constraint, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (2005) ISBN:9783540261520 p.64-78, 10.1007/11493853_7
  22. Sellmann Meinolf, Cost-Based Filtering for Shorter Path Constraints, Principles and Practice of Constraint Programming – CP 2003 (2003) ISBN:9783540202028 p.694-708, 10.1007/978-3-540-45193-8_47
  23. Cambazard, H., Bourreau, E.: Conception d’une contrainte globale de chemin. In: 10e Journées nationales sur la résolution pratique de problFmes NP-complets (JNPC 2004), pp. 107–121 (2004)
  24. Dooms Grégoire, Katriel Irit, The Minimum Spanning Tree Constraint, Principles and Practice of Constraint Programming - CP 2006 (2006) ISBN:9783540462675 p.152-166, 10.1007/11889205_13
  25. Dooms Grégoire, Katriel Irit, The “Not-Too-Heavy Spanning Tree” Constraint, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (2007) ISBN:9783540723967 p.59-70, 10.1007/978-3-540-72397-4_5
  26. Hnich, B.: Function variables for Constraint Programming. PhD thesis, Uppsala University, Department of Information Science (2003)
  27. Frisch, A.M., Jefferson, C., Hernandez, B.M., Miguel, I.: The rules of constraint modelling. In: Proceedings of IJCAI 2005 (2005)
  28. Lauriere Jena-Lonis, A language and a program for stating and solving combinatorial problems, 10.1016/0004-3702(78)90029-2
  29. Smith, D.: Structure and design of global search algorithms. Technical Report Tech. Report KES.U.87.12, Kestrel Institute, Palo Alto, Calif (1987)
  30. Cadoli Marco, Palopoli Luigi, Schaerf Andrea, Vasile Domenico, np-spec: An Executable Specification Language for Solving All Problems in NP, Practical Aspects of Declarative Languages (1998) ISBN:9783540655275 p.16-30, 10.1007/3-540-49201-1_2
  31. Azevedo Francisco, Cardinal: A Finite Sets Constraint Solver, 10.1007/s10601-006-9012-6
  32. Beldiceanu, N.: Global constraints as graph properties on structured network of elementary constraints of the same type. Technical Report T2000/01, SICS (2000)
  33. Thiel, S.: Efficient Algorithms for Constraint Propagation and for Processing Tree Descriptions. PhD thesis, University of Saarbrucken (2004)
  34. Bessiere Christian, Hebrard Emmanuel, Hnich Brahim, Kiziltan Zeynep, Walsh Toby, Filtering Algorithms for the NValue Constraint, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (2005) ISBN:9783540261520 p.79-93, 10.1007/11493853_8
  35. Bessière, C., Hebrard, E., Hnich, B., Kiziltan, Z., Walsh, T.: The range and roots constraints: Specifying counting and occurrence problems. In: IJCAI, pp. 60–65 (2005)
  36. Bessière Christian, Van Hentenryck Pascal, To Be or Not to Be ... a Global Constraint, Principles and Practice of Constraint Programming – CP 2003 (2003) ISBN:9783540202028 p.789-794, 10.1007/978-3-540-45193-8_54
  37. Zampelli Stéphane, Deville Yves, Solnon Christine, Sorlin Sébastien, Dupont Pierre, Filtering for Subgraph Isomorphism, Principles and Practice of Constraint Programming – CP 2007 ISBN:9783540749691 p.728-742, 10.1007/978-3-540-74970-7_51
  38. Foggia, P., Sansone, C., Vento, M.: An improved algorithm for matching large graphs. In: ed. 3rd IAPR-TC15 Workshop on Graph-based Representations. (2001), http://amalfi.dis.unina.it/graph/db/vflib2.0/doc/vflib.html
  39. Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: Performance evaluation of the vf graph matching algorithm. In: ICIAP, pp. 1172–1177. IEEE Computer Society, Los Alamitos (1999)
  40. Ullmann J. R., An Algorithm for Subgraph Isomorphism, 10.1145/321921.321925
  41. Knuth, D.E.: The Stanford GraphBase. A Platform for Combinatorial Computing. ACM Press, New York (1993)
  42. Dovier A., Piazza C., The Subgraph Bisimulation Problem, 10.1109/tkde.2003.1209024
Bibliographic reference Deville, Yves ; Dooms, Grégoire ; Zampelli, Stéphane. Combining two structured domains for modeling various graph matching problems.Recent Advances in Constraints. 12th Annual ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2007 (Rocquencourt, France, 7-8 June 2007). In: Recent Advances in Constraints. 12th Annual ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2007, Springer-verlag2008, p.76-90
Permanent URL http://hdl.handle.net/2078.1/67626