{'fraction_non_alphanumeric': 0.035369946199328824, 'fraction_numerical': 0.012784317903371863, 'mean_word_length': 4.639531390808051, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Choosing the Root of the Tree Decomposition When Solving WCSPs: Preliminary Results

In this paper we analyze the effect of selecting the root in a tree decomposition when using decomposition-based backtracking algorithms. We focus on optimization tasks for Graphical Models using the BTD algorithm. We show that the choice of the root typically has a dramatic effect in the solving performance. Then we investigate different simple measures to predict near optimal roots. Our study shows that correlations are often low, so the automatic selection of a near optimal root will require more sophisticated techniques.


Introduction
Many combinatorial optimization tasks on graphs can be computed in linear time when the graph is acyclic. It is well-known that in many cases we can benefit from this observation even when the graph of interest is cyclic by using a so-called tree decomposition which maps the graph into a tree [1]. Roughly speaking, the nodes in the decomposition contain the cyclic parts of the graph and the edges capture the acyclic interaction between the cyclic parts. Then, the tree decomposition can be used to guide a dynamic programming algorithm that proceeds bottom-up in the decomposition solving the respective subproblems. Typically such algorithms have time and space complexity exponential in the size of the largest cyclic part, which is called the (tree decomposition) width [2]. This approach has been widely studied in the context of Graphical Models [3], which is an umbrella term that covers a broad number of problems such as Bayesian Networks, Markov Networks [4], Weighted CSPs [5,3], etc. If we can find a small tree width for the instance of interest, then we can apply directly a dynamic programming algorithm (e.g. Bucket Elimination [6,7]) and solve it very efficiency. However, if we can only find decompositions with large width, then dynamic programming is useless (typically for its space complexity) and we have to rely on heuristic search methods such as Depth-first or Best-first. Heuristic search algorithms are unfeasible in terms of worst-case complexity because they are exponential in the problems size. However, the Graphical Models com-munity has enhanced them with intelligent pruning techniques and they can solve many large instances in pretty reasonable time [8].
A very fruitful line of research is the exploitation of decomposition trees beyond small widths by adapting heuristic search to the problem decomposition. The basic idea is simple and has been known for decades as AND/OR search [9]. In the context of Graphical Models corresponds to moving from a tabular to a memoization implementation of DP. However, the real challenge is to make it work in practice, that is, to add all the advantageous pruning techniques developed for standard heuristic search [10,11,12]. Such algorithms, that we call decomposition-based backtracking algorithms, have a proven time and space worst-case complexity exponential in the tree width, but their actual performance is much better than that due to the pruning techniques.
The definition of decomposition tree is not rooted, but decomposition-based algorithms must pick one. For standard implementations of dynamic programming algorithms such choice is not very important, since worst-case complexity is a tight bound of average-case complexity. However, some authors have reported that in decompositionbased backtracking algorithms choosing the root has an impact in performance [13].
In this paper we want to dig into this issue. We focus on the backtracking treedecomposition algorithm BTD [10] inside toulbar2 2 which is arguably the best example of this line of work.
We report an experiment in which we solve a carefully selected set of instances with all clusters as root. The experiment confirms that the impact of choosing a good root is high. We also observe that such impact changes very much from one problem to another. In some instances the best root hardly halves the time of the worst root. However, in other instances the best root makes the algorithm thousands of times faster than the expected time of making a random choice. The results from the experiment raise the natural question of how to identify a good root from the structure of the decomposition. To answer that question we have measured the correlation between performance and some simple yet reasonable cluster parameters. We observed that such simple parameters are often uncorrelated to performance, so they cannot be used as a heuristic way to identify a near optimal root.
To the best of our knowledge, this is the first systematic study on the impact of root selection in decomposition-based backtracking algorithms for Graphical Model optimization tasks, and the first attempt to identify a predictor of near optimal roots. Since we have not found simple single measurements correlated to algorithmic performance, we hypothesize that more sophisticated techniques such as machine learning are needed.

Graphical Models
and the goal that we are considering here is to minimize it. In probabilistic problems (i.e, the objective function has a probabilistic interpretation) this task is called most probable explanation. In non-probabilistic problems it is usually referred as Weighted CSP. Solving a Graphical model is an NP hard problem, which means that the existence of polynomial algorithms is unlikely to exist. The design of effective algorithms for this problem has attracted a lot of research interest in the last decade [3,4].

Interaction Graph
The term Graphical Model comes from the existence of an underlying graph that captures important structural properties. Given a Graphical Model P = {X, D, F}, its Interaction graph, noted G P = (V, E), is an undirected graph with vertices V and edges E. There is one vertex i ∈ V associated to each variable x i ∈ X, and there is an edge (i, j) ∈ E if and only if there some cost function f S ∈ F with {i, j} ⊆ S. Thus, the interaction graph tells pairs of variables that are linked (or connected) via cost functions. Figure 1 (left) shows the interaction graph of a graphical model with 8 variables (one per node) and 10 arity-2 cost functions (one per edge).
It is well-known that graphical models whose interaction graph is acyclic can be solved efficiently. For graphical models with a cyclic interaction graph, we can identify its acyclic sub-components through a tree-decomposition.

Tree Decomposition
The set of clusters must cover all the variables (i.e, ∪ e∈V C e = X) and all the cost functions (for every f S ∈ F there is some cluster C e such that S ⊆ C e ). Furthermore, if a variable x i appears in two clusters C e and C k , it must also appear in all the clusters on the unique path from e to k (this is called the running intersection property).
The tree-width of a tree decomposition, noted w, is max e∈V {|C e |} − 1. The treewidth of G is the minimum tree-width of all tree decompositions of G. Figure 1 (right) shows a width 2 tree-decomposition of the graphical model whose cyclic interaction graph is depicted on the left.

Decomposition-based Backtracking Algorithms
Let T = (V, A) be a tree decomposition of graphical model P. If we chose a node r ∈ V as the tree root, then each tree node e ∈ V has a parent pa(e) and a set of children ch(e).
The separator of C e is the set of common variables with its parent S e = C e ∩ pa(C e ). The set of proper variables of C e is V e = C e − S e . Note that proper variables of clusters define a partition of the variables. We denote [i] the index of the cluster where x i is a proper variable. Each cost function f S is associated to the higher cluster that contains S and we denote [S] the index of such cluster. Decomposition-based backtracking algorithms assign variables in a top-down order with respect the decomposition. In other words, if variable x i is a proper variable of cluster C e (that is [i] = e), it cannot be assigned until all the variables of its parent pa(C e ) have been assigned. Therefore, we can think of a partial assignment t as tree-structured. Corresponding to a top-down partial labeling of the variables in the decomposition.
We denote P e the problem with all the variables of C e and its descendent clusters and all the cost functions having in their domain at least one proper variable of these clusters. Consider a partial assignment t of the variables in P that includes the variables in C e but does not include any proper variable of any child of C e . Then for every C k child of C e , we denote P k (t) to P k conditioned by t. Each one of these conditioned subproblems can be solved independently. Consequently, the search space traversed by this algorithms is the space of tree-structured partial assignments. To fully mimic the dynamic programming approach and inherit its good worst-case complexity, these algorithms may record the optimum of each solved subproblem, so they need not to solve it more than once. In terms of search space, this corresponds to merging nodes that correspond to identical subproblems. Figures 2 and 3 show two different search spaces for the tree decomposition of Figure 1 assuming binary domains. The two search spaces correspond to choosing two different roots for the tree-decomposition. Choosing the root producing the most cost-effective search space is the topic addressed in this paper.

Experimental Design
In order to conduct our study we needed a diverse set of instances that were neither too easy (in order to make comparisons meaningful) nor too hard (so that executions would not exceed our computation budget). For that purpose we used two repositories: • The evalgram repository (http://genoweb.toulouse.inra.fr/ degivry/evalgm/) • The Cost Function Library (https://forgemia.inra.fr/thomas.schiex/cost-functionlibrary/-/tree/master/) Together they contain more than 16500 instances coming from different application domains such as Bioinformatics, Boolean discrete problems, Bayesian netorkws, Airplane landing, Satelite observations, Graph coloring, Tractability-preserving Transformations of Global Cost Functions, Warehouse location problems and many others. We made a massive execution of all the instances using toulbar2 default and selected instances whose execution time range from 10 to 30 minutes 3 . For each problem having selected instances we selected two of them. Then we computed their tree decomposition using the minfill heuristic [14] and eliminated hard instances having more than 100 clusters and instances having large tree widths (not suitable for decomposition-based algorithms). We further eliminated instances that were problematic for different reasons such as having several connected components or having soft global constraints. As a result we obtained 19 diverse and challenging instances.  Table 1. Benchmark Description. Composed, geo, aim, packupweighted1, packupweighted2 and cnf3 full names are composed-75-1-2-9 ext 100, geo50-20-d4-75-86 ext 1000, aim-200-1 6-yes1-4.cnf.mo, 978532fa-c730-11df-b070-00163e3d3b7c l1, e69a0e36-9ef1-11df-9d4a-00163e46d37a l1, weightedregular, cnf2.80.1000.266842, respectively. Table 1 contains information about the instances. It can be seen that the guarantee of benchmark diversity does not come only from the different origin of instance, but also from their syntactical structure. The number of variables (column 2) ranges from 50 to 750, the domain size (column 3) ranges from 2 to 44, the number of cost functions (column 4), the maximum arity of cost functions (column 5) ranges from 2 to 10. The number of different costs appearing over the cost functions (column 6) ranges from 409 to 40217. The optimal value (column 7) ranges from 1 to 397147782. In terms of decomposability, using the minfill heuristic the tree-width (column 8) ranges from 11 to 381 and the separator size (column 9) from 8 to 381. Finally, the number of clusters (column 10) ranges from 14 to 591.
Toulbar2 makes a sophisticated pre-process before starting the solving process. This pre-process may change slightly the problem structure (e.g. eliminating variables) and in turn the tree decomposition. To avoid that these changes could obfuscate our results, we transformed each instance to its VAC (that is, virtual arc-consistent [5]) pre-processed version (e.g. "toulbar2 instance.wcsp -A -z=2") and computed a minfill tree decomposition again (e.g. "toulbar2 instanceVAC.wcsp -B=1 -hbfs: -O=-3 -Z=1").
Then we solved each instance instanceVAC.wcsp with each node r of the tree decomposition as root using the BTD algorith [10] (e.g."toulbar2 instanceVAC.wcsp -O=-3 -B=1 -hbfs: -R=r"). In order to make the comparison of cpu time meaningful in this experiment all executions were done using identical machines (Fujitsu Primergy CX250 S1 with Intel Xeon E5-2660 @ 2,2 Ghz and 128G of RAM). Jobs were managed  Table 2. Results solving each instance with every tree decomposition cluster as root. Times (worst, mean and best columns) are given in seconds. with SLURM queue system with each job requesting exclusive use of 1 core and 8Gb of RAM. To bound the duration of the experiment a time out was set to 3600 seconds 4 Results from this experiment are reported in Table 2. The second and fourth columns report execution times for the worst and best roots. In the second column, an asterisk indicates that the time out has been reached as many times as the number within parenthesis. The third column reports the average time over all the roots or, equivalently, the expected time by choosing a root randomly. However, note that in most of the instances the average is underestimated, since the timeout is often reached for several roots. Columns 5 and 6 report ratios. Note again that ratios are underestimations in all the instances where the timeout is reached.
The main observation from the ratios is that most of the times choosing the right root has a dramatic effect in the algorithm's performance. In a couple of instances, the best root makes the algorithm thousands of times faster than the worst root and even than the expected time from a random root selection. In most instances the best root makes the algorithm around an order of magnitude faster. There is only one instance where the best root is more than half the time of the worst. The previous results confirm our initial hypothesis of the interest of finding automatic mechanisms to identify near optimal roots. Aiming at that, we looked for a simple predictor. In particular we considered four options:

S(T, ·) Sd(T, ·) CD(T, ·) H(T, ·)
• Cluster Size: The size of cluster e ∈ V , noted S(T, e), is the number of variables that it contains S(T, e) = |C e |. It seems reasonable choosing as root r the node with the largest size S(T, r), because it means that the solving process will start with a large cluster of highly connected variables. This idea follows the well-known fail-fist principle which, in our context, means that the propagation effect of local consistency properties will become apparent as early as possible. In other words, selecting the node with the largest cluster represents a greedy way to produce good lower bounds quickly which in turn will produce good pruning. where ch(e) is implicit by the choice of r as the root. It seems reasonable choosing as root the node with the smallest decomposition because it is the root that breaks the problem into sub-problems whose largest one is minimal. In other words, the assignment of its variables produces the minimal largest sub-problem. Note that this measure also favors rooting with large clusters since a large root leaves less variables for the sub-problems • Cluster Height: The previous definition only considers the decomposition after the root assignment. It does not account for subsequent deeper decompositions.
To incorporate that we define the height of a tree decomposition rooted with r ∈ V as the size of the longest path starting from r. Formally, the height of root r is H(T, r) with, where ch(e) is implicit by the choice of r as the root. It seems reasonable choosing as root the node with the lowest height, min r H(T, r) because it means that backtracking will search on tree-structured assignments of minimum height (i.e, they will be the widest and most shallow). Table 3 reports, for each instance and its given tree-decomposition T , the correlation between cpu time and the four measurements: cluster size S(T, ·), domain-aware cluster size Sd(T, ·), cluster decomposition size CD(T, ·) and cluster height H(T, ·). In the autocorr and packupweighted instances some measurements did not change over roots, so correlation could not be computed. We were expecting to find negative correlations between cpu and (domain aware) cluster size, and positive correlations between cpu and decomposition and height. Some instances (e.g. hole10, geo, max-cut, cnf) behaved as we expected and the correlations were high, which means that our four measures predict the quality of the root. In some other instances (e.g. rus, parity,...) correlations are very low, so none of our measures do not capture the quality of the root. Surprisingly, in some other instances (e.g. graph, composed,...) correlations were high but with the sign opposed to our conjecture, so our measures worked totally counter intuitively. In summary, simple synctactic measurements of the tree decomposition do not seem to capture the quality of the clusters as roots.

Conclusions and Future Work
In this paper we report our preliminary results in the quest of identifying near optimal roots of tree decompositions to be used in decomposition-based backtracking algorithms for Graphical Models. We proposed 4 different simple criteria based on synctactical measures of the tree-decomposition.
We created a small benchmark selecting from two well-known repositories 19 highly diverse challenging instances. We performed a systematic experiment solving each in-stance with every root and checked for correlations. The first lesson to be extracted from the experiment is the confirmation of the impact of the root on the algorithm performance, which validates the importance of our work. The second lesson is about the significance of the proposed measures: i) none of them showed significant correlation with all the instances, and ii) some instances correlated as expected, but others correlated counter intuitively. Therefore, we conclude that although choosing the root is important, simple measures based on syntactical features of the tree decomposition do not seem to predict well good clusters. Accordingly, in our future work we will search for more informed data (e.g. taking into account cost functions) and more sophisticated techniques to combine it (e.g. machine learning).