TY - GEN

T1 - Complete-to-Sparse: A Novel Graph Construction Strategy for Efficient ShapG

AU - Чжао, Чи

AU - Лю, Цзин

AU - Парилина, Елена Михайловна

PY - 2025/7/6

Y1 - 2025/7/6

N2 - In this paper, we improve the ShapG method (a feature importance algorithm based on graphs) to enhance computational efficiency while maintaining acceptable accuracy. The ShapG method is a novel method in explainable artificial intelligence (XAI) providing the feature importance in complex machine learning models using the Shapley value calculated for the graph constructed based on data. Our primary contribution focuses on optimizing the graph construction stage. Unlike the original ShapG method which starts from an empty graph, our enhanced approach begins with a complete graph and iteratively removes edges based on measures between features and target variables. Throughout this process, we maintain graph connectivity and ensure the graph density remains above a predefined threshold. This optimization procedure significantly reduces computational complexity. For the Shapley value calculations, we retain the original ShapG sampling approach. Experimental results demonstrate that our improved method achieves substantial gains in computational efficiency in comparison with the original ShapG method and other XAI methods. Additionally, we provide recommendations for selecting appropriate measures for different machine learning tasks.

AB - In this paper, we improve the ShapG method (a feature importance algorithm based on graphs) to enhance computational efficiency while maintaining acceptable accuracy. The ShapG method is a novel method in explainable artificial intelligence (XAI) providing the feature importance in complex machine learning models using the Shapley value calculated for the graph constructed based on data. Our primary contribution focuses on optimizing the graph construction stage. Unlike the original ShapG method which starts from an empty graph, our enhanced approach begins with a complete graph and iteratively removes edges based on measures between features and target variables. Throughout this process, we maintain graph connectivity and ensure the graph density remains above a predefined threshold. This optimization procedure significantly reduces computational complexity. For the Shapley value calculations, we retain the original ShapG sampling approach. Experimental results demonstrate that our improved method achieves substantial gains in computational efficiency in comparison with the original ShapG method and other XAI methods. Additionally, we provide recommendations for selecting appropriate measures for different machine learning tasks.

KW - Shapley value

KW - explainable artificial intelligence

KW - feature importance

KW - graph construction

UR - https://www.mendeley.com/catalogue/845c27bd-28ff-3a49-afe6-68f66137557c/

U2 - 10.1007/978-3-031-97077-1_13

DO - 10.1007/978-3-031-97077-1_13

M3 - Conference contribution

SN - 9783031970764

T3 - Lecture Notes in Computer Science

SP - 180

EP - 194

BT - Mathematical Optimization Theory and Operations Research (MOTOR 2025)

PB - Springer Nature

Y2 - 7 July 2025 through 11 July 2025

ER -