Graph Understanding进展I

标题：MAG-GNN

博主点评：

代码地址：https://github.com/LechengKong/MAG-GNN

发表日期：2023-10-29

摘要：虽然图神经网络（GNN）最近成为图学习任务中的强大工具，但在提高GNN的结构编码能力方面仍付出了相当大的努力。一项特定的工作提出了使用子图信息来提高GNN表达能力的子图GNN，并取得了巨大的成功。然而，这种有效性通过枚举所有可能的子图来牺牲GNN的效率。本文分析了完全子图枚举的必要性，并表明通过考虑子图的一个小子集，模型可以达到相当的表达水平。然后，我们将最优子集的识别转化为组合优化问题，并提出了MAG-GNN来解决这个问题，这是一种强化学习（RL）增强的GNN。从候选子图集开始，MAG GNN使用RL代理迭代更新子图，以定位最具表现力的预测集。这将子图枚举的指数复杂度降低到子图搜索算法的恒定复杂度，同时保持良好的表现力。我们在许多数据集上进行了广泛的实验，结果表明MAG-GNN的性能与最先进的方法相当，甚至优于许多子图GNN。我们还证明了MAG-GNN有效地减少了子图GNN的运行时间。

论文地址：https://arxiv.org/abs/2310.19142