nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Sequential and Parallel Solution-Biased Search for Subgraph Algorithms

verfasst von : Blair Archibald, Fraser Dunlop, Ruth Hoffmann, Ciaran McCreesh, Patrick Prosser, James Trimble

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 current state of the art in subgraph isomorphism solving involves using degree as a value-ordering heuristic to direct backtracking search. Such a search makes a heavy commitment to the first branching choice, which is often incorrect. To mitigate this, we introduce and evaluate a new approach, which we call “solution-biased search”. By combining a slightly-random value-ordering heuristic, rapid restarts, and nogood recording, we design an algorithm which instead uses degree to direct the proportion of search effort spent in different subproblems. This increases performance by two orders of magnitude on satisfiable instances, whilst not affecting performance on unsatisfiable instances. This algorithm can also be parallelised in a very simple but effective way: across both satisfiable and unsatisfiable instances, we get a further speedup of over thirty from thirty-six cores, and over one hundred from ten distributed-memory hosts. Finally, we show that solution-biased search is also suitable for optimisation problems, by using it to improve two maximum common induced subgraph algorithms.

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 Constraint Programming for Dynamic Symbolic Execution of JavaScript

Nächstes Kapitel Core-Boosted Linear Search for Incomplete MaxSAT

https://github.com/ciaranm/glasgow-subgraph-solver/.

It may be possible to further improve the solver by also introducing randomness or some form of learning into its variable-ordering heuristic. However, simultaneously introducing a second change would considerably complicate the empirical analysis. Additionally, the solver’s current hand-crafted variable-ordering heuristics already beat adaptive heuristics like impact or activity-based search.

For solving a counting or enumeration problem, matters become slightly more complicated, but not devastatingly so.

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 Bioinform. 14(S-7), S13 (2013)

de Bruin, A., Kindervater, G.A.P., Trienekens, H.W.J.M.: Asynchronous parallel branch and bound and anomalies. In: Ferreira, A., Rolim, J. (eds.) IRREGULAR 1995. LNCS, vol. 980, pp. 363–377. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-60321-2_29CrossRef

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. 4046, pp. 129–143. Springer, Heidelberg (2006). https://doi.org/10.1007/11790754_8CrossRef

Carletti, V., Foggia, P., Saggese, A., Vento, M.: Introducing VF3: a new algorithm for subgraph isomorphism. In: Foggia, P., Liu, C.-L., Vento, M. (eds.) GbRPR 2017. LNCS, vol. 10310, pp. 128–139. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-58961-9_12CrossRef

Chu, G., Schulte, C., Stuckey, P.J.: Confidence-based work stealing in parallel constraint programming. In: Gent, I.P. (ed.) CP 2009. LNCS, vol. 5732, pp. 226–241. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04244-7_20CrossRef

Ciré, A.A., Kadioglu, S., Sellmann, M.: Parallel restarted search. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, Québec City, Québec, Canada, 27–31 July 2014, pp. 842–848 (2014)

Coffman, T., Greenblatt, S., Marcus, S.: Graph-based technologies for intelligence analysis. Commun. ACM 47(3), 45–47 (2004). https://doi.org/10.1145/971617.971643CrossRef

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

10.

Dalla Preda, M., Vidali, V.: Abstract similarity analysis. Electron. Notes Theoret. Comput. Sci. 331, 87–99 (2017). https://doi.org/10.1016/j.entcs.2017.02.006, Proceedings of the Sixth Workshop on Numerical and Symbolic Abstract Domains (NSAD 2016)

11.

Damiand, G., Solnon, C., de la Higuera, C., Janodet, J., Samuel, É.: Polynomial algorithms for subisomorphism of ND open combinatorial maps. Comput. Vis. Image Underst. 115(7), 996–1010 (2011)CrossRef

12.

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

13.

Gay, S., Hartert, R., Lecoutre, C., Schaus, P.: Conflict ordering search for scheduling problems. In: Pesant, G. (ed.) CP 2015. LNCS, vol. 9255, pp. 140–148. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-23219-5_10CrossRef

14.

Geelen, P.A.: Dual viewpoint heuristics for binary constraint satisfaction problems. In: ECAI, pp. 31–35 (1992)

15.

Gent, I.P., MacIntyre, E., Prosser, P., Walsh, T.: The constrainedness of search. In: Proceedings of the Thirteenth National Conference on Artificial Intelligence and Eighth Innovative Applications of Artificial Intelligence Conference, AAAI 1996, IAAI 1996, Portland, Oregon, USA, 4–8 August 1996, vol. 1, pp. 246–252 (1996)

16.

Glorian, G., Boussemart, F., Lagniez, J.-M., Lecoutre, C., Mazure, B.: Combining nogoods in restart-based search. In: Beck, J.C. (ed.) CP 2017. LNCS, vol. 10416, pp. 129–138. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66158-2_9CrossRef

17.

Gomes, C.P., Selman, B., Kautz, H.A.: Boosting combinatorial search through randomization. In: Proceedings of the Fifteenth National Conference on Artificial Intelligence and Tenth Innovative Applications of Artificial Intelligence Conference, AAAI 1998, IAAI 1998, Madison, Wisconsin, USA, 26–30 July 1998, pp. 431–437 (1998)

18.

Hamadi, Y., Jabbour, S., Sais, J.: Control-based clause sharing in parallel SAT solving. In: Hamadi, Y., Monfroy, E., Saubion, F. (eds.) Autonomous Search, pp. 245–267. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21434-9_10CrossRef

19.

Harvey, W.D., Ginsberg, M.L.: Limited discrepancy search. In: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI 1995, Montréal Québec, Canada, 20–25 August 1995, 2 volumes, pp. 607–615 (1995)

20.

Hoffmann, R., et al.: Observations from parallelising three maximum common (connected) subgraph algorithms. In: Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 15th International Conference, CPAIOR 2018, Delft, The Netherlands, 26–29 June 2018, Proceedings, pp. 298–315 (2018). https://doi.org/10.1007/978-3-319-93031-2_22

21.

Hoffmann, R., McCreesh, C., Reilly, C.: Between subgraph isomorphism and maximum common subgraph. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, San Francisco, California, USA, 4–9 February 2017, pp. 3907–3914 (2017)

22.

Hutter, F., Hoos, H.H., Leyton-Brown, K.: Sequential model-based optimization for general algorithm configuration. In: Coello, C.A.C. (ed.) LION 2011. LNCS, vol. 6683, pp. 507–523. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25566-3_40CrossRef

23.

Karoui, W., Huguet, M.-J., Lopez, P., Naanaa, W.: YIELDS: a yet improved limited discrepancy search for CSPs. In: Van Hentenryck, P., Wolsey, L. (eds.) CPAIOR 2007. LNCS, vol. 4510, pp. 99–111. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72397-4_8CrossRefMATH

24.

Korf, R.E.: Improved limited discrepancy search. In: Proceedings of the Thirteenth National Conference on Artificial Intelligence and Eighth Innovative Applications of Artificial Intelligence Conference, AAAI 1996, IAAI 1996, Portland, Oregon, 4–8 August 1996, vol. 1, pp. 286–291 (1996)

25.

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

26.

Kotthoff, L., Moore, N.C.A.: Distributed solving through model splitting. CoRR abs/1008.4328 (2010)

27.

Larrosa, J., Valiente, G.: Constraint satisfaction algorithms for graph pattern matching. Math. Struct. Comput. Sci. 12(4), 403–422 (2002)MathSciNetCrossRef

28.

Lecoutre, C., Sais, L., Tabary, S., Vidal, V.: Recording and minimizing nogoods from restarts. JSAT 1(3–4), 147–167 (2007)MATH

29.

Lee, J.H.M., Schulte, C., Zhu, Z.: Increasing nogoods in restart-based search. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, Phoenix, Arizona, USA, 12–17 February 2016, pp. 3426–3433 (2016)

30.

Li, G., Wah, B.W.: How to cope with anomalies in parallel approximate branch-and-bound algorithms. In: Proceedings of the National Conference on Artificial Intelligence. Austin, TX, 6–10 August 1984, pp. 212–215 (1984)

31.

Li, G., Wah, B.W.: Coping with anomalies in parallel branch-and-bound algorithms. IEEE Trans. Comput. 35(6), 568–573 (1986). https://doi.org/10.1109/TC.1986.5009434MathSciNetCrossRef

32.

Lindauer, M., Hoos, H., Hutter, F.: From sequential algorithm selection to parallel portfolio selection. In: Dhaenens, C., Jourdan, L., Marmion, M.-E. (eds.) LION 2015. LNCS, vol. 8994, pp. 1–16. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-19084-6_1CrossRef

33.

Luby, M., Sinclair, A., Zuckerman, D.: Optimal speedup of Las Vegas algorithms. Inf. Process. Lett. 47(4), 173–180 (1993)MathSciNetCrossRef

34.

Malapert, A., Régin, J., Rezgui, M.: Embarrassingly parallel search in constraint programming. J. Artif. Intell. Res. 57, 421–464 (2016). https://doi.org/10.1613/jair.5247MathSciNetCrossRefMATH

35.

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

36.

McCreesh, C., Prosser, P.: The shape of the search tree for the maximum clique problem and the implications for parallel branch and bound. TOPC 2(1), 8:1–8:27 (2015). https://doi.org/10.1145/2742359

37.

McCreesh, C., Prosser, P., Solnon, C., Trimble, J.: When subgraph isomorphism is really hard, and why this matters for graph databases. J. Artif. Intell. Res. 61, 723–759 (2018)MathSciNetCrossRef

38.

McCreesh, C., Prosser, P., Trimble, J.: A partitioning algorithm for maximum common subgraph problems. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, 19–25 August 2017, pp. 712–719 (2017)

39.

Michel, L., See, A., Van Hentenryck, P.: Parallelizing constraint programs transparently. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 514–528. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74970-7_37CrossRef

40.

Moisan, T., Gaudreault, J., Quimper, C.-G.: Parallel discrepancy-based search. In: Schulte, C. (ed.) CP 2013. LNCS, vol. 8124, pp. 30–46. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40627-0_6CrossRef

41.

Moisan, T., Quimper, C.-G., Gaudreault, J.: Parallel depth-bounded discrepancy search. In: Simonis, H. (ed.) CPAIOR 2014. LNCS, vol. 8451, pp. 377–393. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07046-9_27CrossRef

42.

Moskewicz, M.W., Madigan, C.F., Zhao, Y., Zhang, L., Malik, S.: Chaff: engineering an efficient SAT solver. In: Proceedings of the 38th Design Automation Conference, DAC 2001, Las Vegas, NV, USA, 18–22 June 2001, pp. 530–535 (2001)

43.

Murray, A.C., Franke, B.: Compiling for automatically generated instruction set extensions. In: 10th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2012, San Jose, CA, USA, 31 March–04 April 2012, pp. 13–22 (2012). https://doi.org/10.1145/2259016.2259019

44.

Pesant, G., Quimper, C., Zanarini, A.: Counting-based search: branching heuristics for constraint satisfaction problems. J. Artif. Intell. Res. 43, 173–210 (2012). https://doi.org/10.1613/jair.3463MathSciNetCrossRefMATH

45.

Razgon, M., O’Sullivan, B., Provan, G.M.: Search ordering heuristics for restarts-based constraint solving. In: Proceedings of the Twentieth International Florida Artificial Intelligence Research Society Conference, 7–9 May, 2007, Key West, Florida, USA, pp. 182–183 (2007)

46.

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

47.

Sevegnani, M., Calder, M.: Bigraphs with sharing. Theor. Comput. Sci. 577, 43–73 (2015). https://doi.org/10.1016/j.tcs.2015.02.011MathSciNetCrossRefMATH

48.

Solnon, C.: Alldifferent-based filtering for subgraph isomorphism. Artif. Intell. 174(12–13), 850–864 (2010)MathSciNetCrossRef

49.

Solnon, C., Damiand, G., de la Higuera, C., Janodet, J.: On the complexity of submap isomorphism and maximum common submap problems. Pattern Recogn. 48(2), 302–316 (2015)CrossRef

50.

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

51.

Walsh, T.: Depth-bounded discrepancy search. In: Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI 97, Nagoya, Japan, 23–29 August 1997, 2 volumes, pp. 1388–1395 (1997)

52.

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

Titel: Sequential and Parallel Solution-Biased Search for Subgraph Algorithms
verfasst von: Blair Archibald
Fraser Dunlop
Ruth Hoffmann
Ciaran McCreesh
Patrick Prosser
James Trimble
Verlag: Springer International Publishing
Buch: Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Print ISBN: 978-3-030-19211-2

Electronic ISBN: 978-3-030-19212-9

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-19212-9_2

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