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
Venue: ICLR 2025 Poster (2025)
Keywords: Graph
Reinforcement Learning
Grammar
Cycle Counting
Primary area: reinforcement learning

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.

Published as conference paper ICLR 2025
GRAMMAR REINFORCEMENT LEARNING: PATH AND CYCLE COUNTING IN GRAPHS WITH A CONTEXT-FREE GRAMMAR AND TRANSFORMER APPROACH
Jason Piquenot
Maxime Bérar
Pierre Héroux+
Jean- aven Ramel
Romain Raveaux
Sébastien Adam
'LITIS Lab, University of Rouen Normandy, France LIFAT Lab, University of Tours, France
ABSTRACT
This paper presents Grammar Reinforcement Learning (GRL), reinforcement learning algorithm that uses Monte Carlo Tree Search (MCTS) and a transformer architecture that models Pushdown Automaton (PDA) within a context-free grammar (CFG) framework. Taking as use case the problem of efficiently count- ing paths and cycles in graphs, key challenge in network analysis, computer science, biology, and social sciences, GRL discovers new matrix 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) frame- work for generating gramformers that operate within CFG, (ii) the development of GRL for optimizing formulas within grammatical structures, and (iii) the dis- covery of novel formulas for graph substructure counting, leading to significant computational improvements.
INTRODUCTION
Paths and cycles are fundamental structures in graph theory, playing crucial role in various fields such as network analysis (Wang et al., 2023), chemistry (Ishida et al., 2021), computer science (AbuSalim et al., 2020), biology (Bortner and Meshkat, 2022), and social sciences (Boccaletti et al., 2023). Efficiently counting paths and cycles of varying lengths essential for understanding graph connectivity and network redundancies, and is the foundation of many graph processing algorithms, including graph learning algorithms such as some recent Graph Neural Networks (GNN) (Bouritsas et al., 2022; Michel al., 2023). In particular, Bouritsas et al. (2022) demonstrated that incorporat- ing precomputed counts of paths or cycles, either at the node level or the graph level, into the feature representation significantly enhance the expressive power of GNNs.
This problem of counting paths and cycles has been extensively studied in the literature (Harary and Manvel, 1971; Alon et al., 1997; Jokić and Van Mieghem, 2022). Among existing approaches, matrix-based formulae such as those proposed in Voropaev and Perepechko (2012) (see equation (1) for example) known to be the most efficient methods for paths and cycles of lengths up six and seven, respectively (Giscard et al., 2019). This raises significant open question: Can deep learning algorithm discover more efficient formulae for counting paths?
In Fürer (2017) and Arvind et al. (2019), the length limits mentioned above are theoretically explained by examining the relationship between the subgraph counting problem and the kth- order Weisfeiler-Leman test (k-WL). These papers conclude that 3-WL cannot count cycles longer than seven. Concurrently, Geerts (2020) explored the connection between 3-WL and a fragment of the matrix language MATLANG (Brijder et al., 2019), defined by the operations L3 := {., T diag. 1, @... This paper demonstrates that this fragment, when applied to adjacency matrices, distinguishes the same graph pairs 3-WL. In order to build 3 WL GNN, Piquenot et al. (2024) introduced a 3-W WL Context-Free Grammar (CFG). We observed that, with minor modifica- tions, this generative framework is capable of producing all the formulae previously identified by

---

Published as conference paper ICLR 2025
Voropaev and Perepechko (2012). Taken together, these recent works enable to transform the search for a path/cycle counting algorithm into a CFG-tonsrriined language generation problem where the aim is to build efficient path counting formulae.
The use of context-free grammars (CFGs) for search has gained considerable attention in the litera- ture. In robotics, Zhao et al. (2020) demonstrated that CFGs can effectively describe robotic struc- tures, enabling the design and adaptation of robots for diverse tasks to be formulated as a search problem within CFG. Similarly, in the field of AutoML, the application of CFG-based search has been explored (Klinghoffer et al., 2023; Vázquez et al., 2023). In particular, Vazquez et al. (2022) proposed grammar specifically designed for an AutoML task, where searching within this grammar enables the discovery of the optimal model for a given task.
Searching for formulae within a CFG corresponds to solving combinatorial optimization problem of possibly infinite size. In recent years, Deep Reinforcement Learning (DRL) approaches have been proposed to address such problems (Vinyals al., 2015; Khalil al., 2017; Silver al., 2018; Hubert et al., 2021; Darvariu et al., 2024). A recent success of DRL has been the discovery of more efficient matrix multiplication algorithms through a Monte Carlo Tree Search (MCTS)-based approach (Fawzi et al., 2022). MCTS-based RL algorithms typically consist of two phases: an acting phase and a learning phase. During the acting phase, the agent selects actions based on a heuristic that combines MCTS exploration with deep neural network that predicts both policy and value function to guide the tree search. The network is then updated during the learning phase to reflect search trees from multiple iterations. As the objective is to discover efficient formulae and considering that MCTS aligns with CFG sentence generation process due to its tree-based structure, such a Deep MCTS approach is particularly well-suited to searching formulae within CFGs.
In this paper, we propose Grammar Reinforcement Learning (GRL), a deep MCTS model capable of discovering new efficient formulae for path/cycle counting within a CFG. This particular context raises new research question: How to approximate policy and value function through deep neural network within CFG?
To address this question, we propose the Gramformer model, a transformer architecture that models Pushdown Automata (PDA), which are equivalent to CFGs. Gramformer used learn the policy and value functions within GRL.
When applied to the path/cycle counting problem, GRL not only recovers the formulae from Voropaev and Perepechko (2012) but also discovers new ones, whose computational efficiency is improved by a factor of two to six.
The key contributions of this paper are as follows: (i) We propose GRL, generic DRL algorithm designed to explore and search within given grammar. (ii) We introduce Gramformer new trans- former training pipeline compliant with the CFG/PDA framework. (iii) We propose novel state of the art explicit formulae for path/cycle counting in graphs, leading to substantial improvements in computational efficiency.
The structure of this paper is as follows: Section 2 provides the background about path/cycle count- ing, CFGs and PDAs, defining essential concepts. Section 3 describes the design of GRL, taking as root a given CFG. Section 4 presents Gramformer, connecting transformers and CFGs. Section discusses the results of GRL path/cycle counting tasks. Finally, we conclude with summary of our contributions and suggest avenues for future research.
2 BACKGROUND
2.1 PATH AND CYCLE COUNTING
Path and cycle counting in graphs can be performed at multiple levels: graph, node, and edge. At the graph level, all possible paths or cycles given length within the graph are counted. At the node level, the focus is on counting paths starting specific node, as well as cycles that include the node. At the edge level, for any non-negative integer I, let Pt represent the I-path matrix where (Pt)., is the number of (-length paths connecting vertex i vertex j. Additionally, for / > 2, let C represent the l-cycle matrix where (C)),, indicates the number of l-cycles that include vertex and its adjacent vertex j.
2

---

Published as conference paper ICLR 2025
As mentioned in Section 1, path/cycle counting has been extensively tackled in the literature. In the early 1970s, Harary and Manvel (1971) introduced algorithms for counting cycles up to length five at the graph level. Two decades later, Alon et al. (1997) refined these algorithms, extending cycle counting to lengths of up to seven, and conjectured that these methods can also be adapted to count cycles the node level. Later Voropaev and Perepechko (2012) established a relationship between the counting of l-cycles at the edge level and the counting of (1 - 1) --pahss at the edge level using simple formula. By deriving explicit formulae for the counting of paths of length up six at the edge level, they were able to compute the number of cycles of length up to seven. More recently, Jokić and Van Mieghem (2022) rediscovered the formulae for paths of length up to four from Voropaev and Perepechko (2012). In contrast, Giscard et al. (2019) proposed an algorithm capable of counting cycles and paths of arbitrary lengths. However, they acknowledged that their method slower than those presented by Alon et al. (1997) and Voropaev and Perepechko (2012). Specifically, since the latter algorithms are based on matrix multiplication, they exhibit a computational complexity of O (ne),, where is the number of nodes. As noted by Giscard et al. (2019), these masrix-based approaches remain the most efficient known methods for counting paths and cycles of lengths up to six and seven, respectively.
2.2 CONTEXT-FREE GRAMMAR.
Throughout this paper, we employ standard formal language notation: I denotes the set of all finite-length strings over the alphabet I, and represents the empty string. The relevant definitions used in this context are as follows:
Definition 2.1 (Context-Free Grammar)
A Context-Free Grammar (CFG) G' is defined as a 4-tuple (V, R, S), where V is finite set of variables, Σ finite set of terminal symbols, R finite set of production rules of the form V - (V U V and S' is the start variable. Note that R fully characterizes the CFG, following the convention that the start variable is placed on the top left and that the symbol represents " "or".
Definition 2.2 (Derivation)
v if u can be transformed into v by applying single production rule, and - v if u can be transformed into v by applying sequence production rules from G.
Let G be a CFG. For u, 8 E (VUE)", we define u =
Definition 2.3 (Context-Free Language) set is called a Context-Free Language (CFL.) if there exists a CFG G such that B L(G)= =
{w w E Σ* and S - w).
The generation process in CFG involves iteratively replacing variables with of their corre- sponding production rules, starting from the start variable, until only terminal symbols remain.
As mentioned in Section 1, it is well known that CFGs are equivalent PDAs (Schneider, 1968; Caucal, 1995; Baeten et al., 2023; DuSell and Chiang, 2024). Usually, PDA are language acceptor, but by relabelling the input as output of the PDA. the same PDA can be used as language generator. Thus the following subsection is dedicated to defining PDA.
2.3 PUSHDOWN AUTOMATON
Definition 2.4 (PushDown Automaton)
A PushDown Automaton (PDA) is defined 7-tuple P = (2, E, go. 2, F) where Q is finite set of states, Σ is a finite set of symbols called the input alphabet, r is a finite set of symbol called the stack alphabet, d is a finite subset of Q (EU(=) x I + Q I" the transition function, Yo E Q is the start state, E is the initial stack symbol, F C Q is the set of accepting states.
In the case of PDA corresponding to CFG, the input alphabet Σ corresponds to the terminal symbol alphabet. The stack alphabet I' consits of V U E, which is the union of the set of variables (non- terminal symbols) and the terminal symbols. For such PDA, there are only two states: Zo. the initial state and, qı E F, the accepting state. The initial stack symbol is Z = S, where S is the start variable of the CFG. The transition function 5 consists of two types of transitions:
3

---

Published as conference paper ICLR 2025
Transcription transitions: If the top of the stack is terminal symbol a Σ, the transition is of the form ö(gu. a, a) = ((qu.))) This indicates that the system remains state qu- outputs the symbol a, and removes from the stack.
Transposition transitions: If the top of the stack is variable E V, the transition is of the form (go, v ((00 r), r E Ve where Ve C the subset of rules for v. This means that the system stays in state qo- produces output, and replaces with the rule on the stack.
In the same way that production rules fully defines a CFG, the transition function å completely specifies a PDA. For a PDA constructed from CFG, the transposition transitions alone are sufficient define the automaton.
A PDA generates a string by starting in the initial state 9o- with the stack initialized to Z and the generated string s initialized to E. The PDA then processes the top symbol of the stack according to the transition function 5. I E E, transcription occurs: is popped from the stack and appended to the output string 8. If E V = r' i Σ, transposition occurs: t is popped from the stack, and some {u, (4o. v) 8(go. } is pushed onto the stack. Since
I" it may consist of multiple symbols, which are pushed onto the stack in reverse order. The process continues until the stack is empty, at which point the PDA transitions the accepting state 91, and the generated string is member of the language of the corresponding CFG.
3 GENERATING PATH/CYCLE COUNTING FORMULA THROUGH GRL
The following subsection presents a specific CFG (see Section 2) designed to address the open problem of path counting.
3.1 FROM PATH MATRIX FORMULAE TO THE CFG G3
Let G E), denote an undirected graph, where V = [1. [n] represents the set of nodes, and
E C V V represents the set of edges. We define the adjacency matrix A {0, 1) 1,=xx,, that encodes the connectivity of G, the identity matrix I {0, 1j"x., and the matrix {0, 1) 1 that is filled with ones except along the diagonal.
In the work of Voropaev and Perepechko (2012), all of the proposed formulae are linear combina- tions of terms composed of matrix multiplications and Hadamard products (denoted by @) applied exclusively on the arguments A, 1, J. For example, the matrix formula in equation (1) is used to count the number of 3-paths between two nodes in the graph. The formulae for path of length four six can be found in Appendix of the supplementary material.
P3 = JG - 4 A(T + A
To generate the terms Voropaev's formulae, we define the CFG G3 in equation (2).
( (MM) |
(2)
Voropaev's 's formulae are linear combinations of sentences L(Gg).. This ensures that the problem of counting paths of length up to 6 can be addressed through finding linear combinations of sentences of L(a)..
Additionally, we prove in Appendix A that G3 is 3-WL equivalent, resulting in Theorem 3.
Theorem 3.1 (3-WL CFG) Gy is as expressive as 3-WL
While CFGs are theoretical objects, PDAs are the practical tools for processing and applying the production rules CFG to ensure the correct generation of valid sentences according to the gram- matical structure. The following subsection derives PDA (see Section 2) from G3-
4

---

Published as conference paper ICLR 2025
Transposition
Stack
Sentence
Transcription
0
MA
6.Mr - (M
M))
G(++
M M/ M
2 WT G
48
18
M.M
J M)
(
J,J+
M)
(J
0,0+6
M MMM) C
100
4 C A1
184
(M)))
(10
MM)
(J@(
M A G
AM))
(Jo(
10x
M/:0 M3 Mi
MFM
M7
MD
2 A,A++
1))
(1014
6.M - S
A))
(1
Mi+t
7BL.1
J6.4
Jela4
(AA
1)+4
Figure 1: The left diagram illustrates path in the derivation tree of the PDA D3 which generates the sentence @ A E L(Ga)- The right diagram details the process of generating this sentence, emphasizing the transcription and transposition loops. As depicted, the stack fills during transposi- tion steps and empties during transcription steps, eventually leading to the derivation of sentence from the language.
3.2 FROM G3 TO THE PDA D3
We denote as D3 the PDA described by the following transition 5:
8g0. c, M) = {go. (M @ M)), (40, (MM)), (go, A), (go: 1), J)),
which corresponds directly the production rules of G3.
Figure illustrates how the sentence (J @ (AA)) = J @ A2 E L(Gz) is generated by the PDA Da-
3.3 SEARCH IN D3 THROUGH GRAMMAR REINFORCEMENT LEARNING
To find efficient formulae for path and cycle counting, we propose a two step strategy as illustrated by Figure 2. The first step is generate set of sentences belonging process. The second step compares a linear combination of this set with ground truth matrix in order evaluate the corresponding formula. In the following of this subsection, we detail each of these steps.
G3 by the D3 generation
As stated before, the tree structure sentence generation within PDA (see Figure 2) aligns with MCTS algorithm. Such algorithms have been proposed and refined over the last decade to guide the search within trees with general heuristic (Swiechowski et al., 2023). In this work, we propose an MCTS-based DRL algorithm, termed Grammar Reinforcement Learning (GRL) adapted to the path counting open problem, generating sets of different sentences.
In GRL, MCTS performs a series of walks through the PDA, which are stored in a search tree. The nodes of the tree represent states I, which are concatenation of the written terminal symbols and the stack. The edges correspond actions defined by the CFG rules r that can applied those states.
Each walk begins at the start state To (Z...., Z), whose cardinality is the number of desired sentences, and terminates when state contains only terminal symbols. Such terminal states are sets of sentences located in leaf nodes. For each state-action pair rI, the algorithm tracks the visit count N).,r). the empirical rule value Q(I,r). and two scalars predicted by neural network:
policy probability rI,r) and value v(Irr). From a reinforcement learning perspective, N(Ir) represents the expected return over all possible trajectories that originate from state and follow action At each intermediate state, rule action is selected according the following equation:
Q(.r)
5

---

Published as conference paper ICLR 2025
Acting
inputs
Graph dataset
3-paths ground truth
Computation
Language generation
J@ A
MM
M M
(I A
Evaluation
A(I
Value
MCTS search
MCTS decision
Linear coefficients
Backward pass
Figure 2: From left to right: The agent selects set of N sentences based MCTS heuristic. These sentences are computed for a given set of graphs. The computation is then evaluated against ground truth, yielding a linear combination of the sentences and value representing their perti- nence. This value is subsequently backpropagated through the MCTS search tree.
N(I,a) argmax aQ(I,r) + (1 +(-)))+++(0)())))()))+))))))+ 1+
(3)
where the exploration factor c(I) regulates the influence of the policy III, relative the Q- values, adjusting this balance based the frequency of node traversal. The parameter E [0, 1] controls the reliance on neural network predictions. After a walk reaches leaf node, the visit counts and the values updated via backward pass.
To update the values, computed for a collection of graphs, and a linear combination of these computed sentences is derived by comparing them against a ground truth for each graph. The resulting value, which reflects the relevance of the sentences to specific path counting problem, is used to empirically update the tree that is constructed during sentence generation. The derivation of this linear combination is detailed in Appendix B, with specific focus Figure A concrete example of this approach, applied to the problem of counting 3-paths within G3, is shown in Figure 2. To encourage the generation of efficient sentences, each CFG rule penalized by a value P. in the reward definition, reflecting its computational cost. Additionally, to prevent the generation of overly long sentences, the number of characters is constrained by a maximum limit, Cmaxx
necessary to evaluate a leaf node. Its associated set of sentences is
After a sufficient number of MCTS, the sequences of nodes and edges from each walk are used to train the neural network. The ratio (IIrr) (I) provides policy derived from MCTS exploration, while QT,,)) r) represents the empirical expected return for the current state. The policy is learned using Kullback-Leibler (KI.) divergence loss, and the value function is trained using mean squared error (MSE) loss. The pseudo-code for each algorithm of GRL is provided in Appendix F. Figure depicts both the acting and the learning parts.
The neural network-serving
memory of the search trees that the agent has previously plored- fustdd-must be capable learning the policy and value distributions of the sentence generation within the CFG/PDA. As discussed in Section 1, designing within a CFG/PDA remains an open research question. In the next section, we present the neural network used for estimating the policy and value functions in the GRL algorithm.
architecture that effectively learn

---

Published as conference paper ICLR 2025
Acting
Empirical
Reploy
Updated
network
Learning
Emair iall value
Empliizal cistiibution
Figure 3: In the acting phase, rules are selected based on both the MCTS algorithm and the neural network outputs. Each time MCTS selects node, the decision, empirical policy, and value of the node are stored in replay buffer. During the learning phase, the neural network is updated by predicting the policy and value functions based on the decisions stored the replay buffer.
GRAMFORMER
Since our problem is related to the generation of sentences within language, transformer archi- tecture fits with this CFG framework. Central to this architecture the concept of tokens, which represent individual units of input data.
We propose Gramformer, a transformer architecture that follows the production rules of given CFG, through PDA. It relies on the assignment of the elements of the transition function into three distinct sets of tokens. Recall that å can be partitioned into two subsets: the transcription set & (for writing) and the transposition set 5, (for replacing). Specifically, 8, {ō(go. E, {99,, () u E R,),, E V), where each v E V represents a variable in the CFG.
For each variable E V. define variable token corresponding to For each element in 5(00,, s, E 6,, we define a rule token representing the specific production rule. This rule token divided in two subsets. If the rule contains variable, the token is classified rule token. If the rule consists only of terminal symbols (i.c., E )), the token is classified as terminal rule token. Any symbol o,, is assigned as part of the terminal token along with the terminal rule token.
non-terminal
For each variable token, corresponding mask is provided. This mask indicates the rule tokens associated with that variable. Figure 4 illustrates this framework applied to the CFG G3 that contains only one variable. An example of CFG with more variables is provided in Figure 9 of Appendix C. Once all tokens have been defined, the Gramformer is tasked with predicting two ouputs for given input state. The first output the probability of selecting the production rule for given variable. The second one is scalar that corresponds to the value of the given state.
Gramformer follows classical encoder-decoder architecture with self-attention and cross-attention mechanisms. At any time, the model's input / consists of the concatenation of the stack and the set of terminal symbols generated so far, representing state.
The input is read until variable token associated to variable symbol is encountered. This token, denoted as is passed to the encoder. The decoder receives the encoder output and the input I. The first output of the decoder is combined with the mask corresponding to that tokens not associated with v are set to co. This masking ensures that, when the softmax function is applied to the first decoder's output, it yields valid probability distribution over the rules of v.
The pseudo-code for each algorithm in this framework is provided in Appendix F. Figure depicts the Gramformer process for given input.
7

---

Published as conference paper ICLR 2025
Variable token
Rule Token
Terminal token
Transposition &
e, ((an. (M M)), (MM)),
(m.,A), A), (as. I), ())
M) (M
A
Transcription 6y
8(g A, A) [(s)=))
6(m. (() [(m)+)) +
{m. ((m.e)
d(m.) ).) (m.
dgg. J) [m),)))
d(w, 0, {().+))
00 00
Variable mask
Figure 4: From PDA grammar tokens: D3 is turned into three sets of tokens. The corresponding variables of each element of 6, are turned into variable tokens. For each variable token, a of rule tokens is defined. Eventually, for every corresponding terminal symbols of 8 terminal token is defined. In the end, for each variable token, a variable mask is defined.
Rd
Eni
Policy
seftaax
Dec
Written symbol
Stack
Value
Inout
Figure 5: The input is read until the first variable token (Rd). This token is passed to the encoder (Enc). The decoder (Dec) receives the encoder output and the input. The first output of the decoder is combined with the mask corresponding to variable token to generate policy. The second output the value.
Note that Gramformer, in an autoregressive mode operation, can generate sentences within a CFG, simulating PDA. Figure 6 and Figure 10 of the Appendix C illustrate this generation of the sentence (AA)) E L(G3) using the Gramformer architecture coupled with a replace block. The path in the derivation tree of D3 resulting in the generation this sentence is provided in Figure 1.
We now have the necessary components to use GRL on the path counting problem, which is de- scribed in the following section.
5 FINDING MORE EFFICIENT FORMULAE FOR COUNTING WITH RL.
To address the problem of path counting at the edge level, apply GRL using slightly modified version of the grammar G3. denoted G3. This grammar generates matrices of L(Ga) with null diagonal, reducing the search space. For more details on this modified grammar, please refer to Appendix C.
Ri
26
Figure 6: A sequence of tokens is fed into the transformer architecture, beginning with the start vari- able token. The transformer ouputs the rule token corresponding to the current variable token. The predicted rule's corresponding variables and terminal symbols replace the current variable token, producing a new sequence tokens. The process is repeated, until no variables remains. At this last step, sentence from the grammar is generated.
8

---

Published as conference paper ICLR 2025
Time consumption
0 0.000
0.0015
Formulae
Py20.0
P
Time consumption
0.015
0.020
Fomulae
Pj
P1/2.25
Time consumption
0.060-
0.045
Fomulae
44,00
Time consumption
0.20-
0.15
Fomulaae P6/6.55 P
0.0050
0.10-
0.0115-
0.005
0.015
0.05-
0.000
0.000-
0.000
0.00
100 150
50 100
100
150 200
Number of nodes
Number of nodes
Number nodes
Number of nodes
Figure 7: Comparison of the time consumption of Pt and Pr in function of the number of nodes for 1 E f3, 4, 5, 6). Each time, the yellow correspond to the time computation of Pt divided by the theoretical gain of time consumption.
The primary objective of this experiment was demonstrate that GRL can successfully derive the path counting formulae Pt proposed in Voropaev and Perepechko (2012). Specifically, for = 2. GRL successfully identified the formula Pp. For path lengths / E 5, GRL not only derived the Pt formulae but also discovered more efficient alternatives, denoted as P. These new formulae significantly reduce the time complexity of 1-path counting by factors 2, 2.25, 4, and 6.25, re- spectively. The formulae for P through Pj are provided below, while those for Pg and Pg can be found in Appendix D.
P JO43,
P3 J@ (A(J 9 A3) - A (AJ),
Pr = J (A(J @ (A(J ( - (A(A (AJ))) JO ((4 0 () - A ((4 A²)J) + @ A?.
For each formula, we prove in Appendix D that P. Pf. leading to the following theorem.
Theorem 5.1 (Efficient path counting)
Forl E (2, 4, 6), ())) computes the number of I-paths starting at node and ending at node j.
is visually obvious that P3 more compact than Ps. To quantify this, we compare the number of matrix multiplications required, which allows us to derive the ratio of time complexity between the formulae. The theoretical time savings between Pt and P. are detailed Appendix D.
We also assessed the empirical time savings across various random graphs. For each graph, the time required compute each formula was recorded, and the average computation time was calculated for graphs of the same size. To compare these results with the theoretical time savings, we divided the mean computation time of Pt by the corresponding theoretical time reduction factor. The results of these experiments are presented in Figure 7, demonstrating strong alignment between empirical and theoretical gains. This confirms the significant time savings provided by the new formulae discovered by GRL and supports theoretical analysis.
In Appendix D, we derive the cycle-counting formulae based on the work of Voropaev and Perepechko (2012), using the relation C1+1 A C P.. Additionally, provide detailed ex- planation how Pr counts l-path establishing new methodology for deriving formulae.
Since 3-WL cannot count the 7-paths (Fürer, 2017), theorem 3.1 leads the incapability for G3 to count it either. To go beyond the 6-paths counting, a more expressive grammar needed.
In Appendix E, evaluate GRL directed graphs and compare its performance to baseline al- gorithms. GRL stands out as the only approach capable of discovering novel matrix formulae for counting paths of lengths 4 to 5 in directed graphs.

---

Published as conference paper ICLR 2025
CONCLUSION
This paper introduces Gramformer, a deep learning architecture that learns a policy and a value function within a CFG/PDA framework, by assigning tokens elements of the transition function of PDA. Used within the GRL algorithm, it effectively addresses the question "Can deep learning algorithm discover efficient of sentences for a given task".
Instantiated over the grammar G3 to solve the path counting problem. GRL provides efficient for- mulae that are linear combinations of sets of sentences in L(Gz). These formulae of enhanced computational efficiency by factors ranging from to 6.25 demonstrate the ability of GRL to not only discover explicit formulae for counting paths, but also to provide new ways of designing such formulae.
For paths longer than 6, future research should aim characterize k- W- CFGs to bypass the theo- retical limit on path counting of G3- Such characterization will enable the application of GRL to uncover more explicit formulae for substructure counting across graph structures.
Moreover, applying GRL to real-world datasets to derive formulae for various tasks represents promising direction for future exploration as the grammar provides a link to substructures and thus interpretability.
This approach could potentially improve the applicability and effectiveness of GRL in practical scenarios, thereby broadening its impact.
10

---

Published as conference paper ICLR 2025
ACKNOLEDGEMENTS
The authors acknowledge the support of the French Agence Nationale de la Recherche (ANR) un- der grant ANR-21-CE23-000 (CoDeGNN project) and grant ANR-20-LCCI-0009 (Labeom Lisa). This work was supported by computational resources provided by CRIANN (Centre Régional In- formatique Applications Numériques Normandie).
REFERENCES
S. W. AbuSalim, R. Ibrahim, M. Z. Saringat, S. Jamel, and J. A. Wahab, Comparative analysis between dijkstra and fellman-ford algorithms in shortest path optimization. In IOP Conference Series: Materials Science and Engineering, volume 917, page 012077. IOP Publishing. 2020.
N. Alon, R. Yuster, and U. Zwick. Finding and counting given length eycles. Algorithmica, 17(3): 109-223. 1997.
V. Arvind, Fuhlbrück, Köbler, and O. Verbitsky. graph counts and related graph properties. In I.. A. Gasieniec, J. Jansson, and C. Levcopou- los, editors, Fundamentals of Computation Theory- 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14, 2019, Proceedings. volume 11651 of Lecture Notes in Computer Science, pages 111-125. Springer, 2019. doi: 10. 1011000978---000-55222-- URL https: /twp:///oiioo.oooo org. 10 1007
weisfeiler-leman invariance: Sub-
C. Baeten, C. Carissimo, and B. Luttik. Pushdown automata and context-free grammars in bisim- ulation semantics. Logical Methods in Computer Science, 19, 2023.
S. Boccaletti, P. De Lellis, C. Del Genio, K. Oifaro-Bittmer, R. Criado, S. Jalan, and M. Romance. The structure and dynamics of networks with higher order interactions. Physics Reports, 1018: 1-64, 2023.
C. Bortner and N. Meshkat. Identifiable paths and cycles in linear compartmental models. Bulletin of mathematical biology, 84(5):53, 2022.
G. Bouritsas, F. Frasca, S. Zafeiriou, and M. M. Bronstein. Improving graph neural network expres- sivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, (5(1):657-665) 2022.
R. Brijder, F. Geerts, J. V. den Bussche, and T. Weerwag. On the expressive power of query lan- guages for matrices. ACM Trans. Dutabase Syst., 44:4):15:1115:11, 2019.
D. Caucal. Bisimulation of context-free grammars and of pushdown automata. Modal Logic and process algebra, 53:85-106, 1995.
V.A. Darvariu, S. Hailes, and M. Musolesi. Graph reinforcement learning for combinatorial opti- mization: A survey and unifying perspective. arXiv preprint urXiv:2404.006492, 2024.
B. DuSell and D. Chiang. Stack attention: Improving the ability of transformers to model hierarchi- patterns. International Conference on Learning Representutions, 2024.
A. Fawzi, M. Balog, A. Huang, T. Hubert, B. Romera-Paredes, M. Barekatain, A. Novikov, F. J. R Ruiz, Schrittwieser, G. Swirszez, et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 610(7930):47-53, 2022.
M. Fürer. On the combinatorial power of the weisfeiler-Iehman algorithm. International Confer- ence on Algorithms and Complexity, pages 260-271. Springer, 2017.
Geerts. On the expressive power of linear algebra on graphs. Theory of Computing Systems, Oct 2020.
P.-L. Giscard, N. Kriege, and R. C. Wilson. A general purpose algorithm for counting simple cycles and simple paths of any length. Algorithmica, 81:2716-275 2019.
11

---

Published as conference paper ICLR 2025
F. Harary and B. Manvel. On the number of cycles in graph. Matematicky časopis, 21(():55-63, 1971.
T. Hubert, J. Schrittwieser, I. Antonoglou, M. Barekatain, S. Schmitt, and D. Silver. Learning and planning in complex action spaces. In International Conference on Machine Learning, pages 4476-4486. PMLR, 2021.
S. Ishida, T. Miyazaki, Y. Sugaya, and S. Omachi. Graph neural networks with multiple feature extraction paths for chemical property estimation. Molecules, 26(1 1):3125, 2021.
I. Jokić and P. Van Mieghem. Number of paths in a graph. arXiv preprint wxXiv2209.008400 2022.
E. Khalil, H. Dai, Y. Zhang, B. Dilkina, and L. Song. Learning combinatorial optimization algo- rithms graphs. Advances in neural information processing systems, 30, 2017.
Klinghoffer, K. Tiwary, N. Behari, B. Agrawalla, and R. Raskar. Diser: Designing imaging systems with reinforcement learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 23632-23642, 2023.
G. Michel, G. Nikolentzos, J. F. Lutzeyer, and M. Vazirgiannis. Path neural networks: Expressive and accurate graph neural networks. In International Conference Machine Learning, pages 24737-24755. PMLR, 2023.
J. Piquenot, A. Moscatelli, M. Berar, P. Héroux, R. Raveaux, J.-Y. Ramel, and S. Adam. G²n² Weisfeiler and lehman go grammatical. In The Twelfth International Conference on Learning Representations, 2024.
V. B. Schneider. On the parsing of context-free languages by pushdown automata. In Ann. meeting of the assoc. for computational linguistics, number TR-68-76, 1968.
D. Silver, T. Hubert, Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D, Ku- maran, T. Graepel, al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 16006441):11144-114, 140-1144, 2018.
M. Swiechowski, K. Godlewski, B. Sawicki, and J. Mańdziuk. Monte carlo tree search: A review of recent modifications and applications. Artificial Intelligence Review, 56(3):2497-2562, 2023.
H. C. Vazquez, J. Sánchez, and R. Carrascosa. Gramml: Exploring context-free grammars with model-free reinforcement learning. Sixth Workshop on Meta-Learning at the Conference on Neural Information Processing Systems, 2022.
H. C. Vázquez, J. Sanchez, and R. Carrascosa. Integrating hyperparameter search into model-free automl with context- grammars. In International Conference on Learning and Intelligent Optimization, pages 523-536. Springer, 2023.
O. Vinyals, M. Fortunato, and N. Jaitly. Pointer networks. Advances in neural information process- ing systems, 28, 2015.
A. Voropaev and S. Perepechko. The number of fixed length cycles in undirected graph explicit formula in case of small lengths. Discrete and Continuous Models and Applied Computational Science, 12, 2012.
J. Wang, W. Liu, L. Chen, X. Li, and Z. Wen. Analysis of china's non-ferrous metals industry's path to peak carbon: A whole life cycle industry chain based on copper. Science of The Total Enviroument, 892:16445. 2023.
A. Zhao, J. Xu, M. Konaković-Luković, Hughes, A. Spielberg, D. Rus, and W. Matusik. Robo- grammar: graph grammar for terrain-optimized robot design. ACM Transactions on Graphics (TOG), 39 2020.
12

---

Published as conference paper ICLR 2025
This document provides additional content the main paper.
A CFGS AND PDAS
This section provides the proof of theorem 3.1 of Section 2 and more details about PDA.
Even if G3 different from the 3-WL CFG proposed Piquenot et (2024), they share the same expressive power. Indeed, in the context of this paper, we are not limited by the depth of the CFG while the goal of the grammar reduction in Piquenot et al. (2024) was keep the expressiveness of the CFG at given depth.
important to note that in a separative point view, we separate graphs with scalar, a CFG G separates two graphs Gi and G2 if there exists sentence E L(G) such that s(Ag.) & s(Ag)) ). Knowing that, we have the following proposition and theorem relative to the expressive power of G3.
Proposition A.1
Assume we have sentence that is the sum of two sentences 81 and 82. If separates 91 and G2. then it is necessary that $1 or separate 91 and G2.
Proof. Assume for the sake contradiction that neither 81 nor 82 can separate 91 and Go. Then s(Ag,) = (Ag, ) + s2(,g,
$1 (Ag,) + s2(Agg) s(Agz).
That is absurd.
Theorem A.1 (3-WI.CC CFG) G3 is expressive as 3-WL
Proof.
V. + MV.
(4)
M + (M @ M) (MM) diag (V-) |A.
We will start from the CFG (4) that was proven to be 3-WL. equivalent. We show that Va variable and diag (V2) can be removed.
First of all, we have that for any matrix N and vector w, Nw (N o T)e + (N O J)w, since a sentence the CFG (4) consists on a sum other the resulting vector, we have with the help of proposition A.1 that vectors (N O 1)w and (N @ J)w have a better separability than Nw. To remove Ve variable, we first have I diag (1). Then for any matrix N and vector w, we have that (N (Ndiag (w) J) @ I diag ((N @ J)w) and (Ndiag (w)) @ I diag ((N @ I)w).
(Ndiag (w) J),,
Σ
Nigiiag (w) (w),.. Jm,s
1,
Σ NepwiJ
Σ Ne wi
IN O = ((N @ J)w),
(Ndiag (w))i.
Σ Nandiag (w),,
= =N
= "(N o Da ((N @ I)w);
The conclusion can be made by induction. We obtain G3 expressive 3- 3-WI..
13

---

Published as conference paper ICLR 2025
To give more insight in the construction of PDA from CFG, consider the PDA D3, which corre- sponds to the CFG Gg:
D3 = (fgo, 9: (,) (M, M, 91).
where the transition relation 5 is defined follows:
8(go, e, M) = [(20. (M @ M)), (1o, (MM)), (go. A), (go. T), [1o,
8(00, A, A) 5(go, I, J,J, 8(20, 6O 8(go,) ):)) 6(g0- 3 () {(go E)}
8(9o, E, c) = {(21,))}
In the same way that production rules fully defines CFG, the transition relation å completely specifies a PDA. For a PDA constructed from a CFG, the transposition transitions alone are sufficient define the automaton. For instance, D3 can be fully described by the transition:
8(4. 5, MM = {go. (M @ M)), (4o, (M))), (go. A), (go. 1), (J),
which corresponds directly the production rules of G3.
B ON THE EVALUATION OF GRL IN THE CONTEXT OF PATH COUNTING
We remind the acting phase of GRL described in section 4. In GRL, agent generates set of sentences, S, using pushdown automaton corresponding to given CFG. For a given set of graphs, the agent computes the results of each sentence s. A linear combination of these computed results is then derived and compared to the ground truth path counts, which yields reward Rg, This section aims detailed this evaluation process in the case of GRL applied G3-
In the case of G3, the set of computed sentences for given set of graphs results into set of matrices for each sentence. We have then 8 sets of g matrices, where is the number of sentences and g the number of graphs. Along with this, we have set of y matrices of ground truth. For the sake of explanation, we assume that each graphs have the same size n. Then we chose s indices (1, ... ; and graph G such that, the matrix E of size X s, where E,, sy(A),, is invertible. If such a matrix does not exist, we penalise the set of sentences by attributing a negative value. Along with the construction of F,, define the vector with the ground truth matrix of G, Tg by U, (Tg).-
The linear combination is then obtained by resolving the equation Ex = c. Then, the linear com- bination Σ, 248; (Ag) is compared to the ground truth Tg for all graphs G resulting in the value rs- This value encompasses the pertinence of the set of sentence S over a specific path counting problem. Figure 8 depicts this evaluation procedure.
The existence of Voropaev and Perepechko (2012) formulas, ensure that there exist linear combi- nation of sentences that addresses the path counting of length up
C CFG TO COUNT AT EDGE LEVEL
In investigation of substructure counting the edge level for the grammar G3, we focus the non-diagonal elements of the involved matrices. To streamline this process, we introduce an alternative context-free grammar, denoted as Gg, which is equally expressive as G3 but specifically tailored for edge-related computations. The grammar is defined follows:
E + [ Ø M) (NE) N (N & M) (N@ N) N)
| (EN) | A A|J
(5)
M + (MM) (EE)
In G3, the variable E represents matrices with zero on the diagonal, corresponding to edges in the graph, while represents diagonal matrices, corresponding to nodes, and M represents general matrices. The start variable is E aim to focus edge-level structures. The production rules for each variable describe valid operations and combinations within G3 that yield matrices corresponding to that variable.
14

---

Published as conference paper ICLR 2025
Evaluation
Graph computed sentences
Linear coefficients
4F)
Graph dataset
Invertible matrix
AG (AI)
2-2-
Ground truth vector
KJ 49)
x4 (43(
3-paths ground truth
Graph dataset
Value
The evaluation process of GRL for path counting involves deriving invertible matrix E from the computed sentences corresponding to a given graph, alongside a ground truth vector The solution of the equation Ex v provides linear combination of the computed sentence results. This linear combination is then compared to the ground truth across the entire graph dataset, yielding a value that reflects the effectiveness and relevance the of sentences solving the path counting problem.
Figure 8:
Variable tokens
Rule tokens
Terminal tokens
(I (N
(RSN)
N
(N
MXN
N)
M
(MM)
(EE)
Variable masks
-00
-C
-00
-00
N
00
00
00
00
00
-00
000
M
the top, the tokens the Graformer derived from G3 are separated into three sets. Below, the variable masks of Gramformer are defined to correspond to the rule tokens of their corresponding variable token.
Figure 9:
In the case of N, matrix multiplication is omitted because, for diagonal matrices, the matrix prod- uet behaves like the Hadamard product. This choice reduces computational complexity without sacrificing expressiveness.
D PATH AND CYCLE COUNTING
This section contains the proof of theorem 5.1 of Section 5 and provides a detailed explanation of how P/ counts l-path. the following, all graphs are assumed to be simple, ie., they contain no self-loops. This assumption aligns with the search for paths, self-loops cannot contribute any
15

---

Published as conference paper ICLR 2025
sottmox
softmoo
softmaat
sottman
Figure 10: Generation of the sentence J O A E L(G3), following PDA procedure guide by Gramformer policy.
path due to the repetition of node when traversing through self-loop. Consequently, the adjacency matrix A will always have a zero diagonal. Furthermore, this ensures that ( A.
As GRL found more efficient formulas calculate paths and eycles edge-level in graph, tried to prove that such formulas are correct, and by doing so, we found the following lemma that helps to reduce the computation cost.
Lemma D.1
Let N,M and P be square matrices of the same size, such that No, = En Mi,s. for all indices i. Then have
=
Proof. We have
(PO())) = P.s. E Mi, - Mis)
= P - Po
(6)
and
(1O E Ms
=Na,Pas Mij.
From equations (6) and (7), we can conclude.
2-paths and 3-cycles The most effective explicit formula discovered date for calculating the number of 2-paths connecting two nodes was proposed by Voropaev and Perepechko (2012), is
Pg = J 3 A
(8)
Following the formula for the l-cycle proposed in Voropaev and Perepechko (2012), obtain for the 3-cycle the following formula
C = Ac a 10 A².
Without any surprise, our architecture found the same formulas for both 2-path and 3-cycle.
3-paths and 4-cycles The most effective explicit formula discovered to date for calculating the number of 3-paths connecting two nodes proposed by Voropaev and Perepechko (2012), is
Ja= (I A(1 o A?) + A.
(10)
Following the formula for the l-cycle proposed in Voropaev and Perepechko (2012), we obtain for the 3-cycle the following formula
C = A Ao 3 A(I A?) - (I A A.
(11)
Obviously architecture found Ps. but surprisingly, it found compact formula.
16

---

Published as conference paper ICLR 2025
@@ (A(J @ A
A O (AJ)
P35
Figure 11: computation of P3 for example graph, the dashed lines indicate entry in the column corresponding to the white node in the matrix associated with the term specified above.
Theorem D.2
The following formula, denoted as P3, computes the number of 3-paths linking two nodes
P3 o (A(J o AP)) - A (AJ).
(12)
Proof. We will show that P3 P3. Firstly, we have
JO A(T ④ A2) o ((A(J + 1) @ A2) A(T @ A²)
J (A(J O A)) J (A(I6 A9) -
A(TO43)
@ (A(J A))
(13)
Secondly, we have that A7, = Σx ALA. Thus lemma D.I implies
O1 A Ao (AJ).
(14)
From equality (13) and (14), we can conclude.
An alternative understanding of how P3 computes the number of 3-paths connecting two nodes is illustrated in Figure 11. The process can be described follows:
The expression A(J @ A calculates, from a given node, a non-closed 2-path followed by a 1-path. This computation inherently includes non-closed 3-paths as well as 3-cyeles. The 3-cycles are sub- sequently removed by the Hadamard multiplication with J, which zeroes out the diagonal elements. However, this operation also allows the possibility of traversing 2-path and then returning to the intermediate node. To account for this and eliminate such paths, we subtract the term A O (AJ).
Thanks to formula (12), we can derive the 4-cycle formula.
Corollary D.2.1
The following formula, denoted as Cif computes the number of 4-cycles linking two nodes
==f= = A@ (A(J@ - A 3 (AJ).
(15)
In terms of time complexity, P is more efficient than P3. The ratio of time complexity of P3 over Ps is 1. It is directly derived from the number of matrix multiplications in both formulas. Figure shows the gain of complexity of PsS and the ratio between the two formulas.
Surprisingly, even for 3, GRL allows to improve the computation of path and cycle at edge-level in terms of time complexity.
4-paths and 5-cycles The most effective explicit formula discovered to date for calculating the number 4-paths connecting two nodes was proposed by Voropaev and Perepechko (2012), is
Pa = Jo A - Jo (A(T 43)4) + 2(J 1?)
(16)
(1 A²) (J 43)
O A²) (Io 4 34 A?.
17

---

Published as conference paper ICLR 2025
Following the formula for the l-cycle proposed in Voropaev and Perepechko (2012), we obtain for the 5-cycle the following formula
C = = A A@ (A(I 4) @ ( A?) - (A@ OT A?)
(17)
A A (I A + 5 A
Again, GRL found an improved formula for = 4. Theorem D.3
The following formula, denoted as PI, computes the number of 4-paths linking two nodes
Pi J ④ (A(J (A(J @ A3)))) - Jo (A(A (AJ))) J @ ((A (A A ((A ())) + @ A
(18)
Proof. We will show that PJ = P4. Firstly, we have
J A o ((A((J + A)))
Jo (A(J @ A²) + J@ (A(T A9)) A*)
=A(1oA")
=J (A(J @ (A(() 1) @ A?)))) + A(T 9 A3)
=J (A(J @ (A(J @ A)))) J (A(J O (A(L AR)))) +A(10
(1
J (A(J @ (A(J & ^))))) () A3) A(T 13).
(19)
Secondly, we have from equality (14)
J O ((A @ (AJ)) = JO (110 - A)A)
= JJ ((T@ A²) JJ A
(J04))
A O A?) J@
(20)
Thirdly, we have from equality (14)
JØ (A(A@) @ (AJ))) = J @ (A(1 C A - A))
=J (A(T の 1²)A) J o A².
(21)
And eventually, we have AC, (A ,, Thus lemma D.1 implies
(T A A A @ A A@ ((A AR)J).
(22)
From equality (19). (2)) and (22),
conclude.
An alternative understanding of how Pi computes the number of 4-paths connecting two nodes is illustrated in Figure 12. The process can be described follows:
The expression A(J @ (A(J @ A3))) A(A @ (AJ)) AP3 calculates, from given node, non-closed 3-path followed by a 1-path. This computation inherently includes non-closed 4-paths as well as 4-cycles. The 4-cycles are subsequently removed by the Hadamard multiplication with J, which zeroes out the diagonal elements. However, this operation also allows the possibility of traversing a 3-path and then returning to intermediate node. To account for this and eliminate respectively paths returning to the third and second nodes the 3-paths, we subtract the terms J o ((A @ (A A A A² and A O ((A + A²)J) A A².
Thanks to formula (18), we can derive the 3-cycle formula.
Corollary D.3.1
The following formula, denoted as Csf computes the number of 5-cycles linking two nodes
Czf A@ (A(J o A (A(A @ (AJ))) A ((A (AJ)) A @ ((A o A²)J) + 24 @ 2
(23)
18

---

Published as conference paper ICLR 2025
o (APb))
Jo (14 (4)).4)
10(4049))
24 A
Paf
Figure 12: computation of Pi for two graphs, the dashed lines indicate an entry in the column corresponding to the white node in the matrix associated with the term specified above.
In terms of time complexity, Pi is more efficient than Pt. The ratio time complexity of P1 over P4 is $- It is directly derived from the number of matrix multiplications in both formulas. Figure shows the gain of complexity of P and the ratio between the two formulas.
GRL improves the computation of path and cycle at edge-level for I = 5.
5-paths and 6-cycles The most effective explicit formula discovered date for calculating the number of 5-paths connecting two nodes was proposed by Voropaev and Perepechko (2012), is
P3 = Jo A - 4 (T - (J -1 (T) A3)
(24)
-TO (T (T
+3) A
+2A(10 http:://........oo......aaaaaaa-
A?)
-JO (A(T&) @
(A4 (A(A A²))
+ +L (A(1 + (A( 4 49) A²)
44 A +3 1 44.
Following the formula for the l-cycle proposed in Voropaev and Perepechko (2012), we obtain for the 6-cycle the following formula
C. = Ao - -IN
(25)
(TO (4 A - -A
- (4)
+ O (3)
4910 of A (IGAA))A( A?)
-AO (A(I O A²)49) [4 (9))
(A(A A²))
+ (I (A(T O A*)A)A+ A)4) (lTo (A(Io (94)) 6(T 6 A?)
- 44 O A +4A
Again, GRL found an improved formula for = 5.
Theorem D.4
The following formula, denoted as P computes the number of 5-paths linking two nodes
PS = J (API) (J o ((A 6 A2)J) - A (Ca, (AJ) 3 P3
(26)
P +2 A +33 ((A 42)4) 4.4 @ A².
19

---

Published as conference paper ICLR 2025
Proof. We will show that P5 = Ps. First, we have
JO J ((A(() +1 1 (
=J (A(J の )²) + Jo (A(T@ A+))
=1(1AA))
= = (A((3 +) @ )))) + A(T A+)
= Jo (A(J O (A(J @ (")))) J (A(J (A(T A'))) +A(T 14)
= J (A(J (A(J 6 (A((++T) 00))))1))++
+ (J A 19) A(T 11)
J (A() @ (A(J O (A(J ( (())) +J (AJO (A(L ( ())))) (27)
+Jo (T 0 A AATO
And
J (A() @ (A(J o O A))))))) = JO (A(J 9 (
- (PIIOAA) - (T A3)
-(J04)](049)
=((Oo49((o44))
(TO A7) - A A²) A²).
(28)
Thus equation (27) and (28) give
J J A = J O (A(J O (A(J @ (A(J @ A))))))) (Jo 4') +
4)) 49 A*) (29)
+ A A+) A AT) @ A²).
Second, have from equality (20) J (A(J @ ((A @ (AJ)) = Jo (A((T& @ (J JO A3))
@ (A(1 O A3)A²) - @ A A-))
O (A(J C A?))
=I(16A)((BA9)))
=JOA- A(1GAA)))
J (A(1 O A9)A) - A AP) - J A
(30)
+ A(T 0 A2).
Third, we have from equality (21)
J O (A(J o (A(A @ (AJ)))))
J (A(J @ (A(1 OA(10A7))) - J J A?))
JJ @ A9)4) JO JO O (A(T O A3)A) J (
O A²))
=A(o(A((o449A)
1J0A5-A(lon)
JJ & A9)4) A (A(T A3) JO
(31)
+A(1 AP).
Fourth, we have from equality (22)
JO (A(A @ (2)J)) = J (A((T (4) - AO A²))
= = JA(I A)) - o (A(A O A?)).
(32)
Fifth, we have A3, = (A A Thus lemma D.1 implies
(I (J @ 1²) 6 22 0 A2 (J @ A²) O ((A@ A²)J).
(33)
Sixth, we have (AP)),, = (Ctr),.. Thus lemma D.I implies
@ (AP))) Ctf- = A @ (Ca
(34)
Eventually, we have (A3),, Σ₁ A Thus lemma D. implies
@I P A P3 PS о (AJ).
(35)
By removing equality (29), (30), (31), (32), (33), (35) and 2J (A(A@AA)) to Ps. we obtain exactly P3 Caf 2A 42 の A2 + o ((A 42) 4A の A It concludes the proof. n
20

---

Published as conference paper ICLR 2025
An alternative understanding of how Pğ computes the number of 5-paths connecting two nodes is illustrated in Figure 13. The process can be described as follows:
The expression API calculates, from given node, non-closed 4-path followed by 1-path. This computation inherently includes non-closed 5-paths as well as 5-cycles. The 5-cycles are subsequently removed by the Hadamard multiplication with J, which zeroes out the diagonal el- ements. However, this operation also allows the possibility of traversing a 4-path and then re- turning to an intermediate node. To account for this and eliminate respectively paths returning to the fourth, third and second nodes of the 4-paths, we subtract the terms A @ ((Caf)J) - Caf. (J O A?) @ ((A O A])J) + 4A @ A² 2A @ A @ A - 3J @ ((A@ A)) and (AJ) @ P3 - P3- Thanks to formula (26), we can derive the 6-cycle formula.
Corollary D.4.1
The following forriinngooruuuu formula, denoted as Cas computes the number of 6-cycles linking two nodes
Cg = Ao (APP) (A o A7) O ((A A²)J) - A - o Cas
(36)
+ +c 2A @ A O 2 + 34 ((A O A²) - A
In terms of time complexity, P5 is more efficient than Ps. The ratio time complexity of P3 over Ps is 1. It is directly derived from the number of matrix multiplications in both formulas. The significant decrease in time complexity can be attributed to the presence of both PJ, Caf and P3 in the computational formula. The contributions of these terms to the time complexity meaning that each occurrence of P7, Caf and P3 adds to the total computational gain. As a result, their individual time complexities are aggregated, leading to the observed diminution in the overall time complexity of the formula. Figure 7 shows the gain of complexity of Pg and the ratio between the two formulas.
cumulative,
GRL improves the computation of path and cycle at edge-level for I = 5 by a factor 4.
6-paths and 7-cycles The most effective explicit formula discovered to date for calculating the number of 6-paths connecting two nodes was proposed by Voropaev and Perepechko (2012), is
PB Jo 4 A - (T) A3)
(37)
4+)4) 44)
-00 [1) A9)A)
(
( (0 43)(To (T 13)A
+3J 44000040060000000000000000000010
A²)4))
+JO +JO((10  |CC00
+16 (IO(A(IO |,,,0,14440000000000000000000000
+3J |0000///888010000004444000000000 A3)
- 4J 0 A (4
+3J (A(A6 +)) (A(1 (
4J ((A ((A0A))))
+ - -44 - 5(T@ - 49)4 (A(A A?))
- ((A0 AA)AA 6
77J (3)AA
- @ (A(T@ +)) A A2.
21

---

Published as conference paper ICLR 2025
J@ (APag) - (J ( A ((Ci)))
(AJ) @ Par
Caf
4A@ A
2 A +3J6 A
Po
8
Figure 13: computation of Pg for four graphs, the dashed lines indicate entry in the column corresponding to the white node in the matrix associated with the term specified above.
22

---

Published as conference paper ICLR 2025
Following the formula for the l-cycle proposed in Voropaev and Perepechko (2012), obtain for the 7-cycle the following formula
C A 4 (T -1
(38)
(16
-AQ 11tp::/000000.000.00000001001110
-AO -.014000000000000000000000000100 4 A2)
+ 4 ( (A0GG)
+3A0 41400///00000000000/////04000440 A3)AR)
+ + AAA.C41111HHHH......HH4HAAAA666.
+340 |1A00///10000H444000000000000110 (') (A(I A?)A))
+ ((T
+2 47)4)
HAt.::/AAAA44AAA00000/A//0/0/A/0 (A
+3A ((A (1)
49) (T) 19)
+34 O (A(A (MA))) (M
((A (()A)
+400 A - --A-0:0AA-00000AAAA4444444441410
-4(TO ((A
(4 7 (T)(
-104 @ (A(1 56
Again, GRL found an improved formula for = 6.
Theorem D.5
The following formula, denoted Pg computes the number of 6-paths linking nodes
- (C
(39)
PPT + Csf (J 440 3 (²) A?))
+JO C o - 6 - SA (A(A A?))
-84 ((4@ 19)A) ((A - 34 19)J 174 2 42
23

---

Published as conference paper ICLR 2025
Proof. We will show that Pg = Pg. First, we have
J JO A Jo ((A(() + O A)))
=Jo (A(J A¹)) J (A(T @ A*)
=A(1AA")
= =Jo (A(J @ (A((J +T) A+)))) A(T A²)
= [A(3 (A(J ( J (A(J (A(L A +A(1@ A9)
=J (A(J @ (A(J (A((J+T)) ())))))) + (Jo (T A²) A(T @ A-)
J (A(J @ (A(JO (A(J ) +J (A (A(J O (A(1 & A")))))
+J (1 A
A(1
= =J (A(J @ (A(J (A(J +1) O A2)))))I)) (T A3)
- (1 (J) (1) + A(10
= J (A(J O (A(J (A(J (4(J
+J (1) A - A 4 20)
= J (A(J O (A(J @ (A(J ( (Io
(40)
2 OI -Jo A ((e
+ oJ A ( A4 + A A²).
Second, we have from equality (30)
J@ (A(J Φ (A(J O ((A O (AJ)) (A) (A(T A2)49 - A(T (T)TT 13)
-J A + A(1 @ A?))
Jo (A(J O (A(T O 1))41))
-JJ (T) O (
=
JØ (A(J O 13) +JJ TTT
=JOA"_A(OAA) J@ (T -(TO) 19)43) (41) -J (1 -J 4 A(1
+ +J 13 A9).
Third, we have from equalities (31)
o (A(J @ (A(J o (A(A o (AJ)))) = Jo (A AP) - A(I A3)A))
-JO + A(T AR))
(A (A A))A)) -(J@ ( A?)A))
-JO +
A²)
( 42) (1))))
(42)
(JO (1 (A(1 43)4)) + A(I A
(J (T A²).
24

---

Published as conference paper ICLR 2025
Fourth, have from equality (32)
J (A(J @ (A(A ((A - Jo (A 0 (4(1 @ A)4A - Jo (A(A) A)))))
= J@ O (A(1 O A))
J@ (A(J O (A(A @ AR)))
-
= J - (A(1 A4)A))
(43)
-JO AR) + A( (A(4 @ A3)))
Fifth, we have from equality (33)
Jo (A((J A2) o ((A (3)J))) J (A((T) (J 4 A A A²))
J AJ) @ A") -J A(A A O
@ @ A4)49) A A A-)
(44)
-J A(A A & ( A3).
Sixth, we have from equality (34)
o (A(A @ (C) = @@ (A((1 O -
@J (A(I (A(J @ A A (10 A+ A))AA)
-J@ (A(A @ A A(T - A A))
J (A(10 A4)A) ( ( A7)A)
(45)
-JO (A(T (A(T (A(T) 2J (A(T@ (3)A)
JJ (A(A + 49 49) -
(JO A9).
Seventh, we have from equality (35)
J (A(P3 @ (AJ)))
= Jo (A((1 @ -3)P3-C.))
Jo (A((T @ A3 9 A - A A)))
- @ A -
J J (4(T 4-) - -0) (T(T0A))
(46)
JJ (A(1@ A9) (AA( 4
+ (A(T
A (Jo (3) A2) (J AP).
Eighth, we have
J (AP3) = J (APs)
= J (A(J @ A - A( (16 -10 (10
J A - A A&) - (Jo (T 4²) - Jo 49) 4²). (47)
Ninth, we have
J (ACa))
= J (ACA)
= - (A(A @ A - A(T AP) (T A A)))
J@ (A(A @ A3) - (Jo 41) A9) - Jo +J
(48)
Tenth, we have
[ @ ((A O J A7)4) A ((A A7)A)).
(49)
Eleventh, we have
O (A(J C (A(A , A3)))) = J (A A - A(L 6 (A(A O A²))).
(50)
From equalities (40) to (50) combined with @ (A(A @ A @ A?)) and J@ (A(A c A?)) we obtain
the equivalence between @ (APg) and all those matrices.
25

---

Published as conference paper ICLR 2025
Twelfth, we have A Ex(A k
n. Thus lemma D.1 implies
P3 o ((A o AD)J) (1 19) A 04
= -Io O - (IO A') A (IO (I (IO
- -4 C A0 A +A の (A @ A¹) + O A)4 -A AA
=14049)(149))
(A109))4949)
-IO -
(I A @ A²) - (Io
(51)
+ +IG A')A Ao A 0 A (A (I 4 + (1
A
Thirteenth, we have (APT), = Ex Thus lemma D.I implies
@ (Cs,J) (I (APt))A - Cc
@I (A(J @ A))))A (A( (A(1
(A(J O A))))
=(DAAA
=(184)4
OI (A(TO (J A))) - -10 (A(J O
=(D(A((54))4P))
=(144))(0494
(IO (A(T@
( 3(10 (A(A @ -
+ AO ( (1) (A (1 A²)
+ A(1@ A + (IO - 5404
(52)
2 (1) A (16 (A(1 +)) (A(AQ AR)))
+ AQ (A(I 4²)4)+ (1) AA) +Ao (I 1?) + 2(1 A
+ A(T A + (1@ --)--АC0
Fourteenth, we have (4²);, Σx A Thus lemma D.I implies
P @ (AJ) = (1 CC;
=T (T). (1))- - ((T (T 4)4) 2 (3) A²)
(53)
-O1 (
(1 + A
-TO (T ( (3) -
A A 44)4)
+
A²) + A ((1 +1 5A0 A
Fifteenth, have (AP)).: Ex Thus lemma D.I implies
(Jo A2) (C @I (J 0 A3) (3)4 OC
= O (A(J o (J O - (A(LO A3)A))(J A3)
(JOA))
(1 (A A3) A +( A3) A?) - A 0 Ao 3
+ OJO A (11 AP)A + (J@ A²) o (A(1 A?) - OA
=(1A9)(164))
=(104")(1643)
= OI (J O A7) - @I (A(I A+) 42)
(54)
@I (I AJ) O A²) + (I A²) - o
+I A (A @ A²) (A 6 (I A ACA.
And eventually, from the previous equality, we have
o A ② P5
Ao 42 4 3
(Io (Ao A3) (A 1 AT A A
(55)
26

---

Published as conference paper ICLR 2025
path
10a3
10a2
10"4
Figure 14: Time computation of GRL formulae and preconsumption of GSN (log scale) on IMDB-
MULTI dataset for path of length 3 and 6.
and
- A) - - (A(10A9))) (1O () + A
(56)
By removing the correct combination of @ (AP,) and equations (51) to (56) to Po. we obtain
exactly Pi C5f + 3J o ((A O (J A²)) +J A² o A o A +3J ((A@ o A
4J o A A 8A (A(A @ A?)) 8A O ((A & A)) 4J ((A O A²) 3A 0 ((A((A)) J))J) + 17A @ A 33J @ A?. concludes the proof.
An alternative understanding of how Pg computes the number of 5-paths connecting two nodes can be described as follows:
The expression AP calculates, from given node, non-closed 5-path followed by 1-path, This computation inherently includes non-closed 6-paths as well as 6-cycles. The 6-cycles are subse- quently removed by the Hadamard multiplication with J, which zeroes out the diagonal elements. However, this operation also allows the possibility of traversing a 5-path and then returning to an intermediate node. To account for this and eliminate respectively paths returning to the fifth, fourth, third and second nodes of the 4-paths, we subtract the other terms in Pa
Thanks to formula (26), we can derive the 7-cycle formula.
Corollary D.5.1
The following formula, denoted as C7f computes the number of 7cyycees linking two nodes
Ces = A (APg) - Caf @ ((A @ AR)J) - o (CryJ) - Caf @ (AJ) 205
(57)
- OA A²) o (C1 + + o + 34 ((A (J @ A A
A AG
A2 A²
+ @ ((A O A @ AP)A) 4A A @ A 8 (A(A O A?) 124 o ((A A A2)A)
3. @ ((A A²)J) 2 A²
In terms of time complexity, Pg is more efficient than Pg. The ratio of time complexity of Pg over Ps is 25 It directly derived from the number of matrix multiplications in both formulas. Figure shows the gain of complexity of Pg and the ratio between the two formulas.
GRL improves the computation of path and cycle at edge-level for by a factor 6.25.
We evaluated the computational time of PT and Pr and the precomputation times of GSN on the IMDB-MULTI dataset, with the results shown Figure 14. This analysis underscores the efficiency gains provided by the formulae.
E GRL APPLIED ON DIRECTED GRAPHS
In this section, we extend the application of GRL to derive matrix formulae for counting paths and cycles in directed graphs.
27

---

Published as conference paper ICLR 2025
To adapt the grammar reduction approach proposed in Piquenot et al. (2024) for directed graphs, minor modifications are necessary. Specifically, the transpose operation becomes critical due to the asymmetry of the adjacency matrix in directed graphs. Despite this adjustment, the proof used to eliminate the Ve variable remains valid. Consequently, the grammar Ga provided to GRL for this task is defined as follows.
(EO M) (NE) (EN) ET JAJ
(58)
N O M) (N @ N M (MM) (EE) M
In addition GRL, we explored search within the CFG using two alternative methods: MCTS without GrarFormer, referred to as MC, and a completely random rule selection process, referred as Rand. For both MC and Rand, we maintained the same rollout budget and maximum sentence length as those used for GRL. In the following, we denote the path matrix for directed graphs as P.
For / 2, since the task can be resolved by single short formula, GRL, MC, and Rand all success- fully identified Pz.
P = 3
For = 3, when GRL was initially applied to directed graphs, we aimed to identify a combination of four sentences construct the formula. However, GRL determined that, similar to the case of undirected graphs, only two sentences were required. This resulted in the following simplified formula.
= O A?)) A ((A A
Both MC and Rand failed to converge when tasked with finding combination of four sentences. However, after GRL revealed that only two sentences were necessary, we re-evaluated MC and Rand under this condition. In this case, both methods successfully converged and identified Pa.
For 1 = 4, only GRL successfully discovered a solution.
pf = J (A(J (A(J A3)))) - Ja (A( ((A AT)))
J ((A ((A o AT)J))A) - Ao ((A (2) o..
For 1 = 5, only GRL successfully discovered a solution.
J e (4 (A3()))))
-JJ @ (40
-(460 AAA o ((A AT)J)
AT (A( A3))
( (2) (A (43))4)
J@ ((40 (J (2) + (A (TJ))
+ (((A ) ((A o JJJJ)JJ) + 2 (A(A AT の 13)
To the best of our knowledge, the matrix formulae derived for counting paths of lengths 2 to 5 are novel. This highlights the capability of GRL to generate new and meaningful formulae. Further- more, when assuming that the adjacency matrix AA is symmetric. the formulae discovered by GRL for directed graphs align perfectly with those identified for undirected graphs. This alignment leads us conjecture that GRL has identified optimal formulae, least in the undirected case.
28

---

Published as conference paper ICLR 2025
F ALGORITHMS
This section provides the pseudo code of algorithm of section 2 through 4.
Algorithm 1: PDA sentence generation for a given grammar G.
Input:
The PDA EQ,E,T, r, 6, go, Z, F) derived from a given CFG G.
Output:
L A sentence w E L(G) where each element of w is in E.
Initialisation:
S + [2] # Initialisation the stack
[]# Initialisation of the written sentence
while S [1]do
C SS)
if Σ then
Append to w # Write the terminal symbol
else
Choose E 8(20, e) c) # Choose a transposition for the variable
push(S, t) # Concatenate the rule to the stack
Return:
Definition of the algorithm read, that return the first variable token in input and its position if / contains variable token
Algorithm 2:
Input:
The set of token : = (T., Tr, T:} derived from given CFG G
The Input J, concatenation of Σ) the written terminal symbols with the stack S T*
Output:
b boolean that indicate whether contains elements of the variables token set T,
v E T, a variable token, None if is False
pos the position of in I, None if is False
Initialisation:
L b- False <- None pos None
for c, E enumerate( do
if c E T, then
b True
v - c pos t Break
Return: 6, u. pos
G GRL PARAMETER FOR THE PATH COUNTING PROBLEM
To ensure reproducibility of our results, provide detailed specifications of the hyperparameters used our experiments:
MCTS PARAMETERS
Exploration Parameter (c): The exploration-exxlloittioo trade-off parameter in the UCT formula is set 10.
Rollouts per Node: Each node evaluated using 10000 rollouts, with a maximum trajec- tory length of 20 steps.
29

---

Published as conference paper ICLR 2025
Algorithm 3: Prediction algorithm of the gramformer model M (encoder, decoder).
Input:
variable token E Te of the set of token T' := {T.. Tr, Ti} derived from given CFG
A variable mask M, corresponding to the variable token
The Input I, concatenation of Σ" the written terminal symbols with the stack $ E T
Output:
policy the learned distribution of possible rules selection form the variable corresponding
to v
optional:value the learned empirical value memory t- encoder(u)
latent (lecoder(memory I)
value + M LPPPltennt 1) # Optional
pol + M (lattntt nbtoken)
policy + softmax + M,) # probability distribution of the possible transposition of token
variable e
Return: (value # Optional)
Algorithm 4: Replace the variable of position pos by the list of variable and/or terminal tokens corresponding to the rule token at indices decision
Input:
The Input L, concatenation of " the written terminal symbols with the stack S 1 The position of the variable token to replace pos
The indice decision of the selected rule token
Output:
A new I where, the variable position been replaced by the list of variable and/or terminal tokens corresponding to the rule token at indices decision
sb f- pos]
8f + pos + +1
si cokens(decision)
Return: concatenate(sbb si, sf)
Algorithm 5: Gramformer sentence generation for given grammar G.
Input:
The transformer model M, the token (To, T,, Tr) and the dictionary of variable mask M. derived from a given CFG G.
Output:
L A sentence E L(G) where each element of w is in E.
Initialisation:
I +- [2] # Initialisation of the input
v. pos read(l) # read the input
while b do
policy Mo(u), I) Distribution proposed by the transformer model decision + argmaz(policy)
T replace(1 pos, decision)
b, b,u.pos t- read(T)
Return: 7
30

---

Published as conference paper ICLR 2025
Algorithm 6: GRL algorithm one agent acting phase
Input:
A MCTS defined to search within CFG G' nbwords, the number of sentences to generate
A fixed Gramformer M
buf fer
Output:
buf fer that contains empirical policy and value of the tree explored during MCTS for the selected nodes of this MCTS.
fer
Initialisation:
T [Z] nbwords # Initialisation of the input b, pos t read(1) # read the input tree initt (nitooSS((uuosds fer (T]
while b do
root t- tree(T)
decision, tree <- MCT M)
+ replace(I, pos, decision)
p,s, read(I)
Append to bufser
Return: fill(buf fer, tree)
Algorithm 7: MCTS algorithm
Input:
L The gramformer model M, and root, node of the tree.
Output:
L A child of the root node guided by the MCTS heuristic.
for i=1 to N (Number of simulations) do
leaf + selection(rod M)
child < Eexpansiion(aaa
reward < simulation (child))
Baekpropagation (child, reward)
Return: Bestchidd(rool, M)
Algorithm 8: MCTS selection step
Input:
L The gramformer model M and node of the tree
Output:
L A descendant node of the input node guided by the MCTS heuristic.
while node is fully expanded and not leaf do
L mode +- Bestchild(roote M)
Return: node
Algorithm 9: MCTS expansion step
Input:
L a node of the tree
Output:
A descendant node of the input node or the input node. node is not leaf and not fully expanded then node +- RandomU Sonndommnoisitteehhhlll (node)
Return: node
31

---

Published as conference paper ICLR 2025
Algorithm 10: MCTS simulation step
Input:
L a node the tree
Output:
L reward.
while node is not leaf do
node t- Random.Action(node))
Return: Fvaluate(node)
Algorithm 11: MCTS backpropagation step
Input:
L node of the tree, reward.
while node is not root do
Add to the visit count of node
Add reward to the reward count of the node
node + parent of node
Algorithm 12: MCTS bestchild algorithm
Input:
L The gramformer model M and node of the tree
Output:
L The bestchhld of node.
policy. - f-
Mnode)
N +- visits count of node
res {
for child of node do
rewardd (child)
N t- visits count of child
(child)
Q + value of child visits count of child
VE. I4N
res[child] aQ (1 a)v + policy(child) Return: argmar(res)
Algorithm 13: GRL. learning phase algorithm
Input:
The gramformer model M and buf containing policy and value for given nodes of former trees.
Output:
L The updated gramformer Al optimiser + ADAM Ir)
for i=1 to (number of epoch) do for node in buf s'r do
policy, reaaard <- (nnoe))
policyLoss +- K KLLoss(policy policyyyyyyooycyyyyyoooooo of node)
valse + Hubert value node)
Loss policyLoss + Loss backward(Loss step of optimser
Return: M
32

---

Published as conference paper ICLR 2025
TRANSFORMER ARCHITECTURE (GRAMFORMER)
Number of Layers: 4 transformer layers.
Hidden Dimension: 256.
Number of Attention Heads: 8.
Feedforward Dimension: 512.
Positional Encoding: Learned positional embeddings for sentences to 100 tokens for each sentences.
OPTIMIZER AND TRAINING PARAMETERS
Optimizer: Adam optimizer with 31 = 0.9, 82 0.9999 and 10-8.
Learning Rate: A learning rate 10 was used.
Batch Size: 128 sentences per batch.
Resource consumption GRL, like other MCTS based algorithm. suffers from significant resource consumption. For the 5-path and 6-path counting problems, took weeks converge. Even with substantial CPU resources (124 AMD EPYC 9654) for the acting and GPU (4 NVIDIA A100) resources for the learning, the process remains extremely time-consuming.
These hyperparameter choices are consistent across all experiments unless stated otherwise. Fur- ther details specific to individual tasks and datasets are provided in the respective sections of the Appendix.
33


Reviews:
[{"review_id": "IixBZirHa8", "reviewer": "Reviewer_LTAB", "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.\n\nThe 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).", "questions": "Please discuss the issues mentioned above.\n\nL. 134: in the formula brackets \\{...\\} are missing.\n\nL. 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?\n\nL. 814: Lemme D.1 --> Lemma D.1", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "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.\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lBSjnk8SHg", "reviewer": "Reviewer_XApC", "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.", "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?\n2. 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?\n3. If so, has the proposed approach been compared against exhaustive explorations that utilize such rewriting rules?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper addresses a problem of foundational significance, exploring the automation of mathematical creativity through machine learning. \n- The approach is well-motivated and effectively presented, with a clear architecture and a detailed explanation of generating formulae from a given grammar. \n- 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.\n- 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..\n- 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.\n- The method appears more general beyond its current application domain. The paper could be strengthened by exploring additional applications of the proposed framework.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VIzzi8mEGF", "reviewer": "Reviewer_ZBFH", "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.\n\nWhile 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.", "questions": "Regarding Proofs:\n- 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.\n- 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)))$.\n\nRegarding PDA:\n- 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.\n- There is also an inconsistent use of the terms 'transition relation' vs. 'transition function'.\n- 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.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "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.\n- 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).\n- The paper could include other GRL applications to strengthen the introduced method's flexibility.\n- The relevance of counting cycles could be better illustrated with a few examples next to the literature reference.\n- Some explanations need coherence and clarity, especially the usage of PDAs in the paper, which could be more accurate or even omitted. (see Questions)\n- 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)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ug5UMAaTsg", "reviewer": "Reviewer_5jnX", "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.", "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.\n\nC2. 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.\n\nC3. 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.\n\nC4. I would suggest discussing whether and how the approach could apply to directed graphs as well (it seems undirected graphs are assumed).\n\nC5. 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?\n\nC6. Typos: \"ouputs\" (Fig 6 caption)", "limitations": "", "rating": 8, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "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.\n\nS2. 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:\n\n- Online Monte Carlo Tree Search without any function approximation (to demonstrate the benefit of using the transformer within the search);\n- The learned transformer policy at convergence;\n- A classic metaheuristic such as simulated annealing;\n- A simple random search that samples from the grammar and is given the same amount of rollouts as MCTS.\n\nW2. 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.\n\nW3. 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).\n\n[1] Vinyals, O., Fortunato, M., & Jaitly, N. (2015). Pointer networks. Advances in neural information processing systems, 28.\n\n[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.\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZM00OikPRB", "reviewer": "Reviewer_LKha", "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.", "questions": "- Could you help to answer my concern on the first point of weakness?\n- 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?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "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.\n- 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.\n\n- 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.\n\n- The mathematical notation used throughout the paper tends to create confusion rather than enhance the reader's understanding of the problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)