🔬 applied physics

A Fast Algorithm for the Finite Expression Method in Learning Dynamics on Complex Networks

本文介绍了有限表达式方法（FEX）及其快速随机算法，该方法利用强化学习引导的二叉树，在将计算复杂度从 $O(N^2)$ 降低到 $O(N)$ 的同时，高效且准确地发现复杂网络上动力学的控制方程。

原作者： Zezheng Song, Chunmei Wang, Haizhao Yang

发布于 2026-01-22

📖 1 分钟阅读☕ 轻松阅读

原作者： Zezheng Song, Chunmei Wang, Haizhao Yang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一名试图破解一场大规模、混乱舞会中秘密规则的侦探。你可以看到成千上万的人（节点）在移动、碰撞，并随着音乐做出反应。你有一段记录他们动作的视频（时间序列数据），但你不知道歌曲、编舞，也不知道指导每个人下一步如何移动的具体规则。

你的目标是写下那套解释为什么每个人都在那样跳舞的精确“配方”或数学方程。这就是科学家们所称的复杂网络上的动力学学习（learning dynamics on complex networks）。

以下是该论文如何使用简单的类比来解释问题及其新解决方案——**有限表达式方法（Finite Expression Method, FEX）**的。

问题：一个过于庞大的谜题

在过去，试图弄清楚成千上万人的网络规则就像是在解一个谜题，其中每一个人都必须在同一时间与其他人进行交流。

数学噩梦： 如果你有 1,000 人，且每个人都与其他人互动，那么在每一时刻你都必须计算超过一百万次交互。对于大型群体来说，这在计算上是不可能的（这是一个 $O(N^2)$ 问题）。
“黑箱”问题： 旧的计算机方法（如深度学习）可以猜出舞步，但它们表现得像一个“黑箱”。它们能给你答案，但你看不出它们是如何得出答案的。你无法读懂它们创造出的那本“规则手册”。
噪声数据： 在现实世界中，你的视频录像可能会模糊、丢帧或带有静电噪声（噪声）。旧的方法经常会被这些现象搞混，从而发明出错误的规则。

解决方案：FEX（乐高建筑师）

作者引入了一种名为 FEX 的新方法。FEX 不仅仅是盲目猜测或使用黑箱，它是由乐高积木构建出规则的。

二叉树（蓝图）：
想象一个关于人如何移动的规则就像一棵树。
- 叶子是输入（比如“当前位置”或“速度”）。
- 树枝是简单的数学工具（比如“加”、“乘”、“正弦”或“指数”）。
- 树干是最终的方程。
  FEX 不仅仅是一次性猜测整个方程，它是一步步构建它的，决定哪个数学算子（乐高块）应该放在什么位置。
强化学习教练：
FEX 如何知道该挑选哪些乐高块？它使用了一个由强化学习训练的“教练”（神经网络）。
- 把这个教练想象成一个游戏玩家。它尝试构建一个树状结构。
- 如果这棵树能正确预测舞步，教练就会获得“奖励”。
- 如果失败了，教练就会学习并在下次尝试不同的积木组合。
- 随着时间的推移，教练会变得非常擅长挑选描述舞蹈的完美数学工具组合。
“随机采样”捷径（采样技巧）：
这是标题中“快速算法”的部分。
- 旧方法： 为了检查一个规则是否有效，你必须检查房间里每一个人的互动情况。这非常耗时。
- FEX 方法： 作者意识到你不需要同时检查所有人。你可以随机挑选一小群人（一个“批次”），检查规则在他们身上的表现，并以此更新教练。
- 类比： 想象你在测试一种新的汤的配方。你不需要品尝整锅汤（那太慢了），而是从随机的一个点舀起一勺。如果味道好，你就假设整锅汤的味道也是好的。通过这样做，FEX 将检查过程从检查数百万对交互缩减到仅检查几百对，使其变成了线性（更快）而非二次方（缓慢）的复杂度。

他们证明了什么？

作者在三种著名的复杂系统（模拟网络）上测试了这个“乐高建筑师”：

神经元放电（Hindmarsh-Rose 模型）。
神经元恢复（FitzHugh-Nagumo 模型）。
混沌振荡器（Rössler 模型）。

结果：

准确性： FEX 找到了这些系统的精确数学规则（即“配方”），即使在数据存在噪声或缺失部分的情况下也是如此。
可解释性： 与“黑箱”方法不同，FEX 给出了清晰、可读的方程。你确实可以读懂它找到的数学逻辑。
速度： 通过使用“采样技巧”，FEX 可以处理大型网络而不会导致计算机崩溃。
鲁棒性： 即使他们在网络中添加了虚假连接或删除了真实连接（模拟坏数据），FEX 仍然能找出正确的规则。

总结

简而言之，这篇论文提出了一种新的逆向工程方法，用于推导复杂系统的自然法则。他们没有选择盲目猜测或陷入缓慢的计算，而是构建了一个智能系统，它像组装乐高积木一样组装数学规则，由一个学习教练引导，并利用采样捷径极速完成任务。它让科学家能够观察混乱的现实世界数据，并从中提取出清晰、可理解的定律，从而解释整个系统是如何运作的。

技术摘要：一种用于复杂网络学习动力学中有限表达式方法的快速算法

问题陈述
本文旨在解决从时间序列数据中发现复杂网络系统中支配物理定律和动态相互作用的挑战。虽然数据驱动的方法在发现连续系统（例如偏微分方程，PDEs）的方程方面取得了进展，但从网络数据中提取动力学仍然十分困难，主要由于以下三个因素：

计算复杂度： 在一个拥有 $N$ 个节点的网络中，对完整的成对相互作用进行建模通常会导致 $O(N^2)$ 的复杂度，这对于大规模现实世界网络来说是难以承受的。
数据质量： 现实世界的网络数据通常具有噪声、稀疏性，并可能包含拓扑结构上的不准确性（缺失或虚假的链路）。
可解释性与先验知识： 现有的方法（如 SINDy，即稀疏非线性动力学识别）通常需要庞大的候选函数库，并且需要直接获取时间导数，而这些信息往往是无法直接获得的。深度学习方法（例如图神经网络，GNN）则缺乏可解释性，其功能类似于“黑盒”。

方法论：有限表达式方法 (FEX)
作者提出了有限表达式方法 (FEX)，这是一种利用由有限数学算子组成的二叉树来表示网络动力学的新方法。系统动力学被建模为：
$\frac{dx_i(t)}{dt} = F(x_i(t)) + \sum_{j=1}^N A_{ij}G(x_i(t), x_j(t))$
其中 $F$ 代表自动力学， $G$ 代表相互作用动力学。

FEX 的核心组件：

二叉树表示法： 动力学被编码为二叉树，其中的节点是数学算子（一元算子： $\sin, \cos, \exp$ ；二元算子： $+, -, \times$ ）。叶节点对输入变量进行操作，并带有可学习的权重和偏置。这种结构允许从一个较小的算子字典中生成复杂的函数组合，从而减少了对大型预定义库的需求。
基于强化学习 (RL) 的组合优化： 识别最优树结构被视为一个组合优化问题。控制器网络（一个全连接神经网络）通过策略梯度方法进行训练，以输出每个树节点处算子选择的概率质量函数。目标是采样能够最大化奖励得分的算子序列。
用于可扩展性的随机算法： 为了克服计算成对相互作用时的 $O(N^2)$ 瓶颈，FEX 集成了一种受随机批处理方法 (Random Batch Methods) 启发的随机算法。在优化损失函数期间，节点被分组为随机批次，仅在这些批次内计算相互作用。这使得结构发现阶段的计算复杂度从 $O(N^2)$ 降低到了 $O(N)$ 。
两阶段优化：
1. 粗调 (Coarse-tuning)： 控制器通过结合一阶（如 Adam）和二阶（如 BFGS）优化方法对连续参数进行训练，并利用随机批处理方法来提高速度，从而寻找高得分的算子序列。
2. 精调 (Fine-tuning)： 一旦确定了表现最优的候选结构，便使用完整的相互作用模型来优化系数，以确保高精度。

主要贡献

新颖的表示法： FEX 利用二叉树结构来表示动力学，允许使用极简的算子字典发现复杂的方程，这与依赖于广泛候选库的 SINDy 不同。
无导数估计： 该方法利用数值微分直接从带噪声的时间序列数据中估计时间导数，消除了现有方法中存在的对直接获取导数的依赖问题。
可扩展性： 通过在组合优化阶段采用粒子批次的随机选择，该算法实现了计算成本的线性缩放（ $O(N)$ ），使其在大型网络中具有可行性。
鲁棒性： 该方法旨在处理低分辨率数据、观测噪声以及拓扑结构的不准确性（缺失或虚假链路）。

实验结果
作者在三种经典的动力学系统（Hindmarsh-Rose、FitzHugh-Nagumo 和耦合 Rössler 振荡器）以及包括 Erdős-Rényi 和无标度网络 (Scale-Free) 在内的多种网络拓扑结构上评估了 FEX。

准确性： FEX 成功识别了所有测试动力学的正确函数形式和系数（相对误差通常 <1%）。
噪声鲁棒性： 在信噪比 (SNR) 为 40 和 45 的实验中，FEX 的表现优于基准方法（两阶段 SINDy 和 ARNI），后者在噪声条件下难以识别正确的项或会产生冗余项。
拓扑鲁棒性： 即使在随机增加或删除 15% 的网络链路时，FEX 仍保持了高准确度。
数据稀缺性： 该方法在仅有 5% 到 10% 原始时间序列数据的情况下依然有效。
效率： 计算时间与网络规模的对数-对数图显示，随机化 FEX 算法实现了线性缩放（ $O(N)$ ），而完整的相互作用模型则是二次方缩放（ $O(N^2)$ ）。

意义与主张
论文声称 FEX 提供了一个鲁棒、可解释且计算高效的框架，用于学习复杂网络上的动力学。通过将用于结构搜索的强化学习与用于可扩展性的随机优化相结合，FEX 解决了当前方法在计算成本、数据质量以及对大量先验知识需求方面的局限性。作者断言，这种方法能够发现现实世界复杂系统中的物理定律，而这些系统的支配方程此前是未知或未被充分探索的，这为分析从生物学到流行病学等领域的系统提供了一条路径。该工作也承认了目前的局限性，例如目前主要关注成对相互作用和确定性动力学，并指出向高阶耦合和随机微分方程的扩展是未来的潜在研究方向。

问题：一个过于庞大的谜题

解决方案：FEX（乐高建筑师）

他们证明了什么？

总结

技术摘要：一种用于复杂网络学习动力学中有限表达式方法的快速算法

类似论文