arXiv CS open access

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

2026 · arxiv_cs

arXiv CS · Papers · 2026

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

arXiv:2609.03724v1 [cs.NE] 3 Sep 2026

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

José A. Gámez

Universidad de Castilla-La Mancha Departamento de Sistemas Informáticos, Albacete, Spain Pablo.Torrijos@uclm.es

Universidad de Castilla-La Mancha Departamento de Sistemas Informáticos, Albacete, Spain Jose.Gamez@uclm.es

José M. Puerta

Juan A. Aledo

Universidad de Castilla-La Mancha Departamento de Sistemas Informáticos, Albacete, Spain Jose.Puerta@uclm.es

Universidad de Castilla-La Mancha Departamento de Matemáticas, Albacete, Spain JuanAngel.Aledo@uclm.es

Abstract

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.

Bayesian Networks (BNs) [18, 22, 23] are probabilistic graphical models that represent complex dependencies between variables through Directed Acyclic Graphs (DAGs). Each BN combines a graph structure encoding conditional (in)dependencies with a set of conditional probability distributions quantifying these dependencies. BNs are highly interpretable due to their graphical structure [29, 31] and possess symbolic inference mechanisms [18], making them effective in fields such as bioinformatics [2, 6], healthcare [30], environmental modeling [10], and industrial diagnostic systems [1, 27, 42], where they enable inference and decision-making under uncertainty. Moreover, the increasing focus on explainable AI models [4, 5] reinforces the relevance of BNs in applications that require transparency due to their white-box nature. Although domain experts can manually specify the graph structure and parameters of BNs, this approach becomes infeasible for large-scale problems. Learning BNs from data, although NP-hard [9], has been extensively studied [8, 14, 21, 36, 39]. In this context, structural fusion of BNs [33, 34] is crucial when multiple networks, potentially from different experts or data sources, must be merged into a single, coherent model. Given a set of BNs on the same variables, structural fusion aims to create a consensus BN that best represents the input BNs. This is increasingly relevant due to the rise of distributed [40] and federated learning [28, 41] where BN fusion is essential for aggregating local models, as shown in recent works [25, 24, 37]. Achieving optimal fusion entails constructing a consensus model that captures the conditional dependencies of the input networks. While this problem is NP-hard [33], [34] proposed a heuristic approach to approximate the optimal fused BN, significantly reducing computational requirements. However, the standard fusion of BNs often generates dense and complex graphs, limiting its usability in scenarios requiring efficient inference and interpretability. Inference complexity in a BN depends on its treewidth 𝑡, defined as the size of the largest subset of nodes fully connected (clique) in a triangulated version of the network’s moral graph1 . As 𝑡 increases, inference complexity scales exponentially, 𝑂(𝑛 ·𝑘 𝑡 +1 ) [7], where 𝑛 is the number of variables and 𝑘 the states per variable, making high treewidth BNs infeasible for practical use. To mitigate this, [38] proposed a genetic algorithm that prunes edges in the fused network,

CCS Concepts • Computing methodologies → Genetic algorithms; • Mathematics of computing → Bayesian networks; • Theory of computation → Evolutionary algorithms.

Keywords Bayesian Networks, Fusion, Consensus, Genetic Algorithm, Combinatorial Optimization, Federated Learning ACM Reference Format: Pablo Torrijos, José A. Gámez, José M. Puerta, and Juan A. Aledo. 2025. Genetic Algorithms for Tractable Bayesian Network Fusion via Pre-Fusion Edge Pruning. In Genetic and Evolutionary Computation Conference (GECCO ’25), July 14–18, 2025, Malaga, Spain. ACM, New York, NY, USA, 9 pages. https://doi.org/10.1145/3712256.3726333 Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. GECCO ’25, July 14–18, 2025, Malaga, Spain © 2025 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 979-8-4007-1465-8/2025/07 https://doi.org/10.1145/3712256.3726333

Introduction

1 The moral graph of a BN is the undirected graph obtained by linking all pairs of

non-adjacent nodes with a common child and then removing edge directions.

GECCO ’25, July 14–18, 2025, Malaga, Spain

reducing its treewidth while retaining the essential structure of the unrestricted fusion to enhance scalability and usability. Given the NP-hard nature of many problems related to BNs, evolutionary computation has been widely employed as a heuristic solution approach. This technique has been utilized not only in structural learning of BNs [26], but also in triangulating the moral graph needed for BN inference [15], and finding the most probable explanation given observations [11]. In this paper, we propose a new fusion methodology designed to achieve a desired treewidth in the final consensus BN by selectively removing edges in the original BNs before fusion using a genetic algorithm [19] with operators precisely adjusted to the nature of the problem. We design two distinct approaches: one where each occurrence of an edge in the input BNs is treated as a unique element in the chromosome and can be removed independently, and another where identical edges across the input networks are treated as a single element, with removal decisions applying to all networks simultaneously. For each strategy, a greedy algorithm is developed to provide a baseline for performance comparison. Moreover, our approach differs from [38] by redefining the solution quality metric. While the fusion in [34] is theoretically optimal and captures all conditional independencies, such fidelity may not always be desirable. For instance, in a federated learning setting, if one client introduces erroneous or malicious conditional independencies, it could corrupt the fused BN. Thus, our approach minimizes the divergence between the fused BN and all the input networks while achieving target treewidth, improving robustness against inaccurate or adversarial (in)dependencies. Thus, the main contributions of this work are: • Establishing a new consensus definition for Bayesian Network fusion that minimizes the average divergence between the fused BN and the input networks while complying to a target treewidth constraint. • Proposing two genetic-based algorithms, complemented by corresponding greedy baselines, for achieving BN consensus by selectively pruning edges in the input BNs. • Introducing new metrics to evaluate the quality of fused BNs, focusing on divergence from the input networks. • Providing all the code to allow for reproducibility and boosting research on the topic. The paper is organized as follows: Section 2 covers the basics of Bayesian Networks. Section 3 defines the BN consensus problem and its associated constraints and objectives. Section 4 presents the proposed genetic and greedy algorithms for BN consensus under a treewidth constraint. Section 5 shows experimental results on synthetic and real-world datasets. Section 6 concludes with key findings, implications, and future research directions.

2 Preliminaries 2.1 Bayesian Networks A Bayesian Network (BN) [18, 22, 23] is a probabilistic graphical model representing conditional (in)dependencies among a set of variables X = {𝑋 1, . . . , 𝑋𝑛 }. Formally, a BN is defined as a pair B = (G, P), where G = (X, E) is a Directed Acyclic Graph (DAG) with nodes X representing variables and directed edges E encoding dependencies among these variables, and P is a set of conditional

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

probability distributions, {P(𝑋𝑖 | 𝑝𝑎(𝑋𝑖 ))}𝑛𝑖=1 , where 𝑝𝑎(𝑋𝑖 ) denotes the parent set of 𝑋𝑖 in G. The structure G encodes conditional independencies using the criterion of d-separation [23], which allows factorising the joint Î probability distribution as P(𝑋 1, . . . , 𝑋𝑛 ) = 𝑛𝑖=1 P(𝑋𝑖 | 𝑝𝑎(𝑋𝑖 )). Thus, G imposes that each variable 𝑋𝑖 is conditionally independent of its non-descendants given its parents 𝑝𝑎(𝑋𝑖 ) in the DAG. The independencies encoded by G can be represented as 𝐼 (G), where each element is a conditional independence relationship of the form (𝑋𝑖 ⊥ 𝑋 𝑗 | 𝑍 ), with 𝑋𝑖 and 𝑋 𝑗 conditionally independent given a subset of nodes 𝑍 . A DAG G1 is an I-map (Independence map) of another DAG G2 if 𝐼 (G1 ) ⊆ 𝐼 (G2 ), meaning that G1 encodes at least the same conditional independencies as G2 . A DAG G1 is a minimal I-map of G2 if it is an 𝐼 -map of G2 and no arc can be removed from G1 without violating at least one conditional independence in G2 . Thus, a minimal I-map G1 is the sparsest graph that retains all conditional independencies of G2 .

2.2

Structural Fusion of BNs

Structural fusion in Bayesian Networks aims to merge multiple BNs, potentially derived from different data sources or expert knowledge, into a single BN that captures the essential dependencies of the input networks. Let B = {B1, . . . , B𝑟 } be a set of BNs with corresponding DAGs G = {G1, . . . , G𝑟 }. The goal is to construct a DAG G + that serves as a minimal 𝐼 -map of the intersection of the indeÑ pendence sets in G. Formally, this requires that 𝐼 (G + ) = 𝑟𝑖=1 𝐼 (G𝑖 ), + where G minimizes the number of arcs while capturing the shared conditional independencies among all input DAGs. Thus, any conditional independence in G + is also present in each G𝑖 . For example, consider the three input BNs represented by the DAGs in Fig. 1, each modeling dependencies among variables X = {𝑋 1, 𝑋 2, 𝑋 3, 𝑋 4 }. The goal is to produce a fused DAG G + that maintains only the conditional independencies common to all input DAGs while minimizing the number of arcs. Fig. 2 illustrates two possible fusion outcomes for the DAGs in Fig. 1, where the structure on the right achieves a more optimal fusion by reducing the number of arcs while preserving shared dependencies.

𝑋1

𝑋4

𝑋1

𝑋4

𝑋1

𝑋4

𝑋2

𝑋3

𝑋2

𝑋3

𝑋2

𝑋3

Figure 1: Three input BNs for the fusion process.

𝑋1

𝑋4

𝑋1

𝑋4

𝑋2

𝑋3

𝑋2

𝑋3

Figure 2: Two possible BNs resulting from the fusion of the three input networks in Fig. 1. The process for constructing G + follows these steps [33, 35]: (1) Define an ordering 𝜎 over the variables X. (2) Modify each

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

DAG G𝑖 to obtain an minimal 𝐼 -map G𝑖𝜎 of G𝑖 consistent2 with 𝜎. (3) Construct G + as the union of arcs across all G𝑖𝜎 , i.e.G + = Ð𝑟 𝜎 𝑖=1 𝑎𝑟𝑐𝑠(G𝑖 ), where 𝑎𝑟𝑐𝑠(G) returns the directed edges in G. Algorithm A [33] is applied to perform step (2), maintaining the conditional independencies of each G𝑖 encoded by 𝑑-separation. This guarantees that G + is a minimal 𝐼 -map of the intersection of the independence sets across all input graphs, namely, 𝐼 (G + ) = Ñ𝑟 𝑖=1 𝐼 (G𝑖 ). For the theoretical foundations of algorithm 𝐴, we refer the reader to [33, 35]. The choice of the variable ordering 𝜎 is critical in determining the structure of G + . Algorithm 𝐴 applies this ordering to each input DAG G𝑖 , yielding the minimal 𝐼 -map G𝑖𝜎 of G𝑖 consistent with 𝜎. For example, Fig. 3 illustrates the transformation of DAGs from Fig. 1 using the ordering 𝜎 = (𝑋 1, 𝑋 2, 𝑋 4, 𝑋 3 ). This ordering 𝜎 determines the fused BN shown in Fig. 2 (right).

𝑋1

𝑋4

𝑋1

𝑋4

𝑋1

𝑋4

𝑋2

𝑋3

𝑋2

𝑋3

𝑋2

𝑋3

Figure 3: BNs obtained from those in Fig. 1 after applying algorithm A with 𝜎 = (𝑋 1, 𝑋 2, 𝑋 4, 𝑋 3 ). Although finding the optimal ordering 𝜎 is an NP-hard problem, practical heuristics [34] offer efficient approximate solutions that yield near-optimal fused networks. This is crucial, as a poorly chosen 𝜎 can result in unnecessarily complex fusions. The fusion method proposed in [34] captures all conditional dependencies across the input DAGs G = {G1, . . . , G𝑟 }, but it imposes an “all-or-nothing” requirement: if a dependency exists in any single network G𝑖 , it must also appear in the fused structure G + , regardless of how prevalent it is among the input networks. This strict criterion often results in dense networks with very high treewidth, which increases the computational burden of parameter estimation and inference. High treewidth can render the fused network impractical for applications. To mitigate this issue, we propose exploring a more flexible fusion approach to produce a consensus network with lower treewidth, focusing on capturing a representative subset of dependencies from the input graphs rather than enforcing all conditional dependencies.

2.3

Metrics for Measuring Structural Similarity of BNs

Several metrics can be used to evaluate the structural similarity of BNs. The Structural Hamming Distance (SHD) [39] quantifies structural differences by the minimum number of arc modifications (additions, deletions, or reversals) needed to align two BN structures. However, it neglects conditional independencies encoded by the networks, potentially misrepresenting similarity [34]. To address this, the Structural Moral Hamming Distance (SMHD) [20, 24, 25, 38] compares the moral graphs of two networks SMHD(G1, G2 ) = |Emoral (G1 )△Emoral (G2 )| , 2 A DAG G over X is said to be consistent with an ordering 𝜎 of X if, for every node 𝑋 ∈ X , all parents of 𝑋 in G precede 𝑋 in 𝜎 .

GECCO ’25, July 14–18, 2025, Malaga, Spain

where Emoral (G) is the set of undirected edges in the moralized graph of G, and △ represents the symmetric difference. Complementing this, the Fusion Similarity (FSim, introduced in [34], Section 6.2) evaluates the structural similarity based on the minimal 𝐼 -maps of the networks under a shared topological order 𝜎 of the variables. Unlike SMHD, which focuses on the structural differences of the graphs, FSim emphasizes the differences in the conditional independencies encoded by the BNs.

Problem Definition

The fusion method proposed in [34] generates a fused network G + that retains all dependencies present in any of the input networks G = {G1, . . . , G𝑟 }. While theoretically optimal in preserving all conditional dependencies of the input networks, this approach often yields a network with high treewidth. To address this, [38] introduced the concept of Restricted Structural Fusion of BNs, where edges in the fused network G + are selectively removed to reduce the treewidth under a limit while minimizing the Structural Moral Hamming Distance (SMHD) to G + . This approach aims to approximate G + closely while constraining the treewidth, resulting in a more tractable network denoted as G𝑡+𝑤 ≤𝑡 . However, using G + as the reference structure has limitations. Since G + aggregates all dependences present in the input BNs, it may introduce unnecessary complexity. This issue is particularly evident when one or more input networks contain noisy or irrelevant dependencies, which can disproportionately distort the fusion when G + serves as the reference. Consider the example in Fig. 4 (with metric scores in Table 1). Here, three input networks (each with treewidth 2) are fused (Figs. 4a, 4b, and 4c). The unrestricted fusion G + (Fig. 4d) results in a network with treewidth 5. In contrast, the constrained treewidth approach in [38] yields G𝑡+𝑤 ≤3 (Fig. 4e), which approximates G + by removing only two edges, resulting in a complex network but achieving treewidth 3. Note that Fig. 4f is described later in the document for a different example after Definition 1.

𝑋2 𝑋1

𝑋5

𝑋3

𝑋4

𝑋5

(a) G1 .

𝑋4

𝑋1

𝑋2

𝑋4

(b) G2 .

𝑋1 𝑋3

𝑋2

𝑋3

𝑋1

𝑋4

𝑋2 (c) G3 .

𝑋1 𝑋3

𝑋2

𝑋5

𝑋4

𝑋1 𝑋3

𝑋2

𝑋5

(d) G + .

(e) G𝑡+𝑤 ≤3 .

(f) G𝑡∗𝑤 ≤3 .

Figure 4: Fusion of {G1, G2, G3 }: unrestricted (G + ) and restricted to 𝑡𝑤 = 3 (G𝑡+𝑤 ≤3 and G𝑡∗𝑤 ≤3 ).

GECCO ’25, July 14–18, 2025, Malaga, Spain

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

Table 1: Metrics for BNs in Figure 4 and Figure 5. tw denotes the treewidth of the BN; SMHD G + is the SMHD with respect to the fusion G + ; SMHDG is the average SMHD over the initial BNs G; and FSimG is the average FSim over G. Dashes indicate cases where the metric is not meaningful, such as when averages would involve self-comparisons. Figure 4

BN tw

SMHD G +

SMHDG

3 {G𝑖 }𝑖=1

—

G+ G𝑡+𝑤 ≤3 G𝑡∗𝑤 ≤3

5 3 2

— 3 7

6 4.33 3

7.33 5.33 3.33

99 {G𝑖 }𝑖=1 G100 G+

G𝑡+𝑤 ≤3 G𝑡∗𝑤 ≤3

SMHD G +

SMHDG

FSimG

2 5 5 3 2

6 0 — 3 6

— — 5.94 3 0.06

— — 4.95 2.99 0.05

In a second example (Fig. 5, with metric scores in Table 1), the effect of noise on the fusion process is more pronounced. Here, 99 input networks with treewidth 2 share dependencies (Fig. 5a), but a single input network G100 (Fig. 5b) introduces spurious dependencies. This could, for example, be a case of federated learning in which a client is malicious. As a result, the unrestricted fusion G + incorporates these noisy dependencies and becomes overly dense, essentially replicating G100 . Even with treewidth constrained, G𝑡+𝑤 ≤3 (Fig. 5c) fails to represent a consensus of the majority due to the excessive influence of G100 .

𝑋1 𝑋4 𝑋3

𝑋5

𝑋1

𝑋4

𝑋1

𝑋4 𝑋3

𝑋2 𝑋2

99 , G ∗ (a) { G𝑖 }𝑖=1 𝑡 𝑤 ≤3 .

𝑋5 (b) G100

𝑋3

𝑋2 𝑋5

, G+ .

𝑟

G𝑡∗𝑤 ≤𝑡 = arg

1 ∑︁ 𝑀𝑒𝑡𝑟𝑖𝑐 (G, G𝑖 ) G; tw(G)≤𝑡 𝑟 𝑖=1 min

(1)

where Metric (G, G𝑖 ) represents a structural distance metric, such as SMHD or FSim, used to evaluate the similarity between the fused graph G and each of the original networks G𝑖 .

Figure 5

BN FSimG

fusion is defined as

100 : unrestricted (G + ) and restricted Figure 5: Fusion of {G𝑖 }𝑖=1 to 𝑡𝑤 = 3 (G𝑡+𝑤 ≤3 and G𝑡∗𝑤 ≤3 ).

These examples illustrate that defining restricted fusion based on G + can lead to a complex fused network that fails to capture the (in)dependencies of the input BNs. In response, we propose a new problem definition that avoids using G + as a reference. Instead, we directly measure similarity to each input network G𝑖 , defining the fused network as one that minimizes the average structural distance to all input networks under a treewidth constraint, thus better capturing shared dependencies and mitigating noise or errors. Definition 1 (Restricted Structural Consensus of Bayesian Networks Relative to Original Graphs). Let G = {G1, . . . , G𝑟 } be the DAGs representing the graphical structure of 𝑟 BNs defined over the same domain. The goal of the restricted structural consensus relative to the input graphs is to obtain a fused graph G𝑡∗𝑤 ≤𝑡 , which maximizes the average similarity between the fused graph G and the input graphs G𝑖 , subject to a treewidth constraint, by minimizing a defined structural distance metric. Specifically, for a given maximum treewidth 𝑡 ∈ N, with 𝑡 ≥ 2, the restricted structural

This definition relaxes the notion of fusion to a consensus in which the resulting network G𝑡∗𝑤 ≤𝑡 captures essential dependencies shared across input networks, subject to a treewidth constraint. Revisiting the examples, in Figure 4, while the input networks have simple structures, their conditional independencies vary, making the unrestricted fusion G + complex. Our consensus approach (Fig. 4f) generates a G𝑡∗𝑤 ≤3 network with fewer edges than even the input networks, reflecting a more balanced consensus. Metrics in Table 1 show that G𝑡+𝑤 ≤3 achieves better SMHD G + , while G𝑡∗𝑤 ≤3 achieves better SMHDG and FSimG . This effect is even clearer in the second example (Fig. 5). Since G + and G𝑡+𝑤 ≤3 (Figs. 5b and 5c) both over-represent the noisy dependencies from G100 , our consensus definition G𝑡∗𝑤 ≤3 (Fig. 5b) reflects 99 while omitting the noise introducing the shared structure of {G𝑖 }𝑖=1 by G100 . As shown in Table 1, the new consensus approach yields significantly better SMHDG and FSimG , nearly matching the ideal structure shared by most input networks. An additional advantage of this consensus approach is that unlike the restricted fusion method from [38], which tends to exploit the maximum allowable treewidth 𝑡 to minimize SMHD G + , our new approach produces G𝑡∗𝑤 ≤𝑡 consensus BNs that maintain manageable treewidth values, often similar to or even lower than those of the input BNs. Consequently, our method ensures tractable networks with lower complexity, facilitating efficient parametric learning and inference operations.

Genetic Approach for BN Consensus Under Treewidth Constraints

This work presents a genetic algorithm for the consensus of Bayesian networks introduced in Definition 1 under a treewidth constraint (𝑡). The approach prunes arcs from the input networks to construct a consensus structure that balances structural similarity and computational feasibility. By integrating a problem-specific greedy initialization with tailored genetic operators, the algorithm ensures efficient exploration and exploitation of the search space while adhering to the treewidth limitation.

4.1

Chromosome Representation

The representation of a chromosome 𝐶 depends on the choice of the edge set E, with two possible configurations: Without Repetition: EG∗ . 𝐶 represents all unique edges across Ð the input graphs: EG = 𝑟𝑖=1 edges(G𝑖 ). Let 𝑠 = |EG |, with edges arranged in lexicographical order by their subscripts (e.g., 𝑎 1,3 ≺ 𝑎 1,6 ≺ 𝑎 3,4 ). A chromosome 𝐶 ∈ {0, 1}𝑠 encodes whether each edge is included (1) or excluded (0) across all input networks. With Repetition: EG . 𝐶 accounts for all edges from each input Ã𝑟 graph separately: EG∗ = 𝑖=1 edges(G𝑖 ). Let 𝑠 ∗ = |EG∗ |, with edges arranged in lexicographical order by their subscripts and the graph

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

to which they belong (e.g., 𝑎 12,3 ≺ 𝑎 13,4 ≺ 𝑎 31,2 ). A chromosome ∗ 𝐶 ∈ {0, 1}𝑠 specifies the inclusion (1) or exclusion (0) of each edge for each graph independently. Trade-off. The choice between EG and EG∗ balances simplicity and flexibility. EG∗ defines a smaller search space, facilitating faster convergence and consistent pruning across networks but limiting specificity. In contrast, EG allows network-specific pruning, potentially achieving better solutions but requiring exploration of a larger and more computationally intensive search space.

4.2

Fitness Function

The fitness function evaluates a chromosome 𝐶 based on the structural similarity of the fused graph G𝐶∗ to the original input networks {G1, . . . , G𝑟 }, while penalizing violations of the treewidth constraint. Given 𝐶, the modified input graphs {G𝐶1 , . . . , G𝐶𝑟 } are defined as: ( {𝑎𝑖𝑗𝑘 ∈ edges(G𝑖 ) | 𝐶(𝑎𝑖𝑗𝑘 ) = 1}, if E = EG 𝑖 𝑖 𝑖 G𝐶 = (X, E𝐶 ); E𝐶 = {𝑎 𝑗𝑘 ∈ edges(G𝑖 ) | 𝐶(𝑎 𝑗𝑘 ) = 1}, if E = EG∗ The fused graph G𝐶∗ is obtained by applying the method in Section 2.2 [34] to {G𝐶1 , . . . , G𝐶𝑟 }. The fitness is then computed as: ( 𝑟 1, if tw(G𝐶∗ ) ≤ 𝑡, 1 ∑︁ ∗ Metric(G𝐶 , G𝑖 ) · tw(G ∗ ) 𝑓 (𝐶) = 𝐶 𝑟 𝑖=1 otherwise, 𝑡

where tw(G) denotes the treewidth of G. Minimizing 𝑓 (𝐶) ensures high structural similarity to the input graphs while preserving the treewidth constraint. The penalty term guides the search away from infeasible solutions.

4.3

Algorithm Structure

The proposed genetic algorithm, detailed in Alg. 1, tackles the challenge of BN consensus under a treewidth constraint (Definition 1). The decoding of chromosomes into graphs and the computation of the fitness function are computationally demanding, requiring a careful trade-off between solution quality and efficiency. Due to the exponential growth of the search space with the size of the candidate edge set |E |, the algorithm employs a fixediteration, population-based approach. Excessive population sizes or iterations are avoided to manage the complexity of evaluating individuals, instead focusing on efficient initialization and tailored operators to maximize iteration effectiveness. Key features of the algorithm include: • Hybrid initialization: Combines heuristic solutions from the greedy algorithm (Alg. 2) with random chromosomes, mixing quality starting points and population diversity. • Problem-specific operators: Mutation is tailored to the search space’s structured nature, focusing on efficiently producing high-quality offspring. • Constraint-guided fitness: Solutions exceeding the treewidth constraint are penalized, steering the population toward feasible configurations. The following subsections provide details on initialization, crossover, mutation, and population update strategies.

GECCO ’25, July 14–18, 2025, Malaga, Spain

Algorithm 1 Genetic Pre-Fusion Edge Pruning for BN Consensus with Limited Treewidth Require: {G1, . . . , G𝑟 } defined over X; 𝑡 ≥ 2; 𝑛𝐼𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛𝑠; 𝑝𝑜𝑝𝑆𝑖𝑧𝑒; 𝑟𝑒𝑝 (boolean) Ensure: {G1∗, . . . , G𝑟∗ }, G𝑡∗𝑤 ≤𝑡 ß Ã𝑟 edges(G𝑖 ) if 𝑟𝑒𝑝 Ð𝑟𝑖=1 1: E ← edges(G𝑖 ) o.w. 𝑖=1 ® Í #(𝑎𝑖𝑗𝑘 ) ← 𝑟𝑖=1 1(𝑎𝑖𝑗𝑘 ∈ G𝑖 ), ∀𝑎𝑖𝑗𝑘 ∈ E if 𝑟𝑒𝑝 Í 2: #(𝑎 𝑗𝑘 ) ← 𝑟𝑖=1 1(𝑎 𝑗𝑘 ∈ G𝑖 ), ∀𝑎 𝑗𝑘 ∈ E o.w. 3: {G1∗ , . . . , G𝑟∗ } ← empty graphs over X 4: 𝐶 ∗ , 𝐶 𝑙 ← ∅ ⊲ Best chromosome seen so far/in the last iteration 5: C𝑔𝑟 ← {Alg. 2({G1 , . . . , G𝑟 }, 𝑡, 𝑟𝑒𝑝)} 6: C𝑔𝑟 ← C𝑔𝑟 ∪ {Alg. 2({G1 , . . . , G𝑟 }, 𝑡 − 1, 𝑟𝑒𝑝)} if 𝑡 > 2 7: C ← initialization(𝑝𝑜𝑝𝑆𝑖𝑧𝑒 − |C𝑔𝑟 |, #(𝑎 𝑗𝑘 ), E) ∪ C𝑔𝑟 8: for 𝑖 ← 1 to 𝑛𝐼𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛𝑠 do 9: 𝐶 ∗, 𝐶 𝑙 , {G1∗, . . . , G𝑟∗ }, G𝑡∗𝑤 ≤𝑡 ← evaluate(C, {G1, . . . , G𝑟 }) 10: C ← selection(C) 11: C ← crossover(C) 12: C ← mutation(C) 13: C ← (C \ {𝐶 𝑤𝑜𝑟𝑠𝑡1 , 𝐶 𝑤𝑜𝑟𝑠𝑡2 }) ∪ {𝐶 ∗, 𝐶 𝑙 } ⊲ Elitism 14: end for 15: Return {G1∗ , . . . , G𝑟∗ }, G𝑡∗𝑤 ≤𝑡

4.3.1 Initialization. The population initialization (size 𝑝𝑜𝑝𝑆𝑖𝑧𝑒) combines heuristic solutions from the problem-specific greedy prefusion edge pruning algorithm (Alg. 2) with probabilistic sampling to ensure both quality and diversity. The greedy algorithm, tailored for this task, iteratively adds edges to maximize structural similarity while respecting treewidth constraints, with variants for handling edge repetitions. Two chromosomes are generated using this method: one for treewidth 𝑡 and another for 𝑡 − 1 (if 𝑡 > 2). The remaining chromosomes are initialized probabilistically, guided by the edge frequencies #(𝑎 𝑗𝑘 ) in the input graphs3 . For each 1 edge 𝑎 𝑗𝑘 ∈ E, its inclusion probability is P(𝐶(𝑎 𝑗𝑘 ) = 1) = 1−log(𝑥) , 4 where 𝑥 is the min-max normalized value of #(𝑎 𝑗𝑘 ). 4.3.2 Crossover. Crossover operates by pairing the selected individuals (with a tournament selection of size 2) and applying a common single-point crossover. A random crossover point is chosen for each pair, splitting their chromosomes into two parts. The offspring are generated by combining the first segment of one parent with the second segment of the other, resulting in 𝑝𝑜𝑝𝑆𝑖𝑧𝑒 new individuals in the population. 4.3.3 Mutation. In the mutation stage, all chromosomes are candidates for potential modifications. The probabilities for adding or removing edges are dynamically adjusted based on the ratio tw(G ∗ )

𝑥 = 𝑡 𝐶 , balancing exploration and exploitation. The mutation probabilities are defined as ® 𝑥 −1 2 𝑥 + 0.01, 10 , 𝑥 ≤1 P(add), P(remove) = 0.012 . log(𝑥) , + 0.01, 𝑥>1 𝑥 3 3 By abuse of notation, 𝑎 𝑖 𝑗𝑘 refers to both 𝑎 𝑗𝑘 and 𝑎 𝑗𝑘 in this paragraph. 4 Uniform random initialization (P = 0.5) occurs when all edges have equal frequency.

GECCO ’25, July 14–18, 2025, Malaga, Spain

Algorithm 2 Greedy Pre-Fusion Edge Pruning for BN Consensus with Limited Treewidth Require: {G1, . . . , G𝑟 } defined over X; 𝑡 ≥ 2; 𝑟𝑒𝑝 (boolean) Ensure: {G1∗, . . . , G𝑟∗ }, G𝑡∗𝑤 ≤𝑡 ß Ã𝑟 edges(G𝑖 ) if 𝑟𝑒𝑝 Ð𝑟𝑖=1 1: E ← edges(G o.w. 𝑖) 𝑖=1 ® Í #(𝑎𝑖𝑗𝑘 ) ← 𝑟𝑖=1 1(𝑎𝑖𝑗𝑘 ∈ G𝑖 ), ∀𝑎𝑖𝑗𝑘 ∈ E if 𝑟𝑒𝑝 Í 2: #(𝑎 𝑗𝑘 ) ← 𝑟𝑖=1 1(𝑎 𝑗𝑘 ∈ G𝑖 ), ∀𝑎 𝑗𝑘 ∈ E o.w. ∗ ∗ 3: {G1 , . . . , G𝑟 } ← empty graphs over X 4: G𝑡∗𝑤 ≤𝑡 ← ∅ 5: while E ≠ ∅ do 6: 𝑎 𝑗𝑘 ← arg max𝑎 𝑗𝑘 ∈ E #(𝑎 𝑗𝑘 ) 7: E ← E®\ {𝑎 𝑗𝑘 } G𝑖∗ ∪ {𝑎𝑖𝑗𝑘 }, ∀𝑖 : 𝑎𝑖𝑗𝑘 ∈ edges(G𝑖 ) if 𝑟𝑒𝑝 8: G𝑖∗ ← G𝑖∗ ∪ {𝑎 𝑗𝑘 }, for ∃!𝑖 : 𝑎 𝑗𝑘 ∈ edges(G𝑖 ) o.w. 9: 𝜎 ← an ordering for X ⊲ Use [34] 10: G𝑖𝜎 ← 𝐴(G𝑖∗, 𝜎) ∀𝑖 ∈ {1, . . . , 𝑟 } Ð 11: if tw( 𝑟𝑖=1 G𝑖𝜎 ) ≤ 𝑡 then Ð ∗ 12: G𝑡 𝑤 ≤𝑡 ← 𝑟𝑖=1 G𝑖𝜎 13: else ® G𝑖∗ \ {𝑎𝑖𝑗𝑘 }, ∀𝑖 : 𝑎𝑖𝑗𝑘 ∈ edges(G𝑖 ) if 𝑟𝑒𝑝 ∗ 14: G𝑖 ← G𝑖∗ \ {𝑎 𝑗𝑘 }, for ∃!𝑖 : 𝑎 𝑗𝑘 ∈ edges(G𝑖 ) o.w. 15: end if 16: end while 17: Return {G1∗ , . . . , G𝑟∗ }, G𝑡∗𝑤 ≤𝑡

Each edge in the chromosome is mutated independently. For edge addition, a candidate edge 𝑎 𝑗𝑘 ∉ E𝐶 is added with probability P(add). For edge removal, an existing edge 𝑎 𝑗𝑘 ∈ E𝐶 is removed with probability P(remove). This adaptive approach ensures a balanced search space exploration while steering solutions toward the feasible region with treewidth ≤ 𝑡. 4.3.4 Population Update. After the mutation step, the population is updated using an elitist strategy to balance genetic diversity and solution quality. Specifically, the two least fit individuals in the population are replaced by (1) 𝐶 ∗ , the best chromosome found during the evolutionary process, and (2) 𝐶 𝑙 , the best chromosome from the previous generation. This approach ensures that high-quality genetic material persists across generations while maintaining diversity to prevent premature convergence.

Experimental Evaluation

To ensure comparability, our experimental setup follows the approach in [34, 38], extended to use larger Bayesian Networks (BNs) and new metrics relevant to this problem.

5.1

Networks / datasets

As in [38], we evaluate using synthetic and real-world BNs. Input DAGs G = {G1, . . . , G𝑟 } are generated from a base DAG G0 by applying the method in [34, 38]. Each network of G undergoes 𝑝 = 𝑛 · 0.75 perturbations, where 𝑛 is the number of nodes. A randomly selected edge {𝑋 → 𝑌 } is either added or removed in each perturbation, ensuring acyclicity. BN complexity is constrained

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

by limiting each node to three parents, four children, and 𝑒 = 𝑛 · 2.5 edges in the network, preserving structural similarity to G0 . For the synthetic networks, G0 is generated using the method proposed in [32], as in [34, 38]. For real-world networks, we employ seven BNs from the bnlearn Bayesian Network Repository5 . These networks, selected from various domains, represent a range of complexities regarding node count, edge density, and inference parameters, as seen in Table 2. To facilitate parametric learning on the generated BNs in assessing their potential use for inference across different treewidth limits, we also generate samples of 5000 instances for each real-world BN using the corresponding DAG and parameters. Table 2: Real-world BNs used in the experiments.

#Nodes #Edges #Params

5.2

Child

Insurance

Water

Mildew

Alarm

Barley

Hailfinder

20 25 230

27 52 1 008

32 66 10 083

35 46 540 150

37 46 509

48 84 114 005

56 66 2 656

Algorithms

This study evaluates the performance of genetic and greedy algorithms for BN consensus under a treewidth constraint, considering various candidate edge set configurations: • E G + : Edges are derived from the fused network G + , as defined in [38]. The greedy and genetic algorithms from [38] are adapted to optimize metrics relative to the original input graphs rather than G + . • EG : Edges include repetitions from each input graph, EG = Ã𝑟 𝑖=1 edges(G𝑖 ). The proposed genetic algorithm (Alg. 1) and its greedy baseline (Alg. 2) are applied to allow independent inclusion decisions (rep = True). • EG∗ : Edges are unique across the input graphs, EG∗ = Ð𝑟 𝑖=1 edges(G𝑖 ). Alg. 1 and Alg. 2 are applied with uniform inclusion decisions (rep = False). This setup allows us to investigate how the adapted algorithm from [38] performs in the new consensus framework and whether changing edges in the original graphs before fusion improves the quality of the constrained consensus BN.

5.3

Reproducibility

All algorithms were implemented in Java (OpenJDK 17) using the Tetrad 7.6.5 causal reasoning library6 . For reproducibility, the complete code, BNs, and datasets are available on GitHub7 , with datasets also hosted in OpenML8 . All experiments were conducted in a controlled environment on Rocky Linux 8.9 machines with AMD EPYC 7453 processors, using seven threads and 8 GB RAM per run.

5.4

Methodology

To scale up from prior work [38], we evaluate larger networks with more input DAGs. For both synthetic and real-world BNs, we set 5 https://www.bnlearn.com/bnrepository/ 6 https://github.com/cmu-phil/tetrad/releases/tag/v7.6.5 7 https://github.com/ptorrijos99/BNFusion 8 https://www.openml.org/search?type=data&tags.tag=bnlearn

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

#Nodes = 10 | #DAGs = 30

SMHD

#Nodes = 30 | #DAGs = 10

SMHD

#Nodes = 10 | #DAGs = 50

5 2

2 250

#Nodes = 30 | #DAGs = 30

200

150

100

15 400

150

200

100

8 Algorithm  +  * Genetic Greedy tw()

#Nodes = 50 | #DAGs = 30

300

100

200

#Nodes = 50 | #DAGs = 10

#Nodes = 30 | #DAGs = 50 250

SMHD

FSim

7.5

{tw()}max min

#Nodes = 50 | #DAGs = 50

400

200

0 10

Maximum Treewidth

5.0

2.5 2

#Nodes = 30 | #DAGs = 10

#Nodes = 30 | #DAGs = 30

8 Algorithm  + 

150

FSim

#Nodes = 30 | #DAGs = 50 200

150

*

100

Genetic Greedy

10 0

0 5

#Nodes = 50 | #DAGs = 10

{tw()}max min

#Nodes = 50 | #DAGs = 50

150

200

150

100

tw() 5

#Nodes = 50 | #DAGs = 30

100

40 50

0 10

Maximum Treewidth

Figure 7: FSimG in synthetic BNs, for each possible 𝑡. and the 𝑝-value from Holm’s post-hoc test. The Friedman test yields 1.05 × 10−141 for SMHDG and 1.72 × 10−128 for FSimG , rejecting 𝐻 0 in both cases. For context, the unrestricted G + fusion method shows a mean difference of 211.5 in SMHDG and 98.9 in FSimG from the best-performing algorithm across all datasets. Table 3: Results on synthetic BNs.

This section evaluates the proposed algorithms on synthetic BNs, aiming to minimize two key metrics: SMHD and FSim (Section 2.3) relative to the original input networks, SMHDG and FSimG , respectively. These metrics measure the fused network’s structural similarity to the input BNs. Two independent runs were conducted for the genetic algorithms: one optimizing SMHDG and the other FSimG . Figures 6 and 7 summarize the results, showing average performance across various treewidth constraints, along with the range {tw(G)}𝑚𝑎𝑥 𝑚𝑖𝑛 and average tw(G) of the input graphs for context. #Nodes = 10 | #DAGs = 10

#Nodes = 10 | #DAGs = 50

10.0

Results for Synthetic BNs

#Nodes = 10 | #DAGs = 30

12.5

Maximum Treewidth

Figure 6: SMHDG in synthetic BNs, for each possible 𝑡. Table 3 summarizes the results, including the mean difference between the best-performing algorithm and others (Diff), the number of best performances (#Best), average execution time (Time (s)),

SMHDG

Algorithm Diff Greedy Genetic

5.5

#Nodes = 10 | #DAGs = 10 15.0

FSim

𝑟 = {10, 30, 50} as the number of input DAGs. We vary the number of nodes for synthetic networks with 𝑛 = {10, 30, 50}. Real-world networks, in contrast, have a fixed number of nodes ranging from 20 in child to 56 in hailfinder, as detailed in Table 2. To assess the fusion quality, we introduce two metrics (Section 2.3): the average SMHD score and Fusion Similarity relative to the initial set of DAGs, G = {G1, . . . , G𝑟 }. We denote these metrics as 𝑚 = {SMHDG, FSimG }. For each base DAG G0 , ten sets of input DAGs G𝑖 = {G1𝑖 , . . . , G𝑟𝑖 } were generated using distinct random seeds, along with ten datasets D𝑖 of 5000 instances for real-world networks. For each (𝑖, 𝑟, 𝑛, 𝑚, 𝑡𝑤) combination, with 𝑡𝑤 ∈ {𝑡 | 2 ≤ 𝑡 < tw(G + )}, each genetic algorithm and its greedy counterpart from Section 5.2 was run. Genetic algorithms used a population size of 100, following the optimal configuration identified in [38]. Parametric learning was conducted using the Expectation Maximization (EM) method implemented in the Tetrad library. The gold-standard network was reparametrized with the dataset generated from the corresponding random seed. Results were analyzed using the methodology in [12, 16] with the exreport R package [3]. A Friedman test [13] was applied to test the null hypothesis 𝐻 0 that all algorithms are equal. If rejected, a post-hoc Holm procedure [17] compared the algorithms to the top-ranked one, with both tests at a 1% significance level.

GECCO ’25, July 14–18, 2025, Malaga, Spain

FSimG

𝑝-value #Best Time (s) Diff

𝑝-value #Best Time (s)

EG∗ (Alg. 1) EG (Alg. 1) E G + [38]

3.5 — 15.1 9.16 × 10−7 12.6 1.34 × 10−6

95 95 27

50.5 250.0 4.1

1.4 — 9.5 1.22 × 10−5 5.4 2.31 × 10−5

90 91 30

1 790.5 2 386.2 1 785.9

EG∗ (Alg. 2) EG (Alg. 2) E G + [38]

73.0 4.38 × 10−25 114.5 4.07 × 10−108 85.8 6.24 × 10−56

1 0 0

8.5 127.8 0.1

30.9 4.23 × 10−24 62.7 3.57 × 10−96 39.7 2.86 × 10−50

1 0 0

14.3 274.6 0.1

Based on these results, we can draw the following conclusions: Alg. 1 vs. [38]. Alg. 1 without edge repetition (EG∗ ) consistently achieves the best results across all configurations, offering stability in both SMHDG and FSimG , though with slightly longer runtimes than the genetic algorithm in [38] using E G + . With edge repetition (EG ), Alg. 1 excels at higher treewidths but struggles in constrained settings due to an expanded search space. However, such scenarios, where fusion is restricted to treewidths smaller than those of the original graphs, are uncommon and may reduce the practical value of the fusion process. Statistical tests confirm significant differences among all approaches in both SMHDG and FSimG , rejecting 𝐻 0 , with EG∗ emerging as the best-performing method. Greedy Algorithms. The greedy Algorithm 2 with edge repetition (EG ) performs poorly in all settings, with high runtimes due to a larger search space. This also negatively impacts its corresponding genetic algorithm, leading to suboptimal results and increased runtimes. However, genetic algorithms effectively mitigate these limitations, demonstrating strong adaptability, as the greedy methods serve only as initialization and are not the focus of this work. SMHDG vs. FSimG . Results for SMHDG and FSimG are highly correlated, with differences mainly in execution time. FSimG requires

GECCO ’25, July 14–18, 2025, Malaga, Spain

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

repeated fusions, making it computationally heavier and reducing runtime disparities across configurations.

Algorithm

Results on Real-World BNs

This section evaluates the algorithms on real-world BNs, focusing on structural accuracy (SMHDG , FSimG ) and parametric estimation. 5.6.1 Structural Accuracy of the Generated Model. Table 4 summarizes the mean structural accuracy of the generated models for the real-world BNs described in Table 2. The metrics are the same as in Table 3. The Friedman test yields 1.12 × 10−150 for SMHDG and 2.93 × 10−130 for FSimG , rejecting 𝐻 0 in both cases.

SMHDG

Greedy Genetic

Diff

𝑝-value

FSimG

#Best Time (s) Diff

𝑝-value

SMHDG Time∗ Abs Err∗

FSimG

𝑝-value #NaN Time∗ Abs Err∗

𝑝-value #NaN

1.32

0.0381

—

2.09

0.0385

—

EG∗ (Alg. 1) EG (Alg. 1) E G + [38]

1.02 0.93 1.02

0.0412 0.0406 0.0421

5.76 × 10−7 3.02 × 10−2 1.74 × 10−13

4 7 7

0.95 0.98 1.05

0.0410 0.0414 0.0417

7.21 × 10−2 6.44 × 10−4 4.09 × 10−4

2 2 2

EG∗ (Alg. 2) EG (Alg. 2) E G + [38]

18.01 22.17 19.05

0.0466 0.0498 0.0485

1.90 × 10−14 123 4.36 × 10−53 116 3.35 × 10−25 146

17.99 26.05 23.23

0.0478 0.0515 0.0497

2.78 × 10−14 1.31 × 10−47 3.43 × 10−23

43 58 56

G+

112.84

0.0554

8.05 × 10−67 280

145.03

0.0568

3.87 × 10−55 280

differences between those optimized with SMHDG or FSimG . Statistical tests confirm the original graphs G as the best method, with no significant difference from EG in SMHDG and EG∗ in FSimG .

Table 4: Results on real-world BNs. Algorithm

Greedy Genetic

5.6

Table 5: Parametric estimation results on real-world BNs.

#Best Time (s)

EG∗ (Alg. 1) EG (Alg. 1) E G + [38]

12.6 — 9.3 1.57 × 10−2 22.5 1.46 × 10−8

176 379 27

160.8 397.1 9.2

4.0 — 7.2 2.01 × 10−2 11.2 4.46 × 10−7

178 278 30

1 596.1 1 970.5 1 703.0

EG∗ (Alg. 2) EG (Alg. 2) E G + [38]

160.4 1.25 × 10−34 192.3 1.07 × 10−86 179.5 7.01 × 10−78

2 0 0

18.4 167.5 0.2

51.5 2.14 × 10−24 96.5 2.56 × 10−82 71.1 1.12 × 10−61

1 0 0

13.0 128.2 0.2

Real-world results align with synthetic ones, with some notable differences. EG achieves the most wins in both SMHDG and FSimG and the best average in SMHDG , while EG∗ leads on average in FSimG . Both genetic methods outperform [38], which remains faster for SMHDG . The gap between greedy and genetic algorithms is even more pronounced, reinforcing the robustness of the genetic approach. Statistical tests confirm EG∗ as the best method, though not significantly different from EG , while both significantly outperform all others. 5.6.2 Parameter Estimation in the Generated Model. This section evaluates the parametric learnability of the generated BNs by measuring average learning time (Time∗ ), mean absolute error (Abs Err∗ ) against gold-standard computed marginal probabilities, and the frequency of learning failures (#NaN), where a failure is counted if any seed results in failure (maximum value for #NaN is 551). Time∗ and Abs Err∗ are only computed when all algorithms finish successfully, i.e., if G + completes execution. The results, summarized in Table 5, compare the parametric estimation performance on G + and the average of the input networks G. The table also reports Holm post-hoc test p-values for mean absolute errors. The Friedman test yields 2.24 × 10−106 for SMHDG and 1.43 × 10−100 for FSimG , rejecting 𝐻 0 in both cases. The results align with expectations. The cases where conditional probability distributions cannot be estimated (#NaN) grow exponentially for algorithms producing the densest networks. The original graphs G achieve the lowest error, while the unrestricted fusion G + shows the highest. Greedy algorithms closely approximate G + , while genetic algorithms perform better, generating networks similar or simpler than the originals with reduced execution times. Failures are fewer than with greedy algorithms, due to memory limitations as the treewidth constraint approaches that of G + . Both genetic algorithms outperform the one from [38], with minimal

Conclusions

This study proposed a novel framework for Bayesian Network (BN) fusion, redefining the task as achieving structural consensus under a treewidth constraint. Traditional methods [34] often generate overly complex networks, while constrained approaches [38] risk overfitting to input noise. Our consensus-driven approach addresses these issues by emphasizing shared structures and minimizing divergence between the fused network and the input BNs. To solve this problem, we designed two specialized genetic algorithms featuring advanced initialization strategies, problem-specific genetic operators, and a fitness function that balances structural similarity with treewidth constraints. Furthermore, we introduced metrics to evaluate consensus quality while controlling BN complexity. Experimental results on synthetic and real-world datasets demonstrated the effectiveness of the proposed methods. The genetic algorithms consistently outperformed an adapted version of prior work [38], confirming the benefits of pruning edges directly in the input BNs before fusion. Furthermore, the practical usability of the fused networks was validated by examining the learnability of their conditional probability tables (CPTs). Notably, the algorithm allowing edge repetitions while exploring a larger and more complex search space achieved superior solutions in specific cases, underscoring the trade-off between convergence stability and solution quality. In conclusion, the proposed genetic algorithms offer a robust and flexible solution for constrained BN consensus. Future research could focus on developing enhanced greedy heuristics for initialization, exploring advanced optimization strategies, and extending the framework to applications such as federated learning and other domains requiring constrained graphical model integration.

Acknowledgments This work is funded by MICIU/AEI/10.13039/501100011033 and European Union NextGenerationEU/PRTR under project TED2021-131291B-I00; Junta de Comunidades de Castilla-La Mancha and ERDF, EU under project SBPLY/21/180225/000062; MICIU/AEI/10.13039/501100011033 and ERDF, EU under projects PID2022-139293NB-C32 and FPU21/01074; Universidad de CastillaLa Mancha and ERDF, EU under project 2022-GRIN-34437.

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

References [1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17] [18]

[19]

[20]

[21]

[22]

Tosin Adedipe, Mahmood Shafiee, and Enrico Zio. 2020. Bayesian Network Modelling for the Wind Energy Industry: An Overview. Reliability Engineering & System Safety, 202, (Oct. 2020), 107053. doi:10.1016/j.ress.2020.107053. Nicos Angelopoulos, Aikaterini Chatzipli, Jyoti Nangalia, Francesco Maura, and Peter J. Campbell. 2022. Bayesian networks elucidate complex genomic landscapes in cancer. Communications Biology, 5, 1, (Apr. 2022). doi:10.1038/s4 2003-022-03243-w. Jacinto Arias and Javier Cozar. 2016. exreport: Fast, Reliable and Elegant Reproducible Research. R package version 0.4.1. https://CRAN.R-project.org/package =exreport. Alejandro Barredo Arrieta et al. 2020. Explainable Artificial Intelligence (XAI): concepts, taxonomies, opportunities and challenges toward responsible AI. Information Fusion, 58, (June 2020), 82–115. doi:10.1016/j.inffus.2019.12.012. Jaume Bacardit, Alexander E. I. Brownlee, Stefano Cagnoni, Giovanni Iacca, John McCall, and David Walker. 2022. The intersection of evolutionary computation and explainable AI. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO ’22). Boston, Massachusetts, 1757–1762. doi:10.1145/3520304.3533974. Niko Bernaola, Mario Michiels, Pedro Larrañaga, and Concha Bielza. 2023. Learning massive interpretable gene regulatory networks of the human brain by merging Bayesian networks. PLOS Computational Biology, 19, 12, (Dec. 2023), e1011443. Mingyao Li, (Ed.) doi:10.1371/journal.pcbi.1011443. Venkat Chandrasekaran, Nathan Srebro, and Prahladh Harsha. 2008. Complexity of inference in graphical models. In (UAI’08). AUAI Press, Helsinki, Finland, 70–78. isbn: 0974903949. David Maxwell Chickering. 2002. Optimal Structure Identification With Greedy Search. Journal of Machine Learning Research, 3, Nov, 507–554. http://www.jml r.org/papers/v3/chickering02b.html. David Maxwell Chickering, David Heckerman, and Christopher Meek. 2004. Large-Sample Learning of Bayesian Networks is NP-Hard. Journal of Machine Learning Research, 5, Oct, 1287–1330. https://www.jmlr.org/papers/v5/chickeri ng04a.html. Heng Dai, Jiali Ju, Dongwei Gui, Yan Zhu, Ming Ye, Yujiao liu, Jiebo Cui, and Bill X. Hu. 2024. A two-step Bayesian network-based process sensitivity analysis for complex nitrogen reactive transport modeling. Journal of Hydrology, 632, 130903. doi:10.1016/j.jhydrol.2024.130903. Luis M. de Campos, José A. Gámez, and Serafín Moral. 1999. Partial abductive inference in Bayesian belief networks using a genetic algorithm. Pattern Recognition Letters, 20, 11–13, (Nov. 1999), 1211–1217. doi:10.1016/s0167-8655(99)000 88-4. Janez Demsar. 2006. Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research, 7, (Jan. 2006), 1–30. https://jmlr.org /papers/v7/demsar06a.html. Milton Friedman. 1940. A comparison of alternative tests of significance for the problem of 𝑚 rankings. The Annals of Mathematical Statistics, 11, 1, (Mar. 1940), 86–92. José A. Gámez, Juan L. Mateo, and José M. Puerta. 2011. Learning Bayesian networks by hill climbing: efficient methods based on progressive restriction of the neighborhood. Data Mining and Knowledge Discovery, 22, 1, (Jan. 2011), 106–148. doi:10.1007/s10618-010-0178-6. José A. Gámez and José Miguel Puerta. 2002. Searching for the best elimination sequence in Bayesian networks by using ant colony optimization. Pattern Recognition Letters, 23, 1-3, 261–277. doi:10.1016/S0167-8655(01)00123-4. Salvador García and Francisco Herrera. 2008. An extension on "statistical comparisons of classifiers over multiple data sets" for all pairwise comparisons. Journal of Machine Learning Research, 9, 2677–2694. https://www.jmlr.org/pap ers/v9/garcia08a.html. Sture Holm. 1979. A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 6, 65–70. Finn V. Jensen and Thomas D. Nielsen. 2007. Bayesian Networks and Decision Graphs. (2nd ed.). Springer New York. isbn: 9780387682822. doi:10.1007/978-0387-68282-2. Sourabh Katoch, Sumit Singh Chauhan, and Vijay Kumar. 2020. A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications, 80, 5, (Oct. 2020), 8091–8126. doi:10.1007/s11042-020-10139-6. Gang-Hoo Kim and Sung-Ho Kim. 2019. Marginal information for structure learning. Statistics and Computing, 30, 2, (July 2019), 331–349. doi:10.1007/s112 22-019-09877-x. Neville Kenneth Kitson, Anthony C. Constantinou, Zhigao Guo, Yang Liu, and Kiattikun Chobtham. 2023. A survey of Bayesian Network structure learning. Artificial Intelligence Review, 56, 8, (Jan. 2023), 8721–8814. doi:10.1007/s10462-0 22-10351-w. Uffe B. Kjærulff and Anders L. Madsen. 2013. Bayesian Networks and Influence Diagrams: A Guide to Construction and Analysis. Springer New York. isbn: 9781461451044. doi:10.1007/978-1-4614-5104-4.

GECCO ’25, July 14–18, 2025, Malaga, Spain

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33] [34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

Daphne Koller and Nir Friedman. 2009. Probabilistic Graphical Models: Principles and Techniques - Adaptive Computation and Machine Learning. The MIT Press. isbn: 9780262013192. Jorge D. Laborda, Pablo Torrijos, José M. Puerta, and José A. Gámez. 2024. Distributed fusion-based algorithms for learning high-dimensional Bayesian Networks: Testing ring and star topologies. International Journal of Approximate Reasoning, 175, (Dec. 2024), 109302. doi:10.1016/j.ijar.2024.109302. Jorge D. Laborda, Pablo Torrijos, José M. Puerta, and José A. Gámez. 2024. Parallel structural learning of Bayesian networks: Iterative divide and conquer algorithm based on structural fusion. Knowledge-Based Systems, 296, (July 2024), 111840. doi:10.1016/j.knosys.2024.111840. Pedro Larrañaga, Hossein Karshenas, Concha Bielza, and Roberto Santana. 2013. A review on evolutionary algorithms in Bayesian network learning and inference tasks. Information Sciences, 233, 109–125. doi:10.1016/j.ins.2012.12.05 1. He Li, C. Guedes Soares, and Hong-Zhong Huang. 2020. Reliability analysis of a floating offshore wind turbine using Bayesian Networks. Ocean Engineering, 217, (Dec. 2020), 107827. doi:10.1016/j.oceaneng.2020.107827. Li Li, Yuxi Fan, Mike Tse, and Kuo-Yi Lin. 2020. A review of applications in federated learning. Computers & Industrial Engineering, 149, 106854. doi:10.101 6/j.cie.2020.106854. Yan Lin and Marek J. Druzdzel. 1997. Computational Advantages of Relevance Reasoning in Bayesian Belief Networks. In Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence, Brown University, Providence, Rhode Island, USA, August 1-3, 1997 (UAI’97). Dan Geiger and Prakash P. Shenoy, (Eds.) Morgan Kaufmann Publishers Inc., 342–350. Scott McLachlan, Kudakwashe Dube, Graham A Hitman, Norman E Fenton, and Evangelia Kyrimi. 2020. Bayesian networks in healthcare: Distribution by medical condition. Artificial Intelligence in Medicine, 107, (July 2020), 101912. doi:10.1016/j.artmed.2020.101912. Michelle Meekes, Silja Renooij, and Linda C. van der Gaag. 2015. Relevance of Evidence in Bayesian Networks. In ECSQARU-2015 (Lecture Notes in Computer Science). Vol. 9161. Springer, 366–375. doi:10.1007/978-3-319-20807-7_33. Guy Melançon and Fabrice Philippe. 2004. Generating connected acyclic digraphs uniformly at random. Information Processing Letters, 90, 4, (May 2004), 209–213. doi:10.1016/j.ipl.2003.06.002. J.M. Peña. 2011. Finding Consensus Bayesian Network Structures. The Journal of Artificial Intelligence Research (JAIR), 42, (Jan. 2011). doi:10.1613/jair.3427. José M. Puerta, Juan A. Aledo, José A. Gámez, and Jorge D. Laborda. 2021. Efficient and accurate structural fusion of Bayesian networks. Information Fusion, 66, (Feb. 2021), 155–169. doi:10.1016/j.inffus.2020.09.003. José del Sagrado and Serafín Moral. 2003. Qualitative combination of Bayesian networks. International Journal of Intelligent Systems, 18, 2, 237–249. doi:10.100 2/int.10086. Mauro Scanagatta, Antonio Salmerón, and Fabio Stella. 2019. A survey on Bayesian network structure learning from data. Prog. Artif. Intell., 8, 4, 425–439. doi:10.1007/S13748-019-00194-Y. Pablo Torrijos, José A. Gámez, and José M. Puerta. 2025. FedGES: A Federated Learning Approach for Bayesian Network Structure Learning. In Discovery Science. Springer Nature Switzerland, 83–98. doi:10.1007/978-3-031-78980-9_6. Pablo Torrijos, José A. Gámez, and José M. Puerta. 2024. Structural Fusion of Bayesian Networks with Limited Treewidth Using Genetic Algorithms. In 2024 IEEE Congress on Evolutionary Computation (CEC). Vol. 3. IEEE, (June 2024), 1–8. doi:10.1109/cec60901.2024.10611976. Ioannis Tsamardinos, Laura E. Brown, and Constantin F. Aliferis. 2006. The max-min hill-climbing Bayesian network structure learning algorithm. en. Machine Learning, 65, 1, (Oct. 2006), 31–78. doi:10.1007/s10994-006-6889-7. Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan S. Rellermeyer. 2020. A Survey on Distributed Machine Learning. ACM Computing Surveys, 53, 2, (Mar. 2020), 1–33. doi:10.1145/337745 4. Chen Zhang, Yu Xie, Hang Bai, Bin Yu, Weihong Li, and Yuan Gao. 2021. A survey on federated learning. Knowledge-Based Systems, 216, 106775. doi:10.10 16/j.knosys.2021.106775. Xingang Zhao, Xinyan Wang, and Michael W. Golay. 2023. Bayesian Network–Based Fault Diagnostic System for Nuclear Power Plant Assets. Nuclear Technology, 209, 3, (Jan. 2023), 401–418. doi:10.1080/00295450.2022.2142445.

Received 29 January 2025; revised XX XXXX 2025; accepted XX XXXX 2025

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

Analyze & explore related research in Conceptio

Related documents