nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Finding Subgraphs with Side Constraints

verfasst von : Özgür Akgün, Jessica Enright, Christopher Jefferson, Ciaran McCreesh, Patrick Prosser, Steffen Zschaler

Erschienen in: Integration of Constraint Programming, Artificial Intelligence, and Operations Research

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The subgraph isomorphism problem is to find a small “pattern” graph inside a larger “target” graph. There are excellent dedicated solvers for this problem, but they require substantial programming effort to handle the complex side constraints that often occur in practical applications of the problem; however, general purpose constraint solvers struggle on more difficult graph instances. We show how to combine the state of the art Glasgow Subgraph Solver with the Minion constraint programming solver to get a “subgraphs modulo theories” solver that is both performant and flexible. We also show how such an approach can be driven by the Essence high level modelling language, giving ease of modelling and prototyping to non-expert users. We give practical examples involving temporal graphs, typed graphs from software engineering, and costed subgraph isomorphism problems.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Checking Constraint Satisfaction

Nächstes Kapitel Short-Term Scheduling of Production Fleets in Underground Mines Using CP-Based LNS

https://github.com/ciaranm/glasgow-subgraph-solver/releases/tag/cpaior2021-finding-subgraphs-with-side-constraints.

https://github.com/minion/minion/releases/tag/1.9.

https://github.com/conjure-cp/conjure.

https://github.com/ciaranm/cpaior2021-finding-subgraphs-with-side-constraints.

https://perso.liris.cnrs.fr/christine.solnon/SIP.html.

Actually, because high level modelling can use different names for variables and values, we get slight differences due to changes to tiebreaking in search order heuristics.

https://github.com/gts-morpher/gts_morpher.

Archibald, B., Dunlop, F., Hoffmann, R., McCreesh, C., Prosser, P., Trimble, J.: Sequential and parallel solution-biased search for subgraph algorithms. In: Rousseau, L.-M., Stergiou, K. (eds.) CPAIOR 2019. LNCS, vol. 11494, pp. 20–38. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-19212-9_2CrossRefMATH

Audemard, G., Lecoutre, C., Samy-Modeliar, M., Goncalves, G., Porumbel, D.: Scoring-based neighborhood dominance for the subgraph isomorphism problem. In: O’Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 125–141. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10428-7_12CrossRef

Bansal, S., Read, J., Pourbohloul, B., Meyers, L.A.: The dynamic nature of contact networks in infectious disease epidemiology. J. Biol. Dyn. 4(5), 478–489 (2010)MathSciNetCrossRef

Bill, R., Fleck, M., Troya, J., Mayerhofer, T., Wimmer, M.: A local and global tour on MOMoT. Softw. Syst. Model. 18(2), 1017–1046 (2017). https://doi.org/10.1007/s10270-017-0644-3CrossRef

Hjort Blindell, G., Castañeda Lozano, R., Carlsson, M., Schulte, C.: Modeling universal instruction selection. In: Pesant, G. (ed.) CP 2015. LNCS, vol. 9255, pp. 609–626. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23219-5_42CrossRef

Bonnici, V., Giugno, R., Pulvirenti, A., Shasha, D.E., Ferro, A.: A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinf. 14(S–7), S13 (2013)CrossRef

Boussaïd, I., Siarry, P., Ahmed-Nacer, M.: A survey on search-based model-driven engineering. Autom. Softw. Eng. 24(2), 233–294 (2017). https://doi.org/10.1007/s10515-017-0215-4CrossRef

Bruschi, D., Martignoni, L., Monga, M.: Detecting self-mutating malware using control-flow graph matching. In: Büschkes, R., Laskov, P. (eds.) DIMVA 2006. LNCS, vol. 4064, pp. 129–143. Springer, Heidelberg (2006). https://doi.org/10.1007/11790754_8CrossRef

Burdusel, A., Zschaler, S., John, S.: Automatic generation of atomic consistency preserving search operators for search-based model engineering. In: Kessentini, M., Yue, T., Pretschner, A., Voss, S., Burgueño, L. (eds.) 22nd ACM/IEEE International Conference on Model Driven Engineering Languages and Systems, MODELS 2019, Munich, Germany, 15–20 September 2019, pp. 106–116. IEEE (2019). https://doi.org/10.1109/MODELS.2019.00-10

10.

Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell. 26(10), 1367–1372 (2004)CrossRef

11.

Dell’Olmo, P., Cerulli, R., Carrabs, F.: The maximum labeled clique problem. In: Adacher, L., Flamini, M., Leo, G., Nicosia, G., Pacifici, A., Piccialli, V. (eds.) Proceedings of the 10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. Extended Abstracts, Villa Mondragone, Frascati, Italy, 14–16 June 2011, pp. 146–149 (2011)

12.

Durán, F., Moreno-Delgado, A., Orejas, F., Zschaler, S.: Amalgamation of domain specific languages with behaviour. J. Log. Algebraic Methods Program. 86, 208–235 (2017). https://doi.org/10.1016/j.jlamp.2015.09.005MathSciNetCrossRefMATH

13.

Durán, F., Zschaler, S., Troya, J.: On the reusable specification of non-functional properties in DSLs. In: Czarnecki, K., Hedin, G. (eds.) SLE 2012. LNCS, vol. 7745, pp. 332–351. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36089-3_19CrossRef

14.

Efstathiou, D., Williams, J.R., Zschaler, S.: Crepe complete: multi-objective optimization for your models. In: Paige, R.F., Kessentini, M., Langer, P., Wimmer, M. (eds.) Proceedings of the First International Workshop on Combining Modelling with Search- and Example-Based Approaches co-located with 17th International Conference on Model Driven Engineering Languages and Systems (MODELS 2014), Valencia, Spain, 28 September 2014. CEUR Workshop Proceedings, vol. 1340, pp. 25–34. CEUR-WS.org (2014)

15.

Ehrig, H., Ehrig, K., Prange, U., Taentzer, G.: Fundamentals of Algebraic Graph Transformation. Monographs in Theoretical Computer Science. An EATCSSeries. Springer, Heidelberg (2006). https://doi.org/10.1007/3-540-31188-2CrossRefMATH

16.

Elhesha, R., Sarkar, A., Kahveci, T.: Motifs in biological networks. In: Yoon, B.-J., Qian, X. (eds.) Recent Advances in Biological Network Analysis, pp. 101–123. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-57173-3_5CrossRef

17.

Foggia, P., Percannella, G., Vento, M.: Graph matching and learning in pattern recognition in the last 10 years. IJPRAI 28(1), 1450001 (2014). https://doi.org/10.1142/S0218001414500013MathSciNetCrossRef

18.

Frisch, A.M., Harvey, W., Jefferson, C., Hernández, B.M., Miguel, I.: Essence: a constraint language for specifying combinatorial problems. Constraints Int. J. 13(3), 268–306 (2008). https://doi.org/10.1007/s10601-008-9047-yMathSciNetCrossRefMATH

19.

Gent, I.P., Jefferson, C., Miguel, I.: Minion: a fast scalable constraint solver. In: Brewka, G., Coradeschi, S., Perini, A., Traverso, P. (eds.) ECAI 2006, 17th European Conference on Artificial Intelligence, 29 August–1 September 2006, Riva del Garda, Italy, Including Prestigious Applications of Intelligent Systems (PAIS 2006), Proceedings. Frontiers in Artificial Intelligence and Applications, vol. 141, pp. 98–102. IOS Press (2006)

20.

Holme, P., Saramäki, J.: Temporal networks. Phys. Rep. 519(3), 97–125 (2012). https://doi.org/10.1016/j.physrep.2012.03.001CrossRef

21.

Kotthoff, L., McCreesh, C., Solnon, C.: Portfolios of subgraph isomorphism algorithms. In: Festa, P., Sellmann, M., Vanschoren, J. (eds.) LION 2016. LNCS, vol. 10079, pp. 107–122. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-50349-3_8CrossRef

22.

McCreesh, C., Prosser, P.: A parallel, backjumping subgraph isomorphism algorithm using supplemental graphs. In: Pesant, G. (ed.) CP 2015. LNCS, vol. 9255, pp. 295–312. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23219-5_21CrossRefMATH

23.

McCreesh, C., Prosser, P., Simpson, K., Trimble, J.: On maximum weight clique algorithms, and how they are evaluated. In: Beck, J.C. (ed.) CP 2017. LNCS, vol. 10416, pp. 206–225. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66158-2_14CrossRef

24.

McCreesh, C., Prosser, P., Trimble, J.: The glasgow subgraph solver: using constraint programming to tackle hard subgraph isomorphism problem variants. In: Gadducci, F., Kehrer, T. (eds.) ICGT 2020. LNCS, vol. 12150, pp. 316–324. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-51372-6_19CrossRef

25.

Ohrimenko, O., Stuckey, P.J., Codish, M.: Propagation = lazy clause generation. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 544–558. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74970-7_39CrossRef

26.

Pande, S., Ranu, S., Bhattacharya, A.: SkyGraph: retrieving regions of interest using skyline subgraph queries. Proc. VLDB Endow. 10(11), 1382–1393 (2017). https://doi.org/10.14778/3137628.3137647CrossRef

27.

Prosser, P.: Hybrid algorithms for the constraint satisfaction problem. Comput. Intell. 9, 268–299 (1993). https://doi.org/10.1111/j.1467-8640.1993.tb00310.xCrossRef

28.

Redmond, U., Cunningham, P.: Temporal subgraph isomorphism. In: Rokne, J.G., Faloutsos, C. (eds.) Advances in Social Networks Analysis and Mining 2013, ASONAM 2013, Niagara, ON, Canada, 25–29 August 2013, pp. 1451–1452. ACM (2013). https://doi.org/10.1145/2492517.2492586

29.

Régin, J.: Développement d’outils algorithmiques pour l’Intelligence Artificielle. Application à la chimie organique. Ph.D. thesis, Université Montpellier 2 (1995)

30.

Sekara, V., Stopczynski, A., Lehmann, S.: Fundamental structures of dynamic social networks. Proc. Natl. Acad. Sci. 113(36), 9977–9982 (2016)CrossRef

31.

Semeráth, O., Nagy, A.S., Varró, D.: A graph solver for the automated generation of consistent domain-specific models. In: Chaudron, M., Crnkovic, I., Chechik, M., Harman, M. (eds.) Proceedings of the 40th International Conference on Software Engineering, ICSE 2018, Gothenburg, Sweden, 27 May–03 June 2018, pp. 969–980. ACM (2018). https://doi.org/10.1145/3180155.3180186

32.

Silva, J.P.M., Sakallah, K.A.: GRASP - a new search algorithm for satisfiability. In: Rutenbar, R.A., Otten, R.H.J.M. (eds.) Proceedings of the 1996 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1996, San Jose, CA, USA, 10–14 November 1996, pp. 220–227. IEEE Computer Society/ACM (1996). https://doi.org/10.1109/ICCAD.1996.569607

33.

Solnon, C.: Experimental evaluation of subgraph isomorphism solvers. In: Conte, D., Ramel, J.-Y., Foggia, P. (eds.) GbRPR 2019. LNCS, vol. 11510, pp. 1–13. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-20081-7_1CrossRef

34.

Stuckey, P.J.: Lazy clause generation: combining the power of sat and CP (and MIP?) solving. In: Lodi, A., Milano, M., Toth, P. (eds.) CPAIOR 2010. LNCS, vol. 6140, pp. 5–9. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13520-0_3CrossRef

35.

Vömel, C., de Lorenzi, F., Beer, S., Fuchs, E.: The secret life of keys: on the calculation of mechanical lock systems. SIAM Rev. 59(2), 393–422 (2017). https://doi.org/10.1137/15M1030054MathSciNetCrossRefMATH

36.

Zampelli, S., Deville, Y., Solnon, C.: Solving subgraph isomorphism problems with constraint programming. Constraints 15(3), 327–353 (2010)MathSciNetCrossRef

Titel: Finding Subgraphs with Side Constraints
verfasst von: Özgür Akgün
Jessica Enright
Christopher Jefferson
Ciaran McCreesh
Patrick Prosser
Steffen Zschaler
Verlag: Springer International Publishing
Buch: Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Print ISBN: 978-3-030-78229-0

Electronic ISBN: 978-3-030-78230-6

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-78230-6_22

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner