AI Research Portal

This paper introduces the Min-Cut Bayesian Network Consensus (MCBNC) algorithm, a greedy method for structural consensus of Bayesian Networks (BNs). The core idea is to prune weak edges from an initial unrestricted fusion using a structural score derived from min-cut analysis, integrated into a modified Backward Equivalence Search (BES) phase of the Greedy Equivalence Search (GES) algorithm. MCBNC introduces a pruning threshold θ that can be selected post hoc using only structural information, avoiding fixed treewidth bounds. The main empirical claim is that MCBNC yields sparser, more accurate consensus structures than both canonical fusion and the input networks, and is scalable, data-agnostic, and well-suited for distributed or federated structural learning of BNs or causal discovery.

The paper identifies several bottlenecks in existing approaches for Bayesian Network structural fusion:

Dense Structures and High Treewidth: Common structural fusion strategies, such as computing the union of input DAGs under a fixed node ordering, often produce dense graphs. These dense structures tend to inflate the treewidth (tw) of the resulting network, severely limiting practical use because exact inference in a BN is exponential in treewidth, specifically O(n · k^(tw+1)).

The principal contributions of this paper are:

A max-flow-based score to quantify edge support.
Integration of this score into the Backward Equivalence Search (BES) phase of the Greedy Equivalence Search (GES) algorithm to prune edges within the Markov equivalence class of the fused network.
An adaptive pruning rule with a single threshold θ, selected post hoc using only input graphs.

The Min-Cut Bayesian Network Consensus (MCBNC) algorithm is a greedy method for structural consensus of Bayesian Networks. It operates without access to data, making it suitable for federated learning.

Method Flow:

Initial Fusion: The method begins by fusing the input DAGs {G_i} from r clients into an unrestricted DAG G+ using a heuristic node ordering (Puerta et al. 2021). This process ensures the resulting graph is acyclic. G+ = (V, E+), E+ = ∪_{i=1}^r E_i
CPDAG Conversion: G+ is converted into its Completed Partially Directed Acyclic Graph (CPDAG) G+ to operate within the Markov equivalence class.
Iterative Pruning: MCBNC iteratively prunes edges from G+ following the Backward Equivalence Search (BES) strategy. At each step, it identifies and deletes the edge with the lowest criticality score Ψ(u→v) provided Ψ(u→v) ≤ θ. The process stops when no such edge remains or when Ψ(u→v) > θ.
Criticality Score: The structural score Ψ(e) quantifies how strongly an edge e is supported across the input networks. This score is based on min-cut analysis, which captures edge support by measuring the minimum cut capacity between nodes u and v in a moralized ancestral graph.
- For an edge (u→v) in G, the criticality score Ψ(u→v) is computed by finding the minimum cut capacity between u and v in the moralized CPDAG G_H, where G_H is the ancestral moral graph of v conditioned on a subset H of its parents.
- The min-cut problem seeks the cut of minimum capacity in a directed graph D = (V, E) with non-negative capacities c : E → R+. For a source s and sink t, a cut (S,T) has capacity: cap(S,T) = Σ_{u∈S, v∈T} c(u→v)
- The max-flow problem finds a flow f: E → R+ that respects capacities and flow conservation and maximises: val(f) = Σ_{e∈δ+(s)} f(e)
- The Max-Flow Min-Cut Theorem states that max val(f) = min cap(S,T).
Adaptive Pruning Threshold: The only free parameter is a pruning threshold θ, which can be near-optimally selected a posteriori using only the input graph structures. This avoids predefined treewidth bounds.

Input: A collection of r DAGs {G_i = (V, E_i)} from r clients over a shared variable set V.
Initial Fusion: The unrestricted fusion G+ is obtained using the heuristic node ordering of Puerta et al. (2021).
Pruning Algorithm: MCBNC uses a modified Backward Equivalence Search (BES) phase of the Greedy Equivalence Search (GES) algorithm. The BESTEDGE function (Algorithm 3) is used to find the edge and conditioning set that minimize the criticality score.
Criticality Score Calculation: The criticality score Ψ(u→v) is computed using min-cut analysis on the moralized CPDAG. It involves identifying valid conditioning sets N_uv and generating subsets H of N_uv up to a maximum size k_max.
Edge Capacities: All edge capacities are assumed to be one.
Max-Flow Algorithm: The choice of max-flow algorithm is flexible; any correct implementation (e.g., Edmonds-Karp, Dinic) can be used.
Acyclicity Preservation: Acyclicity is preserved by applying the DELETE operator within the Markov equivalence class.
Conditioning Set Size: The conditioning-set cap k_max is fixed to 10 as an internal constant.
Complexity: The complexity of MCBNC with Ford-Fulkerson is O(r m³ 2^(kmax)) time and O(r m) space, where r is the number of input DAGs, m = |E+| is the number of edges in the unrestricted fusion, and k_max is the conditioning-set cap.
Implementation: All code was implemented in Java (OpenJDK 17) using the TETRAD 7.6.5 causal inference library. Structure learning was performed with GES.
Hardware: Experiments were run on Intel Xeon E5-2650 (8 cores) with 32 GB RAM per run.

Datasets: 15 benchmark networks from the BNLEARN repository (Scutari 2010), including ASIA, SACHS, CHILD, INSURANCE, WATER, MILDEW, ALARM, BARLEY, HAILFINDER, HEPAR2, WIN95PTS, PATHFINDER, ANDES, DIABETES, PIGS.
Metrics:
- Structural Moral Hamming Distance (SMHD): Quantifies structural differences after moralization. Lower values are better.
- BDeu Score: Bayesian Dirichlet equivalent uniform score. Higher values are better.
- Treewidth: Indicates structural complexity. Lower values are desirable.
Baselines:
- Canonical fusion (G+).
- Average of r GES-generated input DAGs ({G_i}=1).
Numeric Results:
- SMHD: MCBNC (G*) achieved a mean rank of 1.40, significantly outperforming GES ({G_i}=1) with a rank of 1.91 (p-value = 6.95 × 10^(-4)) and Fusion (G+) with a rank of 2.69 (p-value = 7.68 × 10^(-18)).
- BDeu Score: MCBNC (G*) achieved a mean rank of 1.70, statistically indistinguishable from GES ({G_i}=1) with a rank of 1.58 (p-value ≈ 0.41). Both MCBNC and GES significantly outperformed Fusion (G+) with a rank of 2.72 (p-value = 3.25 × 10^(-14)).
- Treewidth: MCBNC consistently produces sparser networks with lower treewidths compared to canonical fusion and often the input networks. For example, for the BARLEY network with 100 DAGs, MCBNC reduces treewidth by 58.7% compared to the gold standard.
Runtime/Training Cost: Not stated in the paper, beyond the theoretical complexity O(r m³ 2^(kmax)).

Performance on PATHFINDER BN: For the PATHFINDER BN, SMHD improves monotonically even as the network is pruned to near emptiness. This behavior reflects a structural mismatch in the input DAGs, as GES fails to recover the underlying semi-Naive Bayes structure, which is a known limitation of GES (Laborda et al. 2024) that affects MCBNC's input.

Method evidence: "This paper presents the Min-Cut Bayesian Network Consensus (MCBNC) algorithm, a greedy method for structural consensus of Bayesian Networks (BNs), with applications in federated learning and model aggregation. MCBNC prunes weak edges from an initial unrestricted fusion using a structural score based on min-cut analysis, integrated into a modified Backward Equivalence Search (BES) phase of the Greedy Equivalence Search (GES) algorithm." (section: Abstract)
Result evidence: "For SMHD, MCBNC significantly outperforms both the GES average and the unrestricted fusion. Among the ties, 12 correspond to SACHS and PIGS, where GES already recovers Ggs and no structural improvement is possible. The rest occur in small networks, where differences are minor. For BDeu, MCBNC and GES are statistically indistinguishable (p≈0.41), while both significantly outperform the unrestricted fusion." (section: Interpretation)
Limitation evidence: "An exception is the PATHFINDER BN, where SMHD improves monotonically even as the network is pruned to near emptiness. This reflects a structural mismatch in the input DAGs, as GES fails to recover the underlying semi-Naive Bayes structure. This limitation is known in the literature (Laborda et al. 2024)." (section: Choosing the Fusion Threshold)

Bayesian Network Structural Consensus via Greedy Min-Cut Analysis

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Evidence

Additional Figures