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.