Research map / Label-efficient and robust learning / Recognition and long-tail

Towards Robustness and Explainability of Automatic Algorithm Selection

ICML 2025 · Label-efficient and robust learning › Recognition and long-tail · approach: Data augmentation and generalization bias

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes DAG-AS, a causal DAG-based neural framework for algorithm selection that reconstructs optimal-algorithm features from problem features and ranks algorithms by reconstruction differences, with counterfactual explanations.

Problem

Existing algorithm selection methods learn correlations between meta-features and algorithm performance, which ignores the underlying mechanism linking problem features to required algorithm characteristics and makes them vulnerable to data bias and distribution shift.

Approach

Models the conditional distribution of algorithm features given problem features with a structural causal model learned as a DAG via neural networks (gradient-based causal learning with acyclicity and sparsity penalties); selects algorithms by comparing reconstructed optimal-algorithm features with candidate features, and derives model-level and counterfactual instance-level explanations.

Key results

• DAG-AS achieved the lowest PAR10 on 8 of 10 ASlib datasets, e.g., BNSL-2016 1.81e3 vs. SATzilla11 2.00e3 and GRAPHS-2015 5.42e6 vs. SUNNY 7.56e6.
• DAG-AS lagged behind MCC and SATzilla11 on GLUHACK-18 and SAT03-16-INDU, attributed to difficulty learning causal structure from limited samples.
• Counterfactual analysis on GRAPHS-2015 found only 1.36% of samples changed selection under the stated intervention constraints.

Measured effects reported in the paper

Surprising findings

• DAG-AS underperformed correlation-based baselines on GLUHACK-18 and SAT03-16-INDU, which the authors attribute to limited training samples for causal learning.
• On SAT03-16-INDU, the variant without causality outperformed the full model.

Limitations

• Causal learning struggles with limited training samples, leading to weaker results on some datasets.
• Counterfactual explanation requires numerical optimization (gradient descent) for abduction, which is costly; authors note efficiency improvements as future work.
• Explainability depends on semantic interpretability of algorithm features; ASlib AST-based features are abstract.

Experimental setup

Datasets: ASlib BNSL-2016 GLUHACK-18 GRAPHS-2015 MAXSAT19-UCMS SAT03-16-INDU SAT11-HAND SAT11-INDU SAT11-RAND SAT18-EXP TSP-LION2015

Benchmarks: ASlib

Metrics: PAR10

Baselines: ISAC MCC SATzilla11 SNNAP SUNNY VBS SBS

Builds on: NOTEARS Bayesian Personalized Ranking structural causal models gradient-based causal learning

Closest papers by meaning

• Algorithmic Assurance: An Active Approach to Algorithmic Testing using Bayesian Optimisation (NeurIPS 2018 · similarity 0.84)
• DAGs with NO TEARS: Continuous Optimization for Structure Learning (NeurIPS 2018 · similarity 0.83)
• Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut (NeurIPS 2024 · similarity 0.83)
• LayerDAG: A Layerwise Autoregressive Diffusion Model for Directed Acyclic Graph Generation (ICLR 2025 · similarity 0.83)
• Machine Learning for Online Algorithm Selection under Censored Feedback (AAAI 2022 · similarity 0.83)
• A Framework for Data-Driven Explainability in Mathematical Optimization (AAAI 2024 · similarity 0.82)