A graph analytics framework for portfolio relative hardness prediction and explanation with application to the maximum clique problem

This study introduces a machine learning-based framework for predicting and interpreting portfolio-relative hardness in graph-based combinatorial optimization. The framework was evaluated on the maximum clique problem (MCP), where algorithmic performance can vary substantially with graph structure. Rather than treating hardness as an intrinsic property of an MCP instance, this study defines hardness empirically with respect to a heterogeneous target solver algorithms portfolio. The proposed framework consists of two stages. In the first stage, problem-agnostic graph features were computed and machine learning classification models were trained to predict whether an instance was portfolio-hard. The best-performing classifier, a support vector classifier, achieved a weighted F1-score of 0.9921, a portfolio-hard minority-class F1-score of 0.8780, and a ROC-AUC score of 0.9083 using only three graph features. In the second stage, FP-Growth association rule mining (ARM) was used to identify frequent structural signatures among portfolio-hard instances. The best association rule covered 88.29% of portfolio-hard instances, achieving a specificity of 87.63%, a balanced accuracy of 87.96%, and enriched the portfolio-hard rate by a factor of approximately 5.91 relative to the dataset base rate. Regression models were also trained to predict algorithmic computation times, with the best-performing model achieving a mean absolute percentage error of 1.7% and a coefficient of determination close to 1. Overall, the results show that graph features can support prediction of portfolio-relative solver difficulty and provide interpretable structural signatures associated with simultaneous failure across a diverse target solver portfolio.