Source-linked AI summary
GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks
Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, Dawei Yin, Yi Chang
TL;DR
GNNs effectively represent graph data but are difficult to interpret because their predictions arise from complex nonlinear transformations. GraphLIME learns a nonlinear interpretable model over an explained node’s N-hop neighborhood using HSIC Lasso, and experiments found its explanations more descriptive than existing methods. Its current scope is single-node explanation and does not yet explicitly explain structural graph patterns.
Problem
GNN predictions are difficult to explain, while many neural-network explanation methods do not explicitly use graph information.
Method
GraphLIME samples an explained node’s N-hop neighborhood and uses HSIC Lasso to learn a locally faithful nonlinear interpretable model and select representative features.
Results
Experiments on two real-world graph datasets and two kinds of GNN models demonstrated GraphLIME’s effectiveness, with explanations described as more descriptive than existing methods.
Takeaways & Limitations
GraphLIME provides finite representative-feature explanations for individual GNN predictions while incorporating local neighborhood information.
Takeaways & Limitations
The current framework explains only a single target node and does not yet identify the important subgraph structures influencing predictions.
Abstract
from arXiv · showhide
Graph structured data has wide applicability in various domains such as physics, chemistry, biology, computer vision, and social networks, to name a few. Recently, graph neural networks (GNN) were shown to be successful in effectively representing graph structured data because of their good performance and generalization ability. GNN is a deep learning based method that learns a node representation by combining specific nodes and the structural/topological information of a graph. However, like other deep models, explaining the effectiveness of GNN models is a challenging task because of the complex nonlinear transformations made over the iterations. In this paper, we propose GraphLIME, a local interpretable model explanation for graphs using the Hilbert-Schmidt Independence Criterion (HSIC) Lasso, which is a nonlinear feature selection method. GraphLIME is a generic GNN-model explanation framework that learns a nonlinear interpretable model locally in the subgraph of the node being explained. More specifically, to explain a node, we generate a nonlinear interpretable model from its $N$-hop neighborhood and then compute the K most representative features as the explanations of its prediction using HSIC Lasso. Through experiments on two real-world datasets, the explanations of GraphLIME are found to be of extraordinary degree and more descriptive in comparison to the existing explanation methods.
1 Introduction
GNNs model graph structure and node features effectively but remain difficult to interpret. GraphLIME addresses this by learning nonlinear, locally faithful explanations from a node’s neighborhood and selecting representative features.
- Existing explanation approaches either approximate models locally with simple models or identify representative features and influential instances.
- GNNs combine node features with graph structure, but their predictions remain difficult to explain because of nonlinear transformations.
- GNNexplainer identifies subgraphs and node features but focuses mainly on graph structure, while LIME’s linear model can perform poorly without graph information.
- GraphLIME samples N-hop neighbors and uses HSIC Lasso to capture nonlinear feature-prediction dependencies locally.
- Experiments on two real-world datasets found GraphLIME explanations more descriptive than those from existing explanation methods.
2 Related Work
Related work covers graph neural networks and two main families of neural-model explanation methods. It also motivates nonlinear explanations for complex GNN decision functions.
- 2.1 Graph Neural Networks: GNNs recursively combine neighborhood node features and graph structure to produce node embeddings for downstream tasks.
- 2.1 Graph Neural Networks: GraphSAGE aggregates permutation-invariant neighborhood information, while GAT uses attention mechanisms to weight important neighboring content.
- 2.2 Interpretability and Explanations for Neural Networks: Interpretability methods broadly use either simple proxy models learned locally or techniques that identify relevant computational components.
- 2.2 Interpretability and Explanations for Neural Networks: LIME explains classifier predictions with an interpretable local linear model, whereas gradient- and activation-based methods assign importance to neural features.
- 2.2 Interpretability and Explanations for Neural Networks: For complex GNN decision functions, Figure 2 contrasts a potentially inaccurate local linear approximation with a more precise nonlinear approximation.
3 Proposed Method: GraphLIME
GraphLIME explains GNN predictions by fitting a locally faithful, nonlinear interpretable model over an explaining node’s N-hop neighborhood. It uses HSIC Lasso to select representative features while accounting for feature–output dependence and redundancy.
- GraphLIME is a nonlinear, model-agnostic explanation framework that identifies an interpretable model over an explaining node’s subgraph.The framework is designed to provide locally faithful explanations for GNN predictions.
- Nonlinear Explanation Model: HSIC LASSO: GraphLIME pairs sampled neighbor feature vectors with GNN predictions and fits an interpretable model using HSIC Lasso.The prediction f(xi) serves as the label for the nonlinear explanation model.
- Sampling for Local Exploration by N-hop Network Neighbors: N-hop sampling captures neighboring nodes because GNN predictions aggregate both node features and graph-local information.The sampled neighborhood includes the explaining node’s local structural context and neighboring feature correlations.
- Interpretation of HSIC Lasso: HSIC Lasso favors features dependent on the output while its l1 regularizer promotes sparse explanations.The method uses normalized HSIC terms to measure dependence between features and predictions.
- Interpretation of HSIC Lasso: Redundant features are discouraged because strong dependence between feature pairs causes one of their coefficients to tend toward zero.The resulting coefficient vector is used to select the top-K explanatory features.
4 Experiments
The experiments evaluate GraphLIME against existing explanation methods on two graph datasets and two GNN models. They test noisy-feature filtering, trustworthiness judgments, and model selection.
- 4 Experiments: Experiments use Cora and Pubmed with GraphSAGE and GAT, sampling each explained node’s 2-hop neighborhood and splitting data 80%/20%.The comparison includes GraphLIME, LIME, GNNexplainer, Greedy, and Random procedures.
- 4.1 Setting: Ten artificial noisy features were added to samples, and explanations for 200 test samples were compared by their frequency of selected noisy features.The trained GraphSAGE and GAT models had test accuracy above 80%.
- 4.2 Does the explanation framework filter useless features?: GraphLIME and GNNexplainer rarely selected useless features, whereas LIME’s selected-noise distribution was mainly around 1 to 4.Greedy was only slightly better than LIME and Random, while GraphLIME and GNNexplainer were generally lower.
- 4.3 Do I trust this prediction?: GraphLIME achieved higher averaged F1-Score for trustworthy predictions than the other explanation methods across K = 10, 15, 20, 25.The authors interpret the higher F1-Score as reflecting both high precision and high recall.
- 4.4 Does the explainer help to identify the better model?: GraphLIME outperformed LIME and GNNexplainer in selecting the better classifier, while those methods were only slightly better than random choice.Selection accuracy was averaged over 200 rounds as the number of presented instances B varied from 5 to 30, and GraphLIME’s performance improved with more instances.
5 Conclusion
The conclusion presents GraphLIME as a model-agnostic, local, nonlinear explanation framework for GNNs. Experiments on two datasets and two GNN models support its use for filtering noisy features, assessing prediction trust, and identifying better classifiers, while future work broadens its explanation scope.
- 5 Conclusion: GraphLIME uses N-hop neighbors, predicted labels, and HSIC Lasso to capture nonlinear feature–prediction dependencies locally and produce finite feature explanations.The framework is model-agnostic and targets a particular node prediction.
- 5 Conclusion: Experiments on two real-world graph datasets and two GNN model types demonstrated GraphLIME’s effectiveness.The reported capabilities include filtering noisy features, selecting informative features, guiding trust judgments, and identifying the better classifier.
- 5 Conclusion: Future work targets explanations of structural graph patterns and explanations for sets of same-class nodes rather than only a single target node.The current framework is described as limited to explaining a single target node and not yet extended to important subgraph structure.
A. Proof of Eq. (3)
This appendix states the normalized empirical HSIC estimate and begins a trace-based derivation using a symmetric matrix A.
- A. Proof of Eq. (3): The normalized variant of the empirical HSIC estimate, NHSIC, is introduced from the definition and proof of HSIC.The passage signals the formal starting point for the appendix proof.
- A. Proof of Eq. (3): For the symmetric matrix A, F is written as tr(AAT) = tr(AA) before the subsequent derivation.This trace identity is used as an intermediate algebraic step.
B. Submodular Pick
Submodular Pick selects a small, diverse subset of instances whose GraphLIME explanations collectively cover important features. It computes feature importance from explanation coefficients and uses a greedy procedure because the selection problem is NP-hard.
- Motivation: Submodular Pick addresses the need to reduce many instance explanations to an inspectable subset.It considers both the global importance and diversity of explanation components.
- Explanation matrix: GraphLIME produces an explanation model and coefficient vector for each instance, which together form an explanation matrix W.The matrix represents each explanation component’s local importance across instances.
- Global importance: Feature j receives higher global importance when it appears in explanations for many different instances.The importance is computed from the explanation coefficients associated with the selected components.
- Coverage: The coverage score favors instance sets whose explanation components cover features broadly while avoiding redundant instances.It is defined using the explanation matrix W, global importance I, and instance set V.
- Greedy selection: Because the objective is NP-hard, Submodular Pick greedily adds the instance with the best incremental coverage until B instances are selected.The algorithm first computes GraphLIME explanations and feature importances, then iteratively updates the selected subset.