Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

A Learning Based Branch and Bound for Maximum Common Subgraph Related Problems

Abstract : The performance of a branch-and-bound (BnB) algorithm for maximum common subgraph (MCS) problem and its related problems, like maximum common connected subgraph (MCCS) and induced Subgraph Isomorphism (SI), crucially depends on the branching heuristic. We propose a branching heuristic inspired from reinforcement learning with a goal of reaching a tree leaf as early as possible to greatly reduce the search tree size. Experimental results show that the proposed heuristic consistently and significantly improves the current best BnB algorithm for the MCS, MCCS and SI problems. An analysis is carried out to give insight on why and how reinforcement learning is useful in the new branching heuristic.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal-u-picardie.archives-ouvertes.fr/hal-03636418
Contributeur : Louise Dessaivre Connectez-vous pour contacter le contributeur
Soumis le : dimanche 10 avril 2022 - 11:39:14
Dernière modification le : lundi 11 avril 2022 - 03:31:05

Identifiants

  • HAL Id : hal-03636418, version 1

Collections

Citation

Yanli Liu, Chu-Min Li, Hua Jiang, Kun He. A Learning Based Branch and Bound for Maximum Common Subgraph Related Problems. THIRTY-FOURTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THE THIRTY-SECOND INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE AND THE TENTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, Feb 2020, New-York, United States. pp.2392-2399. ⟨hal-03636418⟩

Partager

Métriques

Consultations de la notice

35