- 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:
- What is an exhausted-pair cache? Exhausted (U, w)? Exhausted member-size pair?
- What is member-size-dependent limit q?
- Is "member U" same as a set?
- What is "global PC cleanup"?