Bayesian Optimization on Networks
网络贝叶斯优化
https://arxiv.org/pdf/2510.27643
摘要
本文研究在被建模为度量图（metric graphs）的网络上进行优化的问题。受实际应用场景的驱动——在这些场景中，目标函数的评估代价高昂，或仅能以黑箱形式提供——我们开发了贝叶斯优化算法，该算法通过依次更新目标函数的高斯过程（Gaussian process, GP）代理模型，以指导查询点的选择。为确保代理模型能够契合网络的几何结构，我们采用基于度量图上的随机偏微分方程（stochastic partial differential equations, SPDEs）所定义的Whittle-Matérn高斯过程先验模型。除了针对足够光滑的目标函数建立优化的遗憾界（regret bounds）外，我们还分析了目标函数光滑性未知这一实际情形，并采用有限元方法表示Whittle-Matérn先验。数值实验结果表明，所提出的算法在合成度量图上优化基准目标函数，以及在通信网络上通过最大后验估计（maximum a posteriori estimation）进行贝叶斯反演方面均具有良好的效果。
关键词：贝叶斯优化；网络；度量图；Whittle-Matérn过程
1 引言
本文研究在由节点通过一维曲线相互连接而成的网络上进行优化的问题。典型应用包括：在道路或街道网络中寻找最拥堵的位置、确定电网中最可能发生故障的地点，以及识别生物神经网络中最活跃的区域等。我们探讨适用于目标函数评估代价高昂或仅以黑箱形式提供的全局优化问题的贝叶斯优化算法[38, 18, 43]。在贝叶斯优化中，使用目标函数的代理模型来决定在何处观测其函数值。高斯过程（GP）常被用作代理模型，但其性能对核函数（kernel）的选择十分敏感。本文针对定义在网络上的目标函数，开发并分析贝叶斯优化策略——在此类问题中，标准欧几里得核函数不再适用，必须采用能够适应网络几何结构的核函数。
我们将网络建模为紧致度量图（compact metric graphs），其由有限个顶点和有限条边组成，每条边均为具有有限长度的一维曲线[5]。为确保代理模型能够契合网络的几何结构，我们采用通过度量图上的随机偏微分方程（SPDEs）所定义的Whittle-Matérn高斯过程先验模型[13]。Whittle-Matérn模型具有两大优势。首先，它提供了一个便利的概率建模框架，能够通过可解释的参数控制函数的全局光滑性、相关长度尺度（correlation lengthscale）以及边缘方差（marginal variance）[41]。其次，该模型可通过有限元方法表示，从而获得协方差矩阵逆的稀疏近似，便于对后验代理模型进行高效的序贯更新[30]。
我们将Whittle-Matérn高斯过程先验模型融入两种主流的贝叶斯优化策略中：改进型高斯过程置信上界（Improved GP-UCB, IGP-UCB）和高斯过程汤普森采样（GP Thompson Sampling, GP-TS）；参见[15]及[40, 1]。在目标函数满足自然的Sobolev光滑性假设下，我们为这两种算法建立了收敛速率（即简单遗憾界）。此外，我们还分析了目标函数光滑性未知这一实际情形：此时采用有限元方法表示Whittle-Matérn核，由此产生的认知性（epistemic）与计算性（computational）核误设（kernel misspecification）将影响遗憾界。数值实验结果展示了所提出算法在合成度量图上优化基准目标函数的有效性，以及在通信网络上求解源识别贝叶斯反问题中的最大后验估计（MAP）时的性能。
1.1 相关工作
度量图（metric graphs）是用于建模由曲线连接节点的网络的自然框架。当配备微分算子时，度量图被称为量子图（quantum graphs），在物理学中已有广泛研究 [27, 26]，近年来也在统计学 [11]、数值分析 [9] 和贝叶斯反演 [10] 中受到关注。本文研究在紧致度量图上进行贝叶斯优化，所采用的核函数通过分数阶椭圆算子定义。
贝叶斯优化算法已被广泛应用于众多领域，包括机器学习任务中的超参数调优 [39, 25]、材料设计 [19, 28]、药物发现 [17, 4]、动力系统参数估计 [24, 23] 以及实验粒子物理 [21, 16]。由于贝叶斯优化算法用代理模型替代目标函数，并在获得新观测数据后序贯更新该代理模型，因此为数字孪生（digital twins）中的控制与传感器布设提供了一个自然的框架。近期探索贝叶斯优化在数字孪生中应用的研究包括 [14, 31, 29]。在我们所考虑的度量图设定下，天然适用于数字孪生系统的例子包括：生物神经网络中信号传播的模拟与控制，以及电力传输网络中动态流的建模与优化。本文为这些及相关问题提供了一种原则性的优化方法。
非欧几里得空间中的贝叶斯优化已有若干研究。例如，[3] 考察了在离散组合结构上的优化问题；[24] 则研究了在流形上优化目标函数的情形，其中流形仅能通过点云数据访问。[24] 的作者将点云建模为组合图（combinatorial graph），并利用图上Matérn高斯过程（graphical Matérn GPs）[36] 为目标函数在图顶点上的取值构建代理模型。据我们所知，本文是首篇研究在紧致度量图所建模的网络上进行贝叶斯优化的工作。与 [24] 不同，我们利用了近期发展的、定义在度量图顶点与边上的Whittle-Matérn高斯过程 [13]。
为了理解在IGP-UCB和GP-TS中引入Whittle-Matérn核的有限元表示所带来的影响，我们分析了核误设（kernel misspecification）情形下的贝叶斯优化。针对GP-UCB，[7] 已建立了核误设下的遗憾界。本文将该理论推广至GP-TS，并借助近期关于度量图上分数阶椭圆微分方程数值逼近的研究成果 [9]，对误设程度进行了量化。其他研究认知性（epistemic）与计算性（computational）核误设下高斯过程回归的工作包括 [35] 和 [37]。
1.2 结构安排与主要贡献
第2节介绍了问题设定，并提供了关于度量图、贝叶斯优化以及度量图上Whittle-Matérn过程的必要背景知识。定理2.4在理想情形下（即所选核函数与目标函数的光滑性匹配，且使用精确的Whittle-Matérn核，不考虑离散化误差）建立了IGP-UCB和GP-TS的遗憾界。
第3节考虑使用Whittle-Matérn过程的有限元表示对IGP-UCB和GP-TS进行实际实现。定理3.4在目标函数光滑性未知且采用有限元表示的情形下，建立了包含认知性与计算性核误设的遗憾界。
第4节通过在合成度量图上优化基准函数，以及在通信网络上进行贝叶斯反演，展示了IGP-UCB和GP-TS的性能。结果清晰表明：相较于基于欧几里得距离定义的标准核函数，使用内在定义于度量图上的Whittle-Matérn核具有明显优势。
第5节总结全文。
附录A提出了一种新的、适用于误设情形的汤普森采样（TS）通用理论，可能具有独立价值；附录B包含所有技术引理的证明；附录C提供了算法实现的补充材料。
1.3 符号
对于实数 a, b，我们记 a ∧ b = min(a, b) 且 a ∨ b = max(a, b)。符号 ≲ 表示“小于或等于，最多相差一个普适常数”，类似地，≳ 也如此定义。对于实数序列 {aₙ}, {bₙ}，若对所有 n 都有 aₙ ≲ bₙ 且 bₙ ≲ aₙ，则我们记作 aₙ ≍ bₙ。
2 度量图上的贝叶斯优化
2.1 问题陈述
设 Γ 是一个具有顶点集 V = {vᵢ} 和边集 E = {eⱼ} 的图。我们关注的是边代表连接顶点的物理一维曲线的图。为建模此设置，我们为每条边 e ∈ E 分配一个正长度 Lₑ > 0，然后任意地为每条边定向，并通过坐标 zₑ 将其与区间 [0, Lₑ] 关联起来。补充了这种结构的图 Γ 称为度量图（metric graph），其中度量自然由最短路径距离给出 [5]，此处记为 d。度量图 Γ 上的一个通用点 x 可表示为 x = (e, zₑ)，其中 e ∈ E 且 zₑ ∈ [0, Lₑ]。我们将专注于由有限多个顶点和边组成的紧致度量图，且每条边均为有限长度。作为说明，图1(a) 描绘了一个紧致度量图，它代表纽约的电信网络，捕捉了运营网络中典型的交通行为。该图取自开放数据集 [32, 33]。
2.3 核的选择：Whittle–Matérn 高斯过程
我们将用于建模目标函数的先验是在紧致度量图 Γ 上由 [13] 引入的 Whittle–Matérn 高斯过程（GP）。与欧几里得情形类似，Matérn 类型的高斯过程可通过一个分数阶随机偏微分方程（SPDE）来定义。在紧致度量图上的主要区别在于，需要施加顶点条件，以获得一个与图几何结构相一致的图原生核（graph-native kernel）（详见 [9, 10]）。此处我们概述该构造的主要思想，同时尽量减少技术细节。
3 基于有限元核表示的贝叶斯优化
算子 ℒ 在式 (7) 中的特征对，对于一般的度量图通常不可得。因此，直接使用核函数 (11) 往往不可行，必须进行数值近似。在本节中，我们考虑文献 [9, 8] 提出的有限元近似方法，该方法不仅易于计算，而且能实现高斯过程回归的高效实现。
此类数值近似所引发的一个主要问题是：真实目标函数 f† 不再保证位于有限元核的再生核希尔伯特空间（RKHS）中，因此定理 2.4 不能直接适用。在本节中，我们通过精心设计和分析基于有限元核的 IGP-UCB 和 GP-TS 算法来解决这一问题。我们首先考虑算法 3.1 中 2α ∈ ℕ 的情形，然后在算法 3.2 中使用有理逼近处理 2α ∉ ℕ 的分数阶情形，并在定理 3.4 中建立遗憾界（regret bounds）。
本节的核心主题是理解有限元核与有理核在多大程度上能够逼近 f†，以便在贝叶斯优化算法中校正由此类近似误差带来的影响。除了考虑由有限元和有理近似引入的计算性误设外，我们的理论还涵盖了当目标函数 f† 的光滑性未知、且核函数的光滑性参数 α 与目标函数的实际光滑性不匹配时所产生的认知性误设（epistemic misspecification）。
3.1 有限元核
3.1.1 Γ 上的有限元空间
首先，我们回顾度量图上的有限元构造 [2]。从高层次来看，该构造通过将每条边 e 与区间 [0, Lₑ] 对应（参见第 2.1 节），在其上构建标准的一维有限元空间，并在顶点处施加额外的注意。
3.1.2 有限元近似
在上述有限元空间构建完成之后，我们即可定义有限元核。回顾式 (9) 中的算子 L所诱导的双线性形式
3.1.3 有理逼近
3.2 后悔界（Regret Bounds）
现在我们准备给出基于有限元近似的 IGP-UCB 和 GP-TS 算法的后悔界。我们指出，算法 3.1 与算法 3.2 的分析是类似的，因此我们仅给出更具一般性的算法 3.2 的分析。回顾所定义的简单后悔（simple regret）为：
4 数值实验
本节研究 IGP-UCB 和 GP-TS 在合成度量图（小节 4.1）上定义的基准目标函数以及在电信网络上的源识别贝叶斯逆问题中最大后验估计（小节 4.2）的有效性。我们比较两种核的选择：
我们注意到，在所有示例中，我们所考虑的网络自然嵌入在 ℝ² 中，且度量图中的点自然与 ℝ² 中的点对应。
我们采用算法 3.1，并补充一层用于核参数的最大似然估计，如算法 C.1 所总结。在整个实验过程中，我们将振幅参数固定为 σ = τ = 1，仅估计控制 SPDE 核和欧几里得核相关长度尺度的参数 κ 和 ℓ。这一选择得到了对 τ 和 σ 进行随机扰动的敏感性测试的支持，测试表明这些扰动对结果影响可忽略。我们使用 Γ 在最短路径距离下的直径来初始化最大似然估计过程的参数：ℓ₀ = 0.25 · diam(Γ) 且 κ₀ = 1/ℓ₀，这使得 SPDE 核与欧几里得核在早期阶段的探索能力相当。为构建度量图、有限元网格以及离散化的 SPDE 核 kₕ（取 α = 1），我们使用 MetricGraph R 包 [12]，其针对半整数 α 的实现基于文献 [9]。这与我们在第 3.2 节注释中提到的理论分析相一致。
我们使用三个互补的指标评估性能：平均简单后悔、达到率和达到容差所需的迭代次数。“平均简单后悔”表示在 Nᵣₑₚ 次重复实验（每次实验采用不同的初始设计）中简单后悔的平均值。每个初始设计均通过第 2.1 节注释中讨论的最大最小选择规则获得。“达到率”表示在给定时间范围内，简单后悔小于指定容差 Tol 的实验运行所占的比例；“达到容差所需的迭代次数”表示第 j 次重复实验中（若成功），首次跨越容差阈值 Tol 所需的迭代次数（不包括初始化阶段）。令
4.1 基准函数
4.1.1 问题设定
在欧几里得域中，Ackley、Rastrigin 和 Lévy 等基准目标函数常被用于评估优化算法的性能。这些经典基准目标函数具有结构清晰的景观，其全局最小值已知，且通常包含振荡结构和多个局部极小值，这使得它们适合用于评估算法的收敛速度、逃离局部极小值的能力以及整体鲁棒性。然而，将这些基准函数扩展到我们的紧致度量图设置并非直接可行，因为必须确保所得到的目标函数在整个图上保持全局连续性，尤其是在多个边交汇的顶点处。
4.1.2 数值结果
我们考虑在一个形状为开放矩形的紧致度量图上的基准函数，如图 2 所示。尽管结构简单，但该开放矩形图会产生显著的距离失真：图中的许多点在欧几里得距离下彼此接近，但在最短路径距离下却相距甚远，这是因为矩形的高度很小且开口极窄。正如我们将看到的，这种度量失真使得欧几里得核不适用于贝叶斯优化。我们考虑三个基准函数，它们分别基于经典的 Ackley、Rastrigin 和 Lévy 目标函数构建，其表达式如下：
在开放矩形图上，这些基准函数可被视为其经典欧几里得对应物的拉伸并平移后的版本。它们提出了不同的挑战：Ackley 函数高度多模态，Rastrigin 函数表现出密集的小尺度振荡，而 Lévy 函数在开口处呈现剧烈变化。欧几里得核会“抄近路”穿过该开口，错误地将最短路径距离上相距甚远的节点关联起来；正如我们的实验所示，这会导致较差的优化结果。
4.2 贝叶斯反演中的最大后验（MAP）估计
4.2.1 问题设定
在本节中，我们将贝叶斯优化应用于点源识别反问题的贝叶斯框架中的最大后验（MAP）估计。设 Γ为一个紧致度量图，考虑如下椭圆方程：
4.2.2 数值结果
图6中的结果表明，采用欧几里得核的贝叶斯优化表现较差：它很少能在40次迭代内恢复源位置，且达到率显著偏低。相比之下，采用SPDE核的算法表现稳定可靠，其达到率在40步内接近1，且达到容差所需的平均迭代次数落在20至30之间。一个合理的解释是，对数后验概率在真实源位置 x† 附近的有效区域呈单峰且高度集中；而尊重图几何结构（通过最短路径距离）的核能够高效地实现局部化。相反，欧几里得核会跨越间隙和平行边“抄近路”，将欧几里得空间中相近但最短路径距离上相距甚远的点错误地视为高度相关，从而导致协方差与目标函数之间的不匹配，并降低优化性能。
5 结论
本文研究了在被建模为度量图的网络上进行的贝叶斯优化。我们采用 Whittle–Matérn 高斯先验，在理想化设定下（即所选核与目标函数的光滑性相匹配，且使用精确的 Whittle–Matérn 核，未考虑离散化误差），在定理 2.4 中建立了后悔界。此外，在目标函数光滑性未知、且采用 Whittle–Matérn 核的有限元表示的实际设定下，我们在定理 3.4 中进行了分析。在此过程中，我们发展了关于核误设情形下贝叶斯优化的新理论。通过数值实验，我们展示了相较于基于欧几里得距离的标准核，自然适配网络几何结构的 Whittle–Matérn 核所具有的优势。
原文链接：https://arxiv.org/pdf/2510.27643
热门跟贴