Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work combines heuristic Bayesian network structure learning algorithms with a Max-SAT-based local improvement method to provide more responsive than BNs provided by treewidth-based methods. Some efforts are devoted to generate fast methods when learning a Bayesian network from data, but it is also important to provide the ‘best possible structure’. Once the network is created (learned or elicited), the use will imply generally multiple inference operations which is the usual way to reason in BNs. This work aims at generating responsive BNs, that is, able to admit fast probabilistic reasoning. In order to allow tractable inference we need to learn Bayesian networks with a bounded-treewidth structure, being then treewidth value of extreme importance to determine the speeding reasoning. Let us remind that the treewidth of a triangulated graph is the size of its largest clique/bag minus one, so it will determine the largest message to be sent, if probability propagation is used for inference. However, state space is also important, as not all the variables present the same number of states, a binary variable will introduce less potential combinations than one with 5 states for instance. The state space of a clique/bag is the product of the domain sizes of the variables it contains. There exist evidence, supported by the initial experiments, which shows that the largest state space size of all bags can be even more decisive on the reasoning time than the treewidth, which seems natural as it is more informed about the dimension of the bag.

Authors’ proposal is heavily based on proposed the hybrid approach BN-SLIM, which improves the score of a heuristically computed BN by multiple applications of a MaxSAT-based exact method. They compare their methodology using  bounded state space (bss) with other baseline methods establishing bounded-treewidth strategies, namely k-greedy and k-MAX. Results indicate that bss methods perform better and faster, both BN-SLIMbss and k-MAXbss allows expanding the search space more carefully and predictably.
main_review: In my opinion the work is original enough, even though it is greatly based on an existing work, it makes an important contribution when using the bss approach. 

The quality is correct. Some parts may assume too specific knowledge but it is possible to be followed by a familiarised reader.

There are a few typos (*) but in general the paper is well written. The structure is a little bit unbalanced, as the results are presented too quickly and without a thorough analysis. Even though the supplementary material provides further plots, I would be happy to see in the paper itself a deeper analysis on the results, maybe using some other objective scores to compare the methods.

The results are of moderate significance, I personally find that exploring the bss alternative is clearly promising.

(*) I will list those detected:

- page 4: consisting pf …
- page 5: Our aim is compute
- page 8: networks' behvaior

I like the way in which section 3 presents the two possibilities, and I think section 4 seems correct, although I did not verify every mathematical detail. As indicated before, the experimental side is a little poor, probably due to space restrictions, but I would personally prefer to keep some proofs as supplementary material and find a more in-depth comparison with a broader analysis in the published paper.

In general I believe it is a paper valuable for discussion and offering helpful and promising ideas.

limitations_and_societal_impact: It is properly addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: A structure learning method for Bayesian networks. The main contribution is the use of state space to bounds in structure learning rather than the more well established treewidth bounds to improve scalability an speed of inference.
main_review: The paper proposes a new structure learning algorithm for Bayesian nets. The main innovation is to use a bound on the state space as compared to tree width bounds that are typically used in structure learning. In Bayesian nets with non-binary variable domains, the state space bound can be a  much more effective bound for learning compared to tree width. Two known heuristics are augmented with the state space bound. A recently developed approach is adapted to include the state space bound. To guarantee the constraints on the state space, a maxSAT encoding is constructed. A counting method using binary decision diagrams is constructed where a solution ensures that the state space bound can be met.

Experiments are performed on standard benchmarks for structure learning and improvements are shown over tree width based structure learning in terms of mean reasoning time, i.e. using the state space bounds we can learn Bayesian nets where inference is faster.

The paper has an interesting new approach to use state space bounds quite different from the tree width bounds commonly used. The case for non-binary domains seem relevant since a lot of real world problems have non binary domains and seems like tree width is a worse bound for such cases, so the proposed approach seems significant. One weakness is perhaps the paper builds a lot on recent results by Ramaswamy and Szeider, so the main novel contribution seems to be theorem 1 and the BDD encoding since the maxsat encoding seems to be known already. Maybe explicitly specifying the new contribution will help understand the significance of the proposed method better.

The experiments do show a consistently significant reduction in reasoning time compared to state of the art implemented in the BLIP package over all the benchmarks, so the experiments do show the benefit of the approach. I am wondering if scalability of structure learning is an issue for large number of variables since there is an overhead of using BDDs for each variable. Overall, the paper though seems to make good contributions with good empirical results to back them up. Some comments about the significance of the contributions beyond the Ramaswamy and Szeider 2021 work will help.

limitations_and_societal_impact: Addressed by the authors. Since the main contribution is improving scalability of existing models, I do not foresee negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This is a paper about the structural learning of Bayesian networks. Analogously to existing methods trying to learning models with bounded treewidth, the authors here are interested in learning models with bounded "state space". Of course the two descriptors differ for non-binary models, the second providing a more precise indicator of the time needed for inferences. 

The approach achieves that by a (simple) modification of the algorithms proposed by Scanagatta et al. for bounded treewidth.
This is followed by a post-processing step which adapts a similar approach by Ramaswamy and Szeider (AAAI 2021) for bounded treewidth to the bounded state space case by a MaxSAT reduction. Experiments are showing how this approach might give models producing faster inferences, but not necessarily higher scores.
main_review: The idea is clear and reasonable. Yet, I see two critical points:

(i) the reason for focusing on bounded state spaces (and not on bounded treewidth) should be better advocated. I can imagine significant differences for the reasoning time only when variables with a huge number of states are present.
(ii) compared to Ramaswamy and Szeider (AAAI 2021) the contribution sounds a bit incremental, being basically an adaptation of what has been done in that paper for bounded treewidth to the bounded state space.
(iii) the experimental results are not well organized, a synthetic (quantitative) description is missing

*** I eventually decided to revise my score after the rebuttal. ***


limitations_and_societal_impact: Nothing.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: A method for learning BNs where the size of the joint state space of a
bag in a tree-decomposition is bounded. It is argued (convincingly)
that this is a more useful quantity to bound than simple treewidth,
and empirical results produced to back this up. Learning has two
phases: an initial heuristic, followed by "local improvement", the
latter developed from earlier work. A (weighted partial) MAXSAT
encoding is presented for the local improvement phase which is an
extension from earlier work. A key contribution is a method for
encoding the constraint on the size of the joint state space: move to
logs, replace product with sums, and a BDD to encode the necessary summation.
main_review: The methods are mainly not-too-big alterations and additions to
existing methods. But I think this is a good thing. The authors know
the literature and have thus saved themselves from (re)inventing some
(possibly inferior) methods.

This is a clearly written paper. We have some useful theoretical
results, but the key issues are: (1) are we using the right measure of
"responsiveness"? and (2) do we learn the "right" networks?

Re (1) Section 3.1 provides evidence for a "yes" answer. Re (2),
naturally there could be a trade-off between fit-to-data and
responsiveness. Fig 4 gives us a reasonable idea of when there is such
a trade-off. I think the authors have provided sufficient evidence
that that the presented method produces the right sorts of BNs.

Not a big issue, but I don't think "responsive" is the right word to
use for BNs which admit speedy query answering, since it does not
convey that the response (to a query) comes back quickly.
limitations_and_societal_impact: The authors consider this.
review_title: null

Meta-review: This manuscript proposes to use a measure based on the max. "bag" size (product of cardinalities) when learning Bayesian networks, instead of treewidth. From a theoretical perspective, this is unimportant: results of hardness hold when all variables have the same cardinality, and one can easily convert nets if needed to/from that. However, the practical results of using the bag size (which is obviously a better measure than treewidth of the graph, no doubt of that, everybody should know it) can be interesting and useful. The novelty and theoretical contribution are not so significant, but on the other hand it is fair to say that someone needs come forward and argue that we should be using bag size instead of treewidth and make that claim work properly.
Decision: Accept (Poster)