Grammar Reinforcement Learning: path and cycle counting in graphs with a Context-Free Grammar and Transformer approach

Authors: Jason Piquenot, Maxime Berar, Romain Raveaux, Pierre Héroux, Jean-Yves RAMEL, Sébastien Adam
Primary area: reinforcement learning
Keywords: Graph, Reinforcement Learning, Grammar, Cycle Counting

Abstract:
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 transformers 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.

Decision: accept (poster)
Reviewer scores: 6, 5, 8, 8, 6

Reviews and discussion:
<thread>
creation date:
1730006260217

thread_type:
official_review

<thread_object>
creator: reviewer_lkha

<content>
summary:
The paper introduces a new approach to efficiently count paths and cycles in graphs. GRL uses a pushdown automaton (PDA) approach to generate and optimize mathematical formulas for path and cycle counting, addressing computational challenges in fields such as network analysis, biology, and social sciences. By framing path/cycle counting as a CFG-constrained search problem, GRL discovers new matrix-based formulas, improving computational efficiency by two to six times over current methods. Key contributions include a generic framework for generating efficient formulas within a CFG, the development of Gramformer to learn policies and values within a PDA model, and the identification of novel, efficient counting formulas for graph substructures.

strengths:
- Great literature work: This paper references existing literature, which demonstrates an awareness of previous work in the area and situates the study within the broader research context.
- Full details of the proposed method with detailed theoretical justification.

weaknesses:
- The focus of this work is on re-solving a problem that requires a polynomial-time algorithm, as indicated in Line 99: "As mentioned in Section 1, path/cycle counting has been extensively tackled in the literature." This context renders the proposed methods less impactful. I recommend that the authors provide a more compelling rationale for why this issue is considered challenging within the fields of network analysis, computer science, biology, and social sciences.

- There are no experiments conducted on datasets from network analysis, computer science, biology, or social sciences. Given that the results in Figure 7 indicate an algorithm running in 0.2 seconds, which is already considered "very fast," it is unclear what specific challenge is being addressed in this figure.

- The mathematical notation used throughout the paper tends to create confusion rather than enhance the reader's understanding of the problem.

questions:
- Could you help to answer my concern on the first point of weakness?
- Could you clarify the purpose of the cubic shapes in Figures 3, 4, and 5? Are they intended to convey a particular meaning beyond their function as symbols?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730657120276

thread_type:
official_review

<thread_object>
creator: reviewer_5jnx

<content>
summary:
This paper considers the problem of path and cycle counting in graphs. It aims to do so efficiently using formulae that perform a set of pre-defined matrix operations, specified as a context-free grammar. The authors frame this task as a combinatorial optimization problem and propose a reinforcement learning method to solve it. The method is made up of a Monte Carlo Tree Search with neural networks for function approximation. Particularly, the authors propose a transformer architecture that can process tokens from the grammar. The authors demonstrate that their method discovers more efficient formulae for path and cycle counting than those that were previously known.

strengths:
S1. The authors treat an important problem with an interesting and novel methodology, and use it to discover demonstrably better path and cycle search algorithms.

S2. The paper is fairly well-written and the technique appears sound.

weaknesses:
W1. The biggest weakness of the work is its very limited evaluation. The paper proposes a very complex methodology for operating in this discrete search space, but does not compare it with meaningful baselines. It is therefore not possible to determine whether the proposed method is indeed a better means of navigating this search space than other more standard methods, especially given the very large reported computational cost. At the very least, in my opinion, the paper should include empirical comparisons with:

- Online Monte Carlo Tree Search without any function approximation (to demonstrate the benefit of using the transformer within the search);
- The learned transformer policy at convergence;
- A classic metaheuristic such as simulated annealing;
- A simple random search that samples from the grammar and is given the same amount of rollouts as MCTS.

W2. Another weakness of the work is that the method does not generate algorithms that are provably correct. Indeed, the authors have to resort to proving the correctness of the algorithms themselves, which they do. This stems from the fact that, to evaluate a given formula, the method needs to compare the output over a limited set of graphs with generated ground truth values. It could be the case that a formula produces the correct outputs for this set of examples while missing some edge cases. This is a limitation that should be acknowledged and discussed.

W3. The literature review omits many related works on reinforcement learning for combinatorial optimization over graphs. I would suggest including at least [1], one of the first recent works to treat this type of problem with RL, and which also uses token-like sequences; [2], a work that made substantial leaps in RL for combinatorial optimization in terms of performance and scalability; as well as other recent works in this space (see [3] for a survey).

[1] Vinyals, O., Fortunato, M., & Jaitly, N. (2015). Pointer networks. Advances in neural information processing systems, 28.

[2] Khalil, E., Dai, H., Zhang, Y., Dilkina, B., & Song, L. (2017). Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30.

[3] Darvariu, V.-A., Hailes, S., & Musolesi, M. (2024). Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective. Transactions on Machine Learning Research.

questions:
C1. Given the usage of a reinforcement learning approach, the Markov Decision Process (i.e., the state/action/transitions/rewards) should be clearly specified in mathematical terms. The current textual description is ambiguous.

C2. The parameters used in your model (e.g., exploration parameter for MCTS, architectural parameters and optimizer / learning rate etc. for the transformer) should be clearly specified in an Appendix. The reproducibility is limited otherwise.

C3. There are a few clashes in notation because of trying to unite RL and CFG/DFA notations. For example, Q is used to refer to both the set of states of the automaton as well as the Q-value in RL. I'd suggest checking that each symbol is used consistently.

C4. I would suggest discussing whether and how the approach could apply to directed graphs as well (it seems undirected graphs are assumed).

C5. Could you also comment on what would be needed to generalise the approach to cycles of arbitrary length (more than 7)? Is it simply a matter of applying your method more computational power, or is the approach limited in this sense to predefined path lengths?

C6. Typos: "ouputs" (Fig 6 caption)
</content>
</thread_object>

</thread>
<thread>
creation date:
1730680834023

thread_type:
official_review

<thread_object>
creator: reviewer_zbfh

<content>
summary:
The paper presents a reinforcement learning setting for the generation of formulae that allow for efficient counting paths and cycles up to length six in directed graphs by implementing a transformer-guided Monte Carlo tree search on a generative syntax tree of a suitable context-free grammar.

While the application of efficiently counting cycles is very intuitive, and the method of transformer-guided MCTS on formal grammar is very interesting, the paper misses any discussion of related work concerning RL methods of deep neural network-guided MCTS or MCTS on formal grammar. The paper would also heavily benefit from discussing other use cases of transformer-guided MCTS on formal grammar for GRL such that the paper could have focused more on the method of GRL rather than a specific use case only. The explanations and proofs also need clarity and seem incomplete or partly wrong.

strengths:
- The paper introduced an exciting setup of transformer-guided MCTS on context-free grammar in a reinforcement learning setting for generating specific words of the corresponding context-free language.
- The chosen application of efficient counting cycles is quite versatile in real-world scenarios.

weaknesses:
- The paper does not mention any other work related to the used/introduced machine learning method of grammar/language/llm-guided MCTS (the cited work is only about the chosen application of efficiently counting paths/cycles in graphs).
- The paper could include other GRL applications to strengthen the introduced method's flexibility.
- The relevance of counting cycles could be better illustrated with a few examples next to the literature reference.
- Some explanations need coherence and clarity, especially the usage of PDAs in the paper, which could be more accurate or even omitted. (see Questions)
- At least two proofs must be completed or corrected, and a proper list of necessary conditions/definitions could improve readability in most cases. (see Questions)

questions:
Regarding Proofs:
- In the proof of theorem 3.1/A.1 it says that $(N \times \mathrm{J} \times \mathtt{diag}(w)) \cdot \mathrm{I} = \mathtt{diag}((N \cdot \mathrm{J}) \times w)$ but if $n=2$, $N = \begin{bmatrix} a & b \\\\ c & d \end{bmatrix}$, $w = \begin{bmatrix} x \\\\ y \end{bmatrix}$, we have $(\begin{bmatrix} a & b \\\\ c & d \end{bmatrix} \times \begin{bmatrix} 0 & 1 \\\\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} x & 0 \\\\ 0 & y \end{bmatrix}) \cdot \begin{bmatrix} 1 & 0 \\\\ 0 & 1 \end{bmatrix} = (\begin{bmatrix} b & a \\\\ d & c \end{bmatrix} \times \begin{bmatrix} x & 0 \\\\ 0 & y \end{bmatrix}) \cdot \begin{bmatrix} 1 & 0 \\\\ 0 & 1 \end{bmatrix} = \begin{bmatrix} bx & 0 \\\\ 0 & cy \end{bmatrix}$ and $(\begin{bmatrix} a & b \\\\ c & d \end{bmatrix} \cdot \begin{bmatrix} 0 & 1 \\\\ 1 & 0 \end{bmatrix}) \times \begin{bmatrix} x \\\\ y \end{bmatrix} = \begin{bmatrix} 0 & b \\\\ c & 0 \end{bmatrix} \times \begin{bmatrix} x \\\\ y \end{bmatrix} = \begin{bmatrix} by \\\\ cx \end{bmatrix}$, hence, $\mathtt{diag}(\begin{bmatrix} by \\\\ cx \end{bmatrix}) = \begin{bmatrix} by & 0 \\\\ 0 & cx \end{bmatrix}$. Therefore, I do not yet see how the induction can work.
- In the proof of theorem D.1, it is used that $\mathrm{J} \cdot (A\times(\mathrm{I} \cdot (A \times A))) = A\times(\mathrm{I} \cdot (A \times A))$ but if $A=\begin{bmatrix} 1 & 1 \\\\ 1 & 1 \end{bmatrix}$, we have $A \times A = 2A, \mathrm{I} \cdot A = \mathrm{I}, \mathrm{J} \cdot A = \mathrm{J}$ and hence $A\times(\mathrm{I} \cdot (A \times A)) = A \times 2\mathrm{I} = 2A  \neq 2\mathrm{J} = \mathrm{J} \cdot (A\times(\mathrm{I} \cdot (A \times A)))$.

Regarding PDA:
- The usage of nondeterministic PDA is a bit confusing as PDAs are usually language acceptors rather than language generators. Still, of course, this is technically just a relabelling of the input as output. This happens in the text without clarification.
- There is also an inconsistent use of the terms 'transition relation' vs. 'transition function'.
- The PDAs could be omitted entirely using generative syntax trees induced by context-free grammar as there is no build-up on automata theory. For Gramformers, this would mean defining a variable token for every nonterminal character, a rule token for every production, and a terminal token for every terminal character. This would make the approach much easier to follow.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730706730523

thread_type:
official_review

<thread_object>
creator: reviewer_xapc

<content>
summary:
This paper introduces a grammar-based reinforcement learning (RL) approach to synthesize novel formulae that describe path and cycle counts in graphs. Building on prior work, particularly by Voropaev and Perepechko, which provided matrix multiplication and Hadamard product-based formulae for counting expressions, this study defines a context-free grammar (CFG) capable of generating these expressions. Using a reinforcement learning and transformer-based approach, the authors search for more compact formulae with improved time complexity. They report multiple successes with this framework, though they note that training the model is time-intensive.

strengths:
- The paper addresses a problem of foundational significance, exploring the automation of mathematical creativity through machine learning. 
- The approach is well-motivated and effectively presented, with a clear architecture and a detailed explanation of generating formulae from a given grammar. 
- The framework successfully recovers several known formulae while also discovering new, more compact ones.

weaknesses:
- The importance of path and cycle counting is not sufficiently argued, particularly for an ICLR audience that may require more context on its broader relevance.
- It remains unclear whether the RL and transformer framework is essential to the solution, as it seems more like a general-purpose tool for exploring terms generated by a given CFG..
- The framework does not provide a proof of correctness for the generated formulae, requiring a time-consuming, manual derivation for each result. Automating the generation of explanations (a sequence of rewriting rules) to demonstrate correctness would significantly improve the approach's appeal.
- The method appears more general beyond its current application domain. The paper could be strengthened by exploring additional applications of the proposed framework.

questions:
1. How are the proofs of equivalence for the grammar-generated formulae derived? Is it challenging to verify correctness once a candidate formula is generated?
2. By characterizing various rewriting rules used in these proofs, could it be possible to automate the generation of more compact formulae using traditional methods, such as a rewriting system?
3. If so, has the proposed approach been compared against exhaustive explorations that utilize such rewriting rules?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730838825518

thread_type:
official_review

<thread_object>
creator: reviewer_ltab

<content>
summary:
This paper proposes a Reinforcement Learning based method to discover an algebraic formula involving (adjacency) matrix of an undirected graph and some constant matrices, for counting the number of paths and cycles of specific (short) lengths in the graph. The main experimental achievement is finding (simple) formulas for path lengths l = 2, 3, 4, 5, 6. In the case of l = 2 the discovered formula is equal to the best known formula proposed by Voropaev and Perepechko (2012), and for l = 3, 4, 5, 6 the algorithm found even more efficient alternative expressions than those introduced by Voropaev and Perepechko.

The algorithm implements a searching strategy to find an optimal formula generated by an appropriate context-free grammar (CFG), or equivalently by a Pushdown Automaton (PDA). To this aim the authors propose a Monte Carlo Tree Search (MCTS) based Deep Reinforcement Learning algorithm, termed Grammar Reinforcement Learning (GRL).

strengths:
Counting the number of paths and cycles (of specific lengths) in graphs is an important task in algorithmics and combinatorics with many applications to different fields. The authors show that using the DRL approach in combination with the Monte Carlo Tree Search method allows the discovery of more efficient matrix-based formulae for counting paths (of lengths up to six) than the best known so far. This is a nice achievement of the work.

The authors present MCTS-based DRL algorithm, termed Grammar Reinforcement Learning (GRL), that started with context-free grammar uses an equivalent Pushdown Automaton (PDA) for generating searching trees. To learn policy and value functions in the GRL a transformer architecture is proposed which models the PDA. This provides an interesting connection between the use of grammars, PDAs and reinforcement learning. Using this approach, the algorithm were able to discover formulae that are more efficient than those proposed by Voropaev and Perepechko (2012).

weaknesses:
The paper is largely based on the work of Piquenot et al. (ICLR 2024), that introduced a methodology based on CFGs that led to the construction of a new Grammatical Graph Neural Network model. It is provably 3-WL equivalent. As stated in the submitted work the generative framework of Piquenot et al. (ICLR 2024) already produces all formulae identified by Voropaev and Perepechko (2012). Hence, the innovative aspects of this submission are somewhat limited. Furthermore, it is not clear to what extent the proposed approach is generic. It would be interesting to have a discussions on such applications. It would be also interesting to compare the methods using the obtained matrix-based formulae with other methods for counting paths and cycles of lengths up to six.

questions:
Please discuss the issues mentioned above.

L. 134: in the formula brackets \{...\} are missing.

L. 186: How do you define the adjacency matrix A? Do you mean really that A_{i,j} = 1 iff i is connected with j in G?

L. 814: Lemme D.1 --> Lemma D.1
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper presents Grammar Reinforcement Learning (GRL) that combines MCTS with a transformer architecture that models a Pushdown Automaton within a context-free grammar (CFG) framework. GRL is empirically shown to discover new matrix-based formulas for path/cycle counting that improve
computational efficiency by factors of two to six. One reviewer pointed out that it appears that previous work could have already achieved the same results; the authors, however, pointed out that this is not the case and changed the wording. Another reviewer points out that GRL does not prove the generated formulae's correctness, requiring a time-consuming, manual derivation for each result. While I agree that automating the generation of explanations (a sequence of rewriting rules) to demonstrate correctness would significantly improve the approach's appeal, the first step is to show that it is useful. Moreover, there was an active discussion between one reviewer and the authors, fixing an error in the presented proof. I very much appreciate this, and the reviewer, in the end, raised the rating. So, while I fully agree that the experimental evaluation could be broadened, the discovery is interesting and will motivate others to push for AI-based algorithm discovery. Hence, I suggest going with the overall assessment of the reviews and accepting the paper.