Explainability is a gateway between Artificial Intelligence and society as\nthe current popular deep learning models are generally weak in explaining the\nreasoning process and prediction results. Local Interpretable Model-agnostic\nExplanation (LIME) is a recent technique that explains the predictions of any\nclassifier faithfully by learning an interpretable model locally around the\nprediction. However, the sampling operation in the standard implementation of\nLIME is defective. Perturbed samples are generated from a uniform distribution,\nignoring the complicated correlation between features. This paper proposes a\nnovel Modified Perturbed Sampling operation for LIME (MPS-LIME), which is\nformalized as the clique set construction problem. In image classification,\nMPS-LIME converts the superpixel image into an undirected graph. Various\nexperiments show that the MPS-LIME explanation of the black-box model achieves\nmuch better performance in terms of understandability, fidelity, and\nefficiency.\n