Explaining Graph Neural Networks with Mixed-Integer Programming

Area of Science:

• Artificial Intelligence
• Machine Learning
• Graph Analytics

Background:

• Graph Neural Networks (GNNs) achieve top performance in graph learning tasks.
• Lack of transparency in GNNs hinders trust and limits their applicability.
• Existing GNN explanation methods focus on individual predictions, not general patterns.

Purpose of the Study:

• To develop a novel method for generating model-level explanations of Graph Neural Networks.
• To address the difficulty of finding representative graphs for GNN explanations.
• To enhance the understandability and trustworthiness of GNN models.

Main Methods:

• Formulated the search for explanatory graphs as a mixed-integer programming (MIP) problem.
• Used decision variables to define the explanation graph and an objective function for explanation quality.
• Developed MIPExplainer to directly optimize over discrete graph spaces.

Main Results:

• MIPExplainer successfully generates accurate and stable explanations for GNNs.
• Outperformed existing methods on both synthetic and real-world datasets.
• The MIP approach directly optimizes for explanation quality in the discrete input space.

Conclusions:

• MIPExplainer provides a robust solution for model-level GNN explanation.
• The method enhances the transparency and interpretability of Graph Neural Networks.
• This approach facilitates broader adoption and trust in GNN applications.