Extendable and Iterative Structure Learning Strategy for Bayesian Networks

Q1. Is there any bound on the total number of CI tests required for running Algorithm 3?

The number of CI tests for the iterative PC algorithm depends on the order of variables. So according to the above discussion, we can find an order that guarantees reducing the number of CI tests in comparison with the PC.

W3. The result in Table 5 shows that the proposed iterative PC does not always require fewer CI tests compared to PC. Under what statistical or topological conditions will that happen? In my opinion this is be the bigger risk, because without any theoretic characterization, this shows the possibility that the proposed approach does not generalize.

Using an iterative approach, at each step, we leverage information about the relationships between nodes from the previous graph to determine the current graph. Since the number of nodes impacts the number of conditional independence (CI) tests, fewer nodes result in fewer CI tests when applying Lemma 1, which restricts the space of possible graphs. Also, the performance of the iterative algorithms depends on the order of selecting variables. According to Lemma 1 and Figure 1 (a-e), if the ordering is close to a topological causal ordering the performance of the iterative will be better. For example, consider a naive Bayes structure with $n$ children $\{X_1,\cdots, X_n\}$ and a parent node $Y$. With ordering like $\langle X_1,\cdots, X_n, Y\rangle$, before dealing with $Y$, the iterative algorithm will first produce the complete graph over $\{X_1,\cdots, X_n\}$. So this ordering will require an exponential number of CI tests. However, with this ordering $\langle Y, X_1,\cdots, X_n\rangle$ the number of CI tests for Algorithm 3 when using Algorithm 1 as the extendable P-map learner will be fewer than the previous ordering.

The new version includes Theorem 2 which proves that there is an order of variables for which the required number of CI tests for the iterative PC algorithm is fewer than for the PC algorithm. The main idea of the proof is based on Lemma 1. By using a topological causal ordering on the variables, according to Lemma 1, the variable $Y$ in Figure 1 (a-e) is chosen sooner than the children variables. This means the extra spurious edges will not occur in the graph during the entire process. In addition, we proved that the number of CI tests for extendable PC is fewer than the PC to check each edge. Thus the number of CI tests for the iterative PC will be fewer than for the PC.

W2. The results in Table 2 - 3 suggest that extendable PC always has a better runtime with fewer number of CI tests compared to PC. Can that be proved?

In section 3.1 of the new version, lines 246-269 (or old version lines 233-256), we discussed the number of CI tests for the extendable PC compared to the PC algorithm and showed that the number of CI tests for the proposed algorithm is always fewer than the PC and summarized the results in Table 1. The revised version includes Proposition 2 to explain this fact clearly.

W1. While the experimental results look good, I wonder if the proposed method of extendable PC has any consistency, faithfulness, or optimality guarantee.

In the new version, we proved that the output of the extendable algorithm is a P-map; see the following Theorem.

Theorem. The output of Algorithms 1 and 5 is a P-map.

Proof. The proof is a straightforward conclusion using Lemma 1, Lemma 3, and Lemma 4 (in Appendix). Lemma 4 shows that adding a new variable cannot add an edge between two nodes. Hence, according to Lemma 1, the output skeleton of the proposed extendable algorithm finds the skeleton of the true DAG. Then, Lemma 3 shows that all collider nodes were found correctly by the proposed algorithm. So the output PDAG for constraint-based algorithms such as Algorithm 1 is a P-map structure. $\square$

The proof is a straight conclusion using Lemma 1, Lemma 3, and Lemma 4 (in Appendix). Lemma 4 leads to the fact that adding a new variable cannot add an edge between two nodes. According to Lemma 1, and using the fact, the output skeleton of the proposed extendable algorithm finds the skeleton of true DAG. Then, Lemma 3 shows that all collider nodes were found correctly by the proposed algorithm. So the output PDAG for constraint-based algorithms such as Algorithm 1 is a P-map structure.

Q3. Minor Comment: i. In abstract, algorithm named PC might not be known to general readers. Similarly, FCI. Some of these acronyms are not defined.

Thanks for noting these limitations. The revised version expands these acronyms and also provides a high-level summary of these algorithms.

Q2. The key assumption that when a new variable $Y$ is added to the existing set $X$, that no new edges get assigned between the elements of $X$, this assumption needs further explanation. This seems to be a necessary condition of the algorithm to have low computational cost. In many situations, the introduction of a new variable might introduce new dependencies between existing nodes, e.g., in root-cause analysis, causal learning, molecular prediction, and others. Also, such situations could occur in time evolving DAGs. Further discussion on these will illustrate the applicability of the proposed method to different problems.

Thank you for your comments. Note, however, that this claim about “adding a new variable cannot add any new edges to the prior model”, is not an assumption, but is a provable proposition, for Bayesian networks. We have now added the following proposition.

Proposition. Consider $\bar G$ is a P-map over $\bar X$ and $G$ is a graph over $X$. If $X_j$ is an adjacent of $X_i$ in $\bar G$, then $X_j$ is an adjacent of $X_i$ in $G$.

Proof. If $X_j$ and $X_i$ are not adjacent in $G$, according to Lemma 4, there is a subset $U \subseteq X\setminus\{X_i,X_j\}$ such that $X_i\perp X_j | U$. Because $\bar G$ is a P-map and due to faithfulness assumption $X_i$ and $X_j$ are d-separated by $U$ in $\bar G$. Then there is no edge between $X_i$ and $X_j$ in $\bar G$. $\square$

One of the basic theorems in Bayesian network structure learning is Lemma 4 (in appendix), which uses the Markov condition and faithfulness assumption. According to the lemma 4, if there is a subset of variables $\mathcal{U}$ such that two variables $X$ and $Y$ would be independent given it, so there is no edge between $X$ and $Y$. So we have only two basic assumptions Markovness and fatefulness which hold for almost all Bayesian networks except a zero-measure set of probability distributions. On the other side, the claim "adding a new variable cannot add a new edge or dependency" is a direct result of Lemma 4. So, we only used the Markov condition and faithfulness assumption for this claim. And this is not an extra assumption.

We added a discussion about this issue. However, we are interested in knowing more about many situations in which the introduction of a new variable might introduce new dependencies between existing nodes, e.g., in root-cause analysis, causal learning, and molecular prediction. Maybe these problems cannot be modeled by Bayesian networks or the faithfulness assumption is violated. Of course, in time-evolving DAGs, since the structure can change over time, the proposed extendable approach cannot guarantee the output is a P-map for all times.

Q1. Performance guarantees such as error analysis, or on how to check whether the algorithm has converged to the correct graph structure are not discussed. A discussion on how to verify the correctness of the P-map finder algorithm used should be added. If the iterative approach is used, how does the error accumulate? Are the conditions in Lemma 1 and 2 sufficient for the P-map finder algorithm output the true structure?

In the revised version, we proved a theorem that shows the output of the extendable algorithm is a P-map. The proof is a straightforward conclusion using Lemma 1, Lemma 3, and Lemma 4 (in Appendix). Lemma 4 shows that adding a new variable cannot add an edge between two nodes. Hence, according to Lemma 1, the output skeleton of the proposed extendable algorithm finds the skeleton of the true DAG. Then, Lemma 3 shows that all collider nodes were found correctly by the proposed algorithm. So the output PDAG for constraint-based algorithms such as Algorithm 1 is a P-map structure.

Theorem. The output of Algorithms 1 and 5 is a P-map.

Proof. The proof is a straightforward conclusion using Lemma 1, Lemma 3, and Lemma 4 (in Appendix). Lemma 4 shows that adding a new variable cannot add an edge between two nodes. Hence, according to Lemma 1, the output skeleton of the proposed extendable algorithm finds the skeleton of the true DAG. Then, Lemma 3 shows that all collider nodes were found correctly by the proposed algorithm. So the output PDAG for constraint-based algorithms such as Algorithm 1 is a P-map structure. $\square$

Error accumulation is a critical challenge in constraint-based approaches and non-exhaustive score-based searches, such as greedy search. These methods rely on iterative updates where decisions to add or delete edges are based on the previous structure. Errors in earlier iterations propagate and compound, affecting subsequent steps. Similarly, iterative algorithms inherit this issue as they rely on standard approaches to refine structures, further perpetuating inaccuracies introduced in prior iterations.

An intuitive explanation for why the iterative learning algorithm outperforms PC algorithm while learning the complete graph is recommended.

The revised version has been modified to explain this issue. Section 3.3 states that: Using an iterative approach, at each step, we leverage information about the relationships between nodes from the previous graph to determine the current graph. Since the number of nodes impacts the number of conditional independence (CI) tests, fewer nodes result in fewer CI tests when applying Lemma 1, which restricts the space of possible graphs. Also, the performance of the iterative algorithms depends on the order of selecting variables. The performance of the iterative algorithms depends on the order of selecting variables. According to Lemma 1 and Figure 1 (a-e), if the ordering is close to causal ordering the performance of the iterative will be better. For example, consider a naive Bayes structure with $n$ children $\{X_1,\cdots, X_n\}$ and a parent node $Y$. With ordering like $\langle X_1,\cdots, X_n, Y\rangle$, before dealing with $Y$, the iterative algorithm will first produce the complete graph over $\{X_1,\cdots, X_n\}$. So this ordering will require an exponential number of CI tests. However, with this ordering $\langle Y, X_1,\cdots, X_n\rangle$ the number of CI tests for Algorithm 3 when using Algorithm 1 as the extendable P-map learner will be fewer than the previous ordering.

What is Sepset(X,Y)?

In the revised version, (discussing Algorithm 1) explicitly introduces $Sepset(X,Y)$. In general, for all $X,Z \in \mathcal{X}$, $Sepset(X,Z)$ is a subset of variables $\mathcal{X}\setminus \{ X,Z \}$ that leads $X\perp Z | Sepset (X,Z)$. In other words, $Sepset(X,Z)$ is a separating set for $X$ and $Z$.

Q1. Is the Extendable P-map learner in Algorithm 3 implemented using Algorithm 1?

Yes, Algorithm 1 is an extendable constraint-based algorithm based on the PC algorithm. So Algorithm 3 can use Algorithm 1 as an extendable P-map learner or use Algorithm 7, the extendable Hill-climbing that is an extendable score-based algorithm.

W1. I found the discussions and organization of Section 3 to be more convoluted than necessary. In particular, it would be helpful to have the relevance of Algorithms 2-4 explictly elucidated.

Thank you for your excellent suggestion. The revised version now better explains the extendable score-based approach. Section 3.2 now states:

Algorithm 2 represents a general extendable score-based algorithm that includes: (1) a search space trimming function (T-function in Algorithm 4) that restricts the graph search space, based on the analysis from Lemmas 1 - 3; and (2) a score-based P-map finder (for example global minimization of the BIC score), that finds the best graph within the restricted search space.

How is this work positioned relative to the prior works that study the information-theoretic limits of Bayesian structure learning?

One can use the information-theoretic limits to find a bound on the minimum number of new instances needed to recover the true DAG once a new variable is added to the previous set of variables. For example, for the case with discrete variables and where the conditional probability distributions are modeled with conditional probability tables (CPT), the addition of one variable to the existing $N$ variables increases the bound for a non-sparse DAG by $\dfrac{2N+1}{\theta_{min}}$ instances, where $\theta_{min}$ is the minimum probability value in the conditional probability tables [1].

[1] Information-theoretic limits of Bayesian network structure learning

Q1. How the score-based and constraint-based methods are used in the extendable PC algorithm?

The proposed extendable approach can be applied to all constraint-based and score-based algorithms that are guaranteed their output is a P-map. We developed “extendable PC” as an example of extendable constraint-based algorithms. The extendable score-based algorithm has been illustrated in Algorithm 2 in its general form. In addition, Algorithm 7 represents the extendable Hill-climbing as a special case of Algorithm 2.

Q2. Are the more existing work that incrementally learn the structure? What are their strengths and weaknesses?

To the best of our knowledge, there is no structure-learning method that can deal with the addition of a new variable (not instance) as explained in our comment above.

W2. Insufficient discussion of related work. There shall be a large number of related work on incremental structure learning, while the submission only cite two most relevant ones ((Kocacoban & Cussens, 2019) and (Alcobe, 2005)). This makes the contribution of the submission less clear.

Thank you for noting this omission. The revised paper now explicitly notes that all incremental/online methods for learning Bayesian network structures consider ways to incorporate a set of new instances to the current dataset – so going from $n$ instances (each with $k$ variables) to $n+1$ instances (over $k$ variables). By contrast, our proposed algorithm adds one (or more) new variables to the current set of variables – but over the same set of instances – so going from $n$ instances over $k$ variables, to $n$ instances over $k+1$ variables. These are two different problems, requiring a new strategy in Bayesian network structure learning.

Imagine we have a dataset $S[X]$ of 100 instances, each describing a different person, by providing the values for 10 features $X$ – 9 covariates describing a person – eg, age, sex, smoker, … – , as well as a 10th, for whether this person has a specific disease (say lung cancer). Now let $BN( S[X] )$ be the Bayesian Network (over 10 variables $X$), learned from those 100 instances. Now imagine we decided to acquire other information about each person – say the expression of $Gene22$. This means we can describe each patient with 11 features, $X’ = X \cup { Gene22 }$ – producing the 100-instance (11-d) dataset $S’[X’]$. The challenge now is to produce a new Bayesian over the 11 features – call it $BN( S’[X’] )$, using this new $S’[X’]$ dataset, along with the earlier $BN( S[X] )$.

Notice this task is fundamentally different from the more traditional online Bayesian network structure-learning task, which might go from this 100-instance dataset $S[X]$, by adding in one (or more) next 10-d instances.

W1. The scope of the paper (symbolic Baysian network) may not fit ICLR conference (representation learning).

Please note that ICLR has published many Bayesian networks, causal discovery, structure learning, and Bayesian network inference, including the following, in years 2023 and 2024. This demonstrates that our proposed paper about structure learning Bayesian networks aligns well with the scope of the ICLR conference.

• Tractable Probabilistic Graph Representation Learning with Graph-Induced Sum-Product Networks
• Federated Causal Discovery from Heterogeneous Data
• Learning Large DAGs is Harder than you Think: Many Losses are Minimal for the Wrong DAG
• Constraint-Free Structure Learning with Smooth Acyclic Orientations
• Structural Estimation of Partially Observed Linear Non-Gaussian Acyclic Model: A Practical Approach with Identifiability
• Causal Structure Recovery with Latent Variables under Milder Distributional and Graphical Assumptions
• Diffusion Models for Causal Discovery via Topological Ordering
• BayesDiff: Estimating Pixel-wise Uncertainty in Diffusion via Bayesian Inference
• Unified Generative Modeling of 3D Molecules with Bayesian Flow Networks
• Training Bayesian Neural Networks with Sparse Subspace Variational Inference