从动力学角度看高阶网络能否被简化|动力学|神经网络|算法|随机化|高阶网络

Reducibility of higher-order networks from dynamics

从动力学角度看高阶网络能否被简化

https://arxiv.org/pdf/2404.08547v4

实证复杂系统不仅可以由成对交互（pairwise interactions）来刻画，还可以由影响集体现象的高阶（群体）交互来刻画，范围涵盖从代谢反应到流行病。然而，高阶网络相比经典成对网络看似优越的描述能力——伴随着模型复杂度和计算成本的大幅增加，这对它们的应用构成了挑战。因此，建立一个定量方法来确定这种建模框架何时相对于成对模型具有优势，以及在何种程度上它能对实证系统提供有价值的描述，是至关重要的。在此，我们提出了一个信息论框架，该框架考虑了结构如何影响扩散行为，通过量化高阶交互的熵代价和可区分性，来评估其在保留相关功能信息的同时还原为低阶结构的可约性。实证分析表明，一些系统保留了本质的高阶结构，而在一些技术和生物网络中，它则坍缩为成对交互。利用受控随机化程序，我们研究了嵌套性（nestedness）和度异质性（degree heterogeneity）在这一可约性过程中的作用。我们的发现有助于目前致力于最小化复杂系统模型维度的努力。

引言

许多复杂系统表现出一种互连结构，该结构可以通过其组分之间的成对交互来编码。此类成对交互已被用于对生物、社会和技术系统建模，提供了一个强大的描述和预测框架[1–6]。最近，高阶结构模式和动力学行为的分析作为对群体交互建模的强大框架吸引了研究界的关注[7–10]，其应用范围从神经科学[11, 12]到生态学[13]和社会科学[14, 15]，凸显了新现象的出现和非平凡的集体行为[16–21]。

高阶网络比成对交互编码了更多信息：例如，代谢反应通过任意数量的试剂和反应物之间的群体交互来描述更为真实，这捕捉了若仅考虑成对交互的并集将会丢失的信息。然而，这种建模灵活性是有代价的：新数据需要被充分记录并存储为群体交互而非成对交互，并且需要开发新的分析[22–25]和计算[26–28]工具。此外，随着考虑的群体交互规模变大，这些工具的复杂度和计算成本呈指数级增长。

因此，理解在何种条件下需要优先采用高阶表示而非经典成对表示至关重要，并且是否可能设计一种定量程序来确定哪种表示能对实证系统提供合适的描述。

一条研究路线从“行为”的角度处理高阶交互，旨在刻画多元时间序列中的统计依赖性[29–33]。在此框架内，信息论方法已表明，此类依赖性可分解为来自不同交互阶数的贡献[34]。与此同时，初步研究揭示，高阶行为与机制（即结构和动力学）之间的关系是微妙的，且通常是非平凡的[10, 35]。如何在给定其上的动力学的情况下，化简一个高阶结构（及其支持的动力学），仍然是一个开放问题。

近十年前，当时间数据和分类数据[36–38]的出现使得复杂网络的多层表示成为可能时，也面临过类似的挑战[39]。对于这些表示，一种信息论方法被用于表明，并非所有层或交互类型都具有同等的信息量：某些信息可以被丢弃或聚合，以降低模型的整体复杂度，同时不牺牲其描述能力[40, 41]。尽管多层网络与高阶网络不同，但这种基于密度矩阵形式体系[42]的方法为当前情况提供了一个良好的候选方案。事实上，该思想在精神上类似于计算机科学中广泛采用的信息压缩算法：通过利用数据中的规律性，可以构建一种压缩表示，以优化用模型描述数据所需的比特数（即描述长度）以及编码模型本身所需的比特数。广义上讲，这种基于贝叶斯推断的最小描述长度原则，允许通过一种原则性的正则化项在最小化模型复杂度的同时最大化模型精度[43–45]。类似的方法也已被用于对复杂和多路网络进行粗粒化[46–48]。

在此，我们立足于这一长期的研究路线，提出一种压缩具有高阶交互的系统的方法，同时兼顾描述复杂数据的能力以及由模型复杂度带来的代价。具体而言，我们确定了一个合适的阶数，在此阶数内需要考虑交互，以获得系统的一个简化且在功能上合理的表示。高于此阈值的更大阶数可以安全地被丢弃。形式上，我们通过将网络密度矩阵的概念[42, 49]推广以考虑具有多阶拉普拉斯算子[17, 50]的高阶扩散动力学，并推导出扩散时间作为交互阶数函数的有意义的重标度，来实现这一点。然后，我们计算一个依赖于所考虑最大阶数的信息论代价函数。通过最小化该代价函数，我们找到了数据的最优压缩，这反过来对应于在给定扩散时间下系统最简约的功能描述。在下文中，我们将此过程称为功能约化（functional reduction）。如果最优阶数为1，则高阶网络是完全可约的（至成对网络），而其可约性随最优阶数的增加而降低。

为此，我们考虑了两种替代但互补的视角：第一种基于Kullback–Leibler散度DKL(ρ|ρ0)，量化了从由密度矩阵ρ0表示的孤立节点集合构建一个由密度矩阵ρ表示的系统的熵代价；第二种基于Jensen–Shannon散度DJS(ρ|ρ0)，衡量了该系统与此类集合的可区分程度。这两种度量是互补的替代方案，在捕捉可约性方面各有独特的优势和局限性，因为它们强调了系统的不同信息方面。两者之间的选择取决于具体的应用和背景。为简便起见，在下文中我们展示基于前者的结果，并参考补充材料中基于后者的分析。

我们解析地推导了旋转不变结构的代价函数，揭示了可约性如何依赖于拉普拉斯特征值和扩散时间。然后，我们通过对合成网络进行广泛分析来证明我们方法的有效性，并调查了广泛真实世界高阶系统的功能可约性。我们的分析揭示：(i) 来自不同领域的数据集具有不同的可约性，(ii) 没有单一简单的结构度量可以解释可约性，以及 (iii) 通过使用随机化程序揭示了度异质性在可约性中的作用。该框架的优势在于，它通过一种很大程度上受量子统计物理学启发的形式体系，在网络分析和信息论之间架起了一座桥梁，该形式体系已在从系统生物学[51]到神经科学[52]的多种应用中得以验证，阐明了诸如网络稀疏性的涌现[53]和重整化群[54]等基本机制。

结果

A. 高阶网络的密度矩阵

同样值得指出的是，最优阶数应根据网络上的扩散动力学来解释，而非直接针对其结构。按照这一规定，代价函数中由编码的似然项保留了似然函数的所有特征 [42]，并且可以恰当地用于我们的目的。最后，我们将扩散时间 τ τ 下超图的可约性定义为

E. 随机结构

我们现在研究两种类型的异质随机结构的可约性：随机超图和随机单纯复形。为此，我们如上所述通过数值计算最优阶数——并指出根据我们的代价函数，它指的是最合适的那一个。

在单纯复形中，高阶超边强嵌套于低阶超边之中。因此，与低阶超边重叠的高阶边几乎不增加新的谱内容，从而产生可约性。相比之下，在随机超图中，或者当嵌套性通过打乱（shuffling）被破坏时，额外的超边通过引入真正新的局部连接而实质性地重塑了谱，从而降低了可约性。

我们同样测试了单一密度对可约性的影响（图 S3 和 S4）。一般来说，整体密度系数似乎不会显著影响可约性。

在长扩散时间下，可约性通常较低，因为期望仅对慢模式加权，这些模式捕捉了全局连接模式。在这种情况下，高阶边的影响更强：除非它们紧密嵌套在低阶边之中，否则它们会重连长程连接并移动最小特征值，使得截断谱与完整谱发生偏离。因此，得益于其嵌套结构，单纯复形保留了一定的可约性，但随机超图或打乱后的系综在长时间下保持不可约。

F. 现实世界的超图表现出多样化的可约性

我们现在通过考察来自 9 个类别的 60 个实证超图数据集，来研究现实世界超图的可约性：合著、面对面接触、药物、生态学、电子邮件、新陈代谢、政治、在线论坛标签和戏剧。

G. 可约性无法由单一简单度量解释

为了更好地理解可约性与超图结构之间的关系，我们计算了可约性与几种典型结构度量之间的皮尔逊相关系数。

为了完整性，我们在图 S8a-f 中报告了可约性与几个额外度量之间的相关性，并在图 S8g 中报告了这些度量之间的相关性。

H. 通过随机化将可约性与度异质性联系起来

我们首先关注嵌套性，作为帮助我们更好地理解实证数据集中可约性的第一个度量。嵌套性描述了低阶超边作为高阶超边子集出现的频率。单纯复形具有最大的嵌套性，因为它们满足向下闭合性，而随机超图的嵌套性最小，因为其不同阶的超边之间没有相关性。为了量化嵌套性，我们如上所述使用单纯形分数。

从嵌套性开始至少有三个原因：(i) 嵌套性是一种结构冗余形式，(ii) 在合成超图中，我们观察到以受控方式降低嵌套性会降低可约性（图 4），并且 (iii) 在实证数据集中，我们观察到嵌套性与可约性之间存在正相关。

如 [58] 所述，许多实证数据集的嵌套性并不高。此处考虑的数据集也是如此，唯一具有嵌套性的属于“接触”类别。因此，我们现在关注该类别，该类别也显示出一定范围的可约性值（图 5）。

我们在图 7 中展示了每种随机化过程 20 次实现的结果。首先，我们观察到正如预期的那样，所有三种过程都破坏了嵌套性（图 7b）：原始值（黑色）大多为 0.7（还有一个在 0.4 左右），但在所有通过配置模型（绿色）、节点交换（蓝色）和打乱（红色）随机化的结构中，嵌套性都接近于 0。正如预料的那样，打乱也导致可约性消失（图 7a），这与我们在合成结构中观察到的结果一致（图 4c-d）。然而，有趣的是，配置模型和节点交换在大多数时候保留了可约性数值。换句话说，在原本具有大嵌套性和可约性的超图中，如果度序列和分布也被保留，则可约性得以保留；否则就会被破坏。这表明，影响这些系统可约性的是包含在每一阶度分布中的信息，而不是嵌套性。

我们还检查了随机化对其他度量的影响：高阶度异质性比率 [17]、谱半径和最大高阶度（图 S9）。最大度作为度分布的另一个汇总统计量，显示出与度异质性相似但较不明显的趋势：当打乱破坏可约性时，它会下降但未被完全破坏。度异质性比率和谱半径在这种情况下没有表现出任何明显的趋势。

总之，结果表明，度分布及其汇总统计量——度异质性（以及在较小程度上的最大度）——是这些高度嵌套的“接触”数据集可约性的关键，而嵌套性和跨阶度相关性则不是。从谱失真的角度来看，这表明异质性——我们要知道它与拉普拉斯谱的宽度直接相关——在这些数据集中与随着阶数增加（在短时间下）没有太多新的谱内容相关联，从而使得低阶截断能够近似完整谱。将其他合适的随机化方法应用于其他类别的数据集（具有较低嵌套性的），可能有助于理清导致可约性的其他关键要素。有趣的是，过去的研究表明跨阶度相关性影响了超图上的动力学：低 DC（跨阶度相关性）能稳定同步 [17]，而高 DC 则促进了双稳态传染模型 [59]。

自然科学、社会科学以及工程学的所有领域，正面临着大量具有复杂结构的公开可用数据的涌入。这些数据使得构建物理、生物、社会学和技术等领域中系统的更详细、更强大的模型成为可能。此类模型中的一类是编码群体交互而非仅编码成对交互的网络：即高阶网络。高阶网络为对涉及两个以上单元间交互的系统进行建模提供了自然框架，例如具有代谢意义的化学反应或社会交互。然而，在数据收集时，这些数据通常——出于设计原因——被投影为成对交互，高阶信息不可避免地会丢失。通过保留这些信息，高阶网络有潜力为某些实证系统提供更可靠的模型。尽管如此，高阶网络也带来了全新的挑战：必须开发新的理论与计算方法，且随着交互阶数的增加，算法的复杂度呈指数级上升。因此，理解在何种条件下应选择高阶建模——或继续使用传统的成对模型——至关重要。在此，我们提出了一种处于统计物理学与信息论边界的方法，通过利用扩散过程，指导研究人员为其数据确定最合适的表示形式。我们通过将久经考验的密度矩阵形式体系推广至结合多阶拉普拉斯算子的高阶交互来构建该方法，其中扩散时间充当拓扑尺度。在此过程中，一个关键挑战在于推导出适用于不同交互阶数的、有意义的扩散时间标度关系。我们的方法基于最小化一个合适的代价函数，该函数同时编码了在给定模型下描述数据所需的比特数，以及描述模型本身所需的比特数（通过其熵进行估计），从而找到合适的群体交互阶数。高于最优值的阶数可以被安全地舍弃，因为它们仅提供了关于系统的冗余信息，同时根据我们的定义，还会增加模型复杂度及其分析的计算成本。正如预料的那样，我们此处定义的代价函数并不等同于真正的描述长度。事实上，密度矩阵是算子而非概率分布，且不存在针对它们的贝叶斯定理的直接推广形式。为部分克服这一局限，我们采用 Kullback–Leibler 散度来近似模型复杂度，从而定义出一个有效的正则化项。

根据上下文和目标，替代定义可能是合适的。例如，我们还考虑了一个基于 Jensen-Shannon 散度的代价函数，该函数量化了在给定阶数下，系统相对于成对情况与孤立节点气体的可区分程度。在这种情况下，结果并未一致支持需要高阶描述，这凸显了表观上的缺乏普适性源于每个代价函数能够捕获的特定特征（第五节）。因此，定义的选择将取决于具体的应用、背景和实际用途。这表明需要建立一种更有原则的方法。

此外，尽管我们在此考虑了无符号、无权重和无向的超图，但该形式体系可以直接推广以放宽所有这些条件（导致产生的密度矩阵不再是类吉布斯指数形式），这遵循了最近针对成对网络所做的工作[60]。

值得注意的是，我们表明并非所有系统都需要高阶模型来描述，并且即使在同类系统内部，也存在一定程度的变异性。我们首先通过在极其规则的情况下来测试该方法，在此情况下，通过解析计算得出所有阶数的代价函数都是平坦的。然后，我们解析推导了稍微复杂一点的情况的代价函数：超环。这揭示了可约性如何与系统的结构和动力学相关联，并明确依赖于扩散时间和多阶拉普拉斯特征值。特别是，谱失真，或者说截断阶数如何影响扩散，是关键所在。

然后我们将该方法应用于随机结构，结果表明随机超图是不可约的：即，通过考虑所有可能的交互阶数能最好地表示它们。这是可以理解的：在这些系综中，超边在阶内和跨阶之间都是最大不相关的，因此每个阶都引入了真正新的谱内容，若不丢失大量信息则无法压缩。相比之下，随机单纯复形是可约的，因为高阶边是以与低阶边相关的方式生成的。这种相关性在跨阶的拉普拉斯谱中引起了冗余，因此在给定的扩散尺度下，通常可以在不保留完整多阶结构的情况下捕捉到动力学。

然后我们将我们的方法应用于包含群体交互的实证数据集。在短扩散时间下，获得的可约性数值呈现出极大的多样性，这表明虽然高阶网络中编码的额外信息为某些系统提供了不可丢弃的基本局部信息，但其他系统可以用较低阶数适当表示，在某些情况下甚至仅用成对交互表示而不会有实质性损失。系统类别似乎对这些短时间可约性模式有显著影响，接触数据集通常比合著数据集等更具可约性。然而，在长扩散时间下，大多数数据集变得不可约，这与慢扩散模式捕捉全局模式的事实一致：在此，高阶边重塑了大规模连接，其贡献不可忽视。这在一般情况下被观察到，表明较短的扩散时间在实践中更具信息量。

相关性分析表明，可约性与许多简单的结构度量（如密度、最大度、嵌套性或度异质性）相关，但其中任何一个单独都无法解释可约性。为了进一步研究结构属性与可约性之间的联系，我们分析了接触数据集，因为它们具有较高的可约性。我们专注于嵌套性（一种高阶结构冗余的形式）、跨阶度相关性和度分布，设计了三种随机化策略以随后破坏这些结构特征中的每一个。通过这种方式，我们揭示了度分布（而非嵌套性或跨阶度相关性）在可约性中的作用。这一点特别令人感兴趣，因为过去这三种高阶结构度量已被联系到高阶网络中动力学的变化 [17, 59]。这也与多阶拉普拉斯谱的作用一致，已知该谱与结构的度相关联。

我们的结果挑战了那种普遍认为必须通过高阶动力学的视角来研究复杂网络数据的假设。事实上，存在完全可约和不可约的系统，在这两个极端情况之间还有一系列中间情况，这表明某些阶数对于描述实证系统可能是无关紧要或无信息量的。展望未来，从生物科学领域收集新的数据集以确定诸如连接组（connectomes）之类的复杂网络在何种情况下可以被视为可约或不可约，将是至关重要的。这将有助于理解在何种条件下高阶机制和行为对于这些系统的功能是必不可少的，正如当今通常假设的那样。

我们的工作也有助于当前对降低高阶网络模型 [61, 62] 以及更广泛地说复杂系统模型 [54, 63–66] 维度的日益增长的兴趣。特别是，耦合振子的相降维技术表明，当将（最初为成对的）耦合高维振子的动力学简化为简单的一维相振子时，高阶交互会自然出现 [63]。这与最近将复矩阵降为低秩矩阵的结果一致，在这种情况下高阶交互也会自然出现 [66]。一种重整化群方法也在实证数据集中识别出了重要的交互阶数，这些阶数并不总是成对的 [62]。与这些关注“机制”（即控制系统演化的结构和动力学规则）的方法相辅相成，其他方法如最大熵模型和高阶信息论度量则关注“行为”（即演化的结果，也就是来自这些系统的可观测量的时间序列）。有趣的是，几项此类研究反而表明，在某些条件下，成对模型足以描述包含高阶交互或机制的系统的行为（或统计特性）[31–34]。例如，在 [32] 中，作者表明截断至成对相关性的统计模型足以近似由具有高阶交互的自旋系统产生的完整多元统计，而在 [34] 中，作者分解了离散随机变量中不同阶的贡献。除了初步工作理清了高阶机制与行为之间的区别 [10] 并表明两者之间的关系很复杂 [35] 之外，人们对它们之间的关系知之甚少，这暗示了未来工作的一个有前景的方向。

检测冗余并利用一种方法来识别数据的压缩表示，有可能增强我们对实证高阶系统的理解，并有助于当前对这类网络降维的日益增长的兴趣 [61, 62, 66]。我们框架的主要优势在于，它建立在一个成熟的形式体系之上，该体系牢固地基于强关联系统的统计物理学。正如多层系统的情况 [40] 一样，我们认为值得注意的是，通过利用量子系统与高阶系统之间的形式类比来解决此类挑战是可能的，这可以进一步被利用以获得对复杂系统结构和功能组织的新见解。

方法

I. 超图的多阶拉普拉斯算子