acceptodds
Under review as a conference paper at ICLR 2027

Exact Distributed Structure-Learning for Bayesian Networks

Abstract

Learning the structure of a Bayesian network is currently practical for only a limited number of variables. Existing distributed learning approaches approximate the true structure. We present an exact distributed structure-learning algorithm to find a P-map for a set of random variables. First, by using conditional independence, the variables are divided into sets such that for each , the presence and absence of edges that are adjacent with any interior node (a node that is not in any other ) can be correctly identified by learning the structure of separately without using the information of the variables other than . Second, constraint or score-based structure learners are employed to learn the P-map of , in a decentralized way. Finally, the separately learned structures are appended by checking a conditional independence test on the boundary nodes (those that are in at least two 's). The result is proven to be a P-map. This approach allows for a significant reduction in computation time, and opens the door for structure learning for a “giant” number of variables.

Primary area:
learning theory
Keywords:
Causal discovery, Bayesuan networks, Structure learning, Distributed learning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_fUjbOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes an algorithm for structure learning in Bayesian networks. The idea is to find a separating set such that conditioning on that set we can divide the nodes into two or more connected components (that is, all connections between the components go through the separating set). Then this procedure can be repeated for each component recursively. Finally, local graphs learned for each of these subproblems can be combined into a global solution.

Critical strengths

None

Critical weaknesses

It is not clear how the proposed algorithm differs from the existing ones.

First of all, the section 3.1 is basically reinventing a wheel. It is well-known that separators exist and that the graph can be partitioned by them. The paper reintroduces the idea of behind tree decomposition. Basically, "boundary" in this paper corresponds to a "bag" in a tree decomposition. Definition 3.2 is also connected to tree decompositions. If T is a tree decomposition of the CPDAG for P, then a cover of X separated by W can be obtained by letting W be a bag in T and the components C_i are the nodes corresponding the nodes in different branches of T rooted in W.

Then we can use the concept of treewidth to get theoretical bounds for the algorithm. For example, if a graph has treewidth k, then there exists a separator of size at most k+1 such that every connected component after removing the separator has size at most 2/3*n.

One thing to note here is that limiting the separator size can lead to erroneous results. For every pair of non-adjacent nodes in the data-generating graph, there is a separating set S such that no separating set is smaller than S. If we limit the algorithm to conduct tests of size at most w < |S| then we will output an erroneous graph. So the guarantees in section 3.3 hold only if W is allowed to be arbitrarily large.

Second problem is the novelty of the algorithm. The current paper ignores the key references by Xie and Cheng (2008) and Yehezkel and Lerner (2009) who developed similar ideas for finding separators and recursively splitting the search space into smaller pieces.

For me, Algorithm 1 in the current paper seems very much like DecompRecovery in Xie and Geng (2008).

Xianchao Xie and Zhi Geng: A Recursive Method for Structural Learning of Directed Acyclic Graphs. Journal of Machine Learning Research 9 (2008) 459-483.

Raanan Yehezkel and Boaz Lerner: Bayesian Network Structure Learning by Recursive Autonomy Identification. Journal of Machine Learning Research 10 (2009) 1527-1570.

Questions for authors

What is the difference of the proposed algorithm compared to the existing algorithms?

The paper has lots of terminology that is not defined:

  1. What is an exhausted-pair cache? Exhausted (U, w)? Exhausted member-size pair?
  2. What is member-size-dependent limit q?
  3. Is "member U" same as a set?
  4. What is "global PC cleanup"?
Reviewer_N7hoOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes a distributed framework for Bayesian network structure learning by decomposing variables into overlapping subsets using conditional independence (CI) tests. The method learns local graph structures separately and combines them through graph merging and global PC cleanup to reconstruct the CPDAG. It uses tensorized Pearson chi-square CI tests to improve computational efficiency. Theorem 3.4 establishes exact CPDAG reconstruction under causal sufficiency, faithfulness, exact CI answers, and unrestricted global PC cleanup.

Critical strengths
  1. The paper provides a theoretical reconstruction guarantee under explicitly stated assumptions. Lemma 3.3 establishes the preservation of true adjacencies during decomposition, and Theorem 3.4 shows that unrestricted global PC cleanup can recover the correct CPDAG under oracle conditions.

  2. The experiments distinguish the effects of tensorization from those of decomposition. D-T-PC is faster than D-S-PC in 33 of 34 matched completed runs, with identical SHD and F1 in all 34 comparisons. The paper reports unsuccessful runs and acknowledges the computational overhead introduced by cover discovery.

Critical weaknesses
  1. Lack of empirical evidence for computational efficiency

The proposed decomposition framework fails to demonstrate a computational advantage over existing approaches. D-T-PC is slower than Tensor PC in all 21 matched completed runs, with a geometric mean runtime ratio of 16.1, while providing no consistent improvement in SHD or F1. The cover discovery stage introduces substantial overhead and dominates the total runtime in several benchmarks. For example, cover discovery consumes approximately 25,005 of 25,013 seconds on PIGS and 23,251 of 23,252 seconds on ANDES at 100 samples. These results directly undermine the central motivation of the proposed framework. The observed speedup over D-S-PC supports the efficiency of tensorized CI testing rather than decomposition itself.

  1. Restrictive theoretical guarantees and insufficient finite-sample validation

Theorem 3.4 relies on causal sufficiency, faithfulness, exact CI answers, and unrestricted global PC cleanup. Although causal sufficiency and faithfulness are standard assumptions in causal discovery, the exact CI oracle assumption limits the applicability of the guarantee to finite-sample settings. The experiments use statistical CI tests, yet the paper does not adequately examine how errors in these tests affect separator discovery, preservation of true adjacencies, or final CPDAG reconstruction. The reconstruction guarantee also depends on unrestricted global cleanup, which raises questions about the computational benefit of decomposition. Furthermore, the theorem applies to the oracle PC-based procedure and does not establish the same guarantee for the score-based local learners considered in the paper.

  1. Insufficient differentiation from prior decomposition methods

The theoretical novelty of the proposed framework is not sufficiently established. Xie and Geng (2008), in "A Recursive Method for Structural Learning of Directed Acyclic Graphs," already investigated recursive decomposition of DAG structure learning, local recovery of graph skeletons, and reconstruction through combining overlapping subsets. These ideas substantially overlap with the main conceptual framework of the present paper. Although the paper discusses related earlier work, it does not adequately distinguish its theoretical guarantees and reconstruction procedure from those of Xie and Geng (2008). A direct comparison of the assumptions, local recovery conditions, separator construction, and graph merging rules is needed to establish the specific theoretical contribution.

  1. Incomplete experiments and limited statistical reliability

Only 339 of the 576 planned experimental cells have valid completed results. The remaining cells include 67 timeouts, 155 cases without verified results, 12 invalid outputs, and three execution errors. Comparisons are restricted to matched completed runs, which can represent different subsets of networks and sample sizes across baselines. The experiments use a single sampling seed, making it difficult to assess variability in reconstruction accuracy and runtime. The paper provides limited analysis of the causes of invalid outputs and statistical errors in CI testing. These limitations weaken the empirical evidence, particularly given the broad claims concerning computational efficiency.

  1. Insufficient evaluation of scalability and distributed computation

The experiments do not adequately demonstrate scalability to large numbers of variables. The reported sample sizes of 100, 1,000, and 10,000 refer to observations rather than variables. Although the implementation parallelizes local learning across CPU cores, cover discovery remains sequential, and the paper does not provide a systematic evaluation of parallel efficiency, communication overhead, or scalability across multiple compute nodes. Parallel methods receive 16 CPU cores per job, while sequential methods receive one, further motivating resource-aware comparisons. The paper should evaluate how the number of variables, graph density, separator size, and balance between cover elements affect total computational cost.

Questions for authors
  1. What is the primary contribution of the proposed framework given the current experimental results? Is it the theoretical reconstruction guarantee, the efficiency of tensorized CI testing, or the decomposition strategy itself? Under what conditions does decomposition outperform Tensor PC, and what empirical evidence supports those conditions?

  2. How does the proposed method differ theoretically from Xie and Geng (2008)? In particular, could the authors clarify the differences in their assumptions, local structure recovery conditions, separator construction, and graph merging procedures?

  3. Can the authors provide a detailed analysis of the computational costs of cover discovery, local learning, and global cleanup? How many separator candidates and CI tests are required in the reported experiments? Given that cover discovery dominates the runtime in several benchmarks, what evidence suggests that the proposed decomposition strategy can reduce the overall computational cost?

  4. What causes the invalid graph outputs observed in the experiments, including those produced by D-T-PC? How does the implementation handle inconsistent CI test results or conflicting edge orientations? Could the authors distinguish implementation failures from finite-sample statistical errors and examine how these errors affect the reconstruction guarantees?

Reviewer_rN6JOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

\

This paper presents an exact distributed structure-learning algorithm for discovering a P-map over a set of random variables. First, leveraging conditional independence, the variables are divided into distinct subsets such that the presence and absence of edges adjacent to any interior node can be correctly identified by learning the structure of each subset independently, without relying on information from outside that subset. Second, constraint- or score-based structure learners are employed to learn the P-map of each subset in a decentralized manner. Finally, the independently learned structures are integrated by performing conditional independence tests on the boundary nodes. The authors demonstrate that the resulting composite structure constitutes a valid P-map.

Critical strengths

1- The proves the correctness of the result of their algorithm.

Critical weaknesses
  1. The authors did not give computational complexity of their algorithm. It has exponential time complexity in the worst case.

2- The title should be revised. The proposed approach is a divide-and-conquer algorithm rather than a distributed one, as it can be implemented in both centralized and distributed environments.

3- The algorithm does not decrease the time-complexity order of the algorithm.

Questions for authors
  1. When you divide the set of nodes into different subsets, what is the maximum number of nodes that can exist in different subsets? If there is more than one node, there are dependent links, and you can not learn in a distributed manner. Can you prove that the upper bound on the number of common nodes in two different subsets is 1?
  2. How do you ensure that the resulting graph is not a clique? If it is a clique, you can not use a distributed algorithm.
  3. The proposed method is not a distributed algorithm, but rather a divide-and-conquer approach. What motivated the use of a distributed architecture?
  4. The title should be revised. The proposed approach is a divide-and-conquer algorithm rather than a distributed one, as it can be implemented in both centralized and distributed environments.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.