KDD 2023 | 以灵活应万变：一种图分布外泛化框架FLOOD

©作者 | 社媒派SMP

来源 | 社媒派SMP

《易经》中的“不易之道”强调了“以不变应万变”的哲学思想，提出了“道”是宇宙的根本，而“道”是永恒不变的。因此，人们应该通过学习和理解“道”的不变性，来应对宇宙中的无尽变化。在机器学习模型训练中采用不变性原则，引导模型学习数据与标签之间的不变因果关系，使得模型在不同环境或数据分布下保持一致的性能，这是不变学习“以不变应万变”的工作机理。

然而，世界瞬息万变，唯一不变的是变化本身，宇宙的根本在当今世界的变化中可能很难找到。“以灵活应万变”是一种面对变化时更加可行的思路，能够及时调整和适应变化的策略或模型。遵循“以灵活应万变”的设计原则，本文提出了一种灵活的不变图表示学习框架 FLOOD，可以根据目标分布灵活地更新图编码器参数以使模型获得最佳的泛化效果。

论文标题：

FLOOD: A Flexible Invariant Learning Framework for Out-of-Distribution Generalization on Graphs

论文链接：

https://dl.acm.org/doi/10.1145/3580305.3599355

研究动机

现有的图数据分布外泛化解决方案基于不变学习（Invariant Learning）[2]设计，其核心目标是在多个环境中学习不变量。不变学习在面临分布偏移时具有显著的优势，能够保持稳定的泛化性能。

在不变学习中，“环境”通常指的是具有特定特征分布的样本集合。例如，在图数据中可以将不同度分布、不同连边密度的节点集合视为不同的“环境”。每个环境都有其独特的数据分布，但所有环境共享相同的因果关系或生成机制。现有的基于不变学习的图分布外泛化解决方案存在如下挑战： 

• 环境构造难：GIL [3] 通过生成一个软掩码矩阵来识别不变子图和环境子图，应用于图分类任务难以适用于节点分类；EERM [4] 用生成器生成多个训练环境，计算开销大且生成器输出难控制。 
• 模型灵活度低：不变学习后模型参数是固定不变的，在测试分布发生偏移时，难以根据目标分布变化灵活地调整模型实现泛化。

研究方法

实现分布外泛化的图表示学习，要求模型在多种训练环境中，学习得到节点的不变表示。通过风险外推准则，在降低每个环境训练风险的同时，要求训练风险之间的相似性增大，当测试环境分布发生偏移时，测试风险的变化减小，模型泛化性增强。

训练环境构造通过对节点特征 和连边关系 的扰动实现。记 为节点 特征缺失的概率， 是从参数为 的伯努利分布中采样得到，若其第 个值为 1，则节点 的第 维特征置为 0。记所有连边集合 是可能减少的连边集合，从未连接的节点对中随机采样 个节点对作为可能增加的连边集合 。

记 为连边 增加或减少的概率， 是从参数为 的伯努利分布中采样得到，若 其且 ，则删除连边 ; 若 其且 ，则增加连边 。完成对节点特征 和连边关系 的改变后，记得到的图结构为 ，其中 表示训练环境。

在给定训练环境 中 ，其训练风险 由交叉摘损失定义，其中 是共享编码器参数， 是分类器参数，二者都是基于图神经网络实现， 是维度为 的向量表示节点 的类别，训练图中节点数量记为 。

风险外推 [5] 不仅要求训练环境中的风险最小化，还要求风险的线性组合外推至分布外一定区域的风险最小化，假设有 个训练环境，其风险外推记为 ，其中 决定风险外推的程度。

整理上述公式后不难看出，风险外推的本质是最小化最大风险，然而，得到风险最大的训练环境是优化困难的，为了解决优化问题，可以将最大化风险替换为所有风险的方差，得出方差风险外推的表达式 ，其中系数 是鼓励风险相似性和最小化风险的平衡系数。

为了捕捉目标分布的变化，需要设计一种不依赖于真实标签的自监督学习模块感知分布变化，因为分布偏移后的样本标签往往是不可获得的。图对比学习是常用的图自监督学习方法，但其中负样本采样往往需要大量计算资源，不利于在发生概念漂移时迅速调整模型，因此拟采用不同训练环境间的自助表示学习，避免负采样带来的计算开销。

在训练环境生成模块的输出中随机选取两个视图，分别记为 和 ，其中 是在线视图，由在线编码器 建模，得到在线表示为 。

是目标视图，由目标编码器 建模，得到目标表示为 。目标编码器为在线编码器提供回归目标用于训练，在线表示 经过预测器 输出对目标表示的预测，在线编码器的参数 通过最小化如下均方误差损失实现更新。

目标编码器的参数 不使用梯度下降，其参数是在线编码器参数 的指数滑动平均，根据当前时间和样本被记录的时间划分数据集 ，其中 是目标衰减率，控制每次更新原参数的保留比例。

在训练阶段，真实标签监督下的不变表示学习与自监督的自助表示学习协同训练，学习得到从输入空间到隐藏空间再到标签空间的映射关系，优化目标函数如下所示。

在测试阶段，自助表示学习可以在测试数据上重新训练以更新共享编码器参数 ，优化目标函数如下所示。

整个算法流程为：

• 由原始图数据 构造 个训练环境 ；
• 基于共享编码器 得到每个训练环境中节点表示 ；
• 在训练图中分别计算不变学习模块和自助学习模块，最小化训练损失函数 ，更新全部编码器和分类器参数；
• 在测试图中只计算自助学习模块，最小化训练损失函数 ，更新共享编码器参数。

实验分析

在图分布外泛化基准数据集 GOOD [7] 上进行实验，四个数据集在不同偏移域上的节点分类的分布内和分布外准确率如下表所示。

可以得出以下结论： 

1. 测试时训练提升模型泛化能力。由于自助表示学习模块的灵活性，模型可以通过共享编码器根据目标分布变化自适应调整参数，使得 FLOOD 取得最佳的分布外泛化效果。 

2. 图数据增强提升模型泛化能力。Mixup 在多个数据集上取得次优表现，说明图数据增强有利于增加训练数据分布的多样性。得益于此，FLOOD 通过图数据增强的方式获得了多样性较高的训练环境。 

测试时训练前后的节点表示可视化如下图所示，不同颜色代表不同的节点类别，可以看出，根据目标分布微调后的表示具有更加明显的边界，更容易被分类器区分开从而取得更好的泛化效果。

总结与展望

本文提出一种灵活的不变图表示学习框架 FLOOD，包括环境无关的不变表示学习、分布感知的自助表示学习和分布偏移自适应的测试时训练三个模块。环境无关的不变表示学习通过图数据增强构建多个训练环境，并在风险外推的准则下学习节点的不变表示；分布感知的自助表示学习以一种自监督的方式与不变表示学习共享图编码器进行训练；在测试阶段，共享编码器可以根据目标分布灵活地更新参数以使模型获得最佳的泛化效果。

参考文献

[1] Liu, Yang, Xiang Ao, Fuli Feng, Yunshan Ma, Kuan Li, Tat-Seng Chua, and Qing He. "FLOOD: A flexible invariant learning framework for out-of-distribution generalization on graphs." In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1548-1558. 2023.

[2] Arjovsky, Martin, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. "Invariant risk minimization." arXiv preprint arXiv:1907.02893 (2019).

[3] Li, Haoyang, Ziwei Zhang, Xin Wang, and Wenwu Zhu. "Learning invariant graph representations for out-of-distribution generalization." Advances in Neural Information Processing Systems 35 (2022): 11828-11841.

[4] Wu, Qitian, Hengrui Zhang, Junchi Yan, and David Wipf. "Handling distribution shifts on graphs: An invariance perspective." In International Conference on Learning Representations, 2022.

[5] Krueger, David, Ethan Caballero, Joern-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville. "Out-of-distribution generalization via risk extrapolation (rex)." In International Conference on Machine Learning, pp. 5815-5826. PMLR, 2021.

[6] Wu, Ying-Xin, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. "Discovering invariant rationales for graph neural networks." In International Conference on Learning Representations, 2022.

[7] Gui, Shurui, Xiner Li, Limei Wang, and Shuiwang Ji. "Good: A graph out-of-distribution benchmark." Advances in Neural Information Processing Systems 35 (2022): 2059-2073.

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：[e-mail] 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

·

·