SGRDN-Data学会了图反应-扩散网络的简化方法
《Journal of Computational Science》:SGRDN-Data learned sparsification of graph reaction–diffusion networks
【字体:
大
中
小
】
时间:2026年04月15日
来源:Journal of Computational Science 3.7
编辑推荐:
阿比谢克·阿贾亚库马尔 | 索米延杜·拉哈
印度科学研究所计算与数据科学系,班加罗尔 560012,印度
摘要
图稀疏化是计算机科学和应用数学中的一个研究领域。图稀疏化通常旨在减少网络中的边数,同时保持图的特定属性,如割集和子图计数。计算图的最稀疏割集被认为是NP难
阿比谢克·阿贾亚库马尔 | 索米延杜·拉哈
印度科学研究所计算与数据科学系,班加罗尔 560012,印度
摘要
图稀疏化是计算机科学和应用数学中的一个研究领域。图稀疏化通常旨在减少网络中的边数,同时保持图的特定属性,如割集和子图计数。计算图的最稀疏割集被认为是NP难问题,现有的稀疏化算法可以在几乎 quadratic 的运行时间 O(n2+?) 内生成线性大小的稀疏化器。因此,获取稀疏化器可能是一项计算要求较高的任务,其复杂性取决于所需的稀疏程度。我们提出了 SGRDN 方法,将稀疏化技术扩展到复杂的反应-扩散系统。该方法试图稀疏化图,以便在结果结构中严格保留原有的反应-扩散动态。通过选择性地考虑一部分轨迹,我们将网络稀疏化问题框架化为降阶模型(ROM)空间中的数据同化问题,施加约束以在扰动下保持拉普拉斯矩阵(L=D?A)、度矩阵(D)和邻接矩阵(A)之间的差异。我们推导出针对扰动拉普拉斯矩阵的计算效率高的特征值和特征向量近似值,并将这些近似值作为谱保持约束纳入优化问题中。为了进一步验证该方法的广泛适用性,我们在神经常微分方程(Neural ODEs)上进行了额外实验,SGRDN 成功实现了参数的稀疏化。
引言
现代深度学习框架利用循环神经网络解码器和卷积神经网络,其特点是参数数量众多。在这些网络中找到冗余边并重新调整权重非常有用;例如 [1] 中的研究。另一种思路是从数据中学习微分方程 [2]、[3]、[4],其中数据生成部分通过使用稀疏神经网络实现。这类工作在流体动力学等领域有应用,参见 [5]。减少神经常微分方程(ODENets)中的参数数量也是本工作的另一个动机。我们定义了一个图 G=(V,E,w),其中 V 和 E 分别表示图的顶点集和边集,w 表示权重函数,即 w:V×V→R。图的稀疏化器旨在减少图中的边数,使得新的重新加权图 G?=(V,E?,w?) 实现特定目标,如保持拉普拉斯矩阵的二次型、割集和子图计数。例如,在谱稀疏化器的情况下,我们有 xTLx(1+?)≤xTL?x≤(1+?)xTLx?x∈Rn,其中 |V|=n,?∈(0,1)。
割集稀疏化的概念由 Karger [6]、[7] 提出,它生成每个割集都被近似的加权子图。该方法涉及以概率 p 采样图的个别边;得到的稀疏化器大小为 O(pm),其中 m=|E|,即图的边集的基数。基于非均匀边采样的改进工作见 [8]、[9]。还有其他类型的稀疏化器可以保持子图计数,如 [10] 中所述。Spielman 和 Teng 提出了一种更高级的稀疏化形式,称为谱稀疏化器 [11]。谱稀疏化器近似图拉普拉斯矩阵的二次型。这类稀疏化器有助于求解线性方程组 [11]、[12]。得到的稀疏化图的边数近似为 O(nlog(n)c),其中 c 是一个较大的常数。在他们的研究中,Spielman 和 Srivastava [13] 证明可以为任何具有 n 个顶点和 O(nlog(n)?2 条边的图构建稀疏化器。此外,他们还提出了一种线性算法来实现这一目标。Goyal、Rademacher 和 Vempala [14] 提出从随机生成树创建割集稀疏化器。Batson、Spielman 和 Srivastava [15] 使用确定性算法在 O(mn3?2) 时间内构建了边数为 O(n?2) 的稀疏化器。Fung 和 Harvey 设计了一种基于边连通性逆的边采样算法来生成割集稀疏化器 [16],他们还描述了从均匀随机生成树生成割集稀疏化器的方法。在 [17] 中讨论了一种基于元学习的图稀疏化方法。虽然文献中提出了各种针对不同目标的图稀疏化技术,但在稀疏化过程中保持系统动态行为的方法尚未得到充分探索。
在本节中,我们回顾了专注于保持图上描述的动态系统的文献。由于网络中的时空动态能够模拟复杂的相互作用系统,因此在物理学、生物学和神经科学等领域受到了相当大的关注 [18]。这类网络由相互连接的组件组成,它们的局部相互作用共同产生了丰富的动态行为。在这种情况下,时空传播指的是动态效应在网络节点和边之间的传播方式。在特定位置引入的局部扰动或刺激可以通过网络连通性影响远距离区域,从而产生非平凡的全局响应。这种传播机制支撑了广泛的实际过程,在物理、生物和神经系统的应用中起着核心作用。因此,图结构的稀疏化可以在保留其基本动态特性的同时实现这些系统的有效模拟。Cencetti、Clusella 和 Fanelli [19] 的论文探讨了在保持图动态特性的同时改变网络拓扑的方法;新获得的网络与原始网络是等动态的。Kumar、Ajayakumar 和 Raha 在他们的工作中 [20] 提供了寻找复杂网络稳定划分的数学条件,并提供了一个启发式算法。图划分不会改变图的边权重;然而,它可能导致边的删除。这项工作表明,具有足够网络连通性的受限内部补丁动态可以确保子网络在其共存平衡点周围的稳定性。
我们文章的贡献可以总结如下:
1. 在第 6 节中,我们介绍了用于图上稀疏化反应-扩散动态系统的 SGRDN 算法。为了实现这一目标:
•我们在 5.1.2 节提出了拉普拉斯矩阵的特征值和特征向量的估计方法。
•本节阐述了使用这些估计方法的优点。
•第 6.1 节描述了该过程的复杂性,并在图 8(a)、8(b) 中进行了实证验证。
2. 在定理 5.4 中,我们讨论了在扰动下对拉普拉斯矩阵的特征值和特征向量进行近似的估计界限。
•表 2 展示了这些估计在实践中的有效性。
3. 在第 7 节中,我们对多个图数据集进行了广泛的 SGRDN 算法实验。
•不同图数据集上获得的稀疏程度显示在表 3.4 中。
虽然本工作的主要焦点是基于图的反应-扩散系统,但我们在附录中还展示了 SGRDN 自然适用于神经常微分方程(Neural ODEs),突显了其更广泛的适用性。在附录中,我们展示了如何将 SGRDN 算法适配用于生成稀疏的 ODENets。
文章的结构如下:我们首先介绍谱图理论的背景材料。下一节提供了图上反应-扩散系统的简要概述。我们简要介绍了可以应用于参数估计问题的伴随数据同化方法。在后续章节中,我们介绍了图上化学布鲁塞尔反应-扩散系统的降维向量场,并讨论了各种性能指标。下一节提出了确保等动态行为所涉及的挑战;最具挑战性的是迭代获得扰动拉普拉斯矩阵的特征对的良好估计。我们在下一节探讨了特征对的近似及其有效性,然后制定了优化问题及其挑战。我们在真实世界图上展示了实验结果,以证明我们方法的有效性。在附录中,我们展示了如何使用该框架生成稀疏的神经 ODENets(见表 1)。
**部分内容**
**拉普拉斯矩阵:**
无向加权图 G=(V,E,w) 的拉普拉斯矩阵,其中 |V|=n,|E|=m,权重函数 w:V×V→R,定义为 Lu,v=dv?wu,v;如果 u 和 v 相邻,则 fu=v?wu,v;否则 fu=0。dv=∑u~vw(u,v) 表示顶点 v 的度。
**关联矩阵:**
具有给定边方向的图的关联矩阵 Bm×n 定义为 Be,v=1 如果 v 在头部,否则为 ?1 如果 v 在尾部,否则为 0。具有权重 w?i=γ?iwi(i=1,2,…,m)的图的拉普拉斯矩阵可以表示为 L?=BTW1/2diag(γ?)W1/2B,其中 γ?∈Rm。
**涉及图的动态系统:**
反应-扩散系统的一般形式如下,如 Cencetti 等人的工作 [19] 所示。网络中的每个节点 i 都有一个 m 维变量 ri(t)∈Rm,表示其在时间 t 的活动。ri 随时间的演变遵循一组特定规则,从初始状态 ri(0) 开始,如下所述:dridt=F(ri)+K∑j=1nAijG(rj?ri),i=1,2,…,n。这里,F 表示反应组分,其余项解释了扩散过程。
**数据同化的伴随方法:**
伴随方法允许我们高效地计算轨迹匹配目标相对于参数的梯度,即使系统动态是高维和非线性的。当对参数施加约束时,不建议使用无迹和扩展卡尔曼滤波方法 [29]。我们使用伴随敏感性方法进行参数估计 [30]。
**基于轨迹的模式保持和特征值近似的稀疏图构建方法:**
我们提出了 SGRDN 框架(图 6),用于无向图上反应-扩散系统的有效稀疏化。该流程整合了模拟、基于 POD 的模型降维和具有谱属性、连通性和权重非负性约束的优化问题,最终输出稀疏图。
**考虑无向图上复杂系统的一部分轨迹,目标是创建边稀疏化器(即边数较少的图)。**
**优化问题:**
我们提出的稀疏化框架涉及解决一个受限优化问题,本节讨论了其中的受限优化问题。在优化目标函数(方程 (13))中,我们通过引入涉及 ?1 范数的项来促进乘数的稀疏性。使用 ?1 项的优化通常会引入稀疏性。目标函数中的项 (T1) 旨在最小化不同时间观测值之间的差异。
**结果:**
SGRDN 已应用于来自实际案例研究 [41]、[42] 的一系列图。所考虑的图是无向图,并进行了初步处理步骤以消除自环。第 6 节中描述的算法中的参数经过广泛参数调整和优化后确定如下:α1=16log(|E|),p1,p2 = 50, Dx=0.1, Dy=1.4, N=2, ω=2, β1=10?2, τ=max(2.1,0.1dmin)/n×1,?=10?2, k=min(?n/5?,50) 和 np=?n/5?。
**扩展到神经常微分方程:**
为了展示 SGRDN 在反应-扩散系统之外的更广泛适用性,我们将该框架应用于神经常微分方程(Neural ODEs)。在这种情况下,模型参数被解释为加权边,稀疏化对应于学习保持输入-输出行为的紧凑 ODE 表示。我们的结果表明,SGRDN 成功实现了参数的稀疏化,同时保持了预测准确性。
**总结:**
我们提出了 SGRDN,这是第一个用于无向图上反应-扩散系统高效稀疏化的框架(图 6)。与关注静态结构或谱保证的经典稀疏化方法不同,SGRDN 将稀疏化问题表述为一个轨迹受限的优化问题,确保了降维图的等动态行为。所提出的框架结合了基于 POD 的降阶建模、使用观测轨迹的数据同化和非线性约束。
**作者贡献声明:**
阿比谢克·阿贾亚库马尔:撰写 – 审稿与编辑、原始草稿编写、软件开发、方法论、调查、形式分析、数据整理。
索米延杜·拉哈:撰写 – 审稿与编辑、监督、资金获取。
**利益冲突声明:**
作者声明他们没有已知的竞争财务利益或个人关系可能影响本文报告的工作。
**致谢:**
作者感谢 Dinesh Kumar 教授、S. Lakshmivarahan 教授、Arun Tangirala 教授和匿名审稿人的宝贵和鼓励性评论,这些评论有助于改进工作。这项工作部分得到了印度科学与工程研究委员会(Science and Engineering Research Board of India)的 MATRIX 授予的 MTR/2020/000186 资助。
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号