I’m using XGBoost-Spark with the “predContribCol” to compute SHAP contributions values for my model. The process is taking a very long time, I am wondering what algorithm XGBoost is using to compute SHAP values under the hood and what the time complexity is. Is it brute force O(TL2^M) or polynomial O(TLD^2), as proposed by the TreeSHAP algorithm in this paper: https://arxiv.org/pdf/1802.03888.pdf. (T = num trees, D = max depth of any tree, M = num features, L = number of leaves).
It uses the polynomial time algorithm. You can further speed up the SHAP computation by using NVIDIA GPUs: https://xgboost.readthedocs.io/en/latest/gpu/index.html#gpu-accelerated-shap-values