基于二值动态数据的未知阶数超图两阶段重构

《Knowledge-Based Systems》：Two-stage reconstruction of hypergraphs with unknown orders from binary dynamical data

　　

- 重建未知阶数且无结构假设的高超图被视为一项挑战。
- 提出了一种新颖的两阶段直接重建方法用于高超图重建。
- 基于直接方法，提出了一种新的两阶段优化重建方法。
- 对比实验证明了优化方法的优越性能。
- 实验表明优化方法表现出令人满意的鲁棒性。

**引言**

复杂网络在自然和社会中无处不在，例如微生物相互作用网络[1]、代谢网络[2]、社会网络[3]、[4]、交通网络[5]以及神经网络[6]、[7]。在探索复杂网络的过程中，已形成一个基础共识，即底层拓扑结构在个体和集体行为的演化中起着关键作用。不同的结构特性必然导致不同的动力学过程和演化范式[8]、[9]、[10]。然而，在现实中，大多数复杂网络的显式拓扑结构仍然不可观测，只有节点的动力学行为数据可以获取[11]、[12]、[13]、[14]。因此，从有限的个体动力学观测中逆向重建复杂网络的完整拓扑结构是网络科学中的一个基本挑战。

在过去的二十年中，已开发了多种方法来重建常规成对网络的拓扑结构。当节点动力学在成对网络中完全未知时，可以应用格兰杰因果分析[15]、[16]或传递熵方法[17]、[18]对观测时间序列数据推断节点间的有向关系。当节点动力学的函数形式已知但其相关参数未知时，网络重建技术可大致分为统计推断框架[19]、[20]、[21]和基于网络稀疏性的优化方法[22]、[23]。前者将网络结构视为潜在变量，通过状态演化的生成模型构建似然函数，然后通过最大化似然函数来重建网络参数。后者将节点动力学方程转化为以网络结构为参数的线性方程组。利用复杂网络的内在稀疏性，这些基于压缩感知[24]、[25]、[26]、[27]的方法将线性方程组的求解转化为带有其他附加惩罚项的L1范数约束优化问题。

除常规成对交互外，许多真实世界网络表现出多体交互[28]、[29]、[30]。在网络科学中，高超图[31]已成为表征此类群体交互的经典范式。早期的高超图重建研究集中于一类特殊的高超图——单纯复形[32]，通过最大似然[33]、[34]来重建二体交互和三体交互。在此基础上，使用贝叶斯推断[35]重建了单纯复形中的四体交互。甚至可以通过数据驱动的似然优化来重建全阶单纯复形[36]。然而，单纯复形的固有结构约束使其无法直接扩展到一般高超图。对于广义高超图的重建，压缩感知类优化已被应用于单层[37]和多层结构[38]，但这些方法受限于小规模和低阶数，当参数维度急剧膨胀时会失效。为缓解维度灾难，提出了一种逐步重建方法[39]。尽管它在每一步中降低了计算复杂度，但它需要高阶交互对低阶交互的严格结构依赖，类似于单纯复形的情况。

总之，大多数现有的高超图重建研究需要事先知道高超图的准确阶数。事实上，高超图中群体交互的基数在事先是不确定的。此外，在少数放宽阶数先验知识要求的研究中，引入了其他限制性结构假设（如[39]）。这些假设在大多数一般高超图中很少成立。此外，高超图重建本身面临着维度爆炸的瓶颈。如何在高超图阶数完全未知的情况下有效降低重建的计算复杂度仍然是一个关键且尚未解决的问题。

为应对这些挑战，本文设计了两种不同的两阶段重建方法——直接方法和优化方法——专门针对未知阶数且无结构预设的一般高超图。以逐步方法[39]作为基准对比，在合成和实证高超图上进行了大量实验以评估所提出的两阶段直接方法和优化方法的重建性能。此外，还对优化方法进行了鲁棒性分析和超参数敏感性分析。本文的主要贡献如下：

- 本文研究了没有先验知识的条件下的高超图重建：最大阶数和任何超边的结构假设。
- 提出了一种两阶段直接重建方法。通过将无权高超图投影到常规加权网络，该方法利用大数定律和压缩感知来重建未知阶数的高超图。
- 开发了一种两阶段优化重建方法。基于直接方法，优化方法再次利用大数定律来优化激活概率，并在通过压缩感知求解之前压缩重建方程。
- 在第三阶合成高超图上的实验表明，所提出的优化方法不仅比直接方法和逐步方法取得了更高的重建精度和更低的计算复杂度，而且还表现出对传输速率、随机扰动和高超图阶数估计偏差的一定程度的鲁棒性。
- 在更大规模的第二阶合成和实证高超图上的实验表明，优化方法对超参数θ?、ε?、θ?和ε?不敏感。

**章节摘要**

**预备知识**

为了便于后续分析，本节简要概述了本文中使用的基本概念和方法。包括高超图的基本定义、二值动力传播机制以及压缩感知的核心原理。

**方法论**

本节针对第2节引入的无向无权高超图H开发并研究了其重建方法。假设H中所有节点的动力学行为均可观测，每个节点在任何时刻的状态都是精确已知的。

根据2.1节的描述，当二值动力传播过程在H上传播时，任意I状态节点i在时刻t的激活概率P?(t)可以表示为P?(t) = P(S?(t+1)=1 | S?(t)=0) = …

**实验**

为确保全面性和通用性，两阶段直接重建方法和优化方法在合成和实证高超图上均进行了实验。详细的实验流程如下：

(i) 通过不同的生成模型构建三种类型的合成高超图，并通过三个实证数据集建立实证高超图；

(ii) 使用蒙特卡洛（MC）方法在每个高超图上模拟二值动力传播过程以生成二值…

**结论**

近年来，复杂网络重建研究已经从成对交互转向高阶交互。高超图是表征高阶交互的经典范式。目前，大多数高超图重建研究依赖于高超图阶数事先已知或高阶超边对低阶超边表现出结构依赖的假设。然而，这两个假设在大多数一般高超图中并不严格成立。

**作者贡献声明**

郭一飞：论文撰写——审阅与编辑，论文撰写——初稿撰写，可视化，软件，方法论，形式化分析，概念化。涂丽岚：论文撰写——审阅与编辑，资金获取，形式化分析，概念化。潘烨：论文撰写——审阅与编辑，软件，方法论。赵秋悦：论文撰写——审阅与编辑，方法论，形式化分析。

**利益冲突声明**

作者声明他们没有已知的竞争性经济利益或个人关系可能影响本论文中报告的工作。

**致谢**

本工作得到了中国国家自然科学基金（资助号72031009）和湖北省冶金加工系统科学重点实验室（资助号Z202501）的支持。

郭一飞 | 涂丽岚 | 潘烨 | 赵秋悦