用强化学习发现图中路径与环计数的新公式，效率提升2至6倍。
Finding path and cycle counting formulae in graphs with Deep Reinforcement Learning
- 基于上下文无关语法和栈式自动机的Transformer模型，结合蒙特卡洛树搜索优化公式
- 新公式在路径/环计数上比现有方法快2到6倍，显著提升计算效率
- 适合对图算法性能优化感兴趣的科研人员和工程开发者
本文提出语法强化学习（GRL），一种结合蒙特卡洛树搜索（MCTS）与基于上下文无关语法（CFG）框架下建模堆栈自动机（PDA）的Transformer架构的强化学习算法。以高效计数图中路径与环为应用场景，该问题在网络分析、计算机科学、生物学及社会科学中具有重要意义。GRL发现了新的基于矩阵的路径/环计数公式，在计算效率上相比当前最优方法提升2至6倍。主要贡献包括：(i) 构建了在CFG框架内生成语法生成器（gramformer）的系统；(ii) 开发了在语法结构中优化公式的GRL算法；(iii) 发现了用于图子结构计数的新公式，带来显著的计算加速。
原文摘要 · Abstract (English)
This paper presents Grammar Reinforcement Learning (GRL), a reinforcement learning algorithm that uses Monte Carlo Tree Search (MCTS) and a transformer architecture that models a Pushdown Automaton (PDA) within a context-free grammar (CFG) framework. Taking as use case the problem of efficiently counting paths and cycles in graphs, a key challenge in network analysis, computer science, biology, and social sciences, GRL discovers new matrix-based formulas for path/cycle counting that improve computational efficiency by factors of two to six w.r.t state-of-the-art approaches. Our contributions include: (i) a framework for generating gramformers that operate within a CFG, (ii) the development of GRL for optimizing formulas within grammatical structures, and (iii) the discovery of novel formulas for graph substructure counting, leading to significant computational improvements.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。