图谱的泛化探索：从不变性到因果性
原文：
towardsdatascience.com/towards-generalization-on-graphs-from-invariance-to-causality-c81a174ac37b?source=collection_archive---------6-----------------------#2024-07-18
这篇博客分享了关于图结构数据的分布外泛化的最新论文
https://medium.com/@qitianwu228?source=post_page---byline--c81a174ac37b--------------------------------https://towardsdatascience.com/?source=post_page---byline--c81a174ac37b-------------------------------- Qitian Wu
·发布于数据科学前沿 ·阅读时间：14 分钟·2024 年 7 月 18 日
–
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/eb13a4c4ace10b85ad4a680e17242b0f.png
图像由 GPT-4 生成
这篇博客介绍了图上的分布外泛化的最新进展，这是机器学习中一个重要但尚未深入探索的问题。我们将首先介绍问题的表述以及涉及图上分布变化的典型场景。然后，我们将概述三篇最近发布的论文（我是作者之一）：
处理图上的分布变化：一种不变性视角，ICLR2022。
图谱的分布外泛化通过因果干预，WWW2024。
学习分歧场以获得抗偏移的图表示，ICML2024。
这些工作聚焦于通过不变性原理和因果干预的视角来研究图上的泛化问题。此外，我们将比较这些方法并讨论该领域未来可能的发展方向。
图机器学习仍然是一个热门的研究方向，尤其是在 AI4Science 浪潮的推动下，图数据的应用领域越来越广泛。与普通的图像和文本数据不同，图是一种数学抽象，描述了实体的属性以及它们在系统中的相互作用。在这方面，图不仅可以表示不同规模的现实世界物理系统（如分子、蛋白质相互作用、社交网络等），还可以描述某些抽象的拓扑关系（如场景图、工业过程、思维链等）。
如何构建通用的图数据基础模型是一个最近受到广泛关注的研究问题。尽管现有方法如图神经网络（GNNs）和图变换器在表示能力上表现强大，但图结构数据上机器学习模型的泛化能力仍然是一个尚未深入探索的开放问题[1, 2, 3]。一方面，图数据中涉及的非欧几里得空间和几何结构显著增加了建模的难度，使得现有的旨在增强模型泛化能力的方法难以成功[4, 5, 6]。另一方面，图数据中的分布转移，即训练数据和测试数据之间的分布差异，源于更为复杂的引导因素（如拓扑结构）和外部环境，使得这个问题更加难以研究[7, 8]。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/ba1c3e0d24e963ef3fdbe2526ec318ce.png
泛化挑战旨在处理从训练到测试的分布转移。
问题与动机
开放世界中的分布转移
泛化问题至关重要，因为在现实场景中，模型通常需要与一个开放、动态且复杂的环境进行交互。在实际情况下，由于观察和资源的限制，训练数据无法涵盖所有可能的环境，模型也无法在训练过程中预见到所有潜在的未来情形。然而，在测试阶段，模型很可能会遇到与训练分布不一致的样本。分布外泛化（OOD）问题的关键焦点是如何使机器学习模型在测试数据上表现良好，即使这些测试数据超出了训练分布。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/22a358ef7dbb045f049ced6606b78efc.png
涉及图数据分布转移的典型场景要求机器学习模型从有限的训练数据泛化到新的测试分布。来自 Medium 博客的图片：时序图网络 和 对流扩散变换器
在这种情况下，由于测试数据/分布在训练过程中是严格未见/未知的，因此关于数据生成的结构假设是必要的前提。相反，如果没有任何数据假设，分布外泛化将是不可能的（无免费午餐定理）。因此，必须事先明确指出，OOD 问题的研究目标不是消除所有假设，而是1）在合理的假设下最大化模型的泛化能力，2）适当增加/减少假设，以确保模型能够处理某些分布转移。
图上的分布外泛化
一般的分布外（OOD）问题可以简单地描述为：
当 p(x,y|train)≠p(x,y|test) 时，如何设计有效的机器学习方法？
在这里，我们遵循文献中常用的设定，假设数据分布由潜在的环境控制。因此，在给定环境 e 下，数据生成可以写作 (x,y)∼p(x,y|e)。对于 OOD 问题，训练和测试数据可以假定来自不同的环境。因此，这个问题可以进一步阐述为
如何学习一个预测模型 f，使其在所有环境 e∈E 中表现（同样）良好？
具体来说，对于图结构数据，输入数据还包含结构信息。在这方面，根据图结构存在的形式，问题可以进一步分为两类：节点级任务和图级任务。下图展示了在这两种任务类型下 OOD 问题的公式化。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/41cb47be812bc54b61c448f24c059046.png
图上的 OOD 泛化形式，其中我们进一步区分了图级任务和节点级任务，这些任务在图结构的形式上有所不同。具体来说，对于节点级任务，由于图结构引入了节点实例之间的相互依赖关系，[5] 提出将整个图分割为以节点为中心的自我图（ego-graphs），这些自我图可以被视为独立的输入。
如前所述，OOD 问题需要关于数据生成的某些假设，这些假设为构建具有泛化能力的机器学习方法铺平了道路。接下来，我们将具体介绍两类方法，分别利用不变性原理和因果干预来实现图上的分布外泛化。
通过不变性原理的泛化
基于不变性原理的学习方法，通常被称为不变学习[9, 10, 11]，旨在设计新的学习算法，引导机器学习模型利用数据中的不变关系。不变关系特别指的是从输入 x 和标签 y 中获得的预测关系，这些关系在所有环境中普遍适用。因此，当预测模型 f（例如神经网络）成功学习到这些不变关系时，它能够跨不同环境中的数据进行泛化。相反，如果模型学习到的是虚假的相关性，即仅在某些环境中成立的从 x 和 y 获得的预测关系，那么过度提高训练准确性将误导预测模型过拟合数据。
根据上述说明，我们注意到不变学习依赖于数据生成中的不变假设，即在不同环境中，x 和 y 之间存在一个保持不变的预测关系。数学上，这可以被公式化为：
存在一个映射 c，使得 z=c(x) 满足 p(y|z,e)=p(y|z)，∀e∈E。
在这方面，我们自然有两个后续问题：i) 如何在图上定义不变假设？ii) 对于常见的图数据，这个假设是否合理？
接下来，我们介绍最近的论文[5]，吴等人，"处理图上的分布变化：一种不变性视角”（ICLR2022）。该论文提出将不变性原则应用于图上的分布外泛化，并提出了图数据的不变假设。
图上的不变假设
受图同构测试中的 Weisfeiler-Lehman 算法启发，[5]考虑了以每个节点为中心的自我图，并描述了所有节点特征在自我图中对中心节点标签的贡献。后者被具体分解为不变特征和虚假特征。这一定义兼顾了拓扑结构，同时也允许足够的灵活性。下图展示了[5]中定义的不变假设，并提供了一个引用网络的示例。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/d61ef3d9b14b6f635324bc8bca0152a8.png
图上的不变假设（左）和引用网络的示例（右）。在引用网络中，每个节点代表一篇论文，待预测的标签 y 是论文的研究领域。节点特征 x 包括论文的发表场所（x1）和引用指数（x2），环境（e）是发表时间。在这个例子中，x1 是一个不变特征，因为它与 y 的关系与环境无关。相反，x2 是一个虚假特征；尽管它与 y 有很强的相关性，但这种相关性会随时间变化。因此，在这种情况下，一个理想的预测器应该利用 x1 中的信息，以实现跨不同环境的泛化。图像来自论文。
提出的方法：探索-外推风险最小化
在不变假设下，一种自然的方法是对不同环境下的损失差异进行正则化，以促进学习不变关系。然而，现实世界中的数据通常缺乏环境标签，即每个实例与其环境之间的对应关系未知，这使得无法直接计算不同环境间的损失差异。为了解决这个挑战，[5]提出了探索-外推风险最小化（EERM），该方法引入了 K 个上下文生成器来扩展和多样化输入数据，从而模拟来自不同环境的输入数据。通过理论分析，[5]证明了新的学习目标可以保证在所提出的分布外泛化问题上得到最优解。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/af67d937affec052f992998fa894ac9d.png
探索-外推风险最小化（EERM）由[5]提出，其中内在目标是最大化由 K 个上下文生成器生成的数据的“多样性”，外在目标则涉及使用来自 K 个生成的（虚拟）环境的数据来计算损失的均值和方差，用于训练预测模型。
除了生成（虚拟）环境外，最近的另一项研究[12]提出从观察数据推断潜在环境，并引入了一个额外的环境推断模型，在训练过程中与预测器一起迭代优化。同时，[13]通过数据增强处理分布外的泛化，使用不变性原理来指导数据增强过程，从而保留不变的特征。
因果干预下的泛化
不变学习要求假设数据中存在可以学习的不变关系。这在一定程度上限制了此类方法的适用性，因为模型只能在与训练数据共享某些不变性的测试数据上可靠地泛化。对于违反此条件的分布外测试数据，模型的泛化性能仍然未知。
接下来，我们介绍最近的工作[14]提出的另一种方法，Wu 等人，“通过因果干预实现图的分布外泛化” (WWW2024)。本文旨在通过因果干预的视角解决分布外泛化问题。与不变学习不同，该方法不依赖于数据生成中的不变假设。相反，它通过学习算法引导模型从 x 到 y 学习因果关系。
图学习的因果视角
首先，让我们考虑由机器学习模型（如图神经网络）通常引起的变量之间的因果依赖关系。我们有输入 G（例如，图中每个节点中心的自我图），标签 Y，以及影响数据分布的环境 E。在使用标准监督学习目标（例如，经验风险最小化或等效的最大似然估计）进行训练后，它们之间的依赖关系在下图中展示。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/b8939081e9596e8c38629ad55d204ae7.png
在因果图中，有三条依赖路径：i) 由预测器引起的从 G 到 Y 的路径；ii) 由数据生成定义给出的从 E 到 G 的路径；iii) 由模型训练引导的从 E 到 Y 的路径。
上面的因果图揭示了传统训练方法的局限性，特别是它们无法实现分布外的泛化。在这里，输入 G 和标签 Y 是环境 E 的结果，暗示它们由于这个混杂因素而相关。在训练过程中，模型不断拟合训练数据，导致预测器 f 学习到输入和标签之间的虚假关联，这些关联是特定于某一环境的。
[14]通过一个社交网络示例来说明这一学习过程。假设我们需要预测社交网络中用户（节点）的兴趣，其中注意到用户兴趣受到年龄和社交圈等因素的显著影响。因此，如果一个预测模型在大学社交网络的数据上训练，它可能很容易预测用户对“篮球”的兴趣，因为在大学环境中，由于环境本身的影响，用户对篮球的兴趣比例较高。然而，当模型转移到 LinkedIn 社交网络时，这种预测关系可能不再成立，因为 LinkedIn 的用户年龄和兴趣更加多样化。这个例子突显了一个理想的模型需要学习输入和标签之间的因果关系，从而能够在不同的环境中进行泛化。
为此，一种常见的方法是因果干预，即切断因果图中 E 与 G 之间的依赖路径。这是通过干扰环境如何影响输入和标签，从而引导模型学习因果关系来实现的。下图展示了这种方法。在因果推断术语[15]中，旨在移除到特定变量的依赖路径的干预，可以使用 do-算子表示。因此，如果我们在训练过程中旨在强制切断 E 与 G 之间的依赖路径，这实际上意味着将传统的优化目标 p(Y|G)（观察数据的似然）替换为 p(Y|do(G))。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/ab6865bfb02c094f00308f3fc481fe28.png
基于因果干预的学习目标。进一步地，利用因果推断中的反向调整[15]，我们可以从因果图中推导出目标的显式形式。
然而，计算这个学习目标需要数据中观察到的环境信息，具体来说是每个样本 G 与其环境 E 之间的对应关系。然而，在实际中，环境往往是不可观察的。
提出的方法：变分上下文调整
为了使上述方法可行，[14]推导了因果干预目标的变分下界，采用了一种数据驱动的方法，通过从数据中推断潜在环境来解决不可观察环境的问题。特别地，[14]引入了变分分布 q(E|G)，从而得出了下图所示的替代学习目标。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/0e36ba25a7486a54d6723529fb018953.png
原始因果干预目标的变分下界以及[14]中提出的最终学习目标中三个项的具体实例。图像来自论文。
新的学习目标由三个部分组成。[14]将其具体化为一个环境推断模型，一个 GNN 预测器，和一个（非参数的）环境先验分布。前两个模型包含可训练参数，并在训练过程中共同优化。
为了验证所提方法的有效性，[14]将该模型应用于多个具有分布偏移的真实世界图数据集。具体而言，由于所提方法 CaNet 不依赖于特定的主干模型，[14]分别使用 GCN 和 GAT 作为主干，并与最先进的 OOD 方法（包括先前介绍的 EERM 方法）进行比较。下表显示了部分实验结果。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/74193aab006dc46f879205a144029993.png
在 Arxiv（或 Twitch）上测试准确率（或 ROC-AUC）的实验结果，其中分布偏移通过根据发表年份（或子图）对数据进行划分引入。
因果干预中的隐性假设
到目前为止，我们已经介绍了因果干预方法，它在图结构的分布外推理中展现了竞争力。正如之前在本博客中提到的，确保泛化能力需要关于数据如何生成的必要假设。这引发了一个自然的问题：因果干预在泛化中需要什么假设？与不变学习不同，因果干预并不是从明确假设开始，而是依赖于建模和分析过程中的隐性假设：
在输入和标签之间仅存在一个混杂因素（环境）。
这个假设在一定程度上简化了实际系统的分析，但也引入了近似误差。对于更复杂的场景，未来仍有大量的探索空间。
使用隐式图结构进行泛化
在之前的讨论中，我们假设输入数据的结构信息是可观察和完整的。对于更一般的图数据，结构信息可能是部分可观察的，甚至完全未知。此类数据称为隐式图结构。此外，图上的分布偏移可能涉及影响数据分布的潜在结构，从而带来了在表征几何对数据分布影响时未解决的挑战。
为了解决这个问题，最近的研究[16]，吴等，“为抗偏移鲁棒图表示学习发散场”（ICML2024），利用了连续扩散方程与消息传递机制之间的固有联系，整合了前述的因果干预方法。该设计旨在开发一种适用于显式和隐式图结构的学习方法，在这些结构中，分布偏移会构成泛化挑战。
从消息传递到扩散方程
消息传递机制作为现代图神经网络和图 Transformer 的基础设计，通过每一层将信息从其他节点传播到中心节点，从而更新其表示。本质上，如果我们将神经网络的层视为连续时间的离散化近似，那么消息传递可以被看作图上的扩散过程的离散形式[17, 18]。下图说明了它们的类比。（有兴趣深入了解此方面的读者可以参考Prof. Michael Bronstein 等人的最新博客）。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/18aaa6a57b7e1d69b6bfa3900007361f.png
消息传递（GNNs 和 Transformers 中的层间更新）可以通过以下类比看作是连续扩散方程的离散迭代：图中的节点被映射到流形上的位置，节点嵌入由热信号表示，嵌入的层次更新对应于热信号随时间的变化，每层中节点之间的交互反映了流形上位置之间的交互。
特别地，扩散方程中的扩散率（记作 d_u）控制了扩散过程中节点之间的交互。当采用局部或全局扩散形式时，扩散方程的离散迭代分别导致了图神经网络[18]和 Transformer[19]的层更新公式。
然而，确定性扩散率无法模拟实例之间交互中的多方面效应和不确定性。因此，[16] 提出了将扩散率定义为概率分布中的随机样本。相应的扩散方程将产生一个随机轨迹（如下图所示）。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/5a55342e17812d86519433c30936b880.png
在将扩散率 d_u 定义为随机变量之后，扩散方程在每个时间点的散度场（即当前层中节点嵌入的变化）将变为随机的。这使得能够对节点之间的交互中的不确定性进行建模。
尽管如此，如果直接应用传统的监督学习目标进行训练，上述模型在分布变化的情况下不能很好地泛化。这个问题与之前讨论的图学习的因果视角相呼应。具体而言，在此处考虑的扩散模型中，输入 x（例如图）和输出 y（例如图中的节点标签）通过扩散率关联。扩散率可以看作是特定数据集环境的体现，决定了实例之间的相互依赖关系。因此，训练数据有限的模型往往会学习到特定于训练集的相互依赖模式，从而无法在新的测试数据上泛化。
因果引导的散度场学习
为了解决这一挑战，我们再次采用因果干预，在训练过程中消除扩散性 d 与输入 x 之间的依赖关系。与之前的工作[14]不同，其中输入到输出的映射是由预测器给出的，这里从 x 到 y 的依赖路径涉及一个多步骤的扩散过程（对应于 GNNs/Transformers 中的多层更新）。因此，每一步的扩散过程中都需要因果干预。然而，由于扩散性是一个抽象的建模概念，无法直接观察（类似于前面讨论的环境），[16]扩展了[14]中使用的变分方法，推导出扩散过程学习目标的变分下界。这作为每一步扩散过程中的因果干预的近似目标。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/adc9aad2a68adae832796aeea7619a98.png
[16]中提出的学习方法估计了扩散模型每一步的扩散性，并应用因果干预。该方法引导模型学习从输入到输出的稳定因果关系，从而增强其在分布偏移下的泛化能力。图片来自论文。
作为上述方法的实现，[16]引入了三种特定的模型设计：
GLIND-GCN：将扩散性视为通过标准化图邻接矩阵实例化的常量矩阵；
GLIND-GAT：将扩散性视为通过图注意力网络实现的时间依赖矩阵；
GLIND-Trans：将扩散性视为通过全局所有对注意力网络实现的时间依赖矩阵。
特别地，对于GLIND-Trans，为了解决全局注意力计算中的二次复杂度问题，[16]进一步采用了 DIFFormer [19]中的线性注意力函数设计。（我们还建议对如何实现所有对注意力的线性复杂度感兴趣的读者参阅此博客）。
下表展示了涉及隐式结构场景中的部分实验结果。
https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/79cdd9decfaf711c8f75a1ee1572cb71.png
在 CIFAR 和 STL 上的测试准确率实验结果，其中原始数据集不包含结构信息，我们使用 k 近邻方法构建图。此外，对于 CIFAR 和 STL，我们通过添加旋转角度（改变 k 近邻的相似度函数）和使用不同的 k，分别引入了分布偏移。
总结与讨论
本文简要介绍了分布外（OOD）泛化的最新进展，主要聚焦于三篇已发表的论文[5, 14, 16]。这些工作从不变学习和因果干预的角度处理该问题，提出了适用于显式和隐式图结构的方法。如前所述，我们指出，OOD 问题需要在数据生成假设的前提下才能有效解决。基于此，未来的研究可以集中于完善现有方法或分析在已建立的假设条件下的泛化极限，也可以探索在其他假设条件下如何实现泛化。
另一个与 OOD 泛化密切相关的挑战是分布外检测[20, 21, 22]。与 OOD 泛化不同，OOD 检测的目的是研究如何在训练过程中使模型具备识别测试阶段出现的分布外样本的能力。未来的研究还可以集中在将博客中提到的方法扩展到 OOD 检测，或者探索这两个问题的交集。
参考文献
[1] Garg 等人，图神经网络的泛化与表示限制，ICLR 2020。
[2] Koh 等人，WILDS：野外分布变化基准，ICML 2021。
[3] Morris 等人，Position：图机器学习理论的未来方向，ICML 2024。
[4] Zhu 等人，抗变化的 GNN：克服局部图训练数据的局限性，NeurIPS 2021。
[5] Wu 等人，在图上处理分布变化：一种不变性视角，ICLR 2022。
[6] Li 等人，OOD-GNN：分布外广义图神经网络，TKDE 2022。
[7] Yehudai 等人，从局部结构到图神经网络中的规模泛化，ICML 2021。
[8] Li 等人，生物数据上的图神经网络规模泛化：
来自谱学视角的洞察与实践，Arxiv 2024。
[9] Arjovsky 等人，不变风险最小化，Arxiv 2019。
[10] Rojas-Carulla 等人，因果迁移学习的不变模型，JMLR 2018。
[11] Krueger 等人，通过风险外推进行分布外泛化，ICML 2021。
[12] Yang 等人，学习分布外分子表示的子结构不变性，NeurIPS 2022。
[13] Sui 等人，释放图数据增强在协变量分布变化中的力量，NeurIPS 2023。
[14] Wu 等人，通过因果干预进行图的分布外泛化，WWW 2024。
[15] Pearl 等人，统计学中的因果推断：入门，2016。
[16] Wu 等人，学习用于应对变化的图表示的发散场，ICML 2024。
[17] Freidlin 等人，图上的扩散过程与平均化原理，概率年鉴 1993。
[18] Chamberlain 等人，GRAND：图神经扩散，ICML 2021。
[19] Wu 等人，DIFFormer：由能量约束扩散生成的可扩展（图）变换器，ICLR 2023。
能量约束扩散，ICLR 2023。
[20] Wu 等人，基于能量的图神经网络图外分布检测，ICLR 2023。
[21] Liu 等人，GOOD-D：无监督图外分布检测，WSDM 2023。
[22] Bao 等人，图神经网络的图外分布检测通过邻域塑形，ICML 2024。