# Finding path and cycle counting formulae in graphs with Deep Reinforcement Learning

arXiv: https://arxiv.org/abs/2410.01661 · HTML: https://mlsanity.com/paper/2410.01661/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 11 of its 27 references that are in the map.
- First posted on arXiv 2 Oct 2024.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 11 of 11)

- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Monte Carlo Tree Search: A Review of Recent Modifications and Applications](https://mlsanity.com/paper/2103.04931/) (2021)
- [Learning and Planning in Complex Action Spaces](https://mlsanity.com/paper/2104.06303/) (2021)
- [On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties](https://mlsanity.com/paper/1811.04801/) (2018)
- [Path Neural Networks: Expressive and Accurate Graph Neural Networks](https://mlsanity.com/paper/2306.05955/) (2023)
- [On the Combinatorial Power of the Weisfeiler-Lehman Algorithm](https://mlsanity.com/paper/1704.01023/) (2017)
- [Stack Attention: Improving the Ability of Transformers to Model Hierarchical Patterns](https://mlsanity.com/paper/2310.01749/) (2023)
- [On the expressive power of query languages for matrices](https://mlsanity.com/paper/1709.08359/) (2017)
- [On the expressive power of linear algebra on graphs](https://mlsanity.com/paper/1812.04379/) (2018)
- [A general purpose algorithm for counting simple cycles and simple paths of any length](https://mlsanity.com/paper/1612.05531/) (2016)
- [Pushdown Automata and Context-Free Grammars in Bisimulation Semantics](https://mlsanity.com/paper/2203.01713/) (2022)

## Abstract (arXiv)

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.