稀疏图的谱密度近似方法：综述

《Journal of Computational Science》：Spectral density approximation methods for sparse graphs: A review

　　

摘要

抽象图提供了简单而强大的抽象，用于表示跨越不同领域（包括社交网络、生物学、经济学和技术）的复杂系统。在这些模型中，顶点代表实体，边代表它们之间的交互。谱密度（即图矩阵表示的特征值的经验分布）捕获了关键的全局结构和动态特性。它支持广泛的任务，包括社区检测、去噪、谱聚类和图比较。然而，谱密度的精确计算随顶点数量呈立方级增长，使得其在大型稀疏图中不切实际。为了解决这个问题，开发了许多近似方法，以精度换取效率。在本综述中，我们全面考察了现有用于近似大型稀疏图谱密度的技术，涵盖了经典和最新的发展。我们还提供了一个开源 Python 库，实现了所有审查的方法，可在 https://github.com/fujita-team/fastSpectralDensity 获取。

引言

图是研究社会、生物、经济和技术系统的基本抽象。通过将系统的各个组成部分表示为顶点，将它们的双边交互表示为边，我们可以应用数学工具来揭示系统的属性和行为。图的谱密度（即合适矩阵表示的特征值分布）是研究复杂系统最强大且原理化的工具之一。谱密度源于随机矩阵理论，提供了结构和动态特性的简洁特征。这使得诸如聚类识别 [1]、降维 [2]、图相似度度量 [3]、中心性计算 [4]、噪声减少 [5]、结构比较 [6]、聚类 [1], [7] 和局部化状态识别 [8] 等任务成为可能。

然而，谱密度的主要缺点在于计算矩阵表示特征值的计算复杂度。具体来说，时间复杂度随顶点数量呈立方级增长，而空间复杂度呈平方级增长。这一计算瓶颈使得大型图（拥有数千个顶点或更多）的谱密度精确计算变得不可行。为了克服这一限制，已经开发了许多近似方法 [1], [4], [9], [10], [11], [12], [13], [14], [15], [16]。

谱密度的近似方法可以大致分为四类：（1）数值方法，（2）消息传递方法，（3）基于随机游走的方法，以及（4）统计物理方法。
1. 数值方法基于矩阵 - 向量运算。
2. 消息传递方法使用闭合游走计数来推导谱密度的自洽方程。
3. 基于随机游走的方法获取矩并利用它们来估计谱密度。
4. 统计物理方法将谱密度建模为相互作用粒子系统，并使用腔方法推导自洽方程。

这四个家族借鉴了包括数值线性代数、随机矩阵理论、统计物理和图论在内的不同领域，并已应用于从社区检测到网络比较的问题。虽然之前的综述通常集中在单一领域（例如数值方法或统计物理方法）[14], [17], [18]，但本综述将四类方法统一在一个框架内。通过比较它们的理论假设、可扩展性和实际权衡，本工作为未来图谱分析的研究和应用提供了全面的路线图。

章节片段

谱密度
图 G=(V,E,ω) 是一个有序对，其中 V={1,2,…,n} 是包含 n=|V| 个元素的顶点集，E?V×V 是边集，ω:E→R 是权重函数。如果 ω(u,v)=ω(v,u),?(u,v)∈E，则图是无向的；否则，图是有向的。如果 ω(u,v)=1,?(u,v)∈E，则图是无权图；否则，它是有权图。此外，如果图中不包含环或相同顶点对之间的多重边，则该图是简单图。本工作专注于无向、有权（其中无权图是

方法
本节描述获取谱密度的方法、它们的优缺点以及最新发展。我们还为每种方法实现并提供了 Python 代码，这些代码是免费可用的。1 我们将方法大致分类为（1）数值方法，（2）基于消息传递的方法，（3）基于随机游走的方法，以及（4）统计物理方法。

结果与讨论
我们计算了两个网络的归一化拉普拉斯矩阵的谱密度：PGP 网络 2 和 poli-large 网络 3，以比较这些方法。PGP 网络代表 PGP 加密软件用户之间的信任关系 [40]，而 poli-large 网络源于大规模动态经济模型或政策模拟 [41]。表 1 总结了网络类型及其

结论
本综述探索了各种用于获取大型、稀疏、无向图谱密度的方法。谱密度在多个领域有应用，证明了其捕获图基本结构和动态特性的能力。例如，在网络科学中，它用于估计图中的社区数量 [1]，开发图的统计方法 [3], [7]，以及改进图神经网络 [43]。总之，谱密度是基础性的

CRediT 作者贡献声明
Grover E.C. Guzman: 写作 - 初稿，验证，软件，方法论，形式分析，数据整理，概念化。Peter F. Stadler: 写作 - 审阅与编辑，监督，资源，项目管理，调查，资金获取，概念化。Andre Fujita: 写作 - 审阅与编辑，监督，软件，资源，项目管理，调查，资金获取，概念化。

关于写作过程中使用生成式人工智能及人工智能辅助技术的声明
在准备本工作时，作者使用了 Grammarly 和 ChatGPT 来提高语言质量和可读性。在使用这些工具/服务后，作者根据需要审阅和编辑了文本和内容，并对发表内容承担全部责任。

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

致谢
本工作得到了 JSPS KAKENHI 项目号 JP25K15019，FAPESP 项目 2013/07699-0, 2023/18337-3, 2024/03261-4, 2024/09195-3 和 2025/22886-8，CNPq 项目 306811/2022-7, 402309/2024-3 和 443972/2024-9，CAPES（资助代码 001），亚历山大·冯·洪堡基金会，德国学术交流服务中心（DAAD 项目号 57598588），BlueMeme Inc. 以及 MEXT 合作项目计划，高深度组学与 CURE 医学研究中心倡议：JPMXP1323015486 由 Grover E.C. Guzman|Peter F. Stadler|Andre Fujita 使用 的支持。

Grover E.C. Guzman|Peter F. Stadler|Andre Fujita
圣保罗大学数学、统计和计算机科学研究所计算机科学系，Rua do Mat?o, 1010, S?o Paulo - SP, 05508-090, 圣保罗，巴西