学习超图动力系统的有效阶数

Learning the effective order of a hypergraph dynamical system

学习超图动力系统的有效阶数

原文链接：https://www.science.org/doi/10.1126/sciadv.adh4053

超图上的动力系统可以展现出成对相互作用系统所无法观察到的丰富行为。对于一个具有假设超图结构的分布式动力系统，一个有趣的问题是，究竟需要多少这种超图结构才能真实地复制出观察到的动力学行为。为了回答这个问题，我们提出了一种方法，用于确定近似相应动力学所需的超图的最小阶数。具体而言，我们开发了一个数学框架，允许我们在已知动力学类型的情况下确定这一阶数。我们将这些思想与超图神经网络结合，直接从包含观察到的系统轨迹的合成数据和真实数据中学习动力学本身以及超图的阶数。

引言

超图上的动力学过程（1, 2）最近受到了广泛关注。相关例子包括同步（3, 4）、共识动力学（5–7）、传染病传播（8–10）、随机游走（11, 12）、标签传播（13–15）以及社会传染（16, 17）。总体而言，人们发现，与基于图的动力学系统相比，基于超图的动力学系统的重要特征可能会发生变化。例如，超图上的传染病过程可能具有不同的流行病暴发阈值（9, 10），或者群体强化效应可能会显著改变超图上意见形成的最终结果（17–19）。超图还作为图神经网络的扩展引起了人们的兴趣，并被应用于从计算机视觉中的三维形状检索（20）和姿态估计（21）到群体推荐任务（22）或医学应用（如癌症组织分类）（23）的多种应用中。

尽管在描述超图动力学系统的数学方程中，这两个方面通常被合并在一起，但从建模的角度来看，区分（i）约束系统中可能相互作用的拓扑关系（如超图中编码的）和（ii）在每个超边上发生的局部多边动力学模型（例如，传染病传播、扩散和同步）是非常重要的。正是这两个方面的相互作用导致了高阶效应的（可能）出现（2, 18, 24）。

例如，如果我们考虑超图上的线性动力学，那么我们不能期望出现任何高阶效应。因为任何有限维空间之间的线性映射都可以用矩阵表示，对于线性动力学，我们总是可以找到一个基于图的成对相互作用动力学来精确建模，通过将矩阵与一个有效的加权图等同起来（5, 6）。实际上，这意味着只要考虑线性动力学，就可以使用图而不是基于超图的动力学系统。同样，研究表明，超图上的半监督和无监督谱聚类问题的各种表述可以简化为一个有效的基于图的问题（25–27）。

更一般地，我们可以设想，根据局部动力学的不同，我们能够将一个在一般阶数k 的超图上的超图动力学系统重写为在阶数不超过 的超图上的动力学。这种简化为低阶关系是相关的，因为使用超图存在几个挑战：最突出的是，由于超边的数量可能随着节点数量呈组合式增长，超图模型的使用可能在计算上非常昂贵。对于大规模系统，这一点尤其重要。

然而，在实践中，我们通常既不知道实体之间的确切关系集合，也不知道局部相互作用动力学的解析形式，而只有一些观测数据，例如以轨迹的形式。例如，我们可以观察到一个群体中传染病的传播，作为个体及其接触模式的轨迹，这些模式由超图表示。另一个例子是测量生态系统中物种的丰度及其相互作用。许多不同的方法已经被探索用来近似这类时间序列数据。例如，最近有研究提出将神经网络视为具有连续层的模型（28）。这种观点允许将神经网络的前向传播重新表述为一个常微分方程（ODE）的初值问题的解。使用这种前向传播的重新解释的深度学习架构被称为神经ODE，它适用于构建连续时间时间序列模型。神经ODE最近也被推广到图（29, 30）。从测量数据中发现控制动力学系统的方程是一个重要问题，已有大量文献对此进行了研究（31–34）。这里的主要挑战是找到一个足够复杂以描述现有数据但又不至于过于复杂而引入过拟合的模型。

对于超图上的动力学系统，有多种可能的方法来抽象观察到的分布式动力学。例如，我们可以将其建模为由一个相对复杂的超图上的简单局部动力学产生的。或者，我们也可以考虑一个更复杂的局部动力学，通过实体之间更受限的关系集合进行相互作用。这引发了我们是否应该将模型的复杂性包含在相互作用的拓扑结构中，还是包含在动力学模型中的问题：在实践中，我们需要在模型中编码哪些多边关系？

在这里，我们考虑了一类广泛的超图动力学系统，并引入了系统的拓扑阶和动力学阶的概念，这些概念从不同角度衡量动力学的复杂性。基于拓扑阶和动力学阶的结合，我们可以确定超图动力学系统的有效阶，即精确表示相应动力学所需的超图的最小阶。特别是，我们提出了一个框架，允许我们在已知动力学函数形式的情况下推导出动力学阶和有效阶。此外，为了从经验数据中推断有效动力学阶，我们提出了一个超图神经网络架构，允许我们直接从数据中学习超图动力学及其有效阶，我们在合成数据和真实数据集上对其进行了测试。总之，我们提出了一种有效的方法，用于降低一类超图动力学系统的复杂性，并从数据中学习它们的表示。

超图动力学系统的可约性

为了说明超图上动力学系统的动力学阶和有效阶的概念，我们以超图上的Kuramoto型动力学（35）为例来阐述。Kuramoto振子动力学已被应用于各种相位振子的同步现象（36），范围从电力网络（37）到大脑活动（38）。已有几项研究致力于将其推广到单纯复形（3, 4）和超图（39）。在这里，我们将比较超图上Kuramoto动力学的两种不同表述

因此，尽管我们在这里处理的是超图上的非线性动力学，但每个超边上的动力学是成对的，我们可以将其简化为成对网络动力学：超图的拓扑结构仅仅是通过矩阵 A 对系统进行缩放。

总体而言，我们的Kuramoto振子动力学示例表明，超图是否可以投影到低阶系统取决于每个超边所支持的动力学形式：如果超边上的动力学可以重写为低阶函数的线性组合，那么动力学就是可约简的。更一般地，对于某些函数形式，非线性动力学总是可以简化为低阶超图系统。在附录S1中，我们展示了动力学必须具备的类似线性的特性，以便能够被约简为网络动力学系统。

在接下来的内容中，我们通过区分超图的拓扑阶和动力学的动态阶来形式化这种动力学约简。结合拓扑结构和动力学，我们得到了一个超图动力学系统，其有效阶数不能大于这两个阶数的最小值。

动力学阶和有效阶

许多最近文献中考虑的常用超图动力学过程可以直接用上述形式表示，例如参见文献[6,10,11,14,17]。例如，如果定义 并且：

这种动力学具有 的动力学阶，因此动力学可以分解为所有超边上的成对函数之和，从而有效地成为网络动力学。总体而言，求和顺序与正弦函数的顺序交换是使方程1和2的动力学阶不同的关键，从而导致系统的有效阶不同。

尽管从概念上很有用，但如本节所述推导有效阶需要知道动力学的解析形式。因此，在下一节中，我们提出了一种通过推导超图神经网络模型来学习相应函数的方法。利用这种计算模型，我们可以从数据中学习动力学，从而隐含地学习系统的有效阶，而无需事先知道动力学的函数形式。

从数据中学习局部动力学和有效阶

在本节中，我们提出了一种方法，直接从数据中学习系统的局部动力学，从而确定系统的动力学阶和有效阶。

学习超图动力学系统

在我们对超图动力学系统的表述中，每个超边的节点值通过一个可能的非线性函数 进行转换，并通过将这些更新值汇总回节点来完成更新。基于这一框架的精神，我们引入了一种基于神经网络的动力学学习方法，用于超图上的动力学。我们称这一框架为超图动力学图神经网络（HyDy-GNN）。除了在“方法”部分更详细描述的一些技术性调整外，HyDy-GNN与我们动力学的解析表述之间的主要区别在于，在HyDy-GNN中，我们使用多层感知器（MLPs）来近似更新函数。因此，我们不需要事先指定动力学的函数形式，而是可以完全从观测数据中学习动力学，因为MLPs是通用函数逼近器，能够以任意精度近似任何函数。我们在实验中使用的MLPs的技术细节可以在附录S3中找到。

寻找有效的模型阶数

利用上述概述的学习范式，我们拟合了一系列阶数递增的 HyDy-GNN，其中即，我们拟合了最高到 k 阶的模型）。请注意，如果所选模型阶数小于系统的实际动力学阶，那么 HyDy-GNN 将无法很好地拟合，因为 的 MLP 无法很好地近似由较大超边诱导的非线性动力学。然而，如果模型阶数等于或大于系统的动力学阶，那么动力学将被准确地学习。由于我们将拓扑阶 k 作为上限，动力学的实际（先验）动力学阶可能大于 。然而，如果我们找到了一个有效阶小于拓扑阶的模型，这意味着我们找到了一个能够充分近似真实动力学的模型阶。这可能发生在动力学本质上可以简化为更低阶的情况，即其动力学阶小于超图的拓扑阶。

因此，为了找到有效的模型阶数，我们需要找到一个既能充分近似动力学又尽可能小的模型阶。根据所考虑的应用场景，选择这样的阶数有多种可能的方法。例如，我们可以通过手动检查或为动力学的近似质量设置一个特定的近似阈值，并选择达到该阈值的最小模型阶。

虽然这不是我们这里工作的主要重点，但我们在下面讨论了一种简单方案，以自动化这一模型选择过程。具体来说，我们定义了一个模型修正的性能评分，用于选择在给定数据集上产生准确结果的最低阶 的模型，如下所述：

我们在附录S4中提供了关于这个模型修正性能评分推导的更多细节。

结果

在本节中，我们展示了如何使用我们的框架从数据中学习超边上的更新函数。然后，我们展示了如何利用这些结果推断超图动力学系统的有效阶。

数据集

我们在合成的Erdős-Rényi超图和一个真实高中学生接触模式的超图（SocioPatterns数据集）上进行实验。这两种超图的拓扑阶均为 k = 4 。在这些超图上，我们模拟了四种常见的线性和非线性模型的高阶变体：Kuramoto动力学（同步）、易感者-感染者（SI）动力学（传染病传播）、多边共识（MCM）动力学（意见动力学）和线性扩散。对于这四种动力学，我们考虑了动力学的不同变体，其中我们将更新函数 限制为最多p-元更新函数的和。超图和动力学生成的详细信息可以在“方法”部分找到。

我们研究了两种可能在现实世界中出现的情景：在第一种情景（I）中，我们观察特定时间点的状态向量及其导数。在第二种情景（II）中，我们观察一组动力学的轨迹。

对于这些设置中的每一个，我们创建了一个相应的数据集，并将其分为训练集和测试集。对于设置（I），每个数据集包含500个独立采样的随机初始状态向量以及该点动力学对应的导数（详见“数值实验中考虑的数据集和动力学”部分）。这些数据可以直接用于通过经验风险最小化（见方程11）训练HyDy-GNN。对于设置（II），我们生成了25条轨迹，其初始状态向量是均匀采样的（具体细节见“数值实验中考虑的数据集和动力学”部分）。从随机初始条件出发，我们通过简单的前向欧拉方案模拟了100个时间步，时间步长为 。从这些轨迹中，我们通过在轨迹的每个时间点用简单的前向时间差分近似时间导数 ，为我们的模型提取一个训练序列。因此，我们创建了一个包含2500个状态向量及其相关导数的训练集，可以用这些数据来训练我们的模型。我们指出，与情景（I）不同，情景（II）中的训练样本不是独立的，因为它们通过动力学的控制方程在时间上耦合。为了区分这两种情景，我们将第一种设置（I）中的训练数据称为基于点的训练数据，第二种设置（II）中的训练数据称为基于轨迹的训练数据。

数值实验：学习更新函数

数值实验：学习超图动力学系统

合成数据

我们发现，只有足够高阶的HyDy-GNN才能很好地近似动力学的长期行为，这也得到了（A）和（C）中结果的证实。尽管基于轨迹的训练集是从较少的不同超图拓扑中得出的（只考虑了25个不同的超图，而不是基于点的数据集中的500个），但它为轨迹提供了一个更好的近似，例如，比较（B）和（D）中 = 4 和 p = 3 的情况。这是因为基于轨迹的数据集偏向于动力学的长期行为。因此，它更适合于这种类型的长期轨迹预测。总体而言，结果证实我们的方法能够学习有效阶，无论是基于点的还是基于轨迹的训练集，且得到的模型能够捕捉系统的长期行为。

真实世界数据集

与合成数据集的结果类似，图4中的结果表明，利用我们的方法，我们还可以学习在真实世界高中学生接触超图上展开的动力学的有效阶。在这里，我们考虑了在接触数据集上预期会出现的三种相互作用动力学：传染病传播（SI）、意见动力学（MCM）和扩散（例如，思想或信息的扩散）。对于扩散（一种线性动力学），推断出的有效阶正确地被确定为2 。对于像传染病传播和意见形成这样的非线性动力学，表现最佳的模型对应于有效阶 = {2, 3, 4} ，而不是超图的阶。这突显了在处理真实世界超图结构时，仔细考虑动力学类型的重要性。尽管这并不总是成立，但在许多情况下，低阶超图足以捕捉相关的动力学。我们的方法使研究人员能够从他们感兴趣的具体数据集中推导出他们可以简化模型的程度。

我们提出了一个框架，用于推断超图动力学系统，权衡拓扑复杂性和动力学复杂性。我们利用这个框架，基于观测数据，从解析和数据驱动两个角度为给定的动力学推导出一个有效的超图动力学系统。特别是，利用神经网络作为一种灵活的方式来近似局部相互作用动力学，我们能够准确地学习超图动力学，并在尊重观测到的动力学的同时降低超图的阶。在这种情况下，找到一个小于超图拓扑阶的有效动力学阶表明，我们可以“修剪”一些超边，使其阶数更小，因为它们对特定的动力学并不起作用。更具体地说，相关超边被所有 阶子边的集合所取代，然后动力学被重写，使其明确地在较小的子边上演化。从模型复杂性降低的角度来看，这是非常有趣的。此外，学习到的模型能够预测动力学系统的长期行为。

我们相信，我们的方法论具有广泛的应用潜力，并为一个目前研究相对较少的研究问题提供了起点，即在超图、单纯复形和细胞复形等高阶领域中，拓扑复杂性和动力学复杂性之间的权衡。未来的研究需要进一步探索（超图）拓扑、动力学和有效阶之间的联系。

方法

在本节中，我们更详细地形式化了我们的超图动力学系统模型。特别是，我们从拓扑结构和局部动力学两个方面来考虑动力学。系统的拓扑结构决定了系统中哪些组成部分在局部相互作用。动力学，特别是边上的更新函数，决定了这些组成部分如何相互作用（更新），而这些局部相互作用如何在全球范围内组合（投影）则再次由拓扑结构决定。

得到的向量对应于将初始状态向量提升到更高维的状态空间；因此，我们将这个矩阵称为提升矩阵。提升矩阵决定了系统中哪些组成部分相互作用，由其非零条目表示（见图5）。

动力学

在完成这个通常是非线性的更新步骤后，更新通过提升算子的转置被投影回节点，这仅仅是对节点所属的所有超边上的更新进行求和。这一过程如图5所示。这导致了以下全局动力学：

HyDy-GNN的技术细节

数值实验中考虑的数据集和动力学

我们在合成（Erdős-Rényi超图）和真实世界拓扑结构（高中学生接触模式数据集）的动力学数据集上进行实验。我们假设图的拓扑结构以邻接表的形式给出，从中我们提取提升算子。基于这种拓扑结构，我们模拟特定的动力学过程。

在本工作中，我们特别关注网络科学中常见的四种线性和非线性动力学：Kuramoto动力学（同步）、SI动力学（传染病传播）、MCM（意见动力学）和扩散。我们在这里根据定义3的符号，为一般阶数 p 定义这些动力学。

同步（Kuramoto振子动力学）

Kuramoto模型（35）已被应用于各种相位振子的同步现象（36），范围从电力网络（37）到大脑活动（38），并且已有几项研究致力于将其推广到超图（39）。节点状态 对应于振子 i 的相位，而（超）边表示振子之间的耦合：

传染病传播（易感者-感染者模型）

传染病的传播可以通过简单的SI（易感者-感染者）模型来描述。节点状态 Xi 表示节点i的感染率，而（超）边侧代表人与人之间的感染率。

意见动力学与强化（MCM）

MCM（多边共识模型）用于模拟具有群体效应的意见形成过程。这些效应通过一个非线性函数来体现，该函数对模型中的共识项进行缩放。根据其形式，缩放函数可以捕捉超边成员之间的强化效应，我们在这里特别选择模型的一个方面——MCMI模型，它模拟了同质性

线性共识动力学（扩散）

自主智能体之间寻求某种合作时的信息交换可以通过这种简单的共识协议来捕捉（41）。这些链接描述了节点之间的相互影响。其应用范围从社交网络中的信息传播到最优控制

动力学的数值积分

合成和真实世界的超图

对于我们的合成超图，我们使用了一组包含20个节点的500个Erdős-Rényi超图。任意两个节点之间创建边的概率为0.1，任意三个节点之间创建超边的概率为0.01，任意四个节点之间创建超边的概率为0.001。超图是通过xgi包（42）根据文献（43）生成的。

作为真实世界的超图示例，我们使用了一个从高中学生佩戴的可穿戴传感器记录的交互中构建的时变高阶数据集的静态版本（44, 45）。该超图包含327个节点和7818个超边，平均大小为2.3个节点，最大大小为5。然而，由于数据集中只包含7条大小为5的超边，我们将超图简化为考虑最多4个节点的超边，从而得到一个4阶超图。最终的数据集包括222条四节点超边、2091条三节点超边和5498条二节点超边。在这个超图上，我们模拟了可以在接触数据集上发生的所有三种社会动力学：传染病传播（SI）、带有同伴压力的意见动力学（MCM）以及扩散。

原文链接：https://www.science.org/doi/10.1126/sciadv.adh4053