机器学习国际顶级会议ICML 2023此前已公布论文接收结果，IDEA研究院3篇论文顺利入选，聚焦图神经网络（GNN）方向，展开包括子图匹配等多个具体问题的研究。

ICML 全称国际机器学习大会（International Conference on Machine Learning），是机器学习、人工智能领域最具影响力的国际学术会议之一。今年，ICML共收到6538篇投稿，其中1827篇被接收，接收率为27.9%。ICML 2023将于7月23日至29日在美国夏威夷檀香山举行。

本期文章为大家简要介绍3篇入选论文，欢迎感兴趣的读者阅读论文原文。

01

首次针对子图匹配问题，提出基于其退化机制的理论最优解，并证实了此前所有基于图神经网络方法均为错误方案。

摘要：子图匹配是基于图的应用程序的基本构建块，由于其高阶组合性质而十分具有挑战性。现有研究通常通过组合优化或基于学习的方法来解决它。然而，它们需要指数级的计算成本，或搜索匹配时缺乏理论保证。在本文中，我们通过利用深度学习和退化性来解决子图匹配问题。更具体地，我们首先证明子图匹配可以退化为子树匹配，随后等价于在二分图上找到完美匹配。然后，我们可以通过图神经网络上的内置树结构聚合机制，取得线性时间复杂度的实现。此外，图上环形结构和节点属性可以轻松地纳入D2Match，以提高匹配性能。最后，我们通过广泛的实验证明了D2Match的卓越性能，并确认D2Match确实利用了子树，与现有基于GNN的子图匹配方法不同，后者依赖于记忆数据分布差异。

（论文链接待公开）

02

首次从理论上证实图神经网络无需训练的合理性，并在神经架构搜索任务中获得百倍性能提升。

摘要：用于图神经网络（GNNs）的神经架构搜索（NAS），称为NAS-GNNs，已在手动设计的GNN架构上取得了显着性能。然而，这些方法遗留了传统NAS方法的问题，例如高计算成本和优化困难，更重要是忽视了GNN的独特性。本文中，我们首次发现GNN具有无需训练即具备表达能力的特点，并给出严格的数学证明。通过随机初始化权重，我们可以通过稀疏编码目标寻找最优的架构参数，从而推导出一种新的NAS-GNN方法，即神经架构编码（NAC）。NAC在GNN上具有无更新方案，并且可以在线性时间内高效计算。对多个GNN基准数据集的实证评估表明，我们的方法实现了SOTA性能，比强基线快最多200倍，准确率高出18.8％。（右二作者更正为Haiqin Yang）

论文链接：https://arxiv.org/abs/2305.14065

03

从特征增广角度为图神经网络提供了统一解释框架，并在公认的异配图数据集获得了50%性能提升。

摘要：图神经网络旨在学习图结构化数据的表示并表现卓越，特别是在节点分类方面。最近，许多方法从优化目标和谱图理论的角度研究了GNN的表示。然而，主导表示学习的特征空间尚未在图神经网络中进行系统研究。在本文中，我们提出通过分析空间和谱模型的特征空间来填补这一空白。 我们将图神经网络分解为确定的特征空间和可训练的权重，提供了使用矩阵空间分析明确研究特征空间的便利。我们从理论上发现，由于重复聚合，特征空间往往是线性相关的。 在这种情况下，特征空间受到共享权重的差表示或现有模型中节点属性的有限维度限制，导致性能较差。获此启发，我们提出了（1）特征子空间展平以及（2）结构主成分来扩展特征空间。广泛的实验验证了我们提出的更全面的特征空间的有效性，与基线相比具有可比较的推理时间，并展示了其有效的收敛能力。

论文链接：https://arxiv.org/abs/2305.06142