将环形Transformer扩展到超图，实现对高阶关系的算法推理。
Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers
- 通过降维机制将超图转为图表示，支持传统图算法模拟。
- 设计超边感知编码，成功模拟赫利算法等超图专属算法。
- 理论证明其处理复杂组合数据的能力，适合结构化算法研究者。
环形Transformer在模拟传统图算法方面展现出卓越的神经算法推理能力，但其在超图等更复杂结构上的应用仍不充分。超图通过建模多个实体间的高阶关系，能提供更丰富的表示，但也带来显著的计算挑战。本文将环形Transformer的神经算法推理能力拓展至超图算法模拟，填补了神经网络与超图组合优化之间的空白。具体而言，提出一种新颖的超图降维机制，将其转化为图表示，从而实现基于图的算法（如戴克斯特拉最短路径算法）的模拟；同时引入超边感知编码方案，成功模拟超图专用算法（如赫利算法）。我们建立了这些模拟的理论保证，证明了环形Transformer处理高维与组合数据的可行性。本工作凸显了Transformer作为通用结构化数据算法求解器的潜力。
原文摘要 · Abstract (English)
Looped Transformers have shown exceptional neural algorithmic reasoning capability in simulating traditional graph algorithms, but their application to more complex structures like hypergraphs remains underexplored. Hypergraphs generalize graphs by modeling higher-order relationships among multiple entities, enabling richer representations but introducing significant computational challenges. In this work, we extend the Loop Transformer architecture's neural algorithmic reasoning capability to simulate hypergraph algorithms, addressing the gap between neural networks and combinatorial optimization over hypergraphs. Specifically, we propose a novel degradation mechanism for reducing hypergraphs to graph representations, enabling the simulation of graph-based algorithms, such as Dijkstra's shortest path. Furthermore, we introduce a hyperedge-aware encoding scheme to simulate hypergraph-specific algorithms, exemplified by Helly's algorithm. We establish theoretical guarantees for these simulations, demonstrating the feasibility of processing high-dimensional and combinatorial data using Loop Transformers. This work highlights the potential of Transformers as general-purpose algorithmic solvers for structured data.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。