PaperlayerView exact revision on arXiv

Source-linked AI summary

Genetic Algorithms for Tractable Bayesian Network Fusion via Pre-Fusion Edge Pruning

Pablo Torrijos, José A. Gámez, José M. Puerta, Juan A. Aledo

arXiv:2609.03724v1cs.NEcs.LG

TL;DR

BN fusion must preserve useful dependencies without producing networks too complex for inference. The paper addresses this with pre-fusion edge-pruning genetic algorithms and a consensus objective, which experiments show outperform adapted prior methods and greedy baselines. The resulting framework emphasizes shared structure while controlling treewidth, though fusion quality still depends on heuristic variable ordering and the chosen treewidth reference.

  • Problem

    BN fusion can produce dense, high-treewidth networks, while unrestricted fusion may be distorted by noisy or irrelevant dependencies.

  • Method

    The paper prunes edges before fusion using two specialized genetic algorithms, greedy baselines, and a fitness function balancing structural similarity with treewidth constraints.

  • Results

    Experiments on synthetic and real-world datasets show that the genetic algorithms consistently outperform an adapted prior method, with edge-repetition variants achieving superior solutions in specific cases.

  • Takeaways & Limitations

    The framework emphasizes shared structures and divergence minimization while controlling BN complexity and supports evaluation of fused-network consensus quality.

  • Takeaways & Limitations

    Fusion quality depends on heuristic variable ordering because finding the optimal ordering is NP-hard, and a poor ordering can produce unnecessarily complex fusions.

Abstract

from arXiv · show

Bayesian Network (BN) fusion combines multiple input networks into a single structure, balancing dependency preservation with computational tractability. While unrestricted fusion retains all dependencies, it often results in overly complex networks with high treewidth, which affects inference scalability. Limited fusion mitigates this by pruning edges to control treewidth but risks overfitting to input-specific noise and omitting dependencies from the original BNs. This paper introduces a consensus framework that prioritizes shared structures among input networks while enforcing treewidth constraints, ensuring a good consensus. We propose genetic algorithms with advanced initialization, specialized operators, and a tailored fitness function. Additionally, we adapt existing methods to this problem and implement greedy baselines for benchmarking and further optimization. Experiments on synthetic and real-world BNs show the superiority of the proposed genetic algorithms over the adapted methods and greedy baselines.

1 Introduction

BN fusion merges networks into a consensus structure, but unrestricted fusion can create dense, high-treewidth graphs that hinder inference. This work proposes pre-fusion edge-pruning genetic algorithms that enforce treewidth constraints while minimizing divergence from input networks.

  • BN fusion combines networks from different experts or data sources into a single consensus model.
  • Unrestricted fusion can produce dense graphs with high treewidth, limiting inference efficiency and interpretability.
  • Inference complexity scales as O(n·k^t+1), making high-treewidth Bayesian Networks impractical for larger problems.
  • The proposed methodology prunes edges in the original networks before fusion to achieve a target treewidth.
  • Two genetic strategies independently remove edge occurrences or jointly remove identical edges across input networks, with greedy algorithms as baselines.
  • The framework minimizes divergence from input networks while targeting treewidth, addressing inaccurate or adversarial dependencies more robustly.
  • The paper introduces consensus-quality metrics and releases code to support reproducibility.

2 Preliminaries

Bayesian Networks encode conditional dependencies with DAGs and probability distributions, while structural fusion constructs a consensus graph from multiple input networks. The section also introduces ordering-based fusion, treewidth concerns, and structural-similarity metrics.

  • 2.1 Bayesian Networks: A Bayesian Network is a DAG over variables paired with conditional probability distributions that quantify their dependencies.
  • 2.1 Bayesian Networks: D-separation encodes conditional independencies and supports factorization of the joint distribution into parent-conditioned terms.
  • 2.1 Bayesian Networks: An I-map preserves at least the conditional independencies of another DAG, while a minimal I-map is the sparsest graph retaining them.
  • 2.2 Structural Fusion of BNs: Structural fusion seeks a DAG representing shared independence structure across input networks, minimizing arcs while preserving common independencies.
  • 2.2 Structural Fusion of BNs: Fusion applies an ordering to each input DAG, modifies them consistently, and unions their resulting arcs to construct the fused graph.
  • 2.2 Structural Fusion of BNs: The choice of variable ordering is critical because poor orderings can create unnecessarily complex fusions, although finding the optimal ordering is NP-hard.
  • 2.2 Structural Fusion of BNs: The all-or-nothing fusion criterion can produce dense, high-treewidth networks, motivating consensus fusion that retains a representative subset of dependencies.
  • 2.3 Metrics for Measuring Structural Similarity of BNs: SMHD measures moral-graph differences, whereas FSim compares differences in conditional independencies under a shared variable ordering.

3 Problem Definition

Restricted BN fusion seeks a tractable consensus under a treewidth limit, while avoiding the unnecessary complexity and noise sensitivity that can arise when the unrestricted fusion is used as the reference. The proposed consensus measures similarity directly to the input networks and can preserve shared dependencies more effectively.

  • Motivation: Unrestricted fusion retains all input dependencies but can produce high-treewidth, overly complex networks that limit practical inference.In the example, three input networks with treewidth 2 yield an unrestricted fusion with treewidth 5.
  • Motivation: Using the unrestricted fusion as the reference can distort consensus when input networks contain noisy or irrelevant dependencies.A single noisy network among 100 inputs can cause unrestricted and treewidth-constrained fusion to over-represent spurious dependencies.
  • Consensus definition: The restricted structural consensus minimizes average structural distance to the original input networks subject to a treewidth constraint.This formulation avoids using the unrestricted fusion as the reference and targets shared dependencies across the inputs.
  • Illustrative results: In the illustrative examples, the proposed consensus produces fewer edges and better SMHD and FSim values than the restricted fusion based on the unrestricted network.The consensus can also omit noisy dependencies and nearly match the ideal structure shared by most inputs.
  • Illustrative results: The consensus approach often maintains treewidth comparable to or lower than that of the input networks, supporting efficient learning and inference.This contrasts with methods that tend to exploit the maximum permitted treewidth.

4 Genetic Approach for BN Consensus Under Treewidth Constraints

The proposed genetic approach prunes input-network edges before fusion to construct a consensus BN that balances structural similarity with a treewidth constraint. It combines alternative chromosome representations, heuristic and probabilistic initialization, specialized genetic operators, and constraint-aware fitness evaluation.

  • The algorithm prunes arcs from input networks to construct a consensus structure balancing structural similarity and computational feasibility under treewidth limit t.
  • Chromosome representation: Chromosomes encode edge inclusion either across unique edges or independently for repeated edges from each input graph.
  • Chromosome representation: The EG and E∗G representations trade off network-specific pruning flexibility against a smaller search space and faster, more consistent convergence.
  • Fitness function: The fitness function rewards structural similarity to the original input networks while penalizing treewidth violations and infeasible solutions.
  • Initialization: Hybrid initialization combines greedy solutions with random chromosomes, while edge-frequency-guided sampling provides probabilistic population initialization.
  • Genetic operators: Mutation independently adds or removes edges with adaptive probabilities, and elitist updates preserve the best current and previous-generation chromosomes.

5 Experimental Evaluation

The experiments evaluate BN consensus methods on synthetic and real-world networks under varied network sizes, input counts, and complexity constraints. Real-world evaluation uses networks from the bnlearn repository and includes generated samples for parametric learning.

  • The evaluation follows prior experimental setups while extending them to larger Bayesian networks and new metrics for the consensus problem.
  • Synthetic networks: Synthetic input DAGs are generated from base DAGs through 0.75n edge perturbations while preserving acyclicity and structural-complexity limits.
  • Real-world networks: Real-world evaluation uses seven Bayesian networks from the bnlearn repository spanning varied node counts, edge densities, and inference parameters.
  • Real-world networks: Generated samples contain 5000 instances per real-world BN to support parametric-learning assessments across treewidth limits.

5.2 Algorithms

The algorithm comparison covers adapted methods and proposed genetic and greedy approaches across candidate edge-set configurations. These configurations test shared-edge pruning, repeated-edge decisions, and adaptation from the prior fusion method.

  • The study evaluates genetic and greedy algorithms for BN consensus under treewidth constraints across multiple candidate edge-set configurations.
  • EG+: EG+ adapts the methods from to optimize similarity metrics against the original input graphs rather than the unrestricted fused network.
  • EG: EG retains repeated edges from each input graph, allowing independent inclusion decisions for the proposed genetic algorithm and greedy baseline.
  • E∗G: E∗G uses unique edges with uniform inclusion decisions to test whether pre-fusion changes improve constrained consensus quality.

5.3 Reproducibility

The implementation uses Java and the Tetrad causal-reasoning library, with code, networks, and datasets released for reproducibility. Experiments run in a controlled hardware and software environment.

  • All algorithms were implemented in Java using OpenJDK 17 and the Tetrad 7.6.5 causal reasoning library.
  • The complete code, Bayesian networks, and datasets are available on GitHub, with datasets also hosted on OpenML.
  • Each experiment ran on Rocky Linux 8.9 machines with AMD EPYC 7453 processors, seven threads, and 8 GB RAM.

5.4 Methodology

The evaluation uses synthetic and real-world Bayesian networks with varying numbers of input DAGs and treewidth constraints. Fusion quality is assessed through structural similarity metrics and statistically compared across genetic and greedy algorithms.

  • Experimental setup: The experiments use r = {10, 30, 50} input DAGs for synthetic and real-world Bayesian networks.Synthetic networks vary n = {10, 30, 50}, while real-world networks contain 20–56 nodes.
  • Evaluation metrics: Fusion quality is measured using average SMHDG and Fusion Similarity FSimG relative to the initial input DAGs.Both metrics evaluate structural similarity between the fused network and the input networks.
  • Experimental setup: Each configuration varies the target treewidth over values from 2 up to below the unrestricted fusion treewidth.The experiments combine network size, input-DAG count, metric, and treewidth settings.
  • Algorithm comparison: Genetic algorithms and their greedy counterparts are run for every experimental configuration, using population size 100 for the genetic algorithms.The population size follows the optimal configuration identified in prior work.
  • Parameter estimation: Parametric learning uses Expectation Maximization in Tetrad, with gold-standard networks reparametrized using data generated from the corresponding random seed.This setup supports subsequent evaluation of parameter estimation in generated networks.
  • Statistical analysis: A Friedman test followed by Holm post-hoc comparisons evaluates whether algorithm performances differ at the 1% significance level.Holm comparisons are made against the top-ranked algorithm when the Friedman null hypothesis is rejected.

5.5 Results for Synthetic BNs

On synthetic Bayesian networks, the proposed methods are compared across treewidth constraints using SMHDG and FSimG. The results favor the genetic approach overall, while revealing trade-offs associated with edge repetition and constrained search spaces.

  • Statistical results: 1.05 × 10^-141 for SMHDG and 1.72 × 10^-128 for FSimG reject the equal-performance hypothesis across algorithms.The Friedman tests indicate statistically significant differences for both metrics.
  • Overall comparison: G) consistently achieves the best results across synthetic configurations for both SMHDG and FSimG.The method provides stable performance, although it runs slightly longer than the genetic algorithm from [38] using EG+.
  • Edge-repetition effects: With edge repetition, Alg. 1 performs best at higher treewidths but struggles when treewidth is more tightly constrained.The expanded search space makes strongly constrained settings less favorable and less practically common.
  • Greedy baselines: The greedy algorithm with edge repetition performs poorly across settings and incurs high runtimes because of its larger search space.The associated genetic algorithm is also affected, whereas genetic optimization mitigates these limitations overall.
  • Metric comparison: SMHDG and FSimG results are highly correlated, with their main reported difference arising in execution time.Both metrics therefore produce broadly similar synthetic-network conclusions.

5.6 Results on Real-World BNs

On real-world Bayesian networks, the proposed genetic methods remain competitive in structural accuracy and improve over the adapted prior method. Their generated networks also show favorable parameter-learning behavior, including fewer failures than greedy approaches.

  • Statistical results: 1.12 × 10^-150 for SMHDG and 2.93 × 10^-130 for FSimG reject equal performance among algorithms.The Friedman tests confirm statistically significant differences on real-world networks.
  • Structural accuracy: EG achieves the most wins and the best average SMHDG, while E∗G leads on average in FSimG.E∗G is not significantly different from EG, and both significantly outperform the other methods.
  • Parameter estimation: Failures in conditional-probability estimation grow exponentially for algorithms producing denser networks.The original graphs have the lowest error, unrestricted fusion the highest, and genetic methods produce networks similar to or simpler than the originals.
  • Parameter estimation: Genetic algorithms have fewer learning failures than greedy algorithms because memory limitations arise as the treewidth constraint approaches that of G+.Both proposed genetic algorithms outperform the method from in the reported parameter-estimation evaluation.

6 Conclusions

The paper frames Bayesian Network fusion as consensus under a treewidth constraint and solves it with specialized genetic algorithms and consensus-oriented metrics. Experiments on synthetic and real-world data support the methods’ effectiveness and practical learnability, while exposing a trade-off between search complexity and solution quality.

  • Framework: The framework seeks structural consensus by emphasizing shared structures and minimizing divergence from input networks under a treewidth constraint.It addresses dense unrestricted fusion and the risk of fitting input-specific noise in constrained approaches.
  • Method: Two specialized genetic algorithms combine advanced initialization, problem-specific operators, and a fitness function balancing structural similarity with treewidth.The paper also introduces metrics for evaluating consensus quality while controlling network complexity.
  • Findings: The genetic algorithms consistently outperform an adapted version of prior work on synthetic and real-world datasets.The results support pruning edges directly in the input networks before fusion.
  • Practical evaluation: Learnability of the fused conditional-probability tables provides evidence of practical usability for the generated networks.The evaluation examines whether the fused structures remain suitable for parameter estimation.
  • Trade-off: Allowing edge repetitions achieves superior solutions in specific cases but explores a larger and more complex search space.This result highlights a trade-off between convergence stability and solution quality.
  • Future work: Future work includes stronger greedy initialization heuristics, advanced optimization strategies, and applications such as federated learning.These directions extend the framework to constrained graphical-model integration settings.
Loading 2609.03724v1…