Finding path and cycle counting formulae in graphs with Deep Reinforcement Learning
<|reference_start|>Finding path and cycle counting formulae in graphs with Deep Reinforcement Learning: This paper presents Grammar Reinforcement Learning (GRL), a reinforcement learning algorithm that uses Monte Carlo Tree Search (MCTS) and a transformer architecture that models a Pushdown Automaton (PDA) within a context-free grammar (CFG) framework. Taking as use case the problem of efficiently counting paths and cycles in graphs, a key challenge in network analysis, computer science, biology, and social sciences, GRL discovers new matrix-based formulas for path/cycle counting that improve computational efficiency by factors of two to six w.r.t state-of-the-art approaches. Our contributions include: (i) a framework for generating gramformers that operate within a CFG, (ii) the development of GRL for optimizing formulas within grammatical structures, and (iii) the discovery of novel formulas for graph substructure counting, leading to significant computational improvements.<|reference_end|>
@article{piquenot2024finding,
    title={Finding path and cycle counting formulae in graphs with Deep
  Reinforcement Learning},
    author={Jason Piquenot, Maxime B'erar, Pierre H'eroux, Jean-Yves Ramel,
  Romain Raveaux, S'ebastien Adam},
    journal={arXiv preprint arXiv:2410.01661},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.01661},
    primaryClass={cs.AI cs.FL}
}