图神经网络泛化理论研究综述

消息传递图神经网络（MPNNs）已成为图机器学习的主要方法，近年来吸引了广泛关注。尽管大量研究探索了MPNNs的表达能力，即其区分图和近似函数的能力，但相对较少的研究关注其泛化能力，即在训练数据之外做出有意义预测的能力。本文系统性地回顾了关于MPNNs泛化能力的现有文献。我们分析了这些领域中各种研究的优势和局限性，提供了对其方法和发现的深入见解。此外，我们指出了未来研究的潜在方向，旨在深化对MPNNs泛化能力的理解。

1. 引言

图模型在生命科学、自然科学和形式科学中用于描述实体之间的交互关系，例如原子系统 [Duval et al., 2023, Zhang et al., 2023] 或社交网络 [Easley and Kleinberg, 2010, Lovász, 2012]，这凸显了机器学习方法处理图结构数据的必要性。因此，专为图结构数据设计的神经网络，主要是消息传递图神经网络（MPNNs）[Merkwirth and Lengauer, 2005, Gori et al., 2005, Hamilton et al., 2017, Kipf and Welling, 2017, Gilmer et al., 2017, Scarselli et al., 2009]，在机器学习社区中获得了广泛关注，并在多个领域展示了显著成果 [Corso et al., 2024]，涵盖药物设计 [Wong et al., 2023]、全球中程天气预报 [Lam et al., 2023] 和组合优化 [Cappart et al., 2021, Gasse et al., 2019, Qian et al., 2023]。 尽管MPNNs在实践中取得了成功并产生了实际影响，但其理论性质的研究相对较少 [Morris et al., 2024]。目前，MPNNs的表达能力已得到一定程度的理解。MPNNs的表达能力主要通过两种数学方法建模：与一维Weisfeiler-Leman算法（1-WL）的算法对齐和通用逼近定理 [Azizian and Lelarge, 2021, Böker et al., 2023, Chen et al., 2019, Geerts and Reutter, 2022, Maehara and NT, 2019, Rauchwerger et al., 2024]。其中，1-WL [Weisfeiler and Leman, 1968, Weisfeiler, 1976, Morris et al., 2021] 是图同构问题中一种被广泛研究的启发式算法。具体而言，Morris et al. [2019a] 和 Xu et al. [2019a] 表明，1-WL限制了任何可能的MPNN架构在区分非同构图方面的表达能力。 相比之下，关于MPNNs在训练数据之外做出有意义预测的能力，研究较少。更准确地说，MPNNs的泛化能力评估了架构在适应来自训练集相同分布的新图数据时的有效性。此外，外推或分布外泛化涉及从与训练集（略微）不同的分布中抽取的未见图数据。目前，已有多种理论框架用于分析MPNNs的泛化能力，例如Vapnik-Chervonenkis维度（VC维度）[Morris et al., 2023, Scarselli et al., 2018]、Rademacher平均值 [Garg et al., 2020] 及相关形式化方法。然而，由于不同的假设、MPNN架构和参数，这些结果往往难以直接比较。

1.1 贡献

本文综述了关于MPNNs泛化能力的理论结果，旨在使不同结果之间的比较更加容易，并帮助读者快速进入该领域。我们基于VC维度、Rademacher复杂度、覆盖数界限、基于稳定性的泛化界限和PAC-Bayesian分析，综述了泛化结果。此外，我们还探讨了使用图论理论的泛化分析以及节点级预测任务和分布外泛化的泛化理论。我们的讨论涵盖了用于建立这些界限的数学工具及其依赖的理论基础。本综述的主要目标是为读者提供关于MPNNs泛化能力的全面概述，并为扩展当前理论以填补文献空白提供见解。此外，我们提出了该领域的开放问题和未来挑战，以促进未来的研究工作。