arXiv:2403.11734v2 通知类型: 替换 摘要: 基于GNN的方法在不同规划领域学习通用策略受限于 $C_2$ 的表辞性能力，即一阶逻辑带有两个变量和计数。可以通过转换到 $k$-GNNs（对于 $k=3$）来进行解决，其中对象嵌入被三元组嵌入取代。然而，虽然 $3$-GNNs 具有 $C_3$ 的表辞性能力，与受限于 $C_2$ 的 $1$-GNNs 和 $2$-GNNs 不同，它们需要四次方时间的消息交换和三次方空间来存储嵌入，使得它们在实践中不可行。在本项工作中，我们介绍了一种参数化的 R-GNN[$t$]（带有参数 $t$）版本的 Relational GNNs。与设计用于在图上执行计算的 GNNs 不同，Relational GNNs 是为了在关系结构上执行计算而设计的。当 $t=\infty$ 时，R-GNN[$t$] 在图上近似 $3$-GNNs，但仅使用二次空间来存储嵌入。对于较低的 $t$ 值，例如 $t=1$ 和 $t=2$，R-GNN[$t$] 通过交换更少的消息实现了较弱的近似，然而有趣的是，这在多个规划领域中往往提供了所需的表达能力。此外，新的 R-GNN[$t$] 架构是原始的 R-GNN 架构，仅应用于输入的适当变换。实验结果表明 R-GNN[$1$] 在性能上的明显提升，同时也超过了同样近似 $3$-GNNs 的 Edge Transformers。