用强化学习重做图算法推理，解决传统方法无法处理复杂问题的难题。
Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning
- 将算法执行过程建模为马尔可夫决策过程，用强化学习构建解法路径
- 在CLRS-30数据集上达成高图准确率，对NP难问题表现超越已有方法
- 无需已知最优算法即可学习，适合未有成熟解法的新问题
神经算法推理（NAR）通过监督学习训练神经网络执行经典算法。尽管取得进展，仍存在诸多局限：无法在不后处理的情况下生成有效解、难以推理多个正确解、在组合类NP难问题上表现不佳，且无法应用于尚无高效算法的问题。为此，我们首次将学习算法轨迹重构为马尔可夫决策过程，引入模仿与强化学习（RL）的强大工具，实现对解构过程的结构化控制。本文提出GNARL框架，包含将NAR问题转化为RL任务的方法论及适用于多种图问题的学习架构。在多个CLRS-30问题上取得极高图准确率；在多项NP难问题上性能达到或超过更窄的NAR方法；尤为关键的是，在缺乏专家算法时仍可有效应用。
原文摘要 · Abstract (English)
Neural algorithmic reasoning (NAR) is a paradigm that trains neural networks to execute classic algorithms by supervised learning. Despite its successes, important limitations remain: inability to construct valid solutions without post-processing and to reason about multiple correct ones, poor performance on combinatorial NP-hard problems, and inapplicability to problems for which strong algorithms are not yet known. To address these limitations, we reframe the problem of learning algorithm trajectories as a Markov decision process, which imposes structure on the solution construction procedure and unlocks the powerful tools of imitation and reinforcement learning (RL). We propose the GNARL framework, encompassing the methodology to translate problem formulations from NAR to RL and a learning architecture suitable for a wide range of graph-based problems. We achieve very high graph accuracy results on several CLRS-30 problems, performance matching or exceeding much narrower NAR approaches for NP-hard problems and, remarkably, applicability even when lacking an expert algorithm.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。