Towards Robustness and Explainability of Automatic Algorithm Selection
Authors: Xingyu Wu
Jibin Wu
Yu Zhou
Liang Feng
KC Tan
Venue: ICML 2025 spotlightposter (2025)
Keywords: algorithm selection
algorithm feature
AutoML
causal learning
causality
directed acyclic graph
Primary area: general_machine_learning->everything_else
TL;DR: We introduce directed acyclic graph to describe the underlying mechanisms of the algorithm selection task, and propose a robust and explainable algorithm selection model.

Abstract: Algorithm selection aims to identify the optimal performing algorithm before execution. Existing techniques typically focus on the observed correlations between algorithm performance and meta-features. However, little research has explored the underlying mechanisms of algorithm selection, specifically what characteristics an algorithm must possess to effectively tackle problems with certain feature values. This gap not only limits the explainability but also makes existing models vulnerable to data bias and distribution shift. This paper introduces directed acyclic graph (DAG) to describe this mechanism, proposing a novel modeling paradigm that aligns more closely with the fundamental logic of algorithm selection. By leveraging DAG to characterize the algorithm feature distribution conditioned on problem features, our approach enhances robustness against marginal distribution changes and allows for finer-grained predictions through the reconstruction of optimal algorithm features, with the final decision relying on differences between reconstructed and rejected algorithm features. Furthermore, we demonstrate that, the learned DAG and the proposed counterfactual calculations offer our approach with both model-level and instance-level explainability.

Towards Robustness and Explainability of Automatic Algorithm Selection
Xingyu Wu Jibin Wu 12 Yu Zhou'
Liang Feng"
Kay Chen Tan'
Abstract
struggles to perform well across all scenarios (Tornede et al., 2023; Pio et al., 2024). The goal of automated algorithm selection is to identify the most suitable algorithm for each specific problem instance, thereby enhancing performance in terms of accuracy (Ruhkopf et al., 2023) and time effi- ciency (Kostovska et al., 2023). Early methods focused on identifying suitable meta-features to characterize problems, such as statistical characteristics (Hutter et al., 2014) and probing features (Nudelman al., 2004). These approaches employed machine learning techniques meta-learn which algorithm performs best for given problem instance (Ab- dulrahman et al., 2018). More recent studies have also recognized the importance of algorithm meta-features, such as hyperparameters (Tornede et al., 2020) and code-related features (Pulatov et al., 2022; Wu et al., 2024). Details of existing techniques are provided in Appendix A.1.
Algorithm selection aims to identify the optimal performing algorithm before execution. Exist- ing techniques typically focus on the observed correlations between algorithm performance and meta-features. However, little research has ex- plored the underlying mechanisms of algorithm selection, specifically what characteristics algo- rithm must possess to effectively tackle problems with certain feature values. This gap not only limits the explainability but also makes existing models vulnerable to data bias and distribution shift. This paper introduces directed acyclic graph (DAG) to describe this mechanism. proposing a novel modeling paradigm that aligns more elosely with the fundamental logic of algorithm selection. By leveraging DAG to characterize the algorithm feature distribution conditioned on problem fea- tures, our approach enhances robustness against marginal distribution changes and allows for finer- grained predictions through the reconstruction of optimal algorithm features, with the final deci- sion relying on differences between reconstructed and rejected algorithm features. Furthermore, we demonstrate that, the learned graph and the pro- posed counterfactual calculations offer our ap- proach with both model-level and instance-level explainability.
However, regardless of whether algorithm features are in- cluded in the meta-features, cxisting methods predominantly construct empirical models based on observed correlations between algorithm performance and meta-features (Ker- schke et al., 2019; Xu et al., 2008). These approaches over- look the underlying mechanism that drives the algorithm selection task, i.e.: What characteristics needs to solve a problem with specific feature values. By exploring this mechanism, we can align more closely with the foundational logic of algorithm selection, moving be- yond mere predictions of the optimal algorithm or algorithm performance based on meta-features This granular model- ing approach not only facilitates a more effective utilization of algorithm features but also allows for deeper insights into model decisions at the feature level, rather than solely from the perspective of performance comparison.
algorithm
1. Introduction
With the advancement of information technology, a multi- tude of algorithms has emerged across various fields, mak- ing automated algorithm selection increasingly vital. This necessity arises from the fact that single algorithm often
Moreover, the core of this mechanism lies in modeling the conditional distribution of algorithm features based on prob- lem features, rather than relying on the marginal distribution of meta- meeta-features for optimal algorithm prediction. This shift can address significant challenge in current techniques: their vulnerability to changes in marginal distribution. This issue is prevalent in all models during deployment, as the marginal distribution in algorithm selection is inherently dynamic (Van Rijn et al., 2014; 2018). As illustrated in Fig- ure (a)), ongoing technological advancements continuously create new application domains and candidate algorithms, leading to fluctuating strengths and weaknesses among them.
'Department Data Science and Artificial Intelligence, The Hong Kong Polytechnic University, Hong Kong SAR, China 2 *Department of Computing, The Hong Kong Polytechnic Uni- versity, Hong Kong SAR, China 'College of Computer Science, Chongqing University, Chongqing, China. Correspondence to: Jibin Wu jjbbin @ polyu.edu.hk...
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Towards Robustness and Explainability of Automatic Algorithm Selection
(a)
(c)
The popularity of different models applications over the past years
M L Level: How does model consider during the selection process?
100
80
Selection change
Algorithm
60
50
Algorithm
10
10
Necral Nerwork
Cregh Nevrol Nerwork
Maltilager Peroegroon
Problem Features
(b)
Dimension
Dimension
Training
Testing
Interventions on problem features
If certain problem features change, what changes will occu the model's 's decision decision-making! (i-zj
Instance Level:
Class Distribution
Figure 1. Illustration of impact of neglecting underlying mechanisms: (a) Shifts in the popularity classical algorithms over the past decade, highlighting data bias in algorithm selection tasks; (b) An example of problem distribution shift, where meta-training data are small-scale problems collected from uniform distribution, while the test problems are high-dimensional with imbalanced distribution: (c) Two levels of the lacking aaplainabiitt--unviiinn the decision-making mechanisms of the "black box" models, and providing counterfactual explanations for the selection outcomes.
Consequently, the meta-training data collected at any point may not accurately reflect the evolving distribution of prob- lems and algorithms. Furthermore, discrepancies between training and deployment environments are widespread (Wu al., 2024). For instance, as shown in Figure I(b), the meta- vetta-tainnng data may come from relatively small-scale, uniformly distributed problems, while the deployment en- vironment could involve high-dimensional and imbalanced problems. Additionally, meta-training data is often skewed towards mainstream algorithms, resulting in inadequate rep- resentation for kesser-known or newly proposed alternatives.
meta-training data, quantifying the strength of causality among variables. The reconstructed algorithm features can represent the feature values of the most suitable algorithm for solving a problem instance. Our framework ranks can- didate algorithms by comparing the reconstructed features of the selected algorithm with those of the rejected ones, leading to a final selection. During training, the model opti- mization is guided by combination of reconstruction error, acyclicity constraints, sparsity penalty, and ranking error.
Beside the performance superiority, causal modeling paradigm offers multi-level explainability for algorithm selection. First, the construction of the DAG visually il- lustrates the interdependencies among variables, while the structural equation model (Pearl, 2012) provides feature- level predictions for the "most suitable algorithm," clearly demonstrating the comprehensive mechanism underlying the model decision. Furthermore, counterfactual explana- tions (Guidotti, 2022) for each individual problem instance can be achieved by manipulating problem features within the structural equations, illustrated in Figure I(c). The goal of manipulation is to identify the minimal interventions required to alter the algorithm selection outcome for each problem instance, clarifying which feature values make the selected algorithm most suitable for solving this problem instance. Following the principle of Occam's Razor (Ras- mussen & Ghahramani, 2000), we measure the minimal intervention from the perspectives of explanation complex-
This paper introduces causality describe this underlying mechanism, taking significant step towards robustness and explainability. Herein, the causal relationships imply that: Because certain problem features are present, the most suitable algorithm must exhibit specific characteristics to effectively address the problem. Under reasonable assump- tions, we employ the structural equation model (Bongers al., 2021) to construct a directed acyclic graph (DAG) that captures the conditional distribution in the algorithm lection task. Hence, the identified variable relations remain robust against both covariate and label shifts (Bühlmann, 2020; Oberst et al., 2021), thereby mitigating the impact of changes in problem and algorithm distributions. Inspired by the gradient- based causal learning and recommendation (Zheng et al., 2018: He al., 2022), deep neural networks employed to identify the reconstruction mechanism in
2

---

Towards Robustness and Explainability of Automatic Algorithm Selection
ity and explanation strength, where complexity pertains to the number of modified features, while strength relates the magnitude of the changes induced by the intervention. By solving this optimization problem, we can ultimately derive the counterfactual explanations for each problem instance.
2.1. Analysis of Distribution in Algorithm Selection
This subsection explores the viability of employing causal models in the algorithm selection task. We will first analyze the alignment between two distinct modeling approaches within the context of algorithm selection. Subsequently, we present Theorem 2.4, which demonstrates that under specific assumptions, utilizing a structural causal model enables accurate modeling of the conditional probability distribution for each algorithm feature. Moreover, this causal framework facilitates the feasible prediction of the optimal algorithm feature given the problem features.
In this paper, we propose the DAG-based algorithm selection (DAG-AS)'. Our key contributions are summarized as:
Robustness: DAG-AS models the invariant causal mechanisms underlying algorithm selection process, which not only enables more accurate selection deci- sions, but also enhances robustness against common forms of data bias and distribution shifts that may exist across the problem and algorithm sets.
In the realm of algorithm selection, the most widely adopted strategy relies on problem feature- methods, where the distribution learned is denoted as [P()) (Kerschke et al., 2019), representing the mapping from problem feature space to candidate algorithm set. On the other hand, some studies have incorporated algorithm features into the selection pro- cess, typically learning the distribution P(A||F,,A (Pula- tov et al., 2022) or P(S|PF, AF) (Wu et al., 2024), where S is binary variable indicating whether the algorithm associ- ated with AF should be selected for the problem associated with PF. The relationship between (P = 1 ||FF, AF) and P(AF|PF, S = 1) can be described according to the Bayes'
Explainability: Centered around the learned graph, DAG-AS provides multi-level explainability. At the model level, it effectively unveils the "black box" by elucidating variable relationships through the causal graph and detailing the computational logic via struc- tural equations. At the instance level, DAG-AS achieves counterfactual explanations that reveal how specific feature values influence the selection decision.
We demonstrate the superiority of DAG-AS in terms of accuracy. robustness, and explainability using the ASlib benchmark. Our analysis of the causal graph underscored the importance of considering algorithm features and causal mechanisms.
Theorem:
P(S = 1/PP,AFF)((APP (I)
PA = 1)
1[F=
In the context of algorithm selection, P(AF(PF) repre- sents the likelihood of each algorithm being considered for each problem and is assumed to follow a uniform dis- tribution. P(S = 1PF is also a constant. Therefore, we can attempt to model [P S = 1) as substi- tute for P(S = 1|FF, AF). Although these two distribu- tions carry similar information, their dependency on the marginal distribution differs from a modeling perspective. P(S =|S=1/PF] AF) relies on the joint distribution PPF,, AF), where the model's input space includes both problem and algorithm features. Thus, both covariate and label shifts can impact the model's 's performance (Park et al., 2023). In contrast, P(AFIPF, S = 1) directly models the conditional distribution, aligning with the underlying mechanism advo- cated in this paper. As long as this underlying mechanism remains unchanged, the model can maintain resilience to variations in the marginal probability distributions (P(FF) or P(AF). To model IPAF PF, S 1). we first propose three assumptions for the DAG G in algorithm selection tasks:
2. DAG-based Algorithm Selection
We introduce the unified notation used in this paper to dis- cuss the causal relationships among these features within the framework of causal graphs (Pearl, 2016). We employ the calligraphic notation P represent the joint probability dis- tribution, and the script notation G {VV," E} to denote the DAG, where V and E represent the node set and edge set of G, respectively. The adjacency matrix of G is denoted as M where Mij- =1 1 indicates the existence of an edge from the i-th node to the j-th node, i.c., (i,j) E E, and otherwise. The definitions of all causal learning-relatee in this paper can be found in Appendix A.2. Algorithm selection task also involves different feature types. We use P and A to represent the problem set and algorithm set, respectively. The bold notations PF and AF are employed to denote the problem feature set and algorithm feature set, with V = PF AF. Specifically, (F)(p) represents the i-th feature of the p-th problem, and (a) represents the j-th feature of the a-th algorithm. Furthermore, when describing the model, we use W, and a; to denote the parameter matrix and activation function of the i-th layer, respectively.
terms involved
Assumption 2.1. There exists a DAG G = (V, E on V C PF U AF, and for any variable AF, E AF, the in-degree of AF; satisfies deg (AF,) > 0.
Assumption 2.2. For any variable AF, E AF, Ch(AF,) n
PF = Ø. Assumption 2.3. Informative algorithm features AF are available for the algorithm selection task.
The implementation of DAG-AS is available at https:// gi tuub. wwwpwwwwi/oooooottttottwwt.ww.ww ngyu-a a //DAG-AA AS.
3

---

Towards Robustness and Explainability of Automatic Algorithm Selection
The first assumptions are primarily constructed based the distinctive characteristics of the algorithm selection task, ensuring the directional flow of model computations and simplifying the model structure. Specifically, Assump- tion 2.1 guarantees that each algorithm feature is predictable, with no exogenous variables present. This because the prediction exogenous variables relies on external environ- mental factors, which are only influenced by noise terms in structural causal model. Reconstructing algorithm features based these noise terms would introduce uncertainties into the algorithm selection model. Assumption 2.2 primar- ily restricts the directionality of causal links within the DAG g, ensuring that the computations in the model flow from problem features to algorithm features. This alignment re- flects the core requirement of the algorithm selection, which to determine the most suitable algorithm based on the given problem features. The few ignored directed edges from algorithm features to problem features do not affect the performance of the proposed model, as we are not con- cerned with the reconstruction accuracy problem features. Assumption 2.3 implies that we can obtain algorithm-relater characteristics that carry meaningful information for differ- entiating the performance of different algorithms various problem instances. This assumption serves a fundamen- tal basis for DAG-AS. For specific details on how to obtain algorithm features, please refer to Appendix A.1.
model that learn the DAG and enable the prediction of the optimal algorithm features for given problem instance.
2.2. Model Framework of DAG-AS
Our proposed model builds upon a neural network frame- work that incorporates causal learning principles recon- struct features. The core of our model is the Causal Learn- ing Network, which aims to learn the causal dependencies between variables, including problem features PF and algo- rithm features AF. According to Definition in Appendix A, their joint probability distribution over the features can be factorized to |PF AF distinct conditional distributions, which then modeled by their parent variables and noise terms to account for observed and unobserved factors, re- spectively. Specifically, the generative process for the prob- lem feature PF, and algorithm feature AF can be described as:
PF; = ʃ: (PP(PF))) + 6 Pa(PF.) PF PF
(2)
AF AF; = 9s (Pa(AF,)) + 6 Pa(AF,) C PF PF (3)
where fç and 9i are nonlinear functions representing the causal mechanisms, and c and cx are noise terms captur- ing the unobserved variables. The noise terms assumed to follow Uniform distribution.
Problem Features
Best pessoperrommed Algorithm Features
Grounded in these assumptions, we present Theorem 2.4, which discusses the feasibility employing causal models solve the algorithm selection task.
Theorem 2.4. Assume that the joint density function of P(PF,AF is continuous and strictly positive on a compact and convex subset of R PPUA,, and zero elsewhere. And can Pa(V;) according to G. Under Assumption 1, any variable AF, E AF is not an exogenous variable in G, and there exists continu- ous function set {f1, f2. -JAP(} with compact sup- port in IR [F]][[011] such that each F(AF (P(FF))(). 1) equals the corresponding fs with uniform distributed noise on [0, 1].
there exists a DAG such that P(PF,A AFFS factorized as P(V) ev, (V; /
Causal Leaming Network
Read from the Network:
Ø
Causal Graph
Parameter Matrix
Proof. Please refer Appendix B.
Theorem 2.4 establishes that the underlying distribution can be modeled as DAG, then each algorithm feature can be associated with function that accurately captures its con- ditional probability distribution. Furthermore, this function serves as mapping from problem features to algorithm fea- tures. By modeling the causal relationships. the proposed model can learn the optimal feature values for the most proper algorithm given the problem features, which is the core premise of our approach. We now proceed construct
Reconstructed Problem Features and Algorithm Features
Figure 2. Causal learning module for algorithm selection.
As shown in Figure 2, the functions f and in Eq. (2) and Eq. (3) are denoted using the colors gold and blue, respectively. The input layer comprises nodes representing the features of problem and its best-performed algorithm.

---

Towards Robustness and Explainability of Automatic Algorithm Selection
To accurately capture the complex, nonlinear causal rela- tionships between the features, we employ multi-layer neural network. This network allows for the modeling of intricate dependencies that simpler models might miss. The 1-th layers, associated with weight matrices W and acti- vation functions o0),, transform the inputs through a series of nonlinear operations. The problem feature reconstruc- tion network (f) and the algorithm feature reconstruction network (g) are defined as follows:
where NN is the Similarity Computation Module used to calculate the similarity score, and [Ry;; RAF] denotes the concatenation of the problem and algorithm representations.
Inspired by (He et al., 2022), the loss function of our model comprises causal learning loss and algorithm selection loss. The causal learning loss includes three components: re- construction loss, sparsity loss, and acyclicity loss (Zheng et al., 2018). The reconstruction loss ensures that the re- constructed problem and algorithm features [PF, AF] are as close as possible to the original features [PF, AF]. This loss captures the fidelity of the causal learning module and ensures that the reconstructed features maintain the essential characteristics of the original features. Mathematically,
PF. = S(PF) f W/( L, (...of)) (...f"((W'IPFFF.
AF, g(PF,AF) +
Ereconstruction PF AFJ |P AFI]
(6) W(O L, OL, 1,-1 (....f) (W PF AF:
(1)
where - denotes the Frobenius norm. This term pe- nalizes the squared difference between the original and re- constructed features, encouraging the model to accurately capture the underlying relationships. By minimizing this loss, the model learns to generate algorithm features that are representative of the best algorithm for given problem. The sparsity loss encourages the adjacency matrix M of the DAG to be sparse. In a causal graph, sparsity is often desirable as it implies fewer direct dependencies between features, making the graph more interpretable and reducing the risk of overfitting. The sparsity loss is defined as:
where f.f and bg denotes the number of layers in the prob- lem and algorithm feature reconstruction networks, and [*] denotes the concatenation of problem features, algorithm features, and noise.
The adjacency matrix M of the DAG, which represents the causal structure among the features, is determined through the weight parameters of the first layer of the neural network. Specifically, the non-zero entries in the weight matrix W1 of the first layer indicate the presence of directed edges between nodes:
Espuriiyy = ||M llu
(10)
- {
if ( + 0, if ( =0
Mij -
(5)
where ||Milo denotes the number of non-zero elements in the adjacency matrix. To address the non-convex and non- differentiable nature of the lo norm, in practical deployment one can use the [|Ml] norm as an approximation. The acyclicity loss ensures that the learned adjacency matrix M represents a DAG, which is fundamental requirement for causal graphs. Acyclicity guarantees that there are no cyclic dependencies among the features, which is crucial for maintaining the logical consistency of causal learning and defined as:
where w(C), the i-the element of W/()), corresponding to the network parameter of j-th feature. This method ensures that the learned causal structure directly influences the pa- rameterization of the neural network, leading to a consistent and interpretable model of the underlying data.
Based on the causal learning module, AF represents the ideal feature values that the best-performing algorithm should have for a given problem. As shown in Figure 3, after obtaining the reconstructed algorithm features, AF and the original algorithm features AF are each passed through a multi-layer neural network to generate the problem and algorithm representation vectors,
Lacyciiity = (oM(MMMM IPFUAFI
(11)
where tr(-) denotes the trace of a matrix, and M O M is the Hadamard product (element-wise product) of the adjacency matrix with itself. The algorithm selection loss focuses on optimizing the ranking of algorithms for given problem. We employ the Bayesian Personalized Ranking loss (Rendle et al., 2009) defined as:
RpF hAP(AFF) <- Oi (...0 (WiAF)), (6)
RAF (AF( +- OA (...01 (W1AF)) (7)
Esetection
Σ (p.ot.a-)
Ino |s(Rer Rar(a=))
The similarity between the problem representation Rpp and the algorithm representation RAF is computed through an- other multi-layer neural network:
(12)
8 <Bpe(p), RaF(a ))]
where s(..)) is the similarity score between the problem rep- resentation Rpr (p) and the algorithm representation RAF(a),
8( (Rpr. RAF) = NNsim RRpr; RAF]);
5

---

Towards Robustness and Explainability of Automatic Algorithm Selection
Reconstructed Algonthm Features
Prokle Pressentatio
Causal Learning Module
Selected Algonthm
Algurilmr
Represenation
Figure 3. Framework of DAG-based algorithm selection.
at is the best-performing algorithm, a is one of the re- jected algorithm, and (-) is the sigmoid function. The BPR loss works by comparing the similarity scores of the best algorithm at and a randomly selected other algorithm am for the same problem By maximizing the difference in similarity scores in favor of at, the model learns to rank the best algorithm higher.
tentially be rectified by enhancing DAG-AS. In the field of causal learning, there are numerous specialized models crafted to handle complex causal relations, such as those dealing with multivariable or nonlinear causality (Wu et al., 2019; 2022). Moreover, there are studies centered on iden- tifying causality in scenarios where the causal sufficiency (Wu et al., 2023) assumption violated. To boost the perfor- mance of DAG-AS, more advanced causal learning models can be employed to substitute (6. and (7).
The overall loss function is the weighted average of the causal learning loss and algorithm selection loss:
C = Oi reconstrccii + Legursity + Lacyclicit + relelccio
3. Explainability of DAG-AS
(13) where a, B, 7, and å are byperparameters. In DAG-AS, the reconstruction of problem features optional. If the focus is solely algorithm selection results, it suffices to ensure the reconstruction of algorithm features. However, if more accurate global causal graph is required, the recon- struction of both types of features is essential. The learned DAG will be recorded as an intermediate result to generate explanations Section 3.1.
3.1. Model-Jevel Explanation
The model-level explainability is achieved through a de- tailed analysis of the DAG, which provides insights into how various problem features influence algorithm selection decisions, and enables workings and the rationale behind its algorithm choices. We can dissect this explainability into three key aspects: vi- sualizing relationships, assessing feature importance, and analyzing algorithm-specifie influences.
understand the model's inner
2.3. Discussion on Applicability of DAG-AS
Firstly, the learned graph allows for a visualization of the relationships within all features. In this context, the ad- jacency matrix M represents the directed edges between nodes, where M,j indicates directed edge from nodes to j. This matrix enables us to visualize how problem fea- tures PF and algorithm features AF are interconnected, Sec- ondly, the structure of the causal graph reveals the in-degree and out-degree each feature, which indicate their impor- tance the decision decision-making process. For example, problem features with zero out-degrees or algorithm features with in-degrees, be considered redundant irrelevant, demonstrating the feature selection capability inherent in the causal graph. Thirdly, the causal graph is closely related to the final performance of algorithm selection. By examining specific properties exhibited by the DAG, we can explain or estimate the predictive and generalization capabilities of models based on the graph. For instance, when certain causal relationships contradict established domain knowl-
Based on the introduction of the DAG-AS method, this sub- section aims to promptly discuss the applicable scenarios of DAG-AS. The key requirement for applying DAG-AS the availability of the general configuration for the AS task, encompassing problem features, algorithm features, and performance data. In datasets that possess rich set of informative features highly relevant to the algorithm's 's per- formance, DAG-AS is better positioned to capture the causal relationships. Nevertheless, like any method, DAG-AS has its weaknesses. believe that the following three scenar- ios may not be suitable for DAG-AS: (1) When the features themselves lack informativeness when the causality be- tween problem features and algorithm features is extremely weak. (2) When the data violates the causal sufficiency assumption. (3) When the causal relationships within the dataset are overly complex.
should noted, however, that cases (2) and (3) can po-
6

---

Towards Robustness and Explainability of Automatic Algorithm Selection
edge or when the causal graph fails adequately represent variable relationships, the model's performance may deteri- orate accordingly. Additionally, an excessively dense causal graph may negatively impact the model's ability to general- ize. In the experimental section, we will demonstrate how the causal graph aids us in achieving these explanations.
features, the optimal algorithm chosen by DAG-AS will change from algorithm to algorithm d'. The counterfac- tual explanation we derive is:
If the features of problem p are slightly decreased / increased by | then the most suitable algorithm will change from algorithm a to algorithm a'.
3.2. Instance-level Explanation
This subsection explores the counterfactual explainability of DAG-AS by leveraging interventions (Pearl, 2010) on input features, which allows us to understand the influence from problem features to algorithm features during the algorithm selection process. We introduce perturbations ópr prob- lem features. To formalize our approach, the Do-Calculus (Huang & Valtorta, 2006), denoted as do(-), is used to repre- sent interventions. The intervention on problem features can be represented as: PPS- =1 dP = p 5pF) AF), indi- cating the probability that AF is the optimal-performance algorithm features under the intervention do(PF = p 6pp), ). where p denotes the values of PF before intervention. The goal is to find the minimal perturbations ôpr that satisfy some interventional constraint denoted as hiPP(S = 1 PF, PF,AF),P(S = 1| (PF = + 6pF)), AF))
The fs in Eq. (14) is calculated based on a counterfactual computation procedure for DAG-AS model. Due to the nonlinear nature of the structural equations in DAG-AS, implemented through neural networks, we need to adjust the traditional steps accordingly, following three main steps: Abduction, Intervention, and Prediction (Pearl, 2010).
Given the observed evidence, i.e., the observed values of PF and AF, we first infer the values of the exogenous noise terms eF and c in the Abduction step. This step involves solving the neural network equations to find the noise terms that match the observed values, where the primary challenge is handling the nonlinear functions here. For complex mul- tilayer neural networks, deriving analytical solution is generally quite challenging. This is due to the fact that the nonlinear activation functions and the multilayer structure render the direct computation of the noise term a nonlinear optimization problem. As a consequence, we employ numer- ical methods, such as gradient descent, to iteratively solve for the solution here. The specific process can be found in Appendix C. After solving for all the exogenous vari- ables corresponding to a given problem, we will modify the DAG-AS model based on the intervention values ópp. For all the variables that are to be intervened, we will delete the incoming edges from their parent nodes in the causal graph, in accordance with the do-operator, and then directly assign values to these features. The modified model is denoted as fa- The intervention step alters the known causal graph and the underlying structural causal model, allowing us to make hypotheses about the model's 's behavior under manipulation. Finally, we can then solve for the counterfactual values of each variable in topological order. The results obtained at this stage represent the desired counterfactual outcomes.
This approach allows us to understand the causal effect of changes in problem features on the algorithm selection deci- sion. Given the DAG-AS model fPF,, AF), the distribution before and after intervention can be observed in the model output, i..., the previous output fPF, AF) and the coun- terfactual output fa f (PF + 6pF, AF). Afterwards, the interventional constraint can be represented as f(f,, f8). Our goal is to understand how minimal intervention in PF can lead to expected selection changes in h fo). This can be formulated as an optimization problem, where we minimize the perturbations subject a constraint on the change in the model's output as follows:
min 6ep
|| 12 + A11oprl1o
s.t.
3F E A, Va' A - {a),
S(FF, AF())) - [(F,, AF(a)) <E,
3o' E A {a),
(PF + +SpF ÖFF,AF AF(d')) - fs(PF + 8PF, AF(a)) > E.
3.3. Discussion on Explainability of DAG-AS
(14) Here, we minimize opr from two perspectives: the overall magnitude of the intervention and the number of manipu- lated variables, inspired by the principle of Occam's 'ss Razor. [|ópP||2 represents the fn-norm of the perturbations, indi- cating its magnitudes. The terms [|órиllo represents the fo-norm, indicating the number of intervened problem fea- tures. The parameter À balances the trade-off' between the magnitude and sparsity of the perturbations. The constraint hff. fa, E) in Eq. (14) states that there exists a candidate algorithm a', such that after intervening on the problem
By applying counterfactual interventions and solving the optimization problems, we can gain a comprehensive under- standing of the impact of problem features and the adapta- tion of algorithm features on the algorithm selection process in the DAG-AS model. This approach provides interpretable and actionable insights into the decision-making process, enabling us to identify key factors that influence the match- ing between problem features and algorithm features. It is important to note that although this paper does not in- vestigate interventions on algorithm features, this does not
7

---

Towards Robustness and Explainability of Automatic Algorithm Selection
imply that such interventions are without significance. Let denotes the values of AF before intervention. By exam- ining P(S = 1 PF, do(AF = + 8AP)), we can analyze how to adjust the optimal algorithms in the candidate set according to ÓAF given the characteristics PF of the prob- lem instance, ultimately leading to better solutions for the problem instance. Interventions on algorithm features hold practical significance for optimizing the algorithm beyond the candidate set.
tion) (Xu et al., 2011), SATzillall I (Xu al., 201 SNNAP (Collautti et al., 2013), and SUNNY (Amadini et al., 2014 2), alongside two baselines: the virtual best solver (VBS) and the single best solver (SBS), aiming to clarify their perfor- mance. Ideally, the performance of these methods should fall between those of SBS and VBS, with closer alignment to VBS indicating a more effective approach.
Performance Comparison (Detailed in Appendix D.2): In this experiment, each scenario was repeated 10 times for fair comparison, using 80% of instances for training and 20% for testing, with batch sizes of 1000 and 100, respectively. The results, as shown in Table 1, revealed that DAG-AS achieved the lowest PARIO 10 values in 8 out of 10 datasets, outperforming baseline algorithms and demonstrating ro- bustness across various tasks, particularly in 5 datasets like GRAPHS-201 and MAXSAT19-UCMS, This underscores the practical value of incorporating causality into algorithm selection. However, in datasets GLUHACK- 18 and SAT03- 16-INDU, DAG-AS lagged behind methods like MCC and SATzilla 1, attributed to the difficulty of capturing causal relationships with limited training samples, leading to better performance by traditional correlation-based methods.
On the other hand, we acknowledge that the explainabil- ity of our approach may not always be immediately in- tuitive. For instance, the algorithm features employed in ASlib are extracted from Abstract Syntax Tree, which are highly abstract and lack direct physical meaning. The util- ity of causal graph explanations and algorithm feature in- terventions hinges the semantic interpretability of the features themselves. Specifically, when algorithm features correspond to intuitive, human- compeeencm attributes, such as the architectural components (e.g., number of lay- ers, neuron counts) or hyperparameters (e.g., learning rate) of deep-learning models, the causal insights derived from DAG-AS become far more actionable. For example, if the causal graph identifies that certain problem features (e-g.- input dimensionality) directly influence the number of neu- rons in a specific layer of a neural network, this insight can guide users in tailoring model architectures to problem characteristics. Such interpretability not only enhances hu- man understanding of the algorithm selection process but also provides empirical guidance for optimizing candidate algorithms or debugging the DAG-AS model itself. This highlights the importance of feature semantics in unlocking the full potential of our causal framework for both explana- tion and algorithm design.
Ablation Study (Detailed in Appendix D.3): In this abla- tion study, we evaluated three variants of DAG-AS to assess the impact of the causal learning module and DAG design on model performance. The variants included: (1) Without Causality, where the causal module is removed, leading to direct matching of problem and algorithm features; (2) With Directed Cyclic Graph, retaining the causal module but al- lowing cycles in the graph; and (3) With Directed Acyelic Graph, the full version of DAG-AS with a constrained DAG structure. Using 10 datasets, results (shown in Figure 5 in Appendix D.3) indicate that the full DAG-AS variant con- sistently outperforms the others, especially on datasets like --NDU and SATI I-RAND, highlighting the DAG's critical role in capturing causal relationships and avoiding information loops. Conversely, the model without causality generally underperformed, particularly in datasets such as and MAXSATI1--UCS
4. Experiments
Benchmarks and Comparing Algorithms (Detailed in Appendix D.1): This study employs the ASlib (Algorithm Selection Library) benchmark (Bischl et al., 2016) to evalu- ate various algorithm selection methods, providing unified dataset with problem instances from multiple domains and their corresponding algorithm performance data. To validate DAG-AS's effectiveness, we test across all datasets that con- tain algorithm features, utilizing ten ASlbb datasets detailed in Table 2 in Appendix D. Notably, algorithm features for the BNSL-2016 dataset were extracted using large language model-based method (Wu et al., 2024). We mea- sure algorithm performance using the PARI0 score, which compares actual rumning times to predetermined cutoff time, assigning penalties for timeouts. A lower 10 score indicates more effective algorithm selection method. Ad- ditionally, we evaluate five established methods, including ISAC (Kadioglu et al., 2010), MCC (multi-class classifica-
confirming that the absence of causal inference limits understanding of com- plex tasks. An exception was observed in 11703-1-INNDU, where focusing on correlations yielded better results due to challenges in capturing causal structures.
GRAPHS-22
Robustness against Distribution Shift (Detailed in Ap- pendix D.4): In this experiment, we evaluated the robust- ness of DAG-AS against various distribution shifts and com- pared its performance degradation to the best benchmark methods. We implemented three types of shifts: (1) Shift on Problem Distribution, where certain problem features were assigned higher sampling weights during training; (2) Shift on Optimal Algorithm Distribution, which involved priori- tizing samples with optimal algorithms; and (3) Distribution
8

---

Towards Robustness and Explainability of Automatic Algorithm Selection
Table 1. Evaluation results ASlih benchmarks with algorithm features.
Scenario
VBS
SBS
ISAC
MCC
SATzillall
SNNAP
SUNNY
DAG-AS
BNSL
211.09
8849,64
(3.79_1.38xx00
(2.0010.766xx00*
(37.5713.46)x100
(3.8611.29)xx
(18111.57)xx00
GLUHACK- 18
906.39
17829.03
(15.56-14,40)x100
(8.10:44.1))000
(8.114.3911)x00'
(20.4414.58)x100
(15.534:3.74)x (10.51+:3.2)x1000 10 10
GRAPHS-200 2015
203
3.59 10"
(8.20=3.20)x10 10
(11.23=+379)x00'
(8.9043.18)x10 10
(64.32-446.9)xx10
10
(7.56+33.0))x 10"
(5.42+22.1)x 10"
MAXSATI9-UCMS
126.93
8991.26
(4.20=2.01)x000 10
(4,00=1.40)x0*
(3.77++1,55xx
10'
(9:43=1,44)x00
(2.15=1.04)x00 (3.37+111)xx00
-XT03-IG-INUU
823.02
5198.46
(4.73=0.84)x00
(4)47=0,63)x00*
(4.27:40.85xx00
(10
(4.46:0.78)xx00
(8.15=0.73)x
SATII-HAND
1789.23
13028.87
(12.1347.33xx10'
(9.50=3.28)x109
(7.5422.3)xx00
(11.4013 (29.5816600)x100
x1)
(4.69=22244x100*
BATII-INDU
1108.52
9704.52
(8.03-3.006)x00 10
(6.40_3.51)xx00
(6.7913.055xx00 10
(6.5413.61)x100 (15,2113.84)x10'
10
(..66_1.3)
SATH RAND
1248.49
9433.79
(9.02-3.13)x10 10
(5.22- (2.82-11.68xx000 10
x0
(35.07+3.66xx10 10
(2.21++.114x100
(1.89 : 1.06)x 10"
SATI8-EXP
1705.43
19445.73
(10.39+4.41)x 10a
(9.7++4.17xx00" 10
(8.9543.
16)x 10
(44.0943.00) 10
(8.1143.66)x 10
(8.07+1.49) 10
TSP-LION2015
44.63
189.65
(1.12=0.55x100
(2.67=044)x10)
(18444042)x100
(10.22+16
(0.78=0.16)x000
(0.48=0021)x00
Shift by Removing Algorithms, where some candidate al- gorithms were omitted from the training data. Using nine ASlib benchmarks with uniformly provided algorithm fea- tures, we analyzed performance loss for each method under these shifts, as illustrated in Figure 6. DAG-AS consistently outperformed other algorithms across all shifts, particularly excelling in optimal algorithm distribution shifts, demon- strating its ability to leverage algorithm feature information effectively. While it maintained a competitive edge in most datasets during problem distribution shifts, it showed slight underperformance on the SAT18- 18-EXP dataset. Neverthe- less, DAG-AS remained robust, especially when algorithms were removed during training, as its causal learning module helped mitigate the impact of missing candidates.
mization problem to determine minimal intervention values that can alter selection results, under constraints of a maxi- mum 20% feature intervention and a magnitude below 10%. The experiment identified 79 instances where the algorithm selection changed, with heatmaps Figure 10 showing total intervention magnitudes and specific feature interventions. For example, in Instance 1846, interventions on certain fea- tures shifted the selection from one candidate algorithm to another, highlighting the sensitivity of specific features to perturbations. Overall, only 1.36% of samples shifted selec- tions, indicating DAG-AS's ' robust decision- decision-making process. This analysis emphasizes DAG-AS's ability to provide inter- pretable insights and enhance transparency through causal graph-based reasoning.
Demonstration of Model-level Explainability (Detailed in Appendix D.5): In the algorithm selection scenario. de- riving a causal graph like Figure 8 that reflects the rela- tionships between problem and algorithm features enhances DAG-AS's accuracy and allows for meaningful causal in- terpretations. This study first analyzes feature importance in the causal graph by measuring the betweenness central- ity (Barrat et al., 2004) of features (as shown in Figure 7), revealing that algorithm features generally have higher centrality values, indicating their significance in algorithm selection. Next, we explore causal relationships among algorithm features (as shown in Figure 8), finding interde- pendencies that vary across datasets, which helps identify predictive features and improve performance. Additionally, we assess the influence of problem features on algorithm features (as shown in Figure 9), noting that datasets with denser causal relationships, like MAXSATI9-UCMM and SATI1- correlate with better DAG-AS performance. In contrast, sparser relationships in datasets like SAT03-16- INDU can lead to underperformance. However, in simpler datasets with ample training data, such as TSP-LION2015, DAG-AS can still excel despite sparse causal relationships, highlighting its ability to focus on critical influences.
5. Conclusion
In this study, we introduce a causal framework for algo- rithm selection, DAG-AS, which models the underlying mechanisms that determine algorithm suitability, addressing the limitations of existing methods. By focusing on the conditional relationships between problem and algorithm features, our approach enhances robustness against distribu- tion changes and explainability of selection decisions. We propose a counterfactual explanation method that identifies minimal interventions necessary to achieve changes in al- gorithm selection decisions. Experimental results on the ASlib benchmark demonstrate that our model outperforms traditional techniques in both robustness and explainabil- ity. Future work could further enhance the efficiency of coun- terfactual interpretability methods. Additionally, by manipu- lating algorithm features, the explanation methods proposed in this paper may help uncover unknown algorithms, thereby facilitating the design of improved algorithms.
Acknowledgements
This work was supported by the National Natural Sci- ence Foundation of China (Grant No U21A20512 12 and 62306259), Research Grants Council of the Hong Kong SAR (Grant No. C5052-23G, PolyU25216423, Po1yU15217424, PolyU15218622, PolyU15215623, and PolyU15229824), The Hong Kong Polytechnic University
Demonstration of Instance-level Explainability (Detailed in Appendix D.6): DAG-AS constructs a causal graph that facilitates counterfactual explanations through targeted in- terventions. A demonstration experiment on the GRAPHS- 2015 dataset illustrates this explainability by solving opti-
9

---

Towards Robustness and Explainability of Automatic Algorithm Selection
(Grant No. P0043563, P0046094, P0053699, P0052694, and P0053758), and Natural Science Foundation of Chongqing (Grant No. CSTB2222NSCQ-MSXIIS3
Collautti, M., Malitsky, Y., Mehta, D., and Oj Suullvan,, B. Snnap: Solver-based nearest neighbor for algorithm portfolios. In Machine Learning and Knowledge Discov- ery in Databases: European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part III 13, pp. 435-450. Springer, 2013.
Impact Statement
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Cunha, T., Soares, C., and de Carvalho, A. C. A label ranking approach for selecting rankings of collaborative filtering algorithms. In Proceedings of the 33rd Anmual ACM Symposium on Applied Computing, pp. 1393-1395, 2018.
References
Abdulrahman, S. M., Brazdil, P., van Rijn, J. N., and Van- schoren, J. Speeding up algorithm selection using average ranking and active testing by introducing runtime. Ma- chine learning, 107:79-108, 2018.
Dagan, I., Vainshtein, R., Katz, G., and Rokach, L. Auto- mated algorithm selection using meta-learning and pre- trained deep convolution neural networks. Information Fusion, 105:102210, 2024.
de Nobel, J., Wang, H., and Baeck, T. Explorative data analysis of time series based algorithm features of cma-es variants. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 510-518, 2021.
Alissa, M., Sim, K., and Hart, E. Automated algorithm selection: from feature-based feature-free approaches. Journal of Heuristics, 29(1):1-33 2023.
Amadini, R., Gabbrielli, M.. and Mauro, Sunny: a lazy portfolio approach for constraint solving. Theory and Practice of Logic Programming. 14(4-5):509-555 524,, 2014.
Fehring, L., Hanselle, J. M., and Tornede, A. Harris: Hybrid ranking and regression forests for algorithm selection. In NeurIPS 2022 Workshop on Meta-Learning (MetaLearn 2022), 2022.
Arena, S., Florian, E., Sgarbossa, F., Sølvsberg, E., and Zen- naro, I. A conceptual framework for machine learning algorithm selection for predictive maintenance. Engineer- ing Applications of Artificial Intelligence, 133: 133:108340, 2024.
Fusi, N., Sheth, R., and Elibol, M. Probabilistic matrix factorization for automated machine learning. Proceed- ings of the Advances Conference in Neural Information Processing Systems, 31, 2018.
Barrat, A., Barthelemy, M., Pastor-Satorras, R., and Vespig- nani, A. The architecture of complex weighted networks. Proceedings of the National Academy of Sciences, 101 (11):3747-3752, 2004.
Guidotti, R. Counterfactual explanations and how to find them: literature review and benchmarking. Data Mining and Knowledge Discovery, pp. 1-55, 2022.
Hanselle, J. Hybrid ranking and regression for algorithm se- lection. In German Conference on Artificial Intelligence, pp. 59-72. Springer, 2020.
Bischl, B., Kerschke, P., Kotthoff, L., Lindauer, M., Malit- sky, Y., Fr"lchette, A., Hoos, H. H., Hutter, Leyton- Brown, K., Tierney, K., and Vanschoren, ASlib: A Benchmark Library for Algorithm Selection. Artificial Intelligence, (237):41-58, 2016.
He, Y., Wang, Z., Cui, P., Zou, H., Zhang, Y., Cui, Q., and Jiang, Y. Causpref: Causal preference learning for out- of of-distribution recommendation. Proceedings of the ACM Web Conference, pp. 410-421, 2022.
Bongers, S., Forré, P., Peters, J., and Mooij, J. M. Founda- tions of structural causal models with cycles and latent variables. The Annals of Statistics, 2915, 2021.
Hilario, M., Kalousis, A., Nguyen, P., and Woznica, A. A data mining ontology for algorithm selection and meta- mining. In Proceedings of the ECML/KDD009 Workshop on 3rd generation Data Mining (SoKD-09), pp. 76-87. Citeseer, 2009.
Bühlmann, Invariance, causality and robustness. Statisti- cal Science, 35(3):404 426. 2020.
Chen, T., Shu, X., Zhou, H., Beckford, F. A., and Misir, M. Algorithm selection for -rotein-ligand docking: strate- gies and analysis on ace. Scientific Reports, 13(1) 2023.
Hough, P. D. and Williams, P. J. Modern machine learning for automatic optimization algorithm selection. Technical report, Sandia National LabL(SN--CA Livermore, CA (United States), 2006.
10

---

Towards Robustness and Explainability of Automatic Algorithm Selection
Huang, Y. and Valtorta, M. Identifiability in causal bayesian networks: sound and complete algorithm. In Proceed- ings of the st National Conference on Artificial Intelli- gence, pp. 1149-1154, 2006.
Park, S., Yang, S., Choo, J., and Yun, S. Label shift adapter for test-time adaptation under covariate and label shifts. In Proceedings of the IEEE/CVF International Confer- ence on Computer Vision. pp. 16421-16431, 2023.
Huerta, I. I., Neira, D. A., Ortega, D. A., Varas, V., Godoy, J., and Asin-Acha, R. Improving the state-of-the-art in the traveling salesman problem: An anytime automatic algorithm selection. Expert Systems with Applications, 187:115948, 2022.
Pearl, J. Causality. Cambridge university press, 2009.
Pearl, J. Causal inference in statistics: An overview. Statis-
tics Surveys, 3:96-146, 2010.
Pearl, J. The causal foundations of structural equation mod- eling. Handbook of structural equation modeling, pp. 68-91, 2012.
Hutter, F,, Xu, L., Hoos, H. H., and Leyton-Brown, K. Al- gorithm runtime prediction: Methods evaluation. Arti- ficial Intelligence, 206:79-111, 2014.
Pearl, J. Causal inference in statistic;: a primer. John Wiley & Sons, 2016.
Kadioglu, S., Malitsky, Y. Sellmann, M., and Tiemne, K. Isac-instance-speecfie algorithm configuration. In ECAI 2010, pp. 751-756. IOS Press, 2010.
Pihera, J. and Musliu, N. Application of machine learning to algorithm selection for tsp. In Proceedings of the 26th International Conference on Tools with Artificial Intelligence, pp. 47-54, IEEE, 2014.
Kerschke, P., Hoos, H. H., Neumann, F,, and Trautmann, H. Automated algorithm selection: Survey and perspectives. Evolutionary Computation, 27(1):3-45 45, 2019.
Pio, P. B., Rivolli, A., Carvalho, A. C. d., and Garcia, L. P. A review on preprocessing algorithm selection with meta- learning. Knowledge and Information Systems, 66(1): 1-28, 2024.
Kostovska, A., Jankovic, A., Vermetten, D., de Nobel, J., Wang, H., Eftimov, T., and Doerr, C. Per-run algorithm selection with warm-starting using trajectory-based fea- tures. In 17th Proceedings of Parallel Problem Solving from Nature- 2022, pp. 46 46-60, 2022.
Pulatov, D., Anastacio, M., Kotthoff, L.,, and Hoos, H. Open- ing the black box: Automated software analysis for al- gorithm selection. In Proceedings of the International Conference on Automated Machine Learning, pp. 6-1. PMLR, 2022.
Kostovska, A., Jankovic, A., Vermetten, D., Džeroski, S., Eftimov, T., and Doerr, C. Comparing algorithm selec- tion approaches black-box optimization problems. In Proceedings of the Companion Conference on Genetic and Evolutionary Compulation, pp. 495-498, 2023.
Rasmussen, C. E. and Ghahramani, Z. Occam's 's razor. In Proceedings of the 13th International Conference Neu- ral Information Processing Systems, pp. 276-282, 2000.
Luo, G. A review of automatic selection methods for ma-
chine learning algorithms and hyper-parameter values. Network Modeling Analysis in Health Informatics and Bioinformatics, 5:1-16, 2016.
Rendle, S., Freudenthaler, C., Gantner, Z., and Schmidt- Thieme, L. Bpr: Bayesian personalized ranking from implicit feedback. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, pp- 452-461 2009.
Misir, M. and Sebag, M. Alors: An algorithm recommender system. Artificial Intelligence, 244:291-314, 2017.
Nudelman, E., Leyton-Brown, K., Hoos, H. H., Devkar, A., and Shoham, Y. Understanding random sat: Beyond the couues-to-vvriablle ratio. In Principles and Practice of Constraint Programming-CG CP 2004: 10th International Conference, CP 2004, Toronto, Canada, September 27- October 1, 2004. Proceedings 10, pp. 438-452. Springer, 2004.
Rice, R. The algorithm selection problem. In Advances in Computers, volume 15, pp. 658118. Elsevier, 1976.
Richter, C., Hüllermeier, E., Jakobs, M.-C., and Wehrheim, H. Algorithm selection for software validation based on graph kernels. Automated Software Engineering. 27(1): 183-186, 2020.
Oberst, M., Thams, N., Peters, J., and Sontag, D. Regu- larizing towards causal invariance: Linear models with proxies. In Proceedings of the 38th International Con- ference on Machine Learning, pp. 8260-827 8270. PMLR, 2021.
Ruhkopf, T., Mohan, A., Deng, D., Tornede, A., Hutter, F., and Lindauer, M. Masif: Meta-learned algorithm selection using implicit fidelity information. Transactions on Machine Learning Research, 2023.

---

Towards Robustness and Explainability of Automatic Algorithm Selection
Seiler, M. V., Kerschke, P., and Trautmann, H. Deep- ela: Deep exploratory landscape analysis with self- supervised pretrained transformers for single-and multi- objective continuous optimization problems. arXiv preprint urXiv:2401.01192 2024.
Zhao, K., Liu, S., Yu, X., and Rong. Y. Towards feature- free tsp solver selection: A deep learning approach. In 2021 International Joint Conference Neural Networks (IJCNN), pp. 1-8. IEEE, 2021.
Zheng, X., Aragam, B., Ravikumar, P., and Xing, E. P.
Tornede, A., Wever, M., and Hüllermeier, E. Extreme al- gorithm selection with dyadic feature representation. In Proceedings of the International Conference on Discov- ery Science, pp. 309-324. Springer, 2020.
Dags with tears: continuous optimization for structure learning, In Proceedings of the 32nd International Con- ference on Neural Information Processing Systems, PP- 9492-9503, 2018
Tornede, A., Gehring, L., Tornede, T., Wever, M., and Hüllermeier, E. Algorithm selection on a meta level. Machine Learning, 112(4)12533-128) 2023.
Van Rijn, J. N., Holmes, G., Pfahringer, B., and Vanschoren, Algorithm selection on data streams. In Proceedings of the 17th International Conference Discovery Science, Springer, 2014.
pp.
Van Rijn, J. N., Holmes, G., Pfahringer, B., and Vanschoren, J. The online performance estimation framework: het- erogeneous ensemble learning for data streams. Machine Learning, 107:149-1766 176, 2018.
Wu, X., Jiang, B., Yu, K., Chen, H., et al. Accurate markov boundary discovery for causal feature selection. IEEE Transactions on Cybernetics, 50(12):4983 4996, 2019.
Wu, X., Jiang, B., Zhong, Y., and Chen, H. Multi-target markov boundary discovery: Theory, algorithm, and ap- plication. IEEK Transactions Pattern Analysis and Machine Intelligence, 45(4):4964-44 4980, 2022.
Wu, X., Jiang, B., Wu, T., and Chen, H. Practical markov boundary learning without strong assumptions. In Pro- ceedings of the AAAI Conference on Artificial Intelli- gence, pp. 10388-10398, 2023.
Wu, X., Zhong, Y., Wu, J.. Jiang, B.. and Tan, K. C. Large language model-enhanced algorithm selection: Towards comprehensive algorithm representation. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence, pp. 1-9, 2024.
Xu, L., Hutter, F., Hoos, H. H., and Leyton- Brown, K. Satzilla: portfolio-based algorithm selection for sat. Jour- nal of Artificial Intelligence Research, 32:565-606, 2008.
Xu, L., Hutter, F., Hoos, H. H., and Leyton-Brown. K. Hydra-min mit:: Automated algorithm configuration and lection for mixed integer programming. In RCRA work- shop on experimental evaluation of algorithms for solving problems with combinatorial explosion at the interna- tional joint conference on artificial intelligence (IJCAI), pp. 16-30, 2011.
12

---

Towards Robustness and Explainability of Automatic Algorithm Selection
A. Background
A.1. Background of Algorithm Selection
With the rapid advancement and widespread adoption of information technology, researchers in various fields have designed a range of algorithms tailored to specific types of problems, each showing different levels of performance across various instances of those problems. Due to the diversity of problems, a single algorithm often fails to perform well across all scenarios (Pihera & Musliu, 2014; Xu et al., 2011). However, selecting the best algorithm for a specifie problem instance is complex and time-consuming process. To meet this challenge, research in algorithm selection (Rice, 1976) has become increasingly important. The primary goal is to identify the most suitable algorithm from a pool of candidates, ultimately enhancing performance on specific tasks, whether in terms of accuracy (Ruhkopf et al., 2023) and time efficiency (Kostovska et al., 2023). In recent years, algorithm selection methods have become essential for tackling complex problems and driving technological advancements, with applications across various fields, such as machine learning (Luo, 2016) and combinatorial optimization (Pihera & Musliu, 2014).
Early algorithm selection methods sought suitable meta-features to characterize given task, such as the statistical characteristics of the input dataset (Hutter et al., 2014) probing features derived from the short execution of well-known solver (Nudelman et al., 2004). By exploring the relationship between these meta-features and the performance of different algorithms, machine learning techniques were employed to meta-learn which algorithm performs best on new problem instances. These methods often formulate the algorithm selection task as either a performance regression or a multi-class classification problem. Specifically, regression-
techniques (Xu et al., 2008) directly predict the performance of each algorithm based on the problem feature set. Conversely, multi-class classification approaches (Cunha et al., 2018; Abdulrahman et al., 2018) assign scores to algorithms based their relative suitability for specific problem and select the most appropriate algorithm based on these scores. In addition, several other methodologies have been proposed. For instance, some studies formalize algorithm selection as a collaborative filtering problem (Misir & Sebag, 2017; Fusi et al., 2018) and utilize a sparse matrix with performance data available for only a few algorithms on each problem instance. And similarity-basa -based methods (Amadini et al., 2014; Kadioglu et al., 2010) select algorithms based on the similarity between the current problem instance and previously encountered instances. There are also some hybrid methods (Hanselle, 2020; Fehring al., 2022) combine multiple techniques above.
On the other hand, some studies (Hough & Williams, 2006; Tornede et al., 2020; Hilario et al., 2009; Pulatov et al., 2022; de Nobel et al., 2021; Wu et al., 2024) have recognized the role of algorithm meta-features, such as hyperparameters (Hough & Williams, 2006; Tornede et al., 2020), model structure information (Hilario et al., 2009), code-related statistical features (Pulatov et al., 2022), abstract syntax tree features (Pulatov et al., 2022), and and large language model-extracted code features (Wu et al., 2024). Empirical studies (Pulatov et al., 2022; Wu et al., 2024) indicate that utilizing algorithm meta-features can enhance a model's generalization across different algorithms and, in certain cases, improve the accuracy of algorithm selection. Models based on algorithm features typically concatenate problem features and algorithm features and employ machine learning algorithms to either regress algorithm performance, predict the most suitable algorithm, or calculate the matching degree between problem features and algorithm features to make compatibility decisions.
In recent years, research on algorithm selection has focused on various domains, including black box optimization problems (Kostovska et al., 2022; Huerta et al., 2022), natural science issues (Chen et al., 2023), software engineering (Richter et al., 2020), and machine learning (Arena et al., 2024; Dagan et al., 2024). Some studies have also explored feature-free approaches (Alissa et al.. 2023), which are mainly applied to specific senoritas, such as traveling salesman problem (Zhao et al., 2021) and continuous optimization problem (Seiler et al., 2024).
A.2. Background of Causal Learning
In this subsection, we introduce the fundamental concepts of causal learning, which are essential for understanding the algorithm selection method based on causality. Causal relationships describe the cause-effect connections between two events, reflecting the internal mechanisms and rules within system. A Causal Bayesian Network (CBN) is framework that uses a directed acyclic graph (DAG) to explain causal relationships. Its definition is as follows:
Definition A.1. Causal Bayesian Network (CBN (Pearl, 2009)). A Causal Bayesian Network is a directed acyelic graph g = {V.E} where nodes represent random variables in the set V, and edges in the set E represent causal relationships between these variables. Each node V; E V associated with conditional probability distribution given its parents Pa
13

---

Towards Robustness and Explainability of Automatic Algorithm Selection
in the graph. The joint probability distribution P over V can be factorized
P(()= = II
P(V. Pa(V)))
(15)
Viev
Random Control Trial is an experimental method for causal inference, regarded as the gold standard for inferring causality, but it is not applicable to the observational data our scenario. To infer causality from observational data, researchers have developed data-driven causal inference models called Structural Causal Models (SCMs). SCMs represent causal relationships through causal graphs (DAGs) and structural equations. The causal graph is graphical qualitative representation of causal relationships, while the structural equations quantitatively represent these relationships.
Definition A.2. Structural Causal Model (SCM (Pearl, 2012)). A Structural Causal Model (SCM) consists of set of structural equations and causal graph G that represents the dependencies between variables. Each structural equation specifies how a particular variable generated by its parent variables and an error term that captures all unobserved influences. Formally, an SCM for can be expressed as:
V; = UP). VV
(16)
where Vi is variable, Pa(V)) are the parents of V; in the causal graph, and Us E l is exogenous error term.
SCMs represent causal relationships among complex multidimensional variables. The variables in V and U are called endogenous and exogenous variables, respectively. Exogenous variables belong the external environment of the model and appear as noise terms, representing influences on endogenous variables that are not influenced by them. Each endogenous variable is a descendant of at least one exogenous variable, so the root nodes in the causal graph over V in SCM have only one parent variable, which is an exogenous variable.
The graphical model and structural equations enable SCMs to conveniently compute causal effects and counterfactual queries from observational data. Pearl developed a comprehensive theory and methods by combining SCMs with do-calculus:
Definition A.3. Causal Effect and Intervention. (Pearl, 2009) The intervention do(T=t) denotes setting the value of variable 7 to i, denoted do(t). The causal effect of variable T on variable Y is a probability distribution function from T to Y, represented using the do operator as P(Y
do(T = t)), abbreviated as Pyy do(()).
In SCMs, interventions are represented by modifying the structural equations. The intervention do(T () replaces the equation 7' = fr((P((T) U,) with T = t in the SCM, and T = is substituted in the remaining equations. This demonstrates the modular nature of causal models, where each function equation represents an independent causal mechanism. The intervention do(T- = t) changes only the assignment function containing T, leaving the assignment functions of other variables unchanged.
Definition A.4. Counterfactuals. (Pearl, 2009) Let and Y be two variables in V. The counterfactual statement "if = I, then Y would be y given U u" represented as Yr=((w) (w) = y. where Yr=((u) is the potential outcome of Y given T t under the specific context U u.
In any SCM, if the counterfactual assumption is T the modified model is denoted SCM,. The counterfactual value (u) in the model SCM is defined as the value of Y obtained in the new model SCM, when T = t:
(u) = YsCM, (u)
(17)
This definition holds even if T and are sets of variables rather than individual variables. In the modified model SCM,, the values of the variables should satisfy the new model's specifications.
Understanding these fundamental concepts is crucial for developing and implementing algorithms that leverage causal knowledge. The formal definitions and mathematical frameworks provide the basis for more advanced applications in causal learning-based algorithm selection.
B. Proof of Theorem 2.4
Theorem B.1. Assume that the joint density function PPF (FF,FF)) is continuous and strictly positive on a compact and convex subset of PPUPU and zero elsewhere. And there exists a DAG 9 such that (PPF (.F,F = 1) can be factorized as Eq.
14

---

Towards Robustness and Explainability of Automatic Algorithm Selection
(15) according G. Under Assumption 2.1, any variable AF, E AF is not an exogenous variable in G, and there exists a continuous function set f J2, ... :..===aaa]]] : with compact support in R. x(0.1) such that each (PAFF; (.LFFF) 1) equals the corresponding fi with uniform distributed noise [0, 1].
Proof. Since the in-degree of any FF, satisfies d ( > 0, i.e., [Pa(AF,) 2 1, we can easily prove that there exists AF; E AF such that its parent set is completely composed of problem features, i.e. Pa(AF,) C PF. Assume that for all AF, E AF, Pa(A Pa(AF,) g PF. This means that for every AF,, there exists at least one algorithm feature X, such that X, Pa(AFi) and X5 E PF. We can then construct causal chain XN feature and X; E Pa( (,,)). However, due the acyclicity requirement, no variable can be its own ancestor or descendant. Therefore, when N > |AF), there will be no new algorithm features to satisfy deg (Xx) > 0, which contradicts the assumption that the in-degree of any AF, is positive. Therefore, we can conclude that EAF; s.t. Pa(AF,) S PF.
X2 + X1, where each X; is an algorithm
Let us divide the nodes in 9 into two sets, A and B, where A is initialized as PF and B is initialized as AF. Next, we find the first node AF, in such that Pa (AF,) C A, and perform the following operations:
A + AUAF, B s B AF,
(18)
We then repeat this process to find the next AF, in B such that Pa(AF,) E A, and so on. This gives us a topologial Along this topological ordering (AF (AFs(1)= AF (2)....., ((AF))))) we will now use mathematical induction to prove as follows:
ordering क. AF + 21,2..... AF)).
For AF x(1), we can construct function to describe the corresponding decomposed distribution: P(AF x(1) Pa(AF R
1). Consider the conditional cumulative distribution function:
Fi (AF (1) (a(AF (1)) = 21, S = 1) = P(AF (L)) < < Pa(AF x(1)) =
(19)
where n2 and 2 are arguments of the function F;, denoting the value of AF ( and (a(AF Since the joint density function is strictly positive, F; is strictly continues and monotonic wrt xT. Therefore, its inverse, the quantile function FT (Pa(AF e) e):
dom x()))) x [0. 1]. where represents the noise term in the causal model and dom(') (+) denotes the domain of the corresponding variable, satisfies the properties in Theorem 1.
Assume that for AF (1)11) we can find a function that satisfies Theorem 1. We now prove the case for AF AFx()): Take the conditional cumulative distribution function F:(AF (+) (A(FF(()) = 21, S = 1) and its inverse FT 1 (Pa(AF (()))))))) (AFF x [o. 1]. By the topological ordering rule, all of the parent nodes of x are included in A. There- fore, AT (P((AFx())
F. '(F,, );=,))) Since F71 (j E i 1)) can be found to satisfy Theorem 1,
F ((F) })=l,e) e) also satisfies the properties in Theorem 1. (Q.E.D))
C. Calculate the Exogenous Variables for Counterfactual Explainability
Given the observed evidence, i.e., the observed values of PF and AF, we first infer the values of the exogenous noise terms d and cAP in the Abduction step. This step involves solving the neural network equations to find the noise terms that match the observed values, where the primary challenge is handling the nonlinear functions here. For complex multilayer neural networks, deriving an analytical solution is generally quite challenging. This is due to the fact that the nonlinear activation functions and the multilayer structure render the direct computation of the noise term a nonlinear optimization problem. As a consequence, we employ numerical methods, such as gradient descent, to iteratively solve for the solution here. For the noise term ? of the problem feature PF; we need to solve for the gradient Ve,F in order iteratively compute the value of e.H with rate 77, i.e., the (t + 1)-th iteration is given by: P (t + 1) PF (t) r/Ve,"" Since the loss function for the prediction of PF, can be represented as:
1 Lrp
PF, - -PF,11
(20)
2
the gradient Ve.F PF can be expressed as:
0CPF PF
PCrF
V
PF
(21)
OPF; PF
PF +1
15

---

Towards Robustness and Explainabilityy of Automatic Algorithm Selection
where PF| 1 denotes the focused dimension of 0Cpr PR; PF]. Let 2 denotes the input the activation function the 1-th layer, then
rf OPF: e = W(O)" dCrr 0z(1)²
(22)
where the value of dCr could be obtained by the following recurrence relation: (x
PLrF
(PF, PF.))oLL (2))))
Üz
(23)
dCrF @z())
(W(++)) dCpF
3 wll (z())
dz(+1)
For the noise term AF of the algorithm feature AF,, we need to replace the LpF with LAP 211AF, - -A', 1 and the gradient V can expressed as:
ŌLAF DeA
AL O|PF AF eAF)
AF
(24)
|PPAAF|-1
In addition to the numerical methods mentioned above, we also provide the analytical solution for a single-layer linear network, which can be used for the rapid computation of the noise term in the context of linear modeling:
PF PF
W W .F WTW,
(25)
W AF
W W - AF
W Wa
where Wa denotes the d-th column of the unique parameter matrix W in the network, and W -d represents the matrix W with the d-th dimension removed. After solving for all the exogenous variables corresponding given problem, we will modify the DAG-AS model based the provided intervention information.
D. Detailed Experiments
In this section, we evaluate the performance of our proposed DAG-AS algorithm across multiple benchmark datasets from ASlib library. The experimental analysis designed to comprehensively assess the effectiveness of DAG-AS in various aspects, including its overall performance, robustness, and explainability. We conduct five major types of experiments to ensure thorough evaluation: We first perform performance comparison to benchmark DAG-AS against five classic algorithm selection methods across ten datasets in Section D.2. Then, an ablation study is carried out in Section D.3 to examine the impact of causal structures the performance of DAG-AS, comparing results with and without the inclusion of causal graphs (both directed and undirected). We investigate the generalization ability of DAG-AS in Section D.4 by evaluating its performance under different types of distribution shifts. Finally, a causal graph analysis conducted to delve into the causal relationships identified by DAG-AS for each dataset in Section D.5, and the explainability of DAG-AS showcased by demonstrating its ability to generate counterfactual explanations using the GRAPHS-201 dataset in Section D.6. Through these experiments, aim to demonstrate only the superior performance of DAG-AS but also its robustness and explainability in the field of algorithm selection.
D.I. ASlib Benchmarks and Comparing Algorithms
The ASlib (Algorithm Selection Library) benchmark (Bischl et al., 2016) is standardized dataset designed to provide unified benchmark for evaluating and comparing the performance of various algorithm selection methods. As one of the most widely used benchmarks in the field of algorithm selection, ASlib encompasses problem instances from diverse domains along with their corresponding algorithm performance data. Each problem instance is described by set of features that reflect the properties and constraints of the problem, with some datasets also including algorithm features. Given that this paper aims to uncover the causal relationships between problem features and algorithm features, we validate the effectiveness of DAG-AS by testing across all available datasets with algorithm features. The ten
Evaluation Benchmarks:
16

---

Towards Robustness and Explainability of Automatic Algorithm Selection
ASlib datasets cover a range of domains and scales, with statistical information presented in Table 2. Notably, the algorithm features for the BNSL-2016 dataset not provided by ASlib; instead, they were extracted from the code of candidate algorithms using the large language model-based feature extraction method proposed in (Wu et al., 2024).
Table The statistical property of experimental benchmarks.
ASlib Scenario
[
A
PF
AF
Cutoff Time
BNSL-2016
1179
8
86
75
7200
GLUHACK-18
353
8
50
75
5000
GRAPHS-2015
5725
4
35
75
100000000
MAXSATI9-UCMS
572
7
54
75
1800
SATO0316-INDDU
2000
8
483
75
5000
SATI1-HAND
296
11
115
75
5000
SATII-INDU
300
18
115
75
5000
SATI1-RAND
600
8
115
75
5000
SAT18-EXP
353
37
50
75
5000
TSP-LION2015
31060
4
122
75
3600
The involved scenarios in this paper focus the solution time of candidate algorithms, and therefore, the PAR10 score to measure the performance of different algorithms. Specifically, the PARIO for instance p is calculated follows:
PAR 1OR) = lp 4p <C
(26)
10.C else
For each problem instance p. the actual running time tp of the selected algorithm is compared to predetermined cutoff time C, as provided in Table 2. If the selected algorithm finds a solution within the cutoff time, the actual running time recorded; otherwise, a penalty of ten times the cutoff time, 10- C, is incurred. Finally, the PARIO score is obtained by averaging the results across all problem instances. The PARIO 10 score takes into account both the solution time and timeout situations, with lower PARIO score indicating more effective algorithm selection method.
Comparing Algorithms: This study evaluates five established algorithm selection methods: ISAC (Kadioglu et al., 2010), MCC (multi-class classification) (Xu et al., 201 1), SATzillal1 (Xu et al., 201 I), SNNAP (Collautti et al., 2013), and SUNNY (Amadini et al., 2014). In addition to these methods, we also compare two key performance benchmarks: the virtual best solver (VBS) and the single best solver (SBS). VBS represents the optimal approach, as it selects the best algorithm for each specific problem instance. In contrast, SBS is a straightforward method that picks the algorithm with the best overall performance without differentiating between instances. By evaluating the algorithm selection methods against SBS and VBS, can gain a clearer understanding of their performance. Ideally, the performance of these methods should fall between those of SBS and VBS, with closer alignment to VBS indicating more effective approach.
D.2. Performance Comparison
In this experiment, we employed multiple ASlib benchmark datasets to evaluate the performance of DAG-AS algorithm selection tasks. To ensure fair comparison between the proposed DAG-AS and existing classical methods, each algorithm selection scenario was repeated 10 times. The training set consisted of 80% of the samples randomly selected from the dataset. The batch sizes for training and testing were set to 1000 and 100, respectively. Both problem features and algorithm features were fed into the model, and the final performance was compared based on the PAR10 scores of the different models, as shown in Table 3.
By analyzing the overall results, we found that DAG-AS achieved the best performance in out of the 10 datasets, obtaining the lowest PARIO values. This indicates that DAG-AS outperformed other baseline algorithms in most tasks, demonstrating strong robustness and wide applicability to different types of algorithm selection problems. In particular, DAG-AS significantly outperformed other methods in datasets such as GRAPHS-2015, MAXSAT19-UCMS, SATI1-HAND, SATII- and TSP-LION2015. This strongly highlights the practical value of incorporating causality into algorithm selection. By leveraging a causal graph structure, DAG-AS enhances the model's 's understanding of complex problems and decision- makiing capabilities, effectively utilizing the causal relationships between problem features and algorithm features to improve the accuracy of algorithm selection.
17

---

Towards Robustness and Explainability of Automatic Algorithm Selection
Table
Evaluation results ASlih benchmarks with algorithm features.
Scenario
VBS
SBS
ISAC
MCC
SATzillall
SNNAP
SUNNY
DAG-AS
2N1L
211.09
8849.64
(6.32-1.22)100
(3.79
(2.0010.76)x100
(37.37.1.446)
(3.8611.29)x
(18111.57)x00'
GLUHACK- 18
906.39
17829.03
(15.56-14,40)x100
(8.10:44.19)x00
(8.114.3.11)x00*
(20.4414.58)x100
(15.534:3.74)x (10.51+..92)x100 10
GRAPHS-200 2015
203
3.59 10"
(8.20=3.20)x10 10"
(11.23=+379)x000
(8.9043.18)-- 18) 10
(64.32-446.91xx11)
10
(7.56+3.50)xx 10"
(5.42+2..3)x 10"
MAXSATI9-UCMS
126.93
8991.26
(4.20=2.01)x000 10
(4.00=1.40)x
(3.77++1335xx 10
(9:43=1.44)x00
(2.15=1.04)x (3.37=119))x0
1IT03-6-INNUU
823.02
5198.46
(4.73=0.84)x00
(4:47=0,63)x00*
(4.27:40.88)x00
(10
(4.46:0.78)x10)
(8.15=0.73)x
SATII-HAND
1789.23
13028.87
(12.1347.33xx00'
(9.50=3.28)x100
(7.5442.39)x10*
(11.4013 (29.5816.08)x10
80)
(4.69:2..4)x102)
SATI1-INDS INDI
1108.52
9704.52
(8.03=3.06)x100'
(6.40.3.51))x000
(6.7913.055)x00 10
(15,2113.849x100
(6.5413.61)x1000 10
L.36_1133)
SATH RAND
1248.49
9433.79
(9.02-3.13)x 10
(2.82+1.688x10 10
(.85)xx
(35.0743.66)
10
(2.21+
(1.89 : 1.06)x 10"
SATI8-EXP
1705
11945.73
(10.3944.44)x 10a
(9.76+4.17)x100 10
(8.9543.
16)x 10
(44.0943.00x 102
(8.1143.655x 10
(8.07 109
TSP-LION2015
44.63
189.65
(1.12=0.35xx00
42,67=0.4))100*
(188440.42)x100
110
(0.78#0.16)x00*
(0.48=0021)x000
Hyperparameter Analysis and
4500
Hygerpuramtter Audlysi
5400
66000
4000
4007
3500
PARIO
PARUIO
8000
3000
3000
2000
0.5
0.75
1030
2,00
8
(10')
2000
0.6
Figure Hyperparameter analysis on SATII-INDU.
At the same time, we also observed that in some datasets, such GLUHACK-JS 18 and SATO3-16-INDU, DAG-AS did not perform as well as other methods, with MCC and SATzillall I achieving the best performance, respectively. The main reason is that causal relationships between problem features and algorithm features in these two datasets are more difficult to capture. With a limited number of training samples, DAG-AS was unable to sufficiently learn the patterns associated with these causal relationships. Instead, the correlations exhibited the data were more easily captured, which led to DAG-AS underperforming compared to traditional correlation- based methods on these datasets.
Hyperparameterr analysis: We conducted hyperparameter analysis the SAT11-INDU dataset to investigate the impact of the three hyperparameters in (15) on the performance of DAG-AS. In the first experiment, we analyzed the balance between the reconstruction loss and the two causal learning constraints by varying and 3, while fixing 1. The second experiment focused on the balance between the causal learning loss and the algorithm selection loss by adjusting with 3 = and a = 0.0001 kept constant. Results are shown in Figure 4. From the left-hand figure, the color-coded visualization (cooler colors indicating lower PARIO scores) reveals a range of a and 3 values where DAG-AS sustains good performance. For the right-hand figure, as y changes, the PARIO score does not exhibit extreme fluctuations, indicating DAG-AS is not overly sensitive to y within the tested range. Notably, when 7 is around 1.4-2.2, the PARIO score attains relatively low values, showcasing excellent performance. Overall, these results demonstrate that DAG-AS maintains relatively good performance across broad spectrum of these hyperparameters, underscoring the model's 's robustness. This robustness is vital as it minimizes reliance on meticulous hyperparameter tuning, enhancing DAG-AS's adaptability to diverse problem scenarios.
D.3. Ablation Study
In this ablation study, we compare three variants of DAG-AS to further validate the impact of the causal learning module and the DAG design on model performance. The three model variants compared in the experiment are as follows: (1) Without Causality: The causal learning module is removed, and algorithm selection is performed directly based on matching problem features and algorithm features. (2) With Directed Cyclic Graph: The causal learning module is retained, but cycles are
18

---

Towards Robustness and Explainability of Automatic Algorithm Selection
A Alation Study of Causal Structures
10
Without Causality
With Directed Cyclic Graph
With Directed A ccyllic Graph
PARIO
BNSL-20166 2016 (x 10²)
GLUHACK- (x (x 10")
GRAPHS-2015 (x 10")
MAXSATI9-UCMS/ (x 10²)
SAT03 IN-UUU (x 10²)
SATIL-INDU> 10²)
(x 10")
SAT18 SATIL-RAND (x 10")
TSP-LION2015 10²)
(x 10²)
SATI1-HAND
Figure 5. Ablation study on ASlib benchmarks.
allowed in the causal graph (i.e., the causal graph is a directed cyclic graph), meaning the learning process is not constrained by the DAG structure. (3) With Directed Acyclic Graph: This is the full version of DAG-AS, where the causal graph is constrained to be a DAG, ensuring no cycles exist between causal relations, enhancing the modeling of the relationships between problem and algorithm features through causal inference. The 10 datasets split into training and test sets, as well as the overall experimental process, follows the same procedure as in previous experiments.
As shown in Figure 5, can clearly observe that the with directed acyclic graph (i.e., the entire DAG-AS) demonstrates superior performance on most datasets, which indicates that the identification of causal relationships and the DAG structure design significantly enhance model performance in algorithm selection tasks. Compared to the case with directed cyclic graph, DAG-AS shows notable advantage across all datasets, especially on the SATI I-INDU and SATI -RAND datasets, suggesting that the DAG essential for capturing causal relationships in complex tasks. The acyclic nature of the causal structure ensures the unidirectionality of causal relationships, which is crucial for avoiding information loops and redundancy, helping the DAG-AS learn more accurate relational patterns. On the other hand, in the case without causality, where the causal learning module is removed, the model generally performs worse across most datasets. The performance gap is particularly evident on GRAPHS-2015 indicating that the absence of causal inference greatly limits the model's 's understanding of the complexity of the task. However, there is one exception: on the SAT03-16-INDU dataset, the model without the causal learning module outperforms DAG-AS, which further validates that the performance deficit of DAG-AS on SAT03-16-INDD is due to its failure to capture the causal structure in this dataset. cases where complex causal relationships cannot be learned due to limited training data, focusing on correlations may yield better performance.
MAXSATI1-UCMM SATI I-HAND, SATI I-NUU, and SATI1-RAND datasets,
Overall, this ablation study strongly validates the importance of the causal learning module and the DAG design enhancing DAG-AS's performance in algorithm selection tasks. The causal graph helps better model the relationships between problem features and algorithm features, and the DAG constraint, particularly in complex tasks, helps prevent overfitting to causal information, thereby improving the accuracy of algorithm selection.
D.4. Robustness Against Distribution Shift
In this experiment, we aimed to evaluate the robustness of DAG-AS under different types of distribution shifts and compare its performance degradation against other benchmark algorithms. The experiment focuses on observing how DAG-AS and its competitors handle performance loss when there a shift in distribution. We designed three types of distribution shifts: (I) Shift on Problem Distribution: We selected 20% of the problem features and assigned higher sampling weights to certain feature values during the training sample selection process, while keeping the feature sampling random in the test samples.
19

---

Towards Robustness and Explainability of Automatic Algorithm Selection
Shill on Problem Distribution
Shill on Optimal Algorithm Distribution
Distribution Shint by Remos ing Algurilhms DAGAS
14
40-
10
DAG AS
DaGaS Best Campetiod
12
Bel Ouspaarr
Decrono Rate (6)
Dicrrsnn Halte eNo
10
Decresse Rate-Bea
GLOBACE 1i 10")
MAASATIIA t015 1SF)
MAXSATIA N171--CMM 10))
SATHH-EAND (x 20")
SAT21 INDU 10")
SATHI-AA Aar1--8ADD (= 10h
54718-55P4 EXP un')
LIONGI55 Mn
GLUHACK--9 10") GRAPHS mils
MAXSA MANSATI9 N19--GMMM PAUCMS 10
SATIB IE-INDUU 10a
SAV21 EATII-INDAC -II--NNA to's
SATT1--A (11---A BAND to's
S4718 EXBBEXP (x. 1at
FSP-LIONGOSS snly
GLUNACK i8 16f)
GRAMIS- 2015--0055s 16f
MAXSA 7194UCS15 10
SATOD SAFII--AND (1r 1ot
TTD-II-NNOU ti's
SATII SITI-INDUs tnts
SATT1-BA BAI--BAD (r. ters
SX715-2XF1 for 10t
TSP-LINNGBSS 1073
SATES 16-INDU
SATTI-HAND
(a) Shift on Problem Distribution.
(b) Shift on Optimal Algorithm Distribution. (c) Distribution Shift by Removing Algo-
rithms.
Figure The generalization performance in the case with distribution shift.
(2) Shift on Optimal Algorithm Distribution: We intervened in the marginal distribution of the optimal algorithms during the training sample collection, giving higher sampling weights to samples where certain candidate algorithms achieve optimal performance, while maintaining random sampling in the test samples. (3) Distribution Shift by Removing Algorithms: We directly removed several candidate algorithms from the training data, while retaining them in the test data. To ensure fair comparison, we choose the 9 ASlib benchmarks, where the algorithm features are uniformly provided. Since all algorithms experience performance loss under distribution shift, we present the proportion of performance loss for each competitor under each distribution shift, as shown in Figure 6. For the baseline comparison, we selected the algorithm with the lowest performance loss for each dataset. The results of the three types of distribution shifts are as presented in Figure 6.
Across all three types of distribution shifts, DAG-AS consistently outperformed the best benchmark algorithms, although the magnitude of the performance advantage varied depending on the type of shift. In general, the causal learning module of DAG-AS enabled it demonstrate strong resilience to these shifts. However, DAG-AS exhibited partieularly notable advantage when dealing with algorithm distribution shifts, which emphasizes its ability to leverage algorithm feature information more effectively than other methods.
Specifically, for the problem distribution shift, DAG-AS showed a competitive edge across most datasets, with lower performance loss compared to benchmark algorithms. This advantage stems from DAG-AS's ability to model the causal relationships between problem features and algorithm features, allowing it to remain robust even when the problem distribution is biased. However, DAG-AS showed a slight disadvantage on the SATI8-EXP dataset, where its performance loss was higher than the benchmark algorithm, indicating that its resilience to problem feature shifts may not be uniformly strong across all datasets. In contrast, the shift on optimal algorithm distribution demonstrated the greatest strength of DAG-AS. These results highlight DAG-AS's s superior ability to handle biases in the optimal algorithm distribution, as it can more effectively utilize algorithm feature information to mitigate the impact of skewed training samples. This highlights DAG-AS's ability to infer the relationships between algorithms and problem features, thus avoiding overfitting to biased algorithm distributions. Finally, for the distribution shift by removing algorithms, all models faced substantial performance degradation due to the removal of candidate algorithms during training. Nonetheless, DAG-AS still demonstrated superior robustness compared to the benchmark algorithms. The causal inference module allowed DAG-AS to better infer the likely performance of missing algorithms by relying on the remaining algorithm features, thus maintaining competitive performance during testing when the removed algorithms were reintroduced.
D.5. Demonstration of the Model-level Explainability
In the algorithm selection scenario, obtaining a causal graph that reflects the relationships between problem features and algorithm features not only helps DAG-AS achieve more accurate results but also enables us to derive many meaningful conclusions through causal interpretation. By analyzing the learned causal relationships, we can gain deeper insights into the underlying interactions between features and improve the decision-makinn process in algorithm selection.
Feature Importance in the Causal Graph: The first part of this experiment focuses on analyzing the importance of all
20

---

Towards Robustness and Explainability of Automatic Algorithm Selection
Betweenness Centrality of Features Across Datasets
Problem Features
0.025
Algorithm Features
Betweenness Centrality
0.020
0.015
0.010
0.005
0.000
GLUHACK-18
GRAPHS-2015
MAXSATI9-UCMS
SAT03-16-INDU
SATUH-NND SATII-HAND
SATH--ANN
SAT18-EXP
TSP-LION2015
Figure 7. Betweenness centrality of features.
problem and algorithm features in the causal graph across different datasets. We measure the betweenness centrality of each feature in the DAG, as shown in Figure From the results, it is evident that high betweenness centrality values predominantly associated with algorithm features, while the betweenness centrality of problem features remains relatively similar across different datasets. This observation highlights the importance of algorithm features in the context of algorithm selection. Algorithm features provide more informative cues than mere algorithm categories and often serve as outcome variables in causal relationships. By interpreting these relationships, the model can establish more compact and interpretable representation of the interactions between problem features, leading to better overall performance in algorithm selection.
Table correspondence between IDs names algorithm features. All names are consistent with those the ASlib benchmark, Algorithm features not included in the table have edges in the causal graph across all data and are considered invalid features.
ID
Name
ID
Namc
ID
Name
ID
Name
0
Avera..
Lines..Total
2
Svera..e
3
Size..Tore
Number.of.filee
Cyclomatic..Average.
6
Cyclomatic..Totll
7
Max. Ivernne..t...rrgee...
8
Max.Indent.
9
nb_nodes
10
nb_edges
11
degree_max
12
degree_mest mean
13
degree.variance
14
degree
15
transitivity
16
clustering_ment
17
clustering.variincee
18
paths_man _mx
19
path_mean
20
variance
21
path_entropy
22
Stmt
23
Type
24
Decl
25
Attribute
26
Operator
27
Literal
28
edge_ss
29
edge_st
30
edge_sd
31
edge_sa
32
edge_so
33
edge_sl edge_ds
34
edge
35
edge.tt
36
edge_td
37
38
edge_dt dt
39
edge_dd
40
edge_a
41
edge_at
42
edge_ad
43
edge_os
44
edge od
45
edge oo
46
edge
47
edge ld
48
lo
49
op_short
50
op_int
51
long
52
op long long
53
op float
54
op double
55
op bit
21

---

Towards Robustness and Explainability of Automatic Algorithm Selection
43
49
54
52
13
37
21
35
Figure 8. Causality between algorithm features. The correspondence between the IDs and names of algorithm features are provided in Table 4.
Next, we investigate the causal relationships between algorithm features across nine datasets. All valid algorithm features, along with their names and IDs, recorded in Table 4. The remaining features are considered invalid, as they have no edges in the causal graph across all data. We averaged the causal graphs obtained from all datasets and visualized the most confident causal links in Figure 8. In this figure, nodes with the highest 10% in-degree and out-degree are highlighted in green and orange, respectively. The causal graphs reveal widespread interdependencies among algorithm features within the ASlib benchmark, though these relationships tend to be sparse. This sparsity suggests a balance between the predictive power and redundancy of the algorithm feature data. As problem features vary across datasets, the importance of different algorithm features shifts accordingly. By modeling this relationship through causal graphs, the model can abstract the most predictive algorithm features and identify key variable relationships, enhancing its performance in algorithm selection.
Causal Relationships Among Algorithm Features:
To further analyze the influence of problem features on algorithm features, we focused on the cause sets of algorithm features the causal graph of each dataset. Figure 9 illustrates the proportion of problem features directly influencing algorithm features, relative to the total number of problem features in each dataset. Since both problem and algorithm features in ASlib are manually designed, and the design of problem features varies across datasets, this result allows to evaluate the rationality of feature design by observing the density of causal relationships in each dataset. We found that datasets with denser causal relationships, such SAT11-HAND. SAT1 I-NDUU, and SAT18- E-EX,, also exhibited a larger performance advantage for DAG-AS. This indicates that causal relationships are prevalent between problem and algorithm features in these datasets, and leveraging these causal relationships allows DAG-AS to better exploit the potential algorithm features. In contrast, in datasets with sparser causal relationships, such as SAT03-16 1A-DU- and GLUHACK-L 18, the advantage of DAG-AS was diminished, and in some cases, DAG-AS even underperformed compared to benchmark algorithms. In these datasets, the causal learning module was only
Impact of Problem Features on Algorithm Features:
MAXSAT19-UCMM
22

---

Towards Robustness and Explainability of Automatic Algorithm Selection
Influence from Problem Features to Algorithm Features
GLUBACK-18
5: 23, 19, 19, 19,26, 10
GRAPHS-2015
Top 5: 19, K 49, 17,53
MAXSATI9-UCMS
Problem Featires as Causes Totaal Problem Features
SATOS-16-INDU
SATTI-HAND
Top 16, 24, 5,54,2
Top S. 55, 38, 33,3
SATI1-INDU
BATII-RAND
SATT8-EXP
Top 5:34, 22,3322
TSP-LION2015
0.6
5,46, 27,
Top 13,77
0.4-
Top 5: 53,16,5, 5,10,,1.51
0.2
Top 8,37,
0.0
GLUHACK-18
GRAPHS-2015 MAXSATT--UMMS SAT08-66-NNDU
SATTI-HAND
SATUI-INDU
SATTI-RAND
SATINEXP
TSP-LION2015
Figure 9, Influence from problem features to algorithm features.
able to identify a limited number of causal relationships, resulting in models that lacked robustness. This outcome suggests that we can estimate the performance of DAG-AS in specific scenarios by analyzing the learned causal graphs.
One notable exception is the TSP-LIO02015 dataset, where DAG-AS still achieved the best performance despite the causal relationships being relatively sparse. This can be attributed to the nature of the dataset: TSP-LION2015 is relatively simple benchmark with large number of training samples and only four candidate algorithms. The abundance of training data enabled DAG-AS to retain the most critical causal relationships while filtering out redundant ones, allowing it to maintain a significant performance advantage. This case demonstrates that in simpler scenarios with sufficient training data, DAG-AS can still excel even when causal relationships are sparse, as it can effectively focus on the most influential relationships.
D.6. Demonstration of the Instance-level Explainability
In the algorithm selection modeling process, DAG-AS generates a causal graph that enables the derivation of counterfactual explanations through interventions based on this graph. This section focuses on a demonstrative experiment conducted on the GRAPHS-2015 dataset to showcase this explainability.
We solve the optimization problem outlined in Eq (17) in the main text determine the minimal intervention values that can alter DAG-AS's S selection results. To streamline the problem and narrow the scope, impose specific constraints: (1) maximum of 20% of the features can be intervened upon; (2) the intervention's magnitude must be less than 10%, with the modified values remaining within the valid range of their respective variables. Under these constraints, we identify 79 instances where the algorithm selection result can be shifted from selecting one algorithm to another, as illustrated in Figure 10. The first heatmap on the left depicts the total intervention magnitude for each sample, with darker colors indicating larger interventions. The second heatmap on the right shows the intervention magnitudes for each feature across samples, where white indicates no intervention, and color gradients from light yellow to deep blue or red reflect small large positive or negative interventions, respectively. The arrows between the heatmaps indicate decision changes by DAG-AS, such as "a + b," which denotes transition from selecting algorithm to algorithm b.
Case Study of Instance 1846: Taking Instance 1846 as an example, applying interventions of -0.00796, -0.00339, -0.07072, -0.00342, 0.00252, -0.00003, and -0.05042 to features 10, 11, 13, 14, 16, 26, and 28 respectively alters its optimal algorithm choice from candidate algorithm 3 to candidate algorithm 1. Conversely, applying interventions of 0.01 0.00685, 0.07201, 0.02622, 0. 0.1838 -0.02242, and -0.15101 to features 2, 3, 5, 6, 8, 19, and 21 changes the choice from candidate
23

---

Towards Robustness and Explainability of Automatic Algorithm Selection
Prodica 10
100
4403
144
141
Intevvttioon Magritade
Peature
Figure 10. Demonstration of counterfactual explainability on GRAPHS-2015 dataset. The correspondence between the IDs and names of algorithm features provided in Table Algorithm IDs 0, I, 2, and 3 correspond glasgow2, lad, supplementallad, and vf2 in the GRAPHS-2011 dataset, respectively.
algorithm 3 to candidate algorithm 0.
The heatmaps indicate that small interventions on certain variables can effectively prompt DAG-AS to make different selection choices. Features 11, 13, 14, 16, 19, and 26 exhibit high sensitivity to perturbations, requiring minimal changes to influence DAG-AS's decision-making their significant interventions can still lead to different outcomes. Overall, only 1.36% of all samples can shift their selection results under the defined limits and range of interventions. Notably, aside from Instance 1846, which exhibited two possible direction shifts, all other samples transitioned towards single candidate algorithm. This underscores the robustness of DAG-AS's decision-making process.
Insights from the Heatmaps:
Although features 2, 3, 5, 6, and are less sensitive,
This analysis highlights DAG-AS's capability to offer interpretable insights through causal graph-based counterfactual reasoning. By strategically applying minimal interventions, we can gain a deeper understanding of how specific features influence algorithm selection, thereby enhancing the transparency and reliability of DAG-AS in practical applications.
24


Reviews:
[{"review_id": "JpjyIU6CsT", "reviewer": "Reviewer_MM5X", "summary": "The paper \"Towards Robustness and Explainability of Automatic Algorithm Selection\" introduces a novel approach to algorithm selection using a directed acyclic graph (DAG) to model the causal relationships between problem features and algorithm features. The proposed method, DAG-based Algorithm Selection (DAG-AS), aims to enhance robustness against distribution shifts and improve explainability at both the model and instance levels. The paper demonstrates the effectiveness of DAG-AS through experiments on the ASlib benchmark, highlighting its advantages in terms of accuracy, robustness, and explainability.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "> The paper's performance on GLUHACK-18 and SAT03-16-INDU, is not as strong as on others, indicating potential limitations ...\n\nWe acknowledge that DAG-AS did not perform well on GLUHACK-18 and SAT03-16-INDU. However, it is unjustified to undermine the significance of DAG-AS merely based on its performance on these 2 datasets. Specifically,\n1. It is challenging for any single method to achieve optimal performance across all problems. In this paper, we conducted comprehensive evaluation on 10 datasets. The results demonstrate that DAG-AS outperformed all the comparison methods on 8 of these data. Notably, on half of them, DAG-AS significantly outperformed other methods, which illustrates the distinct advantages of DAG-AS.\n2. Regarding the DAG-AS's performance on GLUHACK-18 and SAT03-16-INDU, it may be due to the data violating the causal sufficiency assumption or the overly complex causal relations within the data. Nevertheless, these issues are not insurmountable in the causal learning field. There are numerous models specifically designed for complex causality in the causal learning domain, such as models for handling multivariate/non-linear causality, and models for scenarios where the causal sufficiency assumption is violated. The causal learning module of DAG-AS is a relatively simple MLP, mainly to highlight the impact of introducing causality into algorithm selection (AS). If further performance improvement is desired, more advanced causal learning models can be employed to replace Eq(8,9). \n\n> Computational complexity of DAG-AS \n \nThere is no significant difference in computational complexity between DAG-AS and existing methods. Compared to traditional methods, DAG-AS needs to construct a causal DAG and reconstruct algorithm features, while traditional methods often directly predict the optimal algorithm. However, due to the sparsity of the DAG, the reconstruction model for each algorithm feature is actually small-scale. We have provided the running times comparison at the anonymous link: https://imgur.com/a/1w6eLIQ. It can be seen that the running time of DAG-AS is comparable to existing methods. Despite this, DAG-AS achieves remarkable performance gains, indicating its practicability.\n\n> Can DAG-AS be applied to other domains or types of problems beyond those included in the ASlib benchmark? \n\nDAG-AS is designed to be applicable to a wide range of AS scenarios, far beyond the scenarios in the ASlib benchmark. The key requirement for applying DAG-AS is the availability of the general configuration for the AS task, including problem features, algorithm features, and performance data. As long as these elements are provided, DAG-AS can be effectively utilized. Actually, the ASlib itself is also composed of problems from diverse domains.\n\n> How does the choice of problem and algorithm features impact the performance and explainability of DAG-AS? \n\n*Performance Impact*: Different features carry distinct information about the nature of the problem and algorithm. In datasets with a rich set of features that are informative and highly relevant to the algorithm's performance, DAG-AS can better capture the causal relationships. This is similar for other AS methods. Traditional algorithms aim for these features to be correlated with the algorithm's performance, while DAG-AS expects there to be causal relationships behind such correlations. \n\n*Explainability Impact*: When it comes to the impact on explainability, the nature of features matters depending on the user's goals. If users want to understand the decision-making logic of DAG-AS and interpret the causal relationships between features in the DAG, these features should have physical meaning, rather than being representations extracted by deep networks. However, if the sole expectation is for DAG-AS to make AS decisions, features without clear physical meaning can also be perfectly suitable. For example, since ASlib did not provide algorithm features for the BNSL-2016, we used a LLM to extract representations from the code of candidate algorithms. Despite the lack of obvious physical meaning in these features, DAG-AS still achieved the best performance. \n\n> Are there any specific types of distribution shifts or problem characteristics where DAG-AS may not perform well?\n\nThe causal learning module in DAG-AS is essentially built on modeling conditional probabilities. Hence, it can mitigate the impact of covariate shift and prior probability shift. It has been verified in Fig.6 that DAG-AS can handle distribution shifts on problem features and optimal algorithm distributions well. However, DAG-AS may face challenges in dealing with shifts in $P(AF|PF)$. But in AS, $P(AF|PF)$ implies what characteristics an algorithm needs to solve a problem with specific feature values, which does not shift in a given AS task. As for problem characteristics, DAG-AS has no specific requirements regarding the problem domain, as mentioned in previous responses.", "claims_and_evidence": "The paper claims that DAG-AS improves robustness and explainability in algorithm selection tasks. The evidence provided includes experimental results showing that DAG-AS outperforms traditional methods in terms of PAR10 scores across multiple datasets. The paper also presents causal graphs and counterfactual explanations to support the claim of enhanced explainability.", "methods_and_evaluation_criteria": "The authors employ a causal learning framework using DAGs to model the relationships between problem and algorithm features. The evaluation criteria include the PAR10 score, which measures the performance of algorithm selection methods based on solution time and timeouts. The authors compare DAG-AS with several established methods and baselines, including ISAC, MCC, SATzilla11, SNNAP, SUNNY, VBS, and SBS.", "theoretical_claims": "The paper theoretically claims that modeling the conditional distribution of algorithm features based on problem features using a DAG can improve robustness against distribution shifts and provide multi-level explainability. The authors support this claim with a theorem (Theorem 2.3) that establishes the feasibility of using causal models for algorithm selection tasks.", "experimental_designs_or_analyses": "The experimental design includes performance comparisons, ablation studies, and robustness tests against distribution shifts. The authors use ten ASlib datasets with algorithm features and conduct experiments to evaluate the performance, robustness, and explainability of DAG-AS. The experiments are repeated multiple times to ensure reliability, and the results are presented in terms of PAR10 scores and causal graph analyses.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "+\nThe paper introduces a novel approach to algorithm selection that leverages causal learning, which is a relatively unexplored area in this field.\nThe use of DAGs provides a clear and interpretable framework for understanding the relationships between problem and algorithm features.\nThe experimental results demonstrate the effectiveness of DAG-AS in improving robustness and explainability.\n\n-\nThe paper's performance on certain datasets, such as GLUHACK-18 and SAT03-16-INDU, is not as strong as on others, indicating potential limitations in capturing causal relationships with limited training data.\nThe complexity of the causal learning framework may pose challenges for practical implementation and scalability.", "other_comments_or_suggestions": "The authors could provide more details on the computational complexity and scalability of the DAG-AS framework, especially for large-scale datasets.\nIt would be beneficial to explore the potential of DAG-AS in other domains beyond the ASlib benchmark to assess its generalizability.", "questions_for_authors": "How does the computational complexity of DAG-AS compare to traditional algorithm selection methods, and what are the implications for scalability?\nCan DAG-AS be applied to other domains or types of problems beyond those included in the ASlib benchmark?\nHow does the choice of problem and algorithm features impact the performance and explainability of DAG-AS?\nAre there any specific types of distribution shifts or problem characteristics where DAG-AS may not perform well?", "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": "", "extra_scores": {}}, {"review_id": "PqEpk5gNAF", "reviewer": "Reviewer_BWG1", "summary": "The paper argues that current approaches to automatic algorithm selection are mainly based on the correlation between algorithm performance and problem meta-features, which are susceptible to data bias and distributional variations, and lack robustness. The thesis proposes to use DAG to represent the causal relationship between problem features and algorithm features, to model the algorithm selection process, and to provide model-level and instance-level interpretability through counterfactual computation. In ASlib benchmark tests, DAG-AS outperforms existing methods in terms of robustness and interpretability.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "> Weakness 1\n\nThanks for your valuable comments. It's right that \"for a defined problem characteristic, the optimal algorithm should also be defined\", which implies that $P(AF|PF)$ remains constant. In Appendix E.4, our intention was not to change $P(AF|PF)$, but rather to manipulate the marginal distributions $P(AF)$ and $P(PF)$. The “Shift on Optimal Algorithm Distribution” was achieved through a deliberate selection process of the training and test data. Specifically, any candidate algorithm can be the optimal ones for a certain proportion of problems. We manipulate this proportion to induce a distribution shift of the optimal algorithm. For example, in the training data, algorithms A and B are the best-performing ones for 20% and 80% of the problems respectively, while in the test data, these proportions are reversed, with A being optimal for 80% and B for 20% of the problems. We construct the training and test sets by selecting problem instances from the original dataset according to these proportions. Since $P(AF|PF)$ is fixed in algorithm selection, any adjustment to either $P(AF)$ or $P(PF)$ will lead to a corresponding change in the other. Therefore, during the implementation of the “Shift on Optimal Algorithm Distribution”, the distribution of problem features also changed accordingly. \n\n> Weakness 2\n\nThanks for your reminder. We have used hyperparameters to balance the impacts of various losses. As stated on line 278, “The overall loss function is the weighted average of the causal learning loss and algorithm selection loss.” However, we apologize for the misunderstanding caused by not presenting the final form of loss function. In the final version, we will provide the complete loss function with hyperparameters: $L = L_{\\text{reconstruction}} + \\alpha L_{\\text{sparsity}} + \\beta L_{\\text{acyclicity}}+ \\gamma L_{\\text{selection}}$. Current experimental results were obtained under the same parameter settings, where $\\beta=\\gamma=1$ and $\\alpha=0.0001$. Based on your suggestion, we conducted a hyperparameter analysis on SAT11-INDU. The results can be found at the anonymous link: https://imgur.com/a/b8C9l5G. In left figure, we analyzed the balance between reconstruction loss and two causal learning constraints (analyzing $\\alpha$ and $\\beta$), while keeping $\\gamma=1$. In right figure, we analyzed the balance between the causal learning loss and the algorithm selection loss (analyzing $\\gamma$), while keeping $\\beta=1,\\alpha=0.0001$. It can be seen that DAG-AS can maintain relatively good performance within a wide range of parameters. In the final version, we will supplement more detailed hyperparameter analysis. \n\n> Other Comments & Suggestions\n\nWe sincerely appreciate your suggestions. We'll incorporate more details into the final version to highlight the significance of this area, including its practical applications in machine learning, scientific computing, and engineering optimization, as well as its superiority in enabling efficient decision-making, especially in real-time applications. In terms of CausPref, it is a typical study in which causal learning enhances robustness. The strategies of CausPref in causal preference modeling and negative sampling are worth learning. We will cite this paper in the final version and discuss the inspiration for our study.\n\n> Q1\n\nWe apologize for the ambiguity in this part. Our intention was not to illustrate “The advantages of modelling causality over correlation” through Eq(2). Rather, we aimed to express the connection between the two modelling approaches, i.e., $P(S=1|PF,AF)$ and $P(AF|PF,S=1)$ are equivalent in terms of modelling in the algorithm selection task. However, $P(AF|PF,S=1)$ directly models the conditional distribution, which enables it to be more resilient against the marginal distribution shifts. After these discussions, we propose using a causal DAG to model $P(AF|PF,S=1)$. \n\n> Q2\n\nFirst, we would like to clarify that the process does not necessarily require iterating through all PFs. This mainly depends on the DAG learned by DAG-AS. We only need to intervene on all the parent nodes of the algorithm features. Therefore, the DAG has already reduced the dimensionality for counterfactual calculations. \n\nHowever, even with this reduction, a large number of problem features may still be involved in the counterfactual calculations, so improving the efficiency of this process is essential. One potential approach is to model the interpretability calculations as a reinforcement learning system, where the action space would include the features of intervention and their magnitudes, and the reward space would be defined by the changes in the algorithm selection decision. We could take several interventions as samples to train separate Action and Reward networks. This approach may require an independent research paper for in-depth discussion. Therefore, we plan to present this future work in the final version.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes, the approach proposed by the authors models the relationship between problem features and algorithm features from a causal perspective and provides interpretability.", "theoretical_claims": "The author's proof seems reasonable to me.", "experimental_designs_or_analyses": "The authors‘ experimental setup seems reasonable to me, but in the experimental design for distributional shifts in Appendix E.4, I am puzzled by the authors’ simulation of ‘distributional shifts of the optimal algorithm’, the distribution of a particular optimal algorithm, because for a well-designed algorithm, its characteristics should be fixed, and for a defined problem characteristic, the optimal algorithm should also be defined. Intuitively, the optimal algorithm should also be fixed.", "relation_to_broader_scientific_literature": "Previous studies modelled the joint distribution of PF and AF, and the authors concluded that such an approach is sensitive to changes in the distribution and has poor robustness, and the authors proposed modelling P(AF|PF, S = 1) to consider automatic algorithmic choices from a causal perspective.", "essential_references_not_discussed": "The reference is sufficient.", "other_strengths_and_weaknesses": "Strengths:\n\n1.\tExisting algorithm selection methods mainly rely on empirical correlation, the paper is the first to use DAG to describe the relationship between algorithmic features and problem features based on causal modelling, thus enhancing the robustness and interpretability of the model.\n\n2.\tThe paper provides an actionable explanation for algorithmic recommendations by analysing how problem characteristics affect algorithmic choices through minimal intervention in an instance-level explanation.\n\n3.\tThe paper uses multiple causal diagrams (DAG structure), heatmap, and performance comparison table to illustrate the advantages of DAG-AS, making the experimental results intuitive and easy to understand.\n\nWeakness:\n\n1.\tThe question of the reasonableness of the distributional bias experiment (Appendix E.4(2)) setup, i.e., the reasonableness of modifying the optimal algorithmic distribution?\n\n2.\tThe authors do not have corresponding hyperparameters to balance the three aspects of constraints on causality, constraints on feature representation, and constraints on the DAG structure, and do not see this aspect discussed in the experiments. I think this is necessary.", "other_comments_or_suggestions": "1.\tIt is recommended that the authors provide further details on the practical applications of this direction of automatic algorithmic selection as well as on the issue of efficiency to help the reader better understand the importance of this direction.\n\n2.\tEven though the questions are different, I still recommend that the authors read [1], whose modelling of causality and discussion of it is very worthwhile for the authors to learn from.\n\n[1] CausPref: Causal Preference Learning for Out-of-Distribution Recommendation", "questions_for_authors": "1.\tQuestion about Eq. 2:\n\nP(S = 1|PF, AF) seems to be the existing modelling approach, the authors proved through Bayes‘ Theorem the positive relationship between the modelling approach taken by the authors, P(AF|PF, S = 1), and P(S = 1|PF, AF), in my understanding, the advantage of causal modelling over correlational modelling lies in its identification of confounding factors and consideration of the variables’ causal relationships, why did the authors make this clarification? The advantages of modelling causality over modelling correlation seem obvious to me.\n\n2.\tIs there an efficiency problem with exploring interpretability through counterfactual methods? Because it seems that the do operation needs to iterate through all PFs?Do the authors have anything relevant to say about this?", "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": "", "extra_scores": {}}, {"review_id": "PUfL8iNOBJ", "reviewer": "Reviewer_nswt", "summary": "The paper introduces a new approach to algorithm selection using directed acyclic graphs (DAGs) and causal relations. The approach focuses on modeling the causal relations between problem features and algorithm features. The authors argue that this method not only improves the accuracy of algorithm selection but also enhances the model's robustness against distribution shifts and provides multi-level explainability. This approach allows the model to learn the strong feature representations for the most suitable algorithm given a specific problem. The authors of the given paper also propose a counterfactual explanation method to understand how minimal changes in problem features can lead to different algorithm selection outcomes, improving the interpretability of algorithm selection. The authors demonstrate the effectiveness of their approach through experiments on the ASlib benchmark, showing superior performance compared to many traditional algorithm selection methods.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "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": "> Experiments: Missing SOTA approaches. None of the baselines use algorithm features.\n\nThanks for your valuable suggestions. We acknowledge that our experiments lacked some SOTA comparison methods. In response, we have now incorporated ASAP and AutoFolio into our experiments.\n\nRegarding the absence of methods based on algorithm features in our original study, there are two main reasons: 1) these methods mainly differ in feature types rather than model design, and 2) in some scenarios of ASlib, it was difficult to obtain the source code, which made it challenging to extract algorithm features, such as features derived from code or hyperparameters.\n\nAccording to your suggestion, we selected the method proposed by Pulatov et al and AS-LLM as additional comparison baselines. Due to space constraints, we have plotted the experimental results in a figure and presented them at the anonymous link https://imgur.com/a/QmDoUeA. It should be noted that AS-LLM can only be evaluated in scenarios where the source code is available. From the experimental results, it can be clearly seen that DAG-AS still maintains the best performance in most scenarios.\n\n> Whether counterfactual interpretations depends on the DAG-AS\n\nCounterfactual interpretations are indeed closely related to DAG-AS. As described in Page 7, the three steps of counterfactual calculation all rely on the causal model learned by DAG-AS:\n1. Abduction step needs to use the structural equations in DAG-AS to infer the exogenous variables;\n2. Intervention step uses do-operator to modify the causal graph learned by DAG-AS.\n3. Prediction step calculates the results based on the modified causal graph. \n\nIn summary, while counterfactual interpretations can be conceptually applied in other settings, in our work, the DAG-AS framework provides the necessary foundation for a systematic and accurate implementation of counterfactual analysis in algorithm selection. \n\n> Which modeling assumptions are specific to algorithm selection and which ones are quite established modeling approaches for causal learning. \n\nThe two assumptions in the paper are both proposed based on the characteristics of the algorithm selection task, mainly to simplify the complexity of the causal graph. There are some assumptions in causal learning itself, such as causal sufficiency, which are not included in this paper.\n\n> Someone not being fully familiar with causal learning notation is lost in the main paper.\n\nWe sincerely apologize for any confusion caused to readers. We will make adjustments and add a notation tabel into the final version.\n\n> When DAG-AS fails and when not\n\nWe think that DAG-AS may not perform well under 3 cases:\n1. When the features themselves lack informativeness or when the correlation between problem features and algorithm features is extremely weak.\n2. When the data violates the causal sufficiency assumption. This means that there are confounding factors that are not included in the feature set.\n3. When the causal relationships within the dataset are overly complex.\n\nHowever, it should be noted that cases 2 and 3 can potentially be addressed by improving DAG-AS. In the causal learning field, there are numerous specialized models designed to handle complex causal relations, such as those dealing with multivariable or nonlinear causality. Additionally, there are studies focused on identifying causality in scenarios where the causal sufficiency assumption is violated. To enhance the performance of DAG-AS, more advanced causal learning models can be adopted to replace the Eq(8,9).\n\n> I’m least convinced by the interpretation advantage of DAG-AS.\n\nWe sincerely appreciate your criticism. We acknowledge that the interpretability aspect in the context of ASlib may not be as immediately intuitive. The reason is that the algorithm features used in ASlib are AST features, which are highly abstract in terms of their physical meaning. However, the interpretability can be extremely valuable in scenarios where the physical meaning of features is explicit. For example, when considering the architecture features or hyperparameters of deep-learning models as algorithm features. In such cases, if the causal graph reveals which problem features influence the number of neurons in specific layers, this interpretability can significantly assist users in understanding the model design. It also provides great utility for experts when debugging the DAG-AS model. \n\n**Due to space limitations, the following issues are addressed in the response of other Reviewers:**\n\n> Paragraph discussing the assumption on the availability of informative algorithm features.\n\nPlease refer to the 1st response of Reviewer oy94 (Weakness1)\n\n> More discussion on the intervention of algorithm features\n\nPlease refer to the 2rd response of Reviewer oy94 (Weakness2)\n\n> Weights for loss function\n\nPlease refer to the 2rd response of Reviewer BWG1 (Weakness2)", "claims_and_evidence": "I strongly appreciate the proposed approach of applying causal relationship learning with algorithm selection. I agree with the authors that this is in fact a very novel approach for the domain of algorithm selection and makes major contributions to improving the performance of algorithm selection systems. \n\nThe empirical evidence of the paper is strong since the authors compare against established algorithm selection approaches on an established algorithm selection benchmark library (ASlib). However, I’m concerned about missing state-of-the-art approaches for algorithm selection. For example, in the Open Algorithm Selection Challenge ASAP won the competition. Other strong and established systems such as AutoFolio are also not considered. ISAC, SATzilla11 and SNNAP are very old approaches and not considered SOTA. (It is less clear for SUNNY since it would depend on the version of SUNNY.)\n\nI very much like the idea of counterfactual interpretations of algorithm selection. However, it is not fully clear to me whether this depends on the DAG approach proposed by the authors or whether this is completely orthogonal to the rest of the paper. To my understanding, counterfactual interpretation can also be derived on correlation-based approaches.\n\nI fully agree with the claim of robustness of the DAG approach and the conducted experiments.", "methods_and_evaluation_criteria": "The proposed method is very compelling and nicely motivated. The formal derivation is good and with sufficient background knowledge also fairly understandable. Some minor comments: It could be clearer which modeling assumptions are specific to algorithm selection and which ones are quite established modeling approaches for causal learning. Furthermore, I dislike that I had to jump to the appendix to read up on parts of the notation – without it, someone not being fully familiar with causal learning notation is lost in the main paper. \n\nThe evaluation on ASlib with PAR10 follows the common best practices of the community and thus it is very appropriate. However, it is a bit unfortunate that only some of the benchmark scenarios have algorithm features and some others don’t have them s.t. it is not quite clear whether the benchmarks could (unintentionally) biased. \n\nFurthermore, I was missing any kind of baseline that makes use of algorithm features, as the ones cited by Tornede et al. As far as I know, none of the baselines use algorithm features, but only instance features.", "theoretical_claims": "Theorem 2.3 and all the other theoretical derivations made sense to me intuitively, as I am someone with strong expertise in algorithm selection and less in causal learning. I have not read Proof B (in the Appendix) in detail.", "experimental_designs_or_analyses": "The experimental design was overall convincing (with the few exceptions I mentioned above already). I also strongly appreciated the ablation and robustness study showing the strengths and advantages of the approaches and its components. \n\nI was missing a bit more details on when the approach will perform well and why it failed to do so on two ASlib scenarios. The authors briefly mention aspects such as the amount of training data; however, for example, SAT03-16-INDU has a lot more training data than SAT11-RAND; nevertheless, DAG-AS performed very well on SAT11-RAND but not on SAT03-16-INDU. Later on, the authors argued with the sparsity of the DAG; however, also the additional experiments in the appendix (e.g., Figure 9) have not really helped me to get a good grasp of when DAG-AS fails and when not. \n\nAs discussed before, I’m least convinced by the interpretation advantage of DAG-AS. I agree that having a DAG is nice in practice, but DAGs as shown in Figure 8 are not helpful in understanding the underlying modeling problem and causal relationship. Although I am quite familiar with the ASlib scenarios, I was not able to get any good insight from Figure 8. Also as said before, I like the idea of applying counter-factual interpretations and, indeed, a DAG makes this a lot easier, but in principle, methods such as LIME could also be used similarly.", "relation_to_broader_scientific_literature": "The related work is overall well covered. It seems to be a bit biased towards the traditional approaches in algorithm selection and discusses less modern approaches based on deep learning without explicit feature representations.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "I see a lot of potential in this paper because it provides a completely new direction for the algorithm selection community. It is the first very substantial progress in algorithm selection I have seen in recent years.\n\nI was hoping to see more discussion on the intervention of algorithm features in this paper since causal reasoning would make this much more interesting. I wonder whether the authors were thinking about modifying instances or generating completely new instances – both are research directions already proposed (independent of causal reasoning) in the algorithm selection community. \n\nFurthermore, informative algorithm features are not always easily available. Also, the computation graph features proposed by Pulatov et al. are not as trivial and it is unclear whether they are informative enough. I would love to have at least a short paragraph discussing the very important assumption on the availability of informative algorithm features.", "other_comments_or_suggestions": "None", "questions_for_authors": "I have a bit of concern regarding your weighted loss function which seems to be fairly complex. I fully understand and agree with the individual components. But how have you managed to find the weights for your loss functions and on which benchmarks have you done this?", "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": "", "extra_scores": {}}, {"review_id": "Qc3GpDk2HQ", "reviewer": "Reviewer_oy94", "summary": "The paper focuses on the automatic algorithm selection problem. It aims to improve the explainability and robustness of algorithm selection. Main contributions include:\n\n(1) The most significant innovation of this paper is that it changes the modeling approach of the algorithm selection task. Traditionally, models predict which algorithm to choose based on problem features and algorithm features. However, this paper's approach predicts algorithm features based on problem features. In other words, it focuses on \"What characteristics an algorithm needs to solve a problem with specific feature values\". \n\n(2) Causal Modeling with DAG: The paper introduces a causal framework using DAGs to describe the underlying mechanism of algorithm selection.\n\n(3) Model Framework: The DAG-AS model is based on a neural network framework incorporating causal learning principles. The model reconstructs algorithm features, and the final algorithm selection is made by comparing the oringinal features of candidate algorithm and reconstructed features of the optimal algorithm.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "> Weakness 1 / Q3\n\nThanks for your insightful comments. In practical scenarios, informative algorithm features are not always readily available, just as pointed out by Reviewer nswt. In this study, we recognize that the availability of algorithm features has a vital impact on the model's performance. Therefore, we will add an assumption and discussion about the informativeness of algorithm features in Section 2:\n\n**Assumption 3**: Informative algorithm features are available for the algorithm selection task.\n\nIn the context of algorithm selection, the availability of informative algorithm features is a crucial yet often overlooked aspect. This assumption implies that we can obtain algorithm-related characteristics that carry meaningful information for differentiating the performance of different algorithms on various problem instances. This assumption serves as a fundamental basis for DAG-AS. Currently, there are several established algorithm representation methods, such as hyperparameters, model structure information, code-related statistical features, AST features, and code features extracted by LLMs. These features provided valuable insights into the algorithms' properties and significantly contributed to the performance of DAG-AS. However, we are also aware that in some cases, obtaining such informative features can be challenging. For example, code-related features cannot be obtained in the closed-source scenario. \n\n> Weakness 2\n\nWe sincerely appreciate your valuable suggestions. Intervening on algorithm features indeed holds the potential to achieve broader goals beyond the algorithm selection task itself. In real-world scenarios, the most suitable algorithm may not always be present in the candidate set, or may not even have been designed yet. By examining $P(S=1 \\mid \\textbf{PF},do(\\textbf{AF}=\\textbf{a}+\\delta_{\\textbf{AF}}))$, we can explore how to adjust the optimal algorithms within the candidate set based on $\\delta_{\\textbf{AF}}$ for a given problem. This intervention can assist us in two ways:\n1. It helps in searching for more suitable algorithms within or beyond the existing candidate set; \n2. It generates valuable suggestions to aid in the automated algorithm design.\n\nHowever, in the context of ASlib, due to the high level of abstraction of the algorithm features and the fact that many candidate algorithms are closed-source, we are unable to optimize these candidate algorithms according to the results of algorithm feature interventions. As a result, empirical study in this aspect is currently not feasible. In the future, such research could potentially be carried out in scenarios where the physical meaning of features is more explicit. For example, in the selection of deep-learning models, the hyperparameters and architecture features of the models can be used as algorithm features. Interventions on these features can help users to further improve existing models or generate new ones based on the candidate algorithm set.\n\nRegarding the generation of new algorithms, we already have some well-developed ideas. Specifically, by combining the DAG learned by DAG-AS and the results of algorithm feature interventions, we can generate suggestions for improving candidate algorithms. These suggestions, along with the code of the candidate algorithms, can then be submitted to a LLM. Leveraging the code-related ability of the LLM, we can achieve the automated optimization and design of algorithms. We will incorporate the discussion into the final version to further enhance the depth of our research. \n\n> Q1\n\nThe goal of classic SHAP analysis is to explain the prediction results of a model by calculating the contribution of each feature to the prediction. It focuses on quantifying the impact of individual features on the output within the model's framework. In contrast, our paper aims to achieve multi-level explainability in algorithm selection. It not only considers the influence of features on the selection result but also delves into the causal relations between problem features and algorithm features, as well as the overall causal structure. This helps users understand not only which features are important but also how they interact and influence the algorithm selection process in a causal sense.\n\n> Q2\n\nWe appreciate your astute observation. We indeed introduced additional constraints to simplify the search process for determining the appropriate perturbation range and step size in instance-level explanations. As detailed in our last response to the Reviewer BWG1, we have proposed some methods to assist in solving the optimization problem. Due to space limitations, we cannot elaborate on these here. Moreover, it is unnecessary to adjust Eq.15 since this equation represents the original form of the optimization problem.\n\n> Q4\n\nThe construction of the directed cyclic graph still based on the two assumptions. As for performance degradation on SAT03-16-INDU, please read the 5th response to Reviewer nswt.", "claims_and_evidence": "Overall, the claims made in the submission are supported by clear and convincing evidence, including:\n(1) DAG-AS's performance superiority\n(2) Ablation study\n(3) DAG-AS's robustness against distribution shifts\n(4) The model-level explainability of DAG-AS\n(5) The instance-level explainability of DAG-AS", "methods_and_evaluation_criteria": "The evaluation is conducted based on ASlib Benchmark and PAR10 Score, whose use aligns with the algorithm selection community's established practices.", "theoretical_claims": "The paper presents Theorem 2.3 to support the use of causal models in the algorithm selection task. The proof appears to be correct in its logical structure. It first shows the existence of an algorithm feature whose parent set is composed of problem features through a proof by contradiction. Then, it uses topological ordering and mathematical induction to construct functions for each algorithm feature's conditional distribution.", "experimental_designs_or_analyses": "The experimental designs and analyses in the paper, including performance comparison, ablation study, robustness tests, and explainability experiments, are generally sound and valid for validating the DAG-AS model.", "relation_to_broader_scientific_literature": "Researchers in the AutoML and algorithm selection community will benefit from this study. The paper revolutionizes the modeling approach in algorithm selection, offering new inspiration for subsequent research, especially regarding explainability and robustness. However, while the paper uses techniques from causal learning and recommendation systems, its inspiration for these two fields is limited.\n\nOverall, the primary audience for this paper is in the AutoML field, especially algorithm selection researchers. The findings and methods presented can be directly applied or adapted to improve algorithm selection algorithms, making it a valuable contribution to this specific research community.", "essential_references_not_discussed": "It is recommended to add a discussion on explainability in the Background section.", "other_strengths_and_weaknesses": "Strengths:\n\n1. The paper introduces causal learning into the field of algorithm selection, offering a brand-new perspective to address the limitations of traditional methods. The DAG-AS model constructs a causal graph to clarify the causal relationships between problem features and algorithm features. This innovative modeling approach is groundbreaking in algorithm selection research.\n\n2. The paper makes significant contributions in terms of explainability. The model-level explanation can visually display the dependency relationships among variables by analyzing the DAG structure, helping researchers understand the model's decision-making process. The instance-level explanation uses counterfactual interventions to accurately identify the key features that affect algorithm selection, providing actionable explanations for practical applications and enhancing the credibility and practicality of the model.\n\n3. The experimental design is comprehensive and rigorous. The research covers various aspects such as performance comparison, ablation studies, robustness testing, and explainability verification, providing strong support for the viewpoints in the paper. \n\nWeaknesses:\n\n1. How to obtain algorithm features is a prerequisite for this study. The method in this paper assumes that algorithm features are known, but there are scenarios where algorithm features are not provided. Even in ASlib, only 10 datasets contain algorithm features. I suggest that the authors clearly introduce how to obtain algorithm features in the paper, which will improve the practicality of the method.\n\n2. The Discussion in P7 is interesting. I think that after making significant changes to the modeling paradigm of algorithm selection in this paper, one of the key advantages is that the algorithm selection model can, in turn, promote the improvement of algorithms. Unfortunately, this paper does not discuss this content in detail. Therefore, I suggest either enriching this part of the content or including it in future work.\n\n3. A minor issue: The symbol \"a\" in line 371 should be explained.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. The paper achieves multi-level explainability in algorithm selection, which represents the new value emerging from the application of causal concepts and recommendation idea into the algorithm selection field. Are the goals of this explainability consistent with those of the classic SHAP analysis? Or does the connotation of the explainability in this paper cover and go beyond what the SHAP analysis encompasses?\n\n2. In instance-level explanations, the algorithm selection is explained by finding the minimum perturbations through counterfactual interventions. However, in practical operations, how can we determine the appropriate perturbation range and step size to ensure that effective explanations can be obtained? In the experiments of Figure 10, the authors achieved this by imposing certain constraints. But the optimization problem modeled in Eq. (15) does not involve these constraints. Is it necessary to make the form of the optimization problem in Eq. (15) consistent with that in the experiments?\n\n3. How to obtain algorithm features is a prerequisite for this study. The method in this paper assumes that algorithm features are known, but there are scenarios where algorithm features are not provided. Even in ASlib, only 10 datasets contain algorithm features. I suggest that the authors clearly introduce how to obtain algorithm features in the paper, which will improve the practicality of the method.\n\n4. In the ablation study, is the construction of the directed cyclic graph still based on the two assumptions of this paper? Why does the method using DAG perform worse than the method without considering causality in some scenarios?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper provides a well-founded contribution for explaining why certain algorithms perform well on certain instance sets using a DAG mechanism. There has not been much of a focus on explainability in optimization contexts, and especially not for algorithm selection. This paper is thus really pioneering methods in this area. The reviewers compliment both the theory and experimental results. The paper uses standard benchmarks in the area and draws some interesting conclusions. I note that the only negative review was flagged by the LLM detection software, and even ignoring the fact that it may have been written by an LLM, it is of low quality and offers no coherent argument for rejecting the paper.
Decision: Accept (spotlight poster)