acceptodds
Under review as a conference paper at ICLR 2027

Approximate Polytree Learning with Submodular Local Scores

Abstract

Polytrees are a special case of Bayesian networks that seek to capture the conditional dependencies between variables as directed graphs whose underlying undirected graphs are acyclic. In the score-based approach to learning the structure of a polytree, we assign a score for each possible set of parents of each node to measure its quality, with the goal being to maximize the sum of the scores. As there is a variety of possible score functions, it is common to treat the scores as arbitrary blackbox functions, making structure learning NP-hard. At the other extreme, there has been research where additive scores have been assumed, which imposes a lot of structure on the score function but is an unrealistically strong assumption. We seek a middle ground and study the problem for submodular functions, to which the scores are empirically relatively close. We prove that the problem remains NP-hard for submodular scoring functions but also design a local-search algorithm that is guaranteed to find a structure whose score is within a factor of from the optimal one, and if the maximum in-degree of the polytree is bounded, then a single iteration of the algorithm takes polynomial time. Moreover, we show empirically, that the number of iterations of our algorithm is small. Further, we show that this result can be generalized to functions that are close to being submodular without significantly worsening the approximation guarantee.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
NP-hard problem, Matroids, Local Search, Bayesian Network Structure Learning, FPT-algorithms, Polytrees, Approximation algorithms

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_Kc66OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the problem of Bayesian Network structure learning under the setting of polytree structure restriction and submodular scoring function. This leads to a greedy algorithm (as many submodular optimization problems do) where the structure is guaranteed to be a 2-approximation of the optimal structure. The paper provides both theoretical results and empirical evaluation. Theoretical results are supported by proofs included in the appendix.

Critical strengths

The paper is very well written and easy to follow despite the deeply technical material.

While the problem of Bayesian Network structure learning is well studied, the authors present a novel view of the problem under specific restrictions of the structure (polytree) and score function (submodular). The former is further constrained to bounded in-degree and the latter is relaxed as an extension of the main result.

Critical weaknesses

My main concern relates to the c-approximation on the submodular score function. A well known problem with the c-approximation is that it is multiplicative and so not shift-invariant. The score function, however, is submodular. A submodular function shifted by an additive constant remains submodular. So given any scoring function ff satisfying the bound f(D)≤f(Dopt)≤c⋅f(D)f(D) \leq f(D^{opt}) \leq c \cdot f(D) we can construct a new score function f~=f+k\tilde{f} = f + k which does not satisfy the c-approximation bound, e.g., set kk to some large negative number. How is this resolved in the algorithm and Theorem 3.1?

Questions for authors

Please address the question raised above.

3 comments
AuthorsOpenReview ↗

Shifting had no bad influence in our experiments

Thanks for your review!

Your concern that shifting does not preserve approximation factors is valid and we had considered it. Note that shifting to 0-based scores, as they are treated in theory, from negative scores, as they often occur in practice, can both improve or worsen approximation factors, depending on the magnitude of the shift. The short answer is that in the instances we have looked at, shifting indeed yields drastically improved approximation factors for the real (unshifted) scores from practice. This to our mind validates the prevalent theoretical point of view of 0-based scores because both the objective for approximation is stated in a cleaner way and it empirically implies guarantees for the real scores. In particular, in Appendix C we have computed what approximation factors our results and algorithms imply for the original, unshifted (negative) scores. For instance, on the adult dataset, our factor-3.36 approximation yields a factor-1.5 approximation for the original scores.

My concern is less about the experiments and more about Theorem 3.1.

Thanks for responding!

We are confused by this comment: If we interpret it correctly, f is the scoring function and D_opt is an optimal solution with regard to this scoring function. Of course we can change the scoring function after running our algorithm and then the approximation factor would not necessarily hold anymore. But then our algorithm would have output something else for this modified scoring function and this output would indeed satisfy the approximation guarantee.

If you want to point out that the function could be negative in practice, indeed, this is true. As is customary in theoretical analyses of algorithms for structure learning, we deal with 0-based scoring functions in the theoretical part of the paper (see the Preliminaries, Line 124). That is, all scores are nonnegative (note that this follows from the assumption that the empty set has score 0 as all scores of supersets are wlog. larger). In this regime, the approximation guarantee holds regardless of the scoring function in the input as long as it satisfies submodularity or closeness to it. What this implies for practice is analysed in our previous comment and the appendix.

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

The paper looks at the Bayesian network structure learning problem within the score-based paradigm. The problem is restricting to the case of learning polytree structures using submodular scores. The authors present a new learning method that is guaranteed to find a structure within a factor of 2 of the optimal network. They go on to study the method presented experimentally.

The primary contribution of the paper is the novel algorithm presented. Alongside this, the mathematical guarantee on the quality of the network learned is also a notable contribution.

Evaluation of the approach is consists of the mathematical analysis of it noted above. In addition, experimental evaluation is aimed at understanding the number of iterations that the algorithm takes for realistic datasets rather than just in some theoretical worst case. This helps establish the feasibility of the technique in practice.

Critical strengths

The paper studies an interesting and relevant problem. The cited literature makes clear that related topics have received significant attention in recent yearsc. Within this area, the work provides a notable improvement for a particular case.

The paper demonstrates rigor throughout. The mathematical foundations are well explored. The algorithm is presented clearly and analysed. The authors are unable to bound one quantity mathematically, but use experimental results to assess this for realistic datasets in practice. The paper generalises the experimentation to data that does not possess submodularity and shows it is still applicable,

Critical weaknesses

The paper may have limited significance. While such results are interesting to those of us researching directly in the field, it is unclear that there is significant impact amongst a broader ML audience of those utilising graphical models as part of some other task.

Questions for authors

Just comments, not questions that need a response.

Line 126 claims any optimial polytree has a score of 0. I think you meant to say the optimal polytree will have a non-negative score (otherwise the empty graph would always be an optimal tree).

Table 1 is hard to understand. The caption refers to a top and bottom - the table has 4 sections. Not all rows are explained (and some are not explained in the correct order). Abbreviations are introduced with little explanation. I worked it all out in the end, but it could be clearer.

2 comments
AuthorsOpenReview ↗

We esteblish an efficient algorithm using more realistic assumptions

Thank you for the review and helpful comments!

You seem concerned about the significance; here is why we feel our results are relevant to the graphical-models community and ML more generally: From a practitioner’s point of view, one of the tempting aspects of polytrees is that they are more interpretable than many other types of models. What makes their practical use difficult is that learning the best polytree is NP-hard, and moreover, takes roughly O(2n)O(2^n) time in the number nn of vertices under the Set Cover Conjecture (Harviainen et al., 2026; Theorem 3.5). This forces one to use suboptimal polytrees in practice.

Since heuristics for learning them rarely come with guarantees about the quality of the output, our view is that approximation algorithms with guarantees are needed for practitioners to apply polytrees more broadly. This work therefore aims for reasonable running time and more realistic assumptions than previous works while still obtaining a constant approximation ratio.

Indirectly, the work may result in the development of better heuristics for learning polytrees or Bayesian networks more generally: we have identified submodularity to be a practically motivated structural assumption about the instances, which future heuristics could then exploit. An alternative route towards better heuristics could be through incorporating more complex local search moves—similarly to this paper—to greedy hill climbing algorithms implemented by, for example, Weka’s K2 algorithm to enable them to escape local optima.

I thank the authors for their response. I do believe the paper is worthy of acceptance, though not amongst the most important work that is likely to have been submitted to this conference. I believe my original rating and comments still reflect this.

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

This paper studies Polytrees (PT), which are DAGs whose skeleton (undirected graph induced by the graph) contains no cycles and the most general problem is

Polytree Learning (PTPT)

Instance: Given a set of nodes NN of and for each node v∈Nv\in N, a local score functions sv ⁣:2N∖{v}→Rs_v\colon 2^{N\setminus\{v\}}\to \mathbb{R}

Task: compute a polytree D=(N,A)D=(N,A) with maximum score.

However, such polytree learning in such an unrestricted setting remains NP-hard. The authors turn to the following restrictions of Polytree Learning: PTsmPT^{sm}, where each svs_v is monotone submodular, and restricting it even further, PT≤smPT^{sm}_{\leq}, where the parent set size can be at most kk.

Their main contribution is showing that PTsmPT^{sm} and PT≤smPT^{sm}_{\leq} have 2-approximation algorithms.

Critical strengths

The paper studies monotone submodular local scores as a natural restriction of polytree learning and establishes a 2-approximation guarantee for its local-search algorithm for (PT^{sm}) and (PT^{sm}_{\leq})

Critical weaknesses

Their analysis only bounds the running time of each iteration to be 4k⋅∣F∣⋅O(n)4^k\cdot|\mathcal{F}|\cdot O(n), where F\mathcal{F} is set of maximal parent sets and kk is the maximal parent set size. However, it does not bound the number of iterations.

Questions for authors

Clarification

I think having kk explicit in the maximum parent set constraint would be good for clarity, i.e., PT≤ksmPT^{sm}_{\leq k}. Theorem 3.4 is a bit awkward to read as currently stated.

As of writing this, it seems to be the case that ETH has been refuted; I think the statements of Theorems 3.3 and 3.4 should be handled with care. Either the ETH part should be removed, or at the very least there should be a remark stating that this paper was written before the refutation of ETH.

When stating maximization problems, don't you only need f(D)≥12f(OPT)f(D)\geq \frac{1}{2}f(OPT). On line 173, two inequalities are stated, one of which is trivial for maximization problems.

Questions

What is the bound on the number of iterations?

What is the relation between the number of iterations and the approximation factor?

2 comments
AuthorsOpenReview ↗

Please reconsider your score

Thank you for your time evaluating our manuscript. We strongly request to reconsider your score. As it stands, your review contains no clear arguments for rejecting our manuscript. To reiterate from the manuscript: Experimental validation shows that the number of iterations is proportional to the number of variables in standard datasets, meaning that the algorithmic results likely have practical relevance. In particular, they do not seem to be related to the number of parent sets, that is, they are strongly sublinear in the input size. Note that for many extremely widespread algorithms no good iteration upper bound is known in general, such as the k-Means Algorithm and the Simplex Algorithm. That hasn’t prevented them from being applied in practice and extremely successfully so. In addition our theoretical contributions are nontrivial and, as argued, are the first of its kind in this field that bridge between theory and practice.

Questions:

The first question is answered above. The second question: The theoretical guarantee is achieved once no improvement step (further iteration) is possible; in practice we expect that the largest improvements occur in the first couple of iterations and level off quickly.

Clarifications:

  1. We appreciate this idea and we changed this in the paper accordingly.

  2. Yes, with the recent breakthrough it is quite likely that the ETH is wrong. We plan to use the Weak ETH in the updated version which basically states that 3SAT has no 2n1−ϵ2^{n^{1-\epsilon}} time algorithm. This assumption is not affected by this recent breakthrough: https://arxiv.org/pdf/2611.02650. We also changed the proof of Theorem 3.4 slightly and we now reduce from Subcubic VC instead of Cubic VC to argue more easily that the Weak ETH bound transfers.

  3. Yes, the mentioned inequality is sufficient. We chose to have the inequality f(D)≤f(Dopt)f(D)\leq f(D^{opt}) as well to indicate that the score of any polytree D is at most the score of an optimal polytree D^{opt}.

  4. and 2) are done in the updated PDF.

Thank you for your response and for clarifying my concerns. My main concerns were the lack of a worst-case running-time bound and the potentially large size of F\mathcal{F}. Your clarifications and empirical evidence have alleviated these concerns, and I have updated my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.