PaperlayerView exact revision on arXiv

Source-linked AI summary

Structural Fusion of Bayesian Networks with Limited Treewidth Using Genetic Algorithms

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

arXiv:2609.10276v1cs.NEcs.LG

TL;DR

Canonical Bayesian Network fusion can produce dense models that are impractical for reasoning. This paper relaxes fusion requirements, formulates constrained fusion under a treewidth limit as a combinatorial optimization problem, and uses a genetic algorithm to search for a consensus network. Experiments report networks resembling unconstrained fusion while preserving treewidths akin to the input DAGs and consistently outperforming a greedy baseline.

  • Problem

    Canonical structural fusion can produce dense Bayesian Networks with probability tables too large for practical reasoning and inference.

  • Method

    The paper formulates restricted BN fusion as a combinatorial optimization problem and uses a genetic algorithm to maximize preserved unrestricted-fusion arcs under a treewidth constraint.

  • Results

    The genetic algorithm generates networks resembling unconstrained fusion while preserving treewidths akin to those of input DAGs and consistently outperforming the greedy baseline.

  • Takeaways & Limitations

    The approach provides a tool for constrained BN fusion when full fusion is impractical for symbolic or numerical reasoning.

Abstract

from arXiv · show

This paper introduces an evolutionary computation approach for consensus in structural Bayesian Network (BN) fusion under the constraint of limited treewidth. The consensus BN aims to reconcile multiple input BNs into a single one that retains key structural features present in the original networks. Treewidth, a graph-based parameter associated with computationally tractable inference, is utilized to restrict the complexity of the resulting network. A genetic algorithm is proposed to look for a BN that codifies as much information about the unrestricted fusion as possible while ensuring the treewidth restriction. Experimental evaluation demonstrates the genetic algorithm's ability to obtain consensus BNs with limited treewidth, providing a valuable tool for aggregating information from diverse sources while returning a computationally actionable model.

I. INTRODUCTION

The paper addresses structural Bayesian Network fusion, where canonical fusion can produce dense, impractical networks, by relaxing the fusion requirements and constraining consensus-network treewidth. It formulates this restricted fusion as a combinatorial optimization problem and proposes a genetic algorithm alongside a greedy baseline and benchmark evaluation.

  • Motivation: Bayesian Networks represent uncertainty through graphical structures and conditional probability tables, with their structure supporting interpretability and inference.The paper emphasizes their relevance to symbolic analysis, belief updating, revision, and explainable or causal modeling.
  • Problem: Structural fusion seeks a consensus model from networks over the same variables, including networks produced by different experts or private datasets.This setting is relevant to federated learning, where source datasets cannot be shared.
  • Problem: Canonical structural fusion can produce dense networks whose probability tables become too large for practical reasoning and inference.The paper identifies this density as a consequence of the restrictive canonical fusion definition.
  • Proposed formulation: Restricted fusion relaxes canonical requirements while seeking a consensus network with maximum treewidth tw that preserves as many arcs as possible from unrestricted fusion.The resulting model is intended to remain tractable for symbolic and numerical reasoning.
  • Contributions: The proposal formulates constrained structural fusion as a combinatorial optimization problem and uses a genetic algorithm as its search engine.The paper also identifies a greedy algorithm, experimental evaluation on different benchmarks, and the genetic algorithm design as contributions.

II. PRELIMINARIES

Structural fusion seeks a minimal DAG that preserves only conditional independences shared by all input networks. The process uses an ordering and method A to construct compatible minimal I-maps, but different orderings can produce substantially different networks.

  • BN representation: A Bayesian network combines a DAG structure over variables with conditional probability distributions for each variable given its parents.The DAG represents dependencies and independencies, while the distributions quantify the connections.
  • Fusion objective: Structural fusion seeks a DAG with the minimum number of arcs that is an I-map of the intersection of independences in all input DAGs.Any conditional independence represented by the fused DAG must be represented in every input DAG.
  • Fusion procedure: The fusion process first selects a variable ordering, transforms each input DAG with method A, and unions the resulting arc sets.Method A produces a compatible minimal I-map, potentially reversing arcs and adding parents to preserve conditional independences.
  • Fusion procedure: Different variable orderings can yield networks of vastly different quality, so the paper assumes an ordering obtained from a heuristic close to optimal.The ordering problem is NP-hard, although the cited heuristic efficiently produces a high-quality order.
  • Motivation: The canonical fusion requirement can produce dense networks that are too complex for symbolic or numerical reasoning, motivating a more relaxed consensus formulation.The all-or-nothing requirement prevents the result from encoding any conditional independence absent from an input network.

III. PROBLEM DEFINITION

Restricted structural fusion seeks a consensus DAG that remains close to unrestricted fusion while satisfying a maximum treewidth and therefore remaining usable for reasoning. The formulation compares DAGs structurally and constrains inference complexity through moralization and triangulation.

  • Objective: The restricted objective is to obtain a consensus model as similar as possible to unrestricted fusion while remaining usable for reasoning.This balances fidelity to the unrestricted fused network against computational tractability.
  • Similarity measure: Structural Moral Hamming Distance compares DAGs through their moral graphs because graph differences may otherwise exaggerate differences in represented independences.Moralization adds edges between co-parents and removes arc directions before measuring distance.
  • Complexity constraint: Treewidth limits inference complexity by bounding the largest clique produced after moralizing and triangulating the DAG.Inference complexity is exponential in the number of variables in the largest probability table constructed during inference.
  • Formal definition: Restricted structural fusion imposes a maximum admitted treewidth tw, with tw ∈ N and tw ≥ 2, on the consensus network.The definition applies this bound to the result of unrestricted structural fusion over the input DAGs.
  • Illustration: For three input graphs with treewidth 2, unrestricted fusion produced a complete five-variable graph with treewidth 5, whereas limiting treewidth to 3 yielded a much simpler, similar network.The example illustrates the practical effect of replacing unrestricted fusion with a bounded-complexity consensus.

A. Greedy method

The greedy baseline constructs a limited-treewidth consensus by ordering candidate arcs according to how frequently they appear in transformed input DAGs and adding them iteratively while respecting the treewidth bound.

  • A. Greedy method: The greedy method derives a consensus network with constrained treewidth from multiple input networks and serves as a baseline.It requires input DAGs and a treewidth bound tw ≥ 2, and returns G+_tw.
  • A. Greedy method: Candidate arcs are formed from arcs in the transformed input DAGs and processed in decreasing appearance frequency.Ties are broken randomly.
  • A. Greedy method: The algorithm repeatedly extracts the highest-frequency remaining arc and checks whether adding it preserves the treewidth restriction.It continues until no candidates remain, then returns the resulting consensus graph.

IV. PROPOSAL

The proposal formulates limited-treewidth BN fusion as selecting a subset of arcs from an unrestricted fusion, encoding that subset as binary chromosomes for evolutionary search.

  • IV. PROPOSAL: Evolutionary computation is applied to Bayesian-network problems including learning from data, graph triangulation, and most-probable-explanation search.The paper positions genetic algorithms as tools for challenging machine-learning and artificial-intelligence problems.
  • IV. PROPOSAL: The optimization task selects a subset of arcs from the unrestricted fusion G+ to construct the constrained fusion G+_tw.The input DAGs are transformed using A(G, σ) before the unrestricted fusion is used.
  • IV. PROPOSAL: Candidate arcs are lexicographically ordered and represented by a binary chromosome whose length equals the number of candidate arcs.Each gene indicates whether its corresponding arc is included in the graph.
  • IV. PROPOSAL: Although candidate arcs are fewer than all possible DAG arcs, they can still create a large search space.One cited example has 9 candidate arcs, representing 90% of the possible arcs in that case.

B. Fitness function

The fitness function evaluates decoded candidate DAGs against the unrestricted fusion while penalizing violations of the maximum treewidth constraint.

  • B. Fitness function: Each chromosome is decoded into a DAG by including an arc exactly when its corresponding gene equals 1.The decoded graph uses X as its vertex set.
  • B. Fitness function: Feasible individuals are evaluated using structural Hamming distance to the unrestricted fusion when their treewidth is at most tw.The displayed fitness expression combines SMHD(G_C, G+) with the treewidth condition.
  • B. Fitness function: Infeasible individuals are severely penalized to discourage solutions that violate the treewidth constraint.Invalid individuals cannot be selected as the final solution even if they improve the current best fitness value.

C. Algorithm structure

The genetic algorithm follows a canonical evolutionary cycle, but uses informed initialization and elitism to retain strong candidate networks while searching for a limited-treewidth consensus.

  • C. Algorithm structure: The algorithm requires input BNs, a treewidth bound, an iteration count, and a population size, and returns a limited-treewidth consensus BN.It first transforms the input DAGs and constructs the unrestricted fusion.
  • C. Algorithm structure: Population initialization uses greedy solutions at treewidth tw and tw −1, while remaining individuals reflect arc frequencies in transformed input DAGs.This provides informed starting points rather than a wholly random population.
  • C. Algorithm structure: Each iteration evaluates the population, performs selection, crossover, and mutation, then applies elitism.The best chromosome seen so far and the best chromosome in the latest population are retained.
  • C. Algorithm structure: After the final iteration, the best decoded DAG is returned as the limited-treewidth consensus.The algorithm explicitly returns G* as G+_tw.

E. Selection

Selection repeatedly compares pairs of chromosomes and copies the fitter winner into the selected population. The procedure then applies one-point crossover to every paired set.

  • E. Selection: Tournament selection repeatedly samples two chromosomes and copies the fitter individual to the selected population.The tournament size is 2.
  • E. Selection: Chromosomes are paired in selection order before crossover is applied.Pairing follows the order in which chromosomes were selected.
  • E. Selection: One-point standard crossover for binary representations is applied with probability 1.0 to every pair.Thus, all selected pairs are combined.

G. Mutation

Mutation probabilities are adjusted using each individual’s treewidth relative to the allowed maximum. The evolutionary process then preserves elite solutions while experiments evaluate synthetic and real-world networks.

  • G. Mutation: Mutation probabilities encourage arc addition below the treewidth limit and arc deletion above it.The probabilities are based on the individual’s treewidth and the maximum allowed treewidth.
  • G. Mutation: After mutation, the two least-fit individuals are replaced by the best overall and best previous-generation individuals.This elitist replacement retains promising solutions across generations.
  • G. Mutation: The experiments evaluate the proposed methods on synthetic and real-world Bayesian networks.The study uses separate synthetic and real-world experiments.
  • G. Mutation: Synthetic input DAGs are generated by perturbing a base network while controlling node counts, input-network counts, parent limits, child limits, and arc counts.The synthetic study uses nine configurations with n = {10, 25, 50} and r = {10, 20, 30}.
  • G. Mutation: The implementation uses Java with the Tetrad causal reasoning library, and the complete code is released on GitHub.The reported implementation uses OpenJDK 17 and Tetrad 7.1.2-2.

C. Experiment 1 results

In synthetic experiments, the genetic algorithm generally outperforms the greedy baseline, especially when the allowed treewidth leaves substantial search space. Larger populations are particularly beneficial in complex settings.

  • C. Experiment 1 results: The genetic algorithm consistently outperforms the greedy approach, with larger gains when improvement over unconstrained fusion is more available.The comparison uses SMHD under restricted treewidth values.
  • C. Experiment 1 results: For 10-node networks, genetic and greedy methods perform similarly because very low or near-unconstrained treewidth values limit the search space.The similarity holds across population sizes in these restricted settings.
  • C. Experiment 1 results: For 25- and 50-node networks, the genetic algorithm shows substantial improvement over the greedy method when the unconstrained fusion has substantially larger treewidth.The reported advantage is strongest in these larger synthetic networks.
  • C. Experiment 1 results: 0.2 is an observed genetic-to-greedy SMHD ratio, corresponding to five times better performance at favorable treewidth values.Ratios approach 1 when the search space is too limited.
  • C. Experiment 1 results: Larger populations provide more individual diversity and better results, particularly in complex scenarios.Population size is therefore most consequential when the optimization setting is difficult.
  • C. Experiment 1 results: For 50-node networks, average minimum treewidth remains above 20, while the genetic algorithm preserves near-unconstrained structure at lower treewidth and most improves over greedy.This highlights the practical relevance of constrained fusion for high-treewidth networks.

D. Experiment 2 results

Real-world experiments on Child and Insurance networks reproduce the synthetic pattern: the genetic algorithm improves over greedy fusion under limited treewidth. The study concludes that it can produce structurally similar yet more tractable Bayesian networks.

  • D. Experiment 2 results: The real-world evaluation uses Child and Insurance networks with 20 and 27 nodes, respectively.Child has 25 arcs and Insurance has 52 arcs.
  • D. Experiment 2 results: The real-world input sets are generated by perturbing the downloaded network used as the base graph.The procedure follows the synthetic-network construction approach.
  • D. Experiment 2 results: The complexity of the unconstrained fusion network increases quickly as the maximum allowed treewidth increases.This occurs even when the original networks have few parents per node.
  • D. Experiment 2 results: The real-world SMHD results support the same conclusions as the synthetic experiments for greedy and genetic algorithms.The comparison averages results over 10 generated network sets.
  • D. Experiment 2 results: The genetic algorithm is presented as a robust solution for constrained structural fusion of Bayesian networks with high treewidth.Its purpose is to obtain limited-treewidth consensus networks from multiple DAGs.
  • D. Experiment 2 results: The method produces networks resembling unconstrained fusion while preserving treewidths similar to those of the input DAGs and outperforming greedy fusion.The paper positions this as useful for symbolic or numerical reasoning when full fusion is impractical.
  • D. Experiment 2 results: The work motivates future research on limited or approximate Bayesian-network aggregation and consensus methods.This is stated as a future research direction.
Loading 2609.10276v1…