Towards Robustness and Explainability of Automatic Algorithm Selection

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.

Choosing the right algorithm to solve a problem can significantly improve performance, but it's often difficult to know which algorithm works best before actually running them. Traditionally, researchers have relied on data patterns to make this decision, but such methods can be misleading when the data changes or contains bias. This paper introduces a new approach that mimics how humans might reason through the problem: by understanding why certain algorithms work well for certain types of problems. We use a technique called a causal graph—a type of map showing how problem characteristics influence the traits an ideal algorithm should have. This method not only makes the system more robust to changing conditions, but also allows it to explain its decisions more clearly. For example, it can tell us which specific problem features led to the choice of a certain algorithm, or even how small changes to a problem might lead to choosing a different algorithm. Our experiments on a well-known benchmark show that this new method is both more accurate and more interpretable than existing ones.