AAAI 2026 Bayesian network structural fusion consensus min-cut max-flow greedy equivalence search 联邦学习 treewidth

Bayesian Network Structural Consensus via Greedy Min-Cut Analysis¶

会议: AAAI 2026
arXiv: 2504.00467
代码: https://github.com/ptorrijos99/BayesFL
领域: others (贝叶斯网络 / 联邦学习)
关键词: Bayesian network, structural fusion, consensus, min-cut, max-flow, greedy equivalence search, federated learning, treewidth

一句话总结¶

提出 MCBNC 算法，基于最小割（min-cut）分析量化边的结构支持度，并将其嵌入贪心等价搜索（GES）的后向阶段来迭代剪枝融合贝叶斯网络中的冗余边，在不访问数据的情况下生成更稀疏、更精确的共识结构，适用于联邦学习场景。

研究背景与动机¶

贝叶斯网络融合的需求：在联邦学习、专家知识汇聚等场景中，多个参与方各自学到一个贝叶斯网络（BN），需要将多个结构聚合为一个共识 DAG。结构融合（structural fusion）是这一过程的核心步骤，且需在不共享原始数据的前提下完成
朴素融合的致命问题：经典的无约束融合方法（将所有输入 DAG 在某个节点排序下取边的并集）虽然保证了 I-map 性质，但融合后的图往往极度稠密。由于精确推理的复杂度为 \(O(n \cdot k^{tw+1})\)，treewidth（\(tw\)）的膨胀会使推理完全不可行——例如 Win95pts 网络中 treewidth 从约 10 飙升到约 20
现有剪枝方法的不足：(1) 基于遗传算法的方法（Torrijos 2024, 2025）虽可强制约束 treewidth 或优化目标函数，但计算代价极高，且需要预设 treewidth 上限——设太低会删掉重要边，设太高则推理仍不可行；(2) 现有贪心启发式仅利用边频率，忽略其他结构属性，无法独立使用
关键洞察：如果一条边 \(u \to v\) 被删除后，\(u\) 和 \(v\) 在大多数输入 DAG 的道德化祖先子图中仍有大量替代路径（即最小割很大），那么这条边是冗余的。反之，若最小割很小（甚至为零），则该边对维持依赖结构至关重要。这一观察将边的"重要性量化"与经典的最大流/最小割理论自然连接
联邦学习的适配性：该方法仅需结构信息、不需要数据，天然适合联邦学习中各客户端学到的局部 DAG 做聚合的场景，且唯一参数 \(\theta\) 可事后仅依据结构信息确定

方法详解¶

整体框架¶

MCBNC 的完整流程分为三个阶段：

构建无约束融合图 \(G^+\)：给定 \(r\) 个输入 DAG \(\{G_i\}_{i=1}^r\)（共享变量集 \(V\)），首先按照启发式节点排序 \(\sigma\) 将每个 DAG 转换为 \(G_i^\sigma\)，然后取边的并集 \(E^+ = \bigcup_i E_i^\sigma\) 得到融合 DAG \(G^+\)
转换为 CPDAG 并迭代剪枝：将 \(G^+\) 转换为其完全部分有向无环图（CPDAG）\(\mathcal{G}^+\)，然后在 Markov 等价类空间中迭代删除"最不关键"的边——关键性由基于 min-cut 的打分函数 \(\Psi\) 决定
阈值控制与输出：当所有剩余边的关键性分数均超过阈值 \(\theta\) 时停止，将最终 CPDAG 转回 DAG 输出共识结构 \(G^*\)

整个过程等价于将 GES 算法的后向阶段（BES）中基于似然的打分函数替换为基于最大流的结构打分，从而在不需要数据的情况下完成结构剪枝。

关键设计一：基于最小割的边关键性打分（Criticality Score）¶

功能：对融合图中的每条边 \(e = (u \to v)\) 计算结构关键性分数 \(\Psi_{(u \to v)}^H\)
核心计算过程：对每个输入 DAG \(G_i\)：(a) 提取 \(\{u, v\} \cup H\) 的祖先子图（ancestral subgraph）；(b) 对该子图做道德化（moralization）；(c) 移除条件集 \(H\) 中的节点得到条件化图 \(\tilde{G}_i^H\)；(d) 在 \(\tilde{G}_i^H\) 上用 Ford-Fulkerson 算法计算 \(u\)-\(v\) 之间的最小割大小 \(|S_i^H|\)。最终分数为所有输入图上的平均最小割：\(\Psi_{(u \to v)}^H = \frac{1}{r} \sum_{i=1}^r |S_i^H|\)
物理含义：分数越低，说明该边在输入网络集合中的结构支持越弱——在大多数输入网络中，\(u\) 和 \(v\) 之间缺乏替代路径，移除该边不会破坏共识依赖结构。分数越高，说明有大量替代路径，边是冗余的。但剪枝是"删低分边"——低分边的支持弱、替代路径少，反而应该被保留？不，这里需要仔细理解：低分意味着边在输入图中很少出现或其连接在道德化子图中很弱，因此是优先删除的对象
设计动机：利用最大流/最小割定理将边的结构贡献量化为一个连续分数，替代了简单的"出现次数"统计，能捕捉更丰富的拓扑信息

关键设计二：条件集枚举与 BES 删除操作¶

功能：为每条边枚举所有合法的条件集 \(H \subseteq \mathcal{N}_{uv}\)（大小不超过 \(k_{\max}\)），选择使关键性分数最低的 \((e^*, H^*)\) 组合
核心思路：合法条件集 \(\mathcal{N}_{uv}\) 定义为同时是 \(v\) 的父节点且与 \(u\) 有无向边的节点集合（遵循 Chickering 的 BES 删除条件）。对每个候选子集 \(H\)，计算 \(\Psi\) 并选全局最低。通过 BES 的 Delete 操作删边，保证操作始终在 Markov 等价类内进行
设计动机：直接继承 GES/BES 的理论框架保证了搜索的正确性——每次删除后自动更新 CPDAG，维持等价类的一致性。条件集的枚举虽然理论上指数级，但实际中 \(|\mathcal{N}_{uv}|\) 通常很小，且随剪枝进行不断缩小

关键设计三：自适应阈值 \(\theta\) 的事后选择¶

功能：提出无需数据和真实网络即可选择 \(\theta\) 的策略
核心思路：MCBNC 在单次运行中生成完整的剪枝轨迹 \(\{G^*(\theta)\}\)。选择使共识 DAG 到输入 DAG 集合的平均 SMHD（Structural Moral Hamming Distance）最小的 \(\theta\) 值
理论支持：实验表明，最小化相对输入图 SMHD 的 \(\theta\) 同时也近似最小化相对真实网络的 SMHD，且能获得很强的 BDeu 分数。Friedman 检验和 Holm 事后分析在 \(\alpha = 0.01\) 下确认了这一策略的统计显著性

理论性质¶

单调性（Lemma 1）：每删除一条边后，剩余边的关键性分数单调非减，保证了贪心过程不会把本该早删的边留到后面
复杂度（Lemma 3）：总时间复杂度 \(O(r \cdot m^3 \cdot 2^{k_{\max}})\)，空间 \(O(r \cdot m)\)，其中 \(m\) 为融合图边数。实际运行中 \(2^{k_{\max}}\) 项影响有限，因为大条件集很少出现

实验¶

实验设置¶

基准网络：来自 bnlearn 仓库的 15 个标准贝叶斯网络，节点数从 8（Asia）到 441（Pigs），边数从 8 到 602
联邦场景设定：对每个基准网络，模拟 \(r \in \{5, 10, 20, 30, 50, 100\}\) 个客户端，每个客户端从真实网络采样 5000 条 i.i.d. 数据后用 GES 学习局部 DAG，然后仅基于结构进行融合
评价指标：SMHD（到真实网络 / 到输入网络）、BDeu 分数、treewidth
每种配置重复 10 次，使用 Friedman + Holm 统计检验

表1：MCBNC 与基线方法的 SMHD 统计排名比较（15 个网络 × 6 种客户端数 = 90 组）¶

指标	方法	平均排名	p-value (Holm)	胜/平/负
SMHD	MCBNC (\(G^*\))	1.40	—	—
SMHD	GES 平均	1.91	\(6.95 \times 10^{-4}\)	61/13/16
SMHD	无约束融合 (\(G^+\))	2.69	\(7.68 \times 10^{-18}\)	68/17/5
BDeu	GES 平均	1.58	—	—
BDeu	MCBNC (\(G^*\))	1.70	\(4.12 \times 10^{-1}\) (不显著)	48/9/33
BDeu	无约束融合 (\(G^+\))	2.72	\(3.25 \times 10^{-14}\)	71/9/10

MCBNC 在 SMHD 上排名第一且显著优于其他两种方法；在 BDeu 上与直接优化 BDeu 的 GES 统计不可区分（\(p \approx 0.41\)），说明 MCBNC 在完全不访问数据的条件下仍能达到与数据驱动学习相当的似然得分。

表2：MCBNC 在典型网络上的关键改善（从论文 Fig.1 和 Fig.3 提取）¶

网络	节点/边	融合 \(G^+\) SMHD	MCBNC 最优 SMHD	SMHD 改善	\(G^+\) treewidth	MCBNC treewidth
Win95pts	76/112	远高于空图	显著低于输入 DAG 平均	~58.7%	~20	~10
Andes	223/338	极高	比 \(G^+\) 降低约两个数量级	>90%	极高	接近真实网络
Diabetes	413/602	极高	比 \(G^+\) 降低约两个数量级	>90%	极高	接近真实网络
Alarm	37/46	高于输入平均	低于输入平均	显著	高	接近真实网络

在大型网络（Andes、Diabetes）上优势最为明显，SMHD 改善可达两个数量级。treewidth 的下降使得精确推理重新变得可行。

运行效率¶

与遗传算法方法相比，MCBNC 快了数个数量级。大部分计算集中在早期迭代（低 \(\theta\)），随着剪枝推进每轮成本递减。对 \(k_{\max}\) 的敏感性分析（在最大的 Diabetes 网络上测试 \(k_{\max} \in \{0,1,...,20\}\)）表明剪枝质量几乎不受影响，确认 \(k_{\max}\) 不是一个需要精细调节的超参数。

亮点与洞察¶

打分函数的巧妙设计：将最小割问题嵌入贝叶斯网络融合中量化边的支持度，是经典图论工具在概率图模型领域的一次优雅应用。每条边被建模为一个"流网络中的容量单元"，其在道德化祖先子图中的替代路径数量决定了它的可删除性
无数据 ≈ 有数据：最重要的实验发现是 MCBNC 在完全不访问数据的条件下，结构精度显著优于输入的 GES 网络（后者直接优化了数据似然），BDeu 分数也统计不可区分。这说明多个"有噪声"的结构中蕴含的共识信息足以恢复接近真实的依赖结构
阈值选择的"自引用"策略：\(\theta\) 通过最小化共识图与输入图集合之间的距离来选择，形成了一种不需要外部参考的自洽选择机制，在联邦学习场景中具有很强的实用价值
treewidth 的"有机下降"：不需要硬约束 treewidth 上限，剪枝过程自然地将 treewidth 降至真实网络附近甚至更低，规避了"设多少才合适"这一难以回答的问题

局限性¶

假设节点集完全相同：所有输入 DAG 必须定义在相同的变量集 \(V\) 上，无法处理变量集不一致的异构场景（如不同医院采集不同指标）
未考虑非 i.i.d. 数据分布：联邦学习中客户端数据分布常存在异质性（non-i.i.d.），本文实验中所有客户端的数据均从同一分布采样，对分布偏移的鲁棒性未知
贪心搜索的局限：BES 的贪心本质意味着可能陷入局部最优，删除顺序不同可能导致不同的最终结构。论文中重复实验的方差虽小，但理论上无全局最优性保证
合成 → 真实的鸿沟：所有基准网络都是从已知真实结构采样数据再学习，尚未在真正的"未知真实 DAG"的实际场景中验证
可扩展性瓶颈：\(O(r \cdot m^3 \cdot 2^{k_{\max}})\) 的理论复杂度在极大规模网络上仍可能受限，特别是融合图非常稠密时

评分¶

新颖性: ⭐⭐⭐⭐ — 将 min-cut 分析引入 BN 结构融合的打分函数是全新思路，GES/BES 框架的复用也很自然
实验充分度: ⭐⭐⭐⭐ — 15 个标准网络 × 6 种客户端数 × 10 次重复，统计检验严格，且有充分的消融实验和敏感性分析
写作质量: ⭐⭐⭐⭐ — 论文结构清晰，包含完整的理论分析和可视化示例，技术附录详尽
价值: ⭐⭐⭐⭐ — 解决了 BN 融合中的关键实用问题（treewidth 膨胀），方法可扩展到联邦学习，代码公开