The Complexity of Bayesian Network Learning: Revisiting the Superstructure
Authors: Robert Ganian
Viktoriia Korchemna
Venue: NeurIPS 2021 Oral (2021)
Keywords: Bayesian Network Structure Learning
parameterized complexity
fixed-parameter tractability
Polytree Learning

Abstract: We investigate the parameterized complexity of Bayesian Network Structure Learning (BNSL), a classical problem that has received significant attention in empirical but also purely theoretical studies. We follow up on previous works that have analyzed the complexity of BNSL w.r.t. the so-called superstructure of the input. While known results imply that BNSL is unlikely to be fixed-parameter tractable even when parameterized by the size of a vertex cover in the superstructure, here we show that a different kind of parameterization - notably by the size of a feedback edge set - yields fixed-parameter tractability. We proceed by showing that this result can be strengthened to a localized version of the feedback edge set, and provide corresponding lower bounds that complement previous results to provide a complexity classification of BNSL w.r.t. virtually all well-studied graph parameters.

We then analyze how the complexity of BNSL depends on the representation of the input. In particular, while the bulk of past theoretical work on the topic assumed the use of the so-called non-zero representation, here we prove that if an additive representation can be used instead then BNSL becomes fixed-parameter tractable even under significantly milder restrictions to the superstructure, notably when parameterized by the treewidth alone. Last but not least, we show how our results can be extended to the closely related problem of Polytree Learning.

The Complexity of Bayesian Network Learning: Revisiting the Superstructure
Robert Ganian and Viktoriia Korchemna Algorithms and Complexity Group, TU Wien Crganian, vkor chemna) Cac. tuwien ac. at
Abstract
We investigate the parameterized complexity of Bayesian Network Structure Learn- ing (BNSL), classical problem that has received significant attention in empirical but also purely theoretical studies. We follow up previous works that have analyzed the complexity of BNSL w.r.t. so-called superstructure of the input. While known results imply that BNSL is unlikely to be fixed- padrapaaeeter tractable even when parameterized by the size of vertex cover in the superstructure, here we show that a different kind of parameterization-nnnt notally by the size of feedback edge set-yiclds axed-parametee tractability. We proceed by showing that this result can be strengthened to localized version of the feedback edge set, and provide corresponding lower bounds that complement previous results to provide a complexity classification of BNSL w.r.t. virtually all well-studied graph parameters.
We then analyze how the complexity of BNSL depends on the representation of the input. In particular, while the bulk of past theoretical work on the topic assumed the use of the so-called non-zero representation, here we prove that if an additive representation can be used instead then BNSL becomes exed-parameter tractable even under significantly milder restrictions to the superstructure, notably when parameterized by the treewidth alone. Last but least, we show how our results can be extended to the closely related problem of Polytree Learning.
Introduction
Bayesian networks are among the most prominent graphical models for probability distributions. The key feature of Bayesian networks is that they represent conditional dependencies between random variables via directed acyclic graph; the vertices of this graph are the variables, and an are ab means that the distribution networks is that they can be used to infer the distribution of random variables in the network based on the values the remaining variables.
variable b depends on the value a. One beneficial property of Bayesian
The problem of constructing Bayesian network with an optimal network structure is NP-hard, and remains NP-hard even on highly restricted instances [4. This initial negative result has prompted an extensive investigation of the problem's 's complexity, with the aim of identifying new tractable
fragments as well as the boundaries of intractability 26 32 27 22 11 6. 19. The problem-
which we simply call BAYESTAN NETWORK STRUCTURE LEARNING (BNSL) can be stated as follows: given set of V of variables (represented as vertices), family of score functions which assign each variable E V score based on its parents, and a target value E, determine if there exists a directed acyclic graph over that achieves a total score of at least
Forrmal definitions provided in Section We consider the decision version of BNSL for complexity- theoretic reasons only: all the provided algorithms are constructive can output a network as witness.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

To obtain a more refined understanding of the complexity of BNSL, past works have analyzed the problem not only in terms of classical complexity but also from the perspective of parameterized complexity [9 S In parameterized complexity analysis, the tractability of problems is measured with respect to the input size n and additionally with respect to a specified numerical parameter In particular, a problem that is NP-hard in the classical sense may may denedddnn on the parameterization used-be pareameereetter tractable (FPT), which is the parameterized analogue of polynomial- time tractability and means that a solution can be found in time f(k) n2) for some computable function f. or W[1]-hard, which rules out fixed-paraman parameter tractability under standard complexity assumptions. The use of parameterized complexity as a refinement of classical complexity is becoming increasingly common and has been employed not only for BNSL (26 32 27. but also for numerous other
problems arising in the context of neural networks and artificial intelligence
[3
10 16].
Unfortunately, past cunplexity-theorehe works have shown that BNSL is a surprisingly difficult problem. In particular, not only is the problem NP-hard, but it remains NP-hard even when asking for the existence of extremely simple networks such as directed paths 2 and is W[1]-hard when parameterized by the vertex cover number of the network (77. In an effort to circumvent these lower bounds, several works have proposed to instead consider restrictions to the so-called superstructure. which is graph that, informally speaking, captures all potential dependencies between variables [42] K5 Ordyniak and Szeider [2) studied the complexity of BNSL when parameterized by the structural properties of the superstructure, and showed that parameterizing by the treewidth [36] of the superstructure is sufficient to achieve weaker notion of tractability called XP-tractability. However, they also proved that BNSL remains W[1]-hard when parameterized by the treewidth of
the superstructure 32 Theorem 3].
Contribution. Up to now, no "implicit" restrictions of the superstructure were known lead to fixed-pane parameter algorithm for BNSL alone. More precisely, the only known exxe-parameter algorithms for the problem require that we place explicit restrictions on either the sought-affe network or the parent sets on the input: BNSL is known to be fixed prremmprreeterr tractable when parameterized by the number of ares in the target network [22, the treewidth of an "extended superstructure graph" which also bounds the maximum number of parents a variable can have (26), or the number of parent set candidates plus the treewidth of the superstructure (32. Moreover, a closer analysis of the reduction given by Ordyniak and Szeider [32] Theorem 3] reveals that BNSL is also W[1]-hard when parameterized by the treedepth, pathwidth, and even the vertex cover number of the superstructure alone. The vertex cover number is equal to the vertex deletion distance to an edgeless graph, and hence their result essentially rules out the use of the vast majority of graph parameters; among others, any structural parameter based on vertex deletion distance.
As our first conceptual contribution, we show that a different kind of graph parameters that are based on edge deletion distance- give rise to fixe--paraen algorithms for BNSL. in its full generality, without requiring any further explicit restrictions on the target network or parent sets. Our first result in this direction concerns the feedback edge number (fen), which is the minimum number of edges that need to be deleted to achieve acyclicity. In Theorem [3 we show not only that BNSL is fixed-parameter tractable when parameterized by the fen of the superstructure, but also provide a polynomial- equivalent one whose number of variables is linear in the fen (i.e., a kernelization 9 (l).
notably..
preprocessing algorithm that reduces any instance of BNSL to an
Since fen a highly "restrictive" parameter- its value can be large even on simple superstructures such as collections of disjoint cycles-w we proceed by asking whether it is possible to lift fixed- parameter tractability to a more relaxed way of measuring distance to acyclicity. For our second result, we introduce the local feedback edge number (Ifen), which intuitively measures the maximum edge deletion distance to acyelicity for cycles intersecting any particular vertex in the superstructure. In Theorem [ we show that BNSL. is also exxedparammter tractable when prameterized by Ifen; we also show that this comes at the cost of BNSL not admitting any polynomial- procedure akin to Theorem 3 when parameterized by Ifen. We conclude our investigation in the direction of parameters based on edge deletion distance by showing that BNSL parameterized by treecut width [8 45 4 a recently discovered edge-cut based counterpart to treewidth, remains W[r]-hard (Theorem 9). An overview of these complexity-thhoreee results is provided in Figure !
preprocessing
As our second conceptual contribution, we show that BNSL becomes significantly casier when one can use an additive representation of the scores rather than the non-zero representation that was considered in the vast majority of complexity-theoreti works on BNSL to date 26 32
19
2

---

Treewktth
Figure I: The complexity landscape of BNSL with respect to parameterizations of the super- structure. Arrows point from more restrictive parameters to less restrictive ones. Results for the three graph parameters on the left side follow from this paper, while all other W[1]- hardness results follow from the reduction by Ordyniak and Szeider 32 Theorem 3].
W[ir-hard
Treent Width
Pathwidth
Local book
Trewlepth
Edge Number
FPT
Foodbacck Edge
Vertex Cover Number
Number Data Reduction
40 39 and utilizes a succinct The additive representation inspired by known heuristics for BNSL
encoding of the score function which assumes that the scores for parent sets can be decomposed into a sum of the scores individual variables in the parent set; a discussion and formal definitions are provided in Section _ In Theorem 11] show that if the additive representation can be used, BNSL becomes fixed-pant exed-parameter tractable when parameterized by the treewidth the superstructure (and hence under every parameterization depicted in Figure D Motivated by the empirical usage of the additive representation, we also consider the case where we additionally impose a bound on the number of parents a vertex accept; we show that the result of Theorem TT] also covers this case if is taken as an additional parameter, and otherwise rule out lied-paraameee tractability using an intricate reduction (Theorem 12).
For our third and final conceptual contribution, we show how our results can be adapted for the emergent problem of POLYTREE LEARNING (PL), variant of BNSL where require that the network forms a polytree. The crucial advantage of such networks that they allow for a more efficient solution of the inference task B4 23) and the complexity of PL has been studied in several works [21 19 38). We show that all our results for BNSL can be adapted to PL, albeit in some cases is necessary perform non-trivial modifications. Furthermore, we observe that unlike BNSL, PL becomes polynomial-time tractable when the additive representation is used (Observation [6): this matches the "naive" expectation that learning simple networks would be easier than B BNSL. in its full generality. As our concluding result, we show that this expectation is in fact not always validated: while PL was recently shown be W[1]-hard when parameterized by the number of so-called dependent vertices (2I), in Theorem 17 we prove that BNSL is lxed-parameter tractable under that same parameterization.
2 Preliminaries
For an integer i, we let (1, ...,, and - (O}. We denote by N the set of natural numbers, by Ng the [0). We refer to the handbook by Diestel [8] for standard terminology on directed as well as undirected graphs. The skeleton (sometimes called the underlying undirected gruph) directed graph (a digraph) D = (V, A) is the undirected graph G" = (V, E) such that ww E E if ow E A or we E A. A digraph is a polytree if its skeleton is forest.
When comparing two numerical parameters a, of graphs, say that a is more restrictive than 3 if there exists function f such that ((G)= < f(a(G)) holds for every graph G. We refer to the standard sources for the fundamentals of parameterized complexity, including the definitions of fixed-paramend tractability, parameterized reductions, W[1]-hardness and treewidth [5 31]
Problem Definitions. Let V be a set of vertices and F = {fe 2V(()) + Ny l J V
be family of local score functions. For a digraph D AV, define its score follows: (U), where (D()) is the set of vertices of with an outgoing are to v (i.e., the parent of in D). We now formalize our problem of interest 32 22
score(D) = = fo
BAYESIAN NETWORK STRUCTURE LEARNING (BNSL)
Input: A set V of vertices, family F of local score funetions, and integer
Question:
Does there exist an acyclic digraph D = (V. A) such that score D) 2 E?
POLYTREF LEARNING (PI.) is defined analogously, with the only difference that there addition- ally required to be polytree [21]. We call D solution for the given instance.
3

---

Figure 2: Example of superstructure graph (on the top) and a suitable solution DAG (on the bot- tom) when:
d
f.(16)) = fa(fc)) = 1, ((b, = 2: =
fo(fa) = = fo c}) = 3;
f((la)) = 3. fc((b))
fa((b,c)) 1;
1
Note that in the depicted DAG the scores of and are equal to 3, the score of d is equal to 1. Parent set of a is empty; as we assume the non-zero rep- resentation and fa (0) is not specified in the input, we conclude that fa (0) = 0. Therefore the total
score is 0 + 3
7 6 l.
Since both and F are assumed to be given on the input of our problems, an issue that arises here is that an explicit representation of F would be exponentially larger than [V]. A common way to potentially circumvent this is to use a non-zero representation of the family F, i.e., where we only store values for (P) that are different than zero. This model has been used in the vast majority of
works studying the complexity of BNSL and PL 226 32 27 22 19 21.. Let I (v) be the collection of candidate parents of which yield a non-zero score; formally, r 5 {2 (x() * 0 0}, and the input size [Z] of an instance I (V, E) is simply defined as [V++ EveV,Per,to)
I
A natural way to think about and exploit the structure of inter-variable dependencies of an instance is to consider its superstructure graph Gz = (V, E). where ab E if a occurs in at least one candidate set in I (b) (or vice-versa). An example is provided in Figure 2
Naturally, families of local score functions may be exponentially larger than |V] even when stored using the non-zero representation. In this paper, we also consider second representation of F which guaranteed to be polynomial in [V] in the additive representation, we require that for every vertex E V and set Q = {qi...., Im } S V.VAE (v), fQ( = (((1)))) + ................................ + f.(f9m) D)- Hence, each cost function fu can be fully characterized by storing at most [V|-many entries of the form (z) == (=(((r)) for each E V \ {v). To avoid overfitting, one may optionally impose an additional constraint: an upper bound q on the size of any parent set in the solution.
While not every family of local score functions admits an additive representation, the additive model similar in spirit to the models used by some practical algorithms for BNSL. For instance, the algorithms of Scanagatta, de Campos. Corani and Zaffalon 40 39, which can process BNSL instances with up to thousands of variables, approximate the real score functions by adding up the known score functions for two parts of the parent set and applying small, logarithmic correction. Both of these algorithms also use the aforementioned bound g for the parent set size. In spite of this connection to practice and the representation's 's streamlined nature, we are not aware of any prior works that considered the additive representation in cmmplexit--hheoret studies of BNSL and PL. The superstructure graph for the additive representation can be defined in an analogous way as for the non-zero representation: an edge wv simply captures a "suspected dependencey' between variables u and (i.c., one receives positive score for depending on the other).
To distinguish between these models, we use BNSL #0, B.SL* and BNSL denote BAYESIAN NETWORK STRUCTURE LEARNING with the non-zero representation, the additive representation, and the additive representation and the parent set size bound q, respectively (and analogously for PL).
In our algorithmic results, we will often use G (V, E) to denote the superstructure graph of the input instance Z. Without any loss of generality, we will also assume that G is connected.
Graph Parameters Based on Edge Cuts. Traditionally, the bulk of graph-theorees research on structural parameters has focused on parameters that guarantee the existence of small vertex separators in the graph; these are inherently tied to the theory of graph minors [37 36 and the vertex deletion
We remark that the non zero representation could be strengthened even further by omitting each parent set Z of which contains a proper subset Z' such that fz( < fz'z'). This preprocessing step, however, does not have impact any of the results presented in this paper.

---

distance. This approach gives rise not only to the classical notion of treewidth, but also to its well-known restrictions and refinements such as pathwidth [37], treedepth [30] and the vertex cover
number 12 25
The vertex cover number is the most restrictive parameter in this hierarchy.
However, there are numerous problems of interest that remain intractable even when parameterized by the vertex cover number. A recent approach developed for attacking such problems has been to consider parameters that guarantee the existence of small edge cuts in the graph; these are typically based on the edge deletion distance or, more broadly, tied to the theory of graph immersions [S
The parameter of choice for the latter is treecut width (tcw) 45
a counterpart to treewidth which has been successfully used to tackle some problems that remained intractable when parameterized by the vertex cover number [17]
28
14
On the other hand, the by far most prominent parameter based on edge deletion distance is the feedback edge number of connected graph G (V, F.), which is the minimum cardinality of set F _ E of edges (called the feedback edge set) such that G - F acyclic. The feedback edge number can be computed in quadratic time and has primarily been used obtain fixed-paramete algorithms and polynomial kernels for problems where other parameterizations failed [1 2
Up to now, these were the only two edge-cut based graph parameters that have been considered in the broader context of algorithm design. This situation could be seen as rather unstisfactory in view of the large gap between the complexity of the richer class of graphs of bounded treecut width, and the significantly simpler class of graphs of bounded feedback edge number for instance, the latter class is not even closed under disjoint union. Here, we propose new parameter that lies "between" the feedback edge number and treecut width, and which can be seen as a localized relaxation of the feedback edge number: instead of measuring the total size of the feedback edge set, it only measures how many feedback edges can "locally interfere with" any particular part of the graph.
Formally, for connected graph G = E) and spanning tree T of G, let the local feedback edge set at v E be Efe, {uw E E E E(T) | the unique path between u and w in T contains w). The local feedbacck edge number of (G, T) (denoted (G, is then equal to max,gv | (v)), and the local feedback edge number of G is simply the smallest local feedback edge number among all possible spanning trees of G, i.c., (G) = minr spanning of [fen(G,T),
It is not difficult to show that the local feedback edge number is "sandwiched" between the feedback edge number and treecut width. We also show that computing it is FPT.
Proposition 1. For every graph G, tcw(G)= S Ifen(G') + 1 and Ifen(G) < fen(G)).
Theorem 2. The problem of determining whether IGen(G) S l for an input graph G parameterized by an integer k is fixed-parameter parameter tractable. Moreover, if the answer is positive, we may also output a spanning tree T such that (fe((G,T) S k as a witness.
3 Solving BNSL #0 with Parameters Based on Edge Cuts.
In this section we provide tractability and lower-bound results for BNSL#0 from the viewpoint of superstructure parameters based on edge cuts. Together with the previous lower bound that rules out exed-parameter algorithms based on all vertex- pertex-separator parameters [32] Theorem 3]. the results presented here provide a comprehensive picture of the complexity of BNSL 70 with respect to superstructure parameterizations.
Using the Feedback Edge Number for BNSL We say that two instances I, I' of BNSL are equivalent if (1) they are either both cos-instances or both No- instances, and furthermore (2) a solution to one instance can be transformed into a solution to the other instance in polynomial time. Our aim here is to prove the following theorem:
Theorem 3. There is an algorithm which takes as input an instance I of BNSL #0 whose super- structure has fen k. runs in time ((I[2), and outputs an equivalent instance I' = (V', (') of BNSL such that [' 166..
In parameterized complexity theory. such data reduction algorithms with performance guarantees are called kernelizution algorithms 99 (.) These may applied as a polynomial-tine preprocessing step before, e.g., more computationally expensive methods are used. The exedmparrmeter tractability of BNSL, #0 when parameterized by the fen of the superstructure follows as an immediate corollary of Theorem (one may solve I by, e.g., exhaustively looping over all possible DAGs on V" via
5

---

brute-force procedure). We also note that even though the number of variables of the output instance polynomial in the parameter k, the instance I' need not have size polynomial in k:
We begin our path towards a proof of Theorem 3 by computing a feedback edge set Err of G of size in time ((Z))) by, e-g., Prim's algorithm. Let 7 be the spanning tree of G. Er E(G)) E(T). The algorithm will proceed by the recursive application of certain reduction rules, which are polynomial- time operations that alter ("simplify") the input instance in a certain way. A reduction rule is safe if outputs an instance which is equivalent to the input instance. We start by describing a rule that will be used to prune until all leaves are incident to least one edge Ep.
V be a vertex and let Q be the set of neighbors of with de- gree 1 in G. We construct a new instance I' = (V', E) by setting: 1. V' = V Q: 2. r(( == (P Q) P [z(t)); 3. for all w V" (v), Ste smi 4. for every ('E)((o)):
Reduction Rule 1. Let
S((P'):=
(Fc(P) +
Σ (0) +
Σ max(Jua (0), Foo (v))).
max P:P.Q=P
EnEn
Lemma 4. Reduction Rule 7 is safe.
Observe that the superstructure graph G' obtained after applying one step of Reduction Rule is simply G Q: after its exhaustive application we obtain an instance I such that all the leaves of the tree T are endpoints of Ep. Our next step is to get rid of long paths in G whose internal vertices have degree 2. We note that this step is more complicated than in typical kernelization results using feedback edge set as the parameter, since a directed path Q in can serve multiple "roles" in a hypothetical solution D and our reduction gadget needs to account for all of these. Intuitively, Q may or may not appear as a directed path in (which impacts what other ares can be used in 1) due to acyclicity), and in addition the total score achieved by D the internal vertices of Q needs to be preserved while taking into account whether the endpoints of Q have a neighbor in the path or not. Because of this (and unlike in many other kerneiization results of this kind 117 43 15),, we will not be replacing Q merely by a shorter path, but by a more involved gadget. An illustration is provided in Figure 3
Reduction Rule 2. Let a, b,.................. bm, be a path in G such that for each i E [m], b, has degree F..))
precisely 2, and let P = (bi...., J. We construct a new instance I' = -V', (V',F". 2) as follows:
1. V = V U (b} \ (bb....m-1):
2. I' (b) {B U (b1, BB S (a, c where f U {b1, bm is equal the maximum
score that can be achieved by P if B are used as parents;
3. The scores for a and c are obtained F by simply adding to any parent set containing either by or bmi
4. ((b)) contains only {a, b, 3 with score equal to the maximum score that can be achieved by P if is used as a parent but there is no path from a to bm via P:
5. y (bm) contains only {c, b, b with score equal to the maximum score that can be achieved by P if is used as a parent but there is path from to by via P:
6. for all w E V' fa, bi, b, bms c). flo fw-
Lemma S. Reduction Rule is safe.
We begin by exhaustively applying Reduction Rule Ion on instance whose superstructure graph has a feedback edge set of size k, which results in an instance with the same feedback edge set but whose spanning tree T has at most 2k leaves. It follows that there are at most 2k vertices with a degree greater than in T.
Proof of Theorem 3
Let us now "mark" all the vertices that either are endpoints of the edges in Ep or have degree greater then 2 in T; the total number of marked vertices is upper-bounded by 4k. We now proceed to the exhaustive application of Reduction Rule 2 which will only be triggered for sufficiently long paths in T that connect two marked vertices but contain no marked vertices on its internal vertices; there are at most 4k such paths due to the tree structure of T.. Reduction Rule 2 will replace each such path with

---

201
b1
b1
b
byn
Dm
Dm
Dm
Um
Figure 3:
Top: The six possible solution scenarios that may arise when dealing with long paths. Bottom: The corresponding ares in the gadget after the ap- plication of Reduction Rule 2
case
case 2
cause 3
case 4
Cabio 5
casc G
a
by
U
by
bm
bun
byn
byo
Um
bin
BLC exists
....eeee are may exist (any direction)
arC exist
there is no directed poth
set of 3 vertices, and therefore after its exhaustive application we obtain equivalent instance with at most 4k + 4k 3 = 16k vertices, as desired. Correctness follows from the safeness of Reduction Rules [ and the runtime bound follows by observing that the total number of applications of each rule as well as the runtime of each rule are upper-bounded by linear function of the input size. O
As an immediate corollary of Theorem 3. we can apply a standard brute-force branching proce- + 20(4),
dure 33 to solve BNSL in time (())
-arrmmParre Tractability of BNSL 20 using the Local Feedback Edge Number, Our aim here will be lift the exedmparrmettr tractability BNSL #0 established by Theorem 3 by relaxing the parameterization to Ifen. In particular, we will prove:
Theorem 6. BNSL#0 is fixed-parameter tractable when parameterized by the local feedback edge number of the superstructure.
Since fen is more restrictive parameter than Isen, this results in a strictly larger class of instances being identified as tractable. However, the means we will use to establish Theorem will be funda- mentally different: we will not use polynomial-time data reduction algorithm the one provided in Theorem but instead apply a dynamic programming approach. Since the kernels constructed by Theorem contain only polynomially-mie many variables w.r.t. fen, that result is incomparable to Theorem fact one can use standard techniques to prove that, under well-established complexity assumptions, data reduction result such the one provided in Theorem 3 cannot exist for lfen.
Theorem 7. Unless NP C Co-NP/poly there is polynomial-tine algorithu which takes as input an instance I of BNSL# #0 whose superstructure has Ifen k and oulputs an equivalent instance = (V', (") of BNSL* such that [V'| E k0(1), particular, BNSL #0 does not admit polynomial kernel when parameterized by Ifen.
Towards proving Theorem assume that we are given an instance (V,F, of BNSL #0 with connected superstructure graph G = (V, E). Let 7 be a fixed rooted spanning tree of G such that Ifen(Gr G, T) GGe = k. denote the root by r. For u E VTT), let T. be the subtree of T rooted at let V, (TT.). and let V, (V,) U Vy. We define the boundary 8(v) of u to be the set of endpoints of all edges in G with precisely one endpoint in V. (observe that the boundary can never have a size of 1). Notice that [ō(x)] < 2k + 2. We can now proceed to definition of the records that will be used in our dynamic program. Intuitively, these records will be computed in a seaf-to-root fashion and will store at each vertex information about the best score that can be achieved by partial solution that intersects the subtree rooted at v.
Let R be binary relation on 8(v) and an integer. For 8 E Z, we say that (R: s) is record for vertex v and only if there exists a DAG on V, such that (1) E V, for each are uw E A(D), (2) ab R. if there exists a-b path in D, and (3) is the total score achieved by D on vertices in V.,
7

---

The records (R, s) where s is maximal for fixed R are called valid. Denote the set of all valid records for by R(v), and note that (R(v)) - 20(42)
Observe that if v; is a closed child of e, then R(v;) consists of precisely two valid records: one for R 12=0 0 and one for I = {vuz}. Moreover, the root of T has only single valid record (0: : sz), where sI is the maximum score that can be achieved by a solution in I. The following lemma lies at the heart of our result and shows how can compute our records in leaf-to-
fashion along T.
Lemma 8. Let E V() have m children in where m > O, and assume we have computed (e;) for each child 1/ of U. Then R(v) can be computed in time at most m.
(v)) 20(k).
To prove Theorem 6 we start by invoking Theorem to obtain a spanning tree T and then compute the records R(v) for each leaf of T via exhaustive branching. We then apply Lemma 8 to propagate our record sets towards the root of T; once we obtain R(r), we can output a solution in constant time. The runtime of the dynamic programming procedure used in the proof of Theorem ils upper-bounded by |Z]3 20(2).
For our final result for this section, recall that Isen lies between fen and treecut width in the parameter hierarchy (see Proposition I. Since BNSL #0 is FPT when parameterized by Isen, the next step would be to ask whether this tractability result can be lifted to treecut width. Below, we answer this question negatively via a reduction from the W[1]-hard MULTICOLORED CLIQUE problem 59.5.
Theorem 9. is [[]]-hard when parameterized by the treecul width of the superstructure.
4 Additive Scores and Treewidth
While the previous section focused on the complexity of BNSL when the non representation was used (i.e.. BN here we turn our attention to the complexity of the problem with respect to the additive representation. Recall from Subsection that there are two variants of interest for this representation: BNSL and BNSL We begin by showing that, unsurprisingly, both of these NP-hard. We do so by reducing from the classical MINIMUM FEEDBACK ARC SET problem 20 Theorem 10. BNSL+ + is Nardard. Moreover, B is NP-hard for every q 2 3.
While the use of the additive representation did not affect the classical complexity of BNSL, it makes a significant difference in terms of parameterized complexity. Indeed, in contrast to BN
Theorem 11. BNSL* is FPT when parameterized by the treewidth of the superstructure. Moreover, BNSL FPT when parameterized by q plus the treewidth of the superstructure.
Proof Sketch. As noted in the preliminaries, due to space constraints we refer to the usual books for a definition of treewidth and nice tree-decompositions ( 55. We begin by applying Bodlaender's algorithm 3 [2 compute a nice tree-decomposition (T x) of Gr of width k tw(Gz), whose vertices are called nodes. To prove the theorem, we will design a leaf-to-root dynamic programming algorithm which will compute and store a set of records each node of T, whereas once we ascertain the records for r we will have the information required to output a correct answer. Intuitively. the records will store all information about each possible set of ares between vertices in each bag, along with relevant connectivity information provided by ares between all vertices that are either in the current bag i or in some descendant of t (we denote the set of these vertices x²), and information about the partial score. When solving BNSL the records will also keep track of parent set sizes.
Formally, the records will have the following structure. For a node t, let S(t) {(loc, con, inn) loc, con C Ax(0), inn x(t) [9]o} be the set of snapshots of The record R. of t is then mapping from S(t) to No U {11. Observe that |S(t)) s 4 (q + 1)a To introduce the semantics of our records, let Y, be the set of all directed acyelic graphs over the vertex set xa with maximal in in-degree at most q, and let D. = (xt, A) be a directed acyelic graph in Y,. We say that the snapshot of D, in is the tuple (a, 3,p) where a = A n Ax(o) B = Con(x(t), D.) and p (which is only used for B specifies numbers of parents of vertices from x(1) in D,
i.e., p(v) = Kw E x2 E A}L. v E x(). Now, for each snapshot (loc, con, inn) E S(L) we set (loc, con, inn) = if there exists no DAG in Y, with (loc, con, inn) as its snapshot, and otherwise we set R, (loc, con, inn) to the highest score that can be achieved by such a DAG.
8

---

The algorithm computes these records in a leaf-to leaf-to-root fashion while traversing T, which can be achieved in time at most 20(k") g0(k) n. where is the input size. Once reach the root node r, we use the fact that x(r) = @ by the definition of nice rreepeccomoostionns to simply check R, (0, 0, 0) 2 E; the algorithm then outputs "Yes" if and only if this is the case.
This completely resolves the parameterized complexity of BNSL+ w.r.t. all parameters depicted on Figure 1 However, the same is not true for BNSL: while careful analysis of the algorithm provided in the proof of Theorem reveals that BNSL is XP-tractable when parameterized by the treewidth of the superstructure alone, it is not yet clear whether is FPT-in other words, do we need to parameterize by both q and treewidth to achieve fxee-parameter tractability? We conclude this section by answering this question affirmatively via an involved two-step reduction from a variant of the W[1]-hard MULTIDIMENSIONAL SUBSET SUM problem 13).
Theorem 12. BNSL is W[1]-hard when parameterized by the treewidth of the superstructure.
5 Implications for Polytree Learning
Here, we discuss how the results of Sections 3 and and 4 can be adapted to POLYTREE LEARNING (PL).
Theorem 3 Data Reduction. Recall that the proof of Theorem 3 Jused two data reduction rules. While Reduction Rule I carries over to PL,#0, Reduction Rule 2 has to be completely redesigned to preserve the (non-)existence of undirected paths between and c. By doing so, we obtain:
Theorem 13. There is an algorithm which takes as input an instance I of PL whose superstructure has feedback edge number k, runs in time ((I and outputs an equivalent instance (V', F 1") of PL such that [V| 24k.
Theorem 6 Fixed-parameter tractability. Analagously to BNSL data reduction procedure as the one provided in Theorem 13 does not exist for PL parametrized by Ifen unless NP S co-NP poly, since the lower-bound result provided in Theorem can be straightforwardly adapted to PL But similarly for BNSL
provide an FPT algorithm using the same ideas in the proof of Theorem 66] The algorithm proceeds by dynamic programming on the spanning tree T of G with Ifen 7' (G) = k. The records will, however, need to be modified: for each vertex v, instead of the path-connectivity relation on 8(v), we store connected components of the inner boundary 5(v) n V, and incoming ares T.. This yields:
Theorem 14. PL is fixed-parameter tractable when parameterized by the local feedback edge number of the superstructure.
As for treecut width, we remark that a recent reduction for PL implies that the problem is W[1]-hard when parameterized by the treecut width.
21 Theorem 4.2] immediately
Theorem Additive Representation.
We remark that, like BNSL+ + and BNSL a simple reduction shows that PL- is NP-hard for fixed value of g, in this case 1. Moreover, the dynamic programming algorithm for BNSL parameterized by treewidth and q can be adapted to also solve FL The algorithm runs in time most 20(k)) .go)). [Z].
Theorem 15. PL is FPT when parameterized by q plus the treewidth of the superstructure.
The situation is, however, completely different for PL+: unlike BNSL+ this problem is in fact polynomial-time tractable. Indeed, it admits a simple reduction to the classical minimum edge- weighted spanning tree problem.
Observation 16. PL+ is polynomial-time tractable.
This coincides with the intuitive expectation that learning simple, more restricted networks could be easier than learning general networks. We conclude our exposition with an example showcasing that this is not true in general when comparing PL to BNSL. Grüttemeier et al. [21] recently showed that PL is W[1]-han when parameterized by the number of dependent vertices, which vertices with non-empty sets of candidate parents in the non-zero representation. For BNSL #0 we can show:

---

Theorem 17. BNSL70 is thrd-meareeter tractable when parameterized by the number of dependent vertices.
Concluding Remarks
Our results provide new set of tractability results that counterbalance the previously established algorithmic lower bounds for BAYESIAN NETWORK STRUCTURE LEARNING and POLYTREF LEARNING on "simple" superstructures. In particular, even though the problems remain W[1]-hard when parameterized by the vertex cover number of the superstructure [32 21
we obtained fixed-
parameter tractability and a data reduction procedure using the feedback edge number and its localized version. Together with our lower-bound result for treecut width, this completes the complexity map for BNSL w.r.t. virtually all commonly considered graph parameters of the superstructure. Moreover, we showed that the input is provided with an additive representation instead of the non-zero representation considered in previous theoretical works, the problems admit a dynamic programming algorithm which guarantees parammeer tractability w.r.t. the treewidth of the superstructure. We remark that all of our results assume that the score functions provided explicitly; future work could also consider the behavior of the problem when these functions are supplied by a suitably defined oracle.
This theoretical work follows up on previous complexity studies of the considered problems, and as such we do not claim any immediate practical applications of the results. That being said, it would interesting to see if the polynomial-time data reduction procedure introduced Theorem could be adapted and streamlined to allow for speedup of previously introduced heuristics for the problem [40, (3), at least for some sets of instances. Finally, we believe that the local feedback edge number be used to push the boundaries of tractability for other problems of interest as well.
Acknowledgments. P31336 and Y1329).
The authors acknowledge support by the Austrian Science Fund (FWF, projects
Funding Transparency Statement. Funding in direct support of this work: FWF Project P31336, FWF Project Y1229.
Declaration of Competing Interests. None the authors have financial relationships with entities that could potentially be perceived to influence the content of the submitted work.
References
[1] Matthias Bentert, Roman Haag, Christian Hofer, Tomohiro Koana, and André Nichterlein. Parameterized complexity of min-power asymmetric connectivity. Theory of Computing Systems, 64:1158-1188 2020.
[2] Nadja Betzler, Robert Bredereck, Rolf Niedermeier, and Johannes Uhlmann. On bounded- degree vertex deletion parameterized by treewidth. Discret. Appl. Math., 160(1-2):53 60, 2012.
[3] Hans L. Bodlaender. A linear- algorithm for finding tree-decompositinns of small treewidth. SIAM J. Comput., 25(6): 1996.
[4] David Maxwell Chickering. Learning Bayesian networks is NP-complete. In Learning from data (Fort Lauderdale, FL, 1995), volume 112 of Lecture Notes in Statist., pages 121-130. Springer Verlag, 1996.
[5] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipezuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
[6] Sanjoy Dasgupta. Learning polytrees. In Kathryn B. Laskey and Henri Prade, editors, UAI '99: Proceedings of the Fifteenth Conference Uncertainty in Artificial Intelligence, Stockholm, Sweden, July August 1, 1999, pages 134-141. Morgan Kaufmann, 1999.
[7] Camil Demetrescu and Irene Finocchi. Combinatorial algorithms for feedback problems in directed graphs. Inf. Process. Lett., 86(3):129-136. 2003.
10

---

[8] Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012.
[9] Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013.
[10] Eduard Eiben, Robert Ganian, lyad Kanj, and Stefan Szeider. The parameterized complexity of cascading portfolio scheduling. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Bus Emily B. Fox, and Roman Gameet, editors, Advances Neural Infor- mation Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 7666-7676, 2019.
[11] Gal Elidan and Stephen Gould. Learning bounded treewidth bayesian networks. In Daphne Koller, Dale Schuurmans, Yoshua Bengio, and Léon Bottou, editors, Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 8-11, 2008, pages 417-424. Curran Associates, Inc., 2008
[12] Jirí Fiala, Petr A. Golovach, and Jan Kratochvíl. Parameterized complexity of coloring problems: Treewidth versus vertex cover. Theor. Comput. Sci., 412(23):2513-2552 2011.
[13] Robert Ganian, Iyad A. Kanj, Sebastian Ordyniak, and Stefan Szeider. Parameterized algorithms for the matrix completion problem. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018 volume 80 of Proceedings of Machine Learning Research, pages 1642-1651. PMLR, 2018.
[14] Robert Ganian, Eun Jung Kim, and Stefan Szeider. Algorithmic applications of tree-cut width. In Giuseppe F. Italiano, Giovanni Pighizzini, and Donald Sannella, editors, Mathematical Foundations of Computer Science 2015 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, volume 9235 of Lecture Notes in Computer Science, pages
Springer, 2015.
[15] Robert Ganian, Fabian Klute, and Sebastian Ordyniak. On structural parameterizations of the bounded-degree vertex deletion problem. Algorithmica, 83(1):297-336, 2021.
[16] Robert Ganian and Sebastian Ordyniak. The complexity landscape of decompositional parame- ters for ILP. Artif. Intell., 257:61-71, 2018.
[17] Robert Ganian and Sebastian Ordyniak. The power of cut- but-based parameters for computing edge-disjoint paths. Algorithmica, 83(2):22-7552, 2021.
[18] Robert Ganian, Sebastian Ordyniak, and Ramanujan Sridharan. On structural parameterizations of the edge disjoint paths problem. Algorithmica, 83:1605-1637, 2021.
[19] Serge Gaspers, Mikko Koivisto, Mathieu Liedloff, Sehastian Ordyniak, and Stefan Szeider. On finding optimal polytrees. Theor. Comput, Sci., 592:49 08,449958,000 2015.
[20] Fanica Gavril. Some np-complete problems on graphs. In Proceedings of the I 11th Conference on Information Sciences and Systems, pages 91-95, 1977.
[21] Niels Grüttemeier, Christian Komusiewicz. and Nils Morawietz. On the parameterized complex- ity of polytree learning. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI-2I), 2021. To appear; preprint available at https:/aariv.orr/aas//111333 wttp:///////1......0000 05.09675.
[22] Niels Grüttemeier and Christian Komusiewicz. Learning bayesian networks under sparsity constraints: A parameterized complexity analysis. In Christian Bessiere, editor, Proceedings of the Twetty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 4245 4251. ijcai.org, 2020.
[23] Haipeng Guo and William Hsu. A survey of algorithms for real-time bayesian network inference. In Working Notes of the Joint AAAI/UAI/KDD Workshop on Real-Ture Decision Support and Diagnosis Systems, 2002.
11

---

[24] T. Kloks. Treewidth: Computations and Approximations. Springer Verlag, Berlin, 1994.
[25] Yasuaki Kobayashi and Hisao Tamaki. Treedepth parameterized by vertex cover number. In Jiong Guo and Danny Hermelin, editors, 11th International Symposium Parameterized and Exact Computation, IPEC 2016, August 24-26. 2016, Aarhus, Denmark, volume 63 of LIPlcs, Schloss Dagstuhl- Leibniz-7Zentrum für Informatik, 2016.
pages 18:1-18:11,
[26] Janne H. Korhonen and Pekka Parviainen. Exact learning of bounded tree-width bayesian networks. In Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statisties, AISTATS 2013, Scottsdale, AZ, USA, April 29 May 1, 2013, volume 31 of JMLR Workshop and Conference Proceedings, pages 370-378. JMLR.MM...... .org. 2013.
[27] Janne H. Korhonen and Pekka Parviainen. Tractable bayesian network structure learning with bounded vertex cover number. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 622-630, 2015.
[28] Dániel Marx and Paul Wollan. Immersions in highly edge connected graphs. SIAM J. Discret. Math., 28(1) 28(1):503-520, 2014.
[29] Christopher Meek. Finding path is harder than finding tree. J. Artif. Intell. Res., 15:383-389, 2001.
[30] Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity Graphs, Structures, and Algorithms, volume 28 of Algorithms and Combinatorics. Springer Verlag, 2012.
[31] Rolf Niedermeier. Invitation to SxeedParrmeetr Algorithms. Oxford Lecture Scries in Mathe- matics and its Applications. Oxford University Press, Oxford, 2006.
[32] Sebastian Ordyniak and Stefan Szeider. Parameterized complexity results for exact bayesian network structure learning. J. Artif. Intell. Res., 46:263-302, 2013.
[33] Sascha Ott, Seiya Imoto, and Satoru Miyano. Finding optimal models for small gene networks. In Russ B. Altman, A. Keith Dunker, Lawrence Hunter, Tiffany A. Jung, and Teri E. Klein, editors, Biocomputing 2004, Proceedings of the Pacific Symposium, Hawaii, USA, 6-10 January 2004, pages 557-567 World Scientific, 2004.
[34] Judea Pearl. Probabilistic reasoning in intelligent systems- networks of plausible inference. Morgan Kaufmann series in representation and reasoning. Morgan Kaufmann, 1989.
[35] Eric Perrier, Seiya Imoto, and Satoru Miyano. Finding optimal bayesian network given a super-structure. J. Mach. Learn. Res., 9()):2251-2288) 2008
[36] Neil Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithmms, 7(3):309-322, 1986.
[37] Neil Robertson and Paul D. Seymour. Graph minors. i. excluding forest. J. Comb. Theory, Ser.
B, 35(1):39-6) 61, 1983.
[38] Javad Safaei, Ján Manuch, and Ladislav Stacho. Learning polytrees with constant number of roots from data. In Stephen Cranefield and Abhaya C. Nayak, editors, Al 2013: Advances in Artificial Intelligence 26th Australasian Joint Conference, Dunedin, New Zealand, December 1-6, 2013. Proceedings, volume 8272 of Lecture Notes in Computer Science, pages 447-452. Springer, 2013.
[39] Mauro Scanagatta, Giorgio Corani, Cassio P. de Campos, and Marco Zaffalon. Learning nrewidth-bounder bayesian networks with thousands of variables. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 1462-1470, 2016.
12

---

[40] Mauro Scanagatta, Cassio P. de Campos, Giorgio Corani, and Marco Zaffalon. Learning bayesian networks with thousands of variables. Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Process- ing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 1864-1872, 2015.
[41] Kirill Simonov, Fedor V. Fomin, Petr A. Golovach, and Fahad Panolan. Refined complexity of PCA with outliers. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 9818-5826. PMLR, 2019.
[42] loannis Tsamardinos, Laura E. Brown, and Constantin Aliferis. The max-min hill-climbing bayesian network structure learning algorithm. Mach. Learn., 65(1): 2006.
[43] Johannes Uhlmann and Mathias Weller. Two-layer planarization parameterized by feedback edge set. Theor. Comput. Sci., 494:99-111, 2013.
[44] René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko. Parameterized algorithms and data reduction for the short secluded s-t-path problem. Networks, 75(1):34-63, 2020.
[45] Paul Wollan. The structure of graphs not admitting fixed immersion. J. Comb. Theory, Ser. B, 110:47-66, 2015.
13


Reviews:
[{"review_id": "piQ1PuC_Bf", "reviewer": "Reviewer_3mFx", "summary": "This paper investigates the fixed-parameter tractability of the Bayesian Network Structure Learning (BNSL) problem, according to new parameters related to the network superstructure. Namely, since the BNSL problem is known to be W[1]-hard for various vertex-related parameters, the authors concentrate on edge-related parameters, by showing that fixed-parameter tractability can indeed be achieved in some cases. In doing so, the authors consider two parameters, the feedback edge number (fen) and its “local” version (lfen), which are less restrictive than the tree-cut width (tcw). Orthogonally, the authors examine three families of scoring (function) representations: non-zero representations, additive representations, and bounded additive representations. Finally, the authors explore the fixed-parameter tractability of polytrees.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this paper is well-motivated, well-written, and its technical quality is remarkable. As far as I could check, the paper is well-positioned with respect to the related work, and the main proofs are well-detailed. Importantly, positive FPT results are balanced against negative ones, which together provide natural limitations of this study.  \n\nUnsurprisingly, the main concern with such a paper is the applicability of theoretical results. In fact, the lack of “immediate” practical applications is a limitation emphasized by the authors in the conclusion. Yet, I think that the paper could be improved in order to have a better insight into the pragmatic aspects of the theoretical results. Namely, instead of just claiming that “Problem X is FPT …”, I would suggest providing a detailed complexity result. For example, using the kernelization result in Theorem 3, together with an upper bound on the number of directed acyclic subgraphs (for the complexity of the brute-force enumeration algorithm in Lines 218-219), we would get a result in $n^{O(1)} 2^{O(k^2)}$. On the other hand, even if the “lfen” metric is more restricted than the “fen” one, it seems that in this case, the term in the exponential is in $O(k^3)$. So, for the moment, unless the superstructure of a BNSL instance has very small global/local feedback edge numbers, the practical aspects of FPT algorithms are questionable. Based on the sketch of proof of Theorem 11 (number of snapshots), it seems that a similar consideration holds for the treewidth parameter in the setting of additive scores.\n\nMinor comments:\n* Lines 135-136: The sentence “Let $\\Gamma_f(v)$ be the set of candidate parents of $v$ [...]” is a bit ambiguous. I would suggest “Let $\\Gamma_f(v)$ be the collection of candidate parent-sets of $v$ [...]”.\n* Line 178: “caardinality” -> “cardinality”.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations: Yes to some extent. As mentioned in the review, the paper is providing both positive and negative FPT results for related parameters, and this helps in circumscribing the theoretical aspects of the BNSL problem. On the other hand, the paper could be further improved by presenting concrete complexity results. ", "review_text": "", "extra_scores": {"ethical_concerns": "Not Applicable.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "K6b6hjZ6DY8", "reviewer": "Reviewer_6TGC", "summary": "This is a paper about the parametrized complexity of BN structural learning. To achieve that the authors consider the learning task as a decision problem and distinguish tasks wrt the way the local scores are represented (non-zero, additive, additive with bound on the number of parents).\nSeparately for each class, the authors discuss tractability wrt various parameters (and not only the treewidth) used to describe the superstructure. This in particular suggests a dynamic programming approach for the additive case that is fixed-parameter tractable wrt the treewidth. Those results are also specialized to the case of learning polytree-shaped models.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a theoretical paper that might improve the understanding of the computational complexity of BN structural learning. I think the paper should be accepted. As also noticed by the authors, the work is very theoretical and using these result to practically implement algorithmic schemes might not be obvious. Yet, some more discussion in this direction could help as well as a quick taxonomy of the scores used in the literature wrt the categories considered by the authors.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Nothing.", "review_text": "", "extra_scores": {"ethical_concerns": "Nothing.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "5bsMVMrX18H", "reviewer": "Reviewer_9zsF", "summary": "Summary. \nThe paper is about the parameterized complexity of Bayesian Network Structure Learning.\nIn particular, it is focused to analyze and develop previous contributions on superstructure of the input.\nThe author/s show/s that changing the parametrization yields to achieve fixed-parameter tractability. \nThe paper also anallyzes how the complexity of structural learning of bayesian networks depends on the input representation, with specific reference to non-zero representation, and additive representation.\nFinally the paper shows how to extend the main contirbutions presented to the problem of Polytree Learning.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: \nI'm under the impression that the paper is original because it proposes and investigates a new parametrization for solving the problem of structural learning in Bayesian networks, i.e., it investigates how such a parametrization impact on tractability of the problem of structural learning of bayesian networks.\n\nQuality: \nThe paper is well structured and written in my humble opinion. SOme terms and wuantities are not defined in the paper but are left to reader to find them on reference books. Theoretical results seem to be interesting but it is difficult for me, not being specifically working in thei very specific subarea to fully appreciate how such results can bring practical benefit to solve the problem of learning bayesian network structure.\nPersonally, I think that this type of papers, containing many theorems with proof left to the supplementary material are very difficult to manage having just few weeks.\n\nClarity:\nThe paper is somewhat clear, even if my marginal knowledge of the research subject makes me unsecure about this.\nI think that adding some practical example would have improved a lot the readability of the paper and had help the interested reader to better appreciate the quality of the work.\n\nSignificance: \nThe paper is significant to provide a different research direction to analyze the ocmplexity of lstructural learning of bayesian networks. Also in this case I think that some numerical experiments would have better clarified the significance and relevance of the different contributions described in the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Apparently the paper clarifies that the achievements are limited and suggests further developments.\nIn particular, the paper states that even if fixed-parameter tractability is obtained and a data reduction procedure using the feedback edge number and its localized version are provided, the problems remain W[1]-hard when parameterized by the vertex cover number of the superstructure.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}, {"review_id": "4d-Nzbo4v71", "reviewer": "Reviewer_F8cX", "summary": "This paper contains a number of significant FPT results for BNSL, as\nwell as providing a concise summary of existing FPT results. A key\nparameter considered is \"local feedback edge number\" which provides\nFPT. Results for when local scores are additively decomposable are\ngiven. The paper has many results and so many proofs are relegated to\nthe supplementary material.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and contains a number of significant\ntheoretical results. It will be interesting to see how/whether these\nresults can be used to inform better BNSL solving, but that is a\nquestion for a different paper.\n\nOne can remove (i.e. not store) any parent set which has a proper\nsubset with a score that is not lower. Not storing zero scores is just\na special case of this, why not consider the more general case?\n\nConcerning the additive representation: it is no surprise that *if* a\nlocal score admits an additive representation then \"BNSL becomes\nsignificantly easier\" (and thus more positive FPT results are\navailable). However, it is something of an understatement for the\nauthors to say that \"not every family of local score functions admits\nan additive representation\", the only examples the authors give of local\nscores which are \"additive\" are those which are approximations to\n\"real score functions\". (I too don't know of any others.) So basically\nthis boils down to the fact that BNSL problems with real\n(statistically-motivated) local scores are a lot easier to solve\napproximately than exactly. Having tractability results for (exactly)\nsolving an approximation is of some use, but one needs to consider\nalso what is lost by the approximation.\n\nThe instances the authors consider, I=(V,F,l), have the parent sets F\nexplicitly given, which, as the authors state, could lead to very\nlarge instances. It would be interesting to extend this line of work to\nwhere the parent sets, rather than being precomputed in order to\ncreate the instance, are supplied by some function which supplies\nparent sets on demand. Evaluating this function might take, say, O(np)\nwhere n is the number of datapoints and p-1 the size of the parent set.\n(Of course, finding the superstructure would be more involved in this\nsetting.) \n\n\n157: fix \"dependencey\"\n178: fix \"caardinality\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "These issues are not addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is clear consensus among all involved in the assessment. I would be very glad to see the talk about this paper myself too. Please do take suggestions in consideration.
Decision: Accept (Oral)