6. Interpretability of Graph Neural Networks

Interpretability

What is Interpretability?

Interpretability in machine learning refers to the ability to explain or present the workings of a model in understandable terms to humans. It is crucial for ensuring transparency, trust, and actionable insights from AI systems.

Why and How is it Used?

• Trust: Building confidence in model predictions by providing understandable explanations.
• Debugging: Identifying and correcting model errors or biases.
• Compliance: Meeting regulatory requirements for transparency in AI decisions.
• Knowledge Discovery: Gaining insights into the underlying patterns in data.

Types

• Post-hoc Interpretability: Techniques applied after the model is trained to explain its predictions (e.g., SHAP, LIME).
• Intrinsic Interpretability: Models inherently interpretable due to their simplicity (e.g., decision trees, linear models).

Relation to GNN

Graph Neural Networks (GNNs) operate on complex, interconnected data structures, making them powerful but often opaque. Interpretability methods for GNNs aim to elucidate how these models make predictions, which parts of the graph are influential, and what features are significant.

Algorithms

SHAP (SHapley Additive exPlanations)

Idea:

SHAP explains the output of a model by distributing the prediction among the input features based on their contributions. It is grounded in cooperative game theory, specifically the Shapley value.

Algorithm:

1. Simplified Input: Use a simplified input $x'$ where features are either included or excluded.
2. Local Accuracy: Ensure the explanation model $g(x')$ approximates the original model $f(x)$ closely.
3. Shapley Values Calculation:
4. Calculate the contribution of each feature $i$ by averaging its marginal contributions across all possible feature subsets.
5. Formula: $$\phi_i(f, x) = \sum_{z' \subseteq x'} \frac{|z'|! (M - |z'| - 1)!}{M!} \left[ f(z') - f(z' \setminus \{i\}) \right]$$
   • $z'$: Subset of features.
   • $M$: Total number of features.

MUSE (Model Uncertainty and Sensitivity Estimation)

Idea:

MUSE aims to provide explanations based on decision rules. It focuses on fidelity (closeness to the original model) and interpretability (simplicity and understandability of the rules).

Algorithm:

1. Rule Selection: Start with a set of candidate rules.
2. Rule Optimization: Optimize the selection of rules to balance fidelity and interpretability.
3. Subspace Definition: Define subspaces where the rules are valid.
4. Decision Making: Use the optimized rules to explain the model's decisions within each subspace.

LIME (Local Interpretable Model-agnostic Explanations)

Idea:

LIME explains individual predictions by approximating the model locally with an interpretable model. It perturbs the input and observes changes in the output to learn the local behavior of the model.

Algorithm:

1. Data Perturbation: Generate new samples by perturbing the original input.
2. Model Training: Train a simple, interpretable model (e.g., linear model) on the perturbed data.
3. Weighting Samples: Weight the samples based on their similarity to the original input.
4. Local Explanation: Use the simple model to explain the prediction locally.

LIME for Graphs (GraphLIME)

Idea:

GraphLIME extends LIME to graph data, focusing on explaining predictions based on node attributes rather than graph structure.

Algorithm:

1. Neighborhood Sampling: Define the $k$-hop neighborhood of the node of interest.
2. Feature Selection: Use HSIC Lasso to select relevant features.
3. Local Model Training: Train an interpretable model (e.g., linear model) on the neighborhood data.
4. Local Explanation: Use the interpretable model to explain the node's prediction.

GNN Explainer

Idea:

GNN Explainer aims to provide detailed explanations for GNN predictions by identifying the most influential subgraphs and node features.

Algorithm:

1. Identify Influential Subgraph: Determine the subgraph $G_s(v)$ that most influences the prediction for node $v$.
2. Feature Selection: Identify the subset of node features $X_s$ that are most influential.
3. Mutual Information: Optimize for the subgraph and features that maximize mutual information with the original prediction.
4. Explanation Generation: Provide the influential subgraph and features as the explanation.

Temporal Explanation

Idea:

Temporal explanations focus on identifying patterns and motifs in temporal graphs that lead to certain predictions.

Algorithm:

1. Motif Sampling: Sample motifs (repeating patterns) from the temporal graph.
2. Motif Encoding: Use graph convolution to encode motifs into vector representations.
3. Information Bottleneck: Identify which motifs are most informative for the model's predictions.
4. Explanation Generation: Provide the most informative motifs as the explanation.