用GNN精确学习执行图算法，无需错误地完成分布式计算任务。
Learning to Execute Graph Algorithms Exactly with Graph Neural Networks
- 用多层感知机集合学习节点局部指令，再嵌入GNN中执行
- 小样本训练即可在推理时无误差运行算法，概率接近1
- 适用于广度优先搜索、贝尔曼-福特等经典图算法
理解图神经网络能学到什么，尤其是其学习执行算法的能力，仍是核心理论挑战。本文在有界度和有限精度约束下，证明了图算法的精确可学习性。方法分两步：首先训练一个MLP集成来执行单个节点的局部指令；其次在推理时，将训练好的MLP集合作为GNN的更新函数使用。基于神经正切核（NTK）理论，我们证明局部指令可从小样本中学习，使整个图算法在推理阶段无误差执行，且成功概率很高。为展示该框架的学习能力，我们建立了对分布式计算中局部模型（LOCAL model）的严格可学习性结果。进一步，我们对消息泛洪、广度优先搜索、深度优先搜索及贝尔曼-福特算法均获得了积极的可学习性结果。
原文摘要 · Abstract (English)
Understanding what graph neural networks can learn, especially their ability to learn to execute algorithms, remains a central theoretical challenge. In this work, we prove exact learnability results for graph algorithms under bounded-degree and finite-precision constraints. Our approach follows a two-step process. First, we train an ensemble of multi-layer perceptrons (MLPs) to execute the local instructions of a single node. Second, during inference, we use the trained MLP ensemble as the update function within a graph neural network (GNN). Leveraging Neural Tangent Kernel (NTK) theory, we show that local instructions can be learned from a small training set, enabling the complete graph algorithm to be executed during inference without error and with high probability. To illustrate the learning power of our setting, we establish a rigorous learnability result for the LOCAL model of distributed computation. We further demonstrate positive learnability results for widely studied algorithms such as message flooding, breadth-first and depth-first search, and Bellman-Ford.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。