MIP-Explainer: An Explainability Method for Graph Neural Networks Based on Mutual Information

Graph Neural Networks (GNNs) garnered significant success in modeling graphs due to their powerful capabilities in representation learning and reasoning. However, the lack of explainability in GNNs largely limits their application in security, sensitive, and other such scenarios. Due to their interpretability and high fidelity, surrogate methods in explainability techniques have sparked some explorations, but many challenges are still not well-addressed. 1) Most surrogate based explainers generate local neighborhoods by randomly perturbing node features, ignoring the graph topology perturbations. 2) As the graph grows, the combinations of perturbations increase exponentially, whereas only a few perturbation combinations are close to the prediction. 3) The application of multiple relaxation steps and regularization terms in practice may diminish the intrinsic interpretability of surrogate models in previous works. Towards this end, we propose a novel framework named MIP-Explainer, which consists of Selector and Explainer modules. In the Selector module, we leverage mutual information to perturb the graph structure, efficiently generating local neighborhoods of the data. In the Explainer module, we propose an intuitive and interpretable linear model to these local neighborhoods, without incorporating any relaxation or regularization terms. Extensive experiments on real-world and synthetic datasets show the effectiveness of our MIP-Explainer by outperforming state-of-the-art baselines.