Source-linked AI summary
ProtGNN: Towards Self-Explaining Graph Neural Networks
Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, Cheekong Lee
TL;DR
Explaining GNN predictions is difficult because existing approaches are mainly post-hoc and may not reveal the model’s original reasoning. ProtGNN integrates prototype learning into GNN classification, with ProtGNN+ sampling similar subgraphs for interpretability and efficiency. The reported experiments show inherent interpretability with classification accuracy comparable to non-interpretable counterparts.
Problem
GNN predictions remain difficult to explain, while post-hoc explanations may not reveal the original reasoning process.
Method
ProtGNN compares input graphs with learned prototypes in latent space, and ProtGNN+ conditionally samples subgraphs most similar to each prototype.
Results
ProtGNN and ProtGNN+ provide built-in interpretability with classification accuracy comparable to non-interpretable counterparts.
Takeaways & Limitations
The models provide a human-intelligible reasoning process while retaining acceptable classification accuracy and time-complexity.
Takeaways & Limitations
The theoretical proof assumes equal numbers of prototypes per class and specified class-prototype connections in the final layer.
Abstract
from arXiv · showhide
Despite the recent progress in Graph Neural Networks (GNNs), it remains challenging to explain the predictions made by GNNs. Existing explanation methods mainly focus on post-hoc explanations where another explanatory model is employed to provide explanations for a trained GNN. The fact that post-hoc methods fail to reveal the original reasoning process of GNNs raises the need of building GNNs with built-in interpretability. In this work, we propose Prototype Graph Neural Network (ProtGNN), which combines prototype learning with GNNs and provides a new perspective on the explanations of GNNs. In ProtGNN, the explanations are naturally derived from the case-based reasoning process and are actually used during classification. The prediction of ProtGNN is obtained by comparing the inputs to a few learned prototypes in the latent space. Furthermore, for better interpretability and higher efficiency, a novel conditional subgraph sampling module is incorporated to indicate which part of the input graph is most similar to each prototype in ProtGNN+. Finally, we evaluate our method on a wide range of datasets and perform concrete case studies. Extensive results show that ProtGNN and ProtGNN+ can provide inherent interpretability while achieving accuracy on par with the non-interpretable counterparts.
Introduction
GNNs achieve strong performance on graph tasks, but their predictions remain difficult to explain, motivating models with built-in interpretability. ProtGNN addresses this gap by using prototype-based reasoning during classification while tackling graph-specific efficiency and visualization challenges.
- Motivation: GNN predictions remain difficult to explain, limiting trust and wider use in critical applications.The passage specifically highlights medical diagnosis as an example where understanding prediction rationales matters.
- Related methods: Existing GNN explanation methods select or infer explanations after a trained model has made its prediction.Examples include compact-subgraph selection through mutual information and surrogate Bayesian-network fitting.
- Core idea: Prototype learning offers built-in interpretability by comparing new instances with learned exemplar cases during prediction.The paper connects this case-based reasoning process to identifying functional subgraphs in molecular graphs.
- Challenges: Graph-specific prototype models face difficult projection and visualization because graph edges are discrete and graph structure is combinatorial.These properties also make it challenging to achieve both efficiency and high accuracy.
- Proposed approach: ProtGNN compares input graphs with learned prototypes, while ProtGNN+ conditionally samples similar subgraphs for improved interpretability and efficiency.Monte Carlo tree search is used to explore subgraphs for prototype projection and visualization.
- Evaluation: Extensive experiments report built-in interpretability with performance comparable to non-interpretable counterparts.
Related Work
GNNs learn graph representations through message passing and have been effective across graph tasks. Existing explanation approaches include several post-hoc families, while built-in interpretability is presented as more desirable for faithful, accurate models.
- GNN background: GNNs learn node or graph embeddings by aggregating neighboring representations through message passing.The background uses GCNs to illustrate this iterative representation-update paradigm.
- Explanation methods: Explanation methods for GNNs include gradients/features-based, perturbation-based, decomposition, and surrogate approaches.These categories use feature importance, prediction changes, decomposed terms, or interpretable surrogate models.
- Built-in interpretability: Existing approaches are post-hoc, whereas built-in interpretability is considered more desirable because post-hoc explanations may not fit the original model precisely.The paper therefore motivates models combining inherent interpretability with high accuracy.
The Proposed ProtGNN
ProtGNN builds interpretability into GNN classification by comparing graph embeddings with learned class prototypes, while ProtGNN+ additionally identifies similar input subgraphs. Prototype projection and conditional sampling make these explanations more human-intelligible and computationally practical, with sampling preserving correct predictions under a stated logit-margin condition.
- ProtGNN architecture: ProtGNN learns representative prototypes for each class and derives predictions by comparing new graph embeddings with those prototypes in latent space.The architecture uses a GNN encoder, prototype layer, and classification layer; similarity scores feed the output probabilities.
- Learning objective: Prototype-learning constraints combine classification loss with cluster, separation, and diversity objectives to support accuracy and interpretable prototypes.Cluster cost pulls embeddings toward same-class prototypes, separation cost pushes them away from other-class prototypes, and diversity discourages redundant prototypes.
- Prototype projection: Each learned prototype is projected onto the nearest same-class training subgraph, making the latent prototype interpretable as a human-intelligible graph pattern.Because graph subgraphs cannot feasibly be enumerated, projection uses Monte Carlo Tree Search over connected, small subgraphs.
- Prototype projection: MCTS balances exploration and exploitation when searching pruning actions, initially favoring under-visited nodes and eventually favoring actions with higher similarity scores.The search tree represents node-pruning actions, and each explored subgraph is evaluated through the GNN encoder and similarity function.
- Conditional subgraph sampling: ProtGNN+ conditionally samples prototype-specific subgraphs to show which input regions support each prototype, using a parameterized alternative to MCTS for efficient selection.The sampling module relaxes discrete graph selection for gradient-based optimization; its time complexity is O(|E|), though it requires additional training.
- Classification condition: If a correctly classified ProtGNN graph has top-two output-logit separation of at least 2mlog((1+δ)(2−δ)), ProtGNN+ also classifies it correctly.The result follows when subgraph sampling changes the graph embedding insufficiently to alter the correct prediction.
- Extensions: ProtGNN and ProtGNN+ generalize beyond graph classification to tasks such as node classification and link prediction.For node classification, the explanation target is the reasoning behind a node prediction based on its computation graph.
Experimental Evaluation
Experiments evaluate ProtGNN and ProtGNN+ across molecular, text, and synthetic graph datasets using multiple GNN backbones. The models provide prototype-based reasoning and interpretable subgraphs while maintaining comparable accuracy and acceptable training cost.
- Experimental Settings: Experiments cover molecule, sentiment, and synthetic datasets using GCN, GAT, and GIN variants.MUTAG and BBBP support graph classification, Graph-SST2 and Graph-Twitter represent sentiment graphs, and BA-Shape supports node classification.
- Classification Performance: ProtGNN and ProtGNN+ achieve comparable classification performance with the corresponding original GNN models.The comparison reports means and standard deviations from three independent runs on random data splits.
- Reasoning Process: ProtGNN+ bases decisions on prototype similarity and selects input subgraphs that most closely match class prototypes.Similarity scores are weighted and summed to produce the final class score, while selected subgraphs provide visual evidence.
- Reasoning Process: The case studies identify domain-relevant evidence, including a mutagenic NO2 group and carbon-ring fragment and the phrase “never worry about bored” for positive sentiment.The positive example also has larger similarity to positive prototypes such as “kind of entertainment love to have” than to negative prototypes such as “embarrassed by invention”.
- Prototype Visualization: ProtGNN prototypes occupy centers of BBBP graph-embedding clusters in t-SNE visualization, supporting the effectiveness of prototype learning.The visualization shows graph embeddings as dots and prototype embeddings as stars, with colors indicating classes.
- Efficiency: The conditional subgraph sampling module reduces ProtGNN+ training cost relative to MCTS-based sampling, while ProtGNN and ProtGNN+ remain more costly than GCN.The authors describe the remaining time cost as acceptable given the built-in interpretability.
Conclusion
ProtGNN and ProtGNN+ provide built-in, prototype-based explanations by incorporating similar graph patterns and subgraphs into prediction. Experiments report human-intelligible reasoning with acceptable classification accuracy and time complexity.
- Conclusion: ProtGNN compares inputs with learned prototypes, while ProtGNN+ identifies input subgraphs most similar to those prototypes.The subgraph module is designed to improve interpretability and efficiency.
- Conclusion: Extensive experiments show human-intelligible reasoning with acceptable classification accuracy and time complexity.
Dataset Statistics
The evaluation uses five datasets spanning biological, text, and synthetic data. Four datasets support graph classification, while BA-Shape supports node classification.
- Dataset Statistics: The five datasets include biological, text, and synthetic data.
- Dataset Statistics: The first four datasets are used for graph classification, whereas BA-Shape is used for node classification.
Proof of Theorem 1
Theorem 1 gives a sufficient margin condition under which ProtGNN+ preserves a correct ProtGNN classification after subgraph sampling. The proof bounds score changes for correct and incorrect classes under stated prototype and embedding assumptions.
- Assumptions: The theorem assumes equal numbers of prototypes per class and class-specific output connections that distinguish same-class from non-class prototypes.
- Assumptions: ProtGNN and ProtGNN+ share graph encoder f, with δ constrained by 0 < δ < 1 and embedding-distance assumptions for the correct class.
- Theorem: 2mlog((1+δ)(2−δ)) is the required top-two output-logit margin for ProtGNN+ to preserve a correct ProtGNN classification.
- Proof: The proof derives lower and upper bounds on summed prototype-contribution gaps for correct and incorrect classes.
Sampling Module
The conditional subgraph sampling module is documented as a distinct architecture component, with graph datasets and symmetric adjacency handling specified alongside it.
- The conditional subgraph sampling module uses deep neural networks to learn eij.
- The architecture specifies 128-dimensional node embeddings and prototypes, with E set to E+ET to ensure a symmetric adjacency matrix.
More Case Studies
Case studies on BBBP and Graph-Twitter illustrate how the method identifies class-relevant graph or phrase substructures during reasoning.
- The case studies cover BBBP and Graph-Twitter, with Graph-Twitter using three classes: negativeness, neutrality, and positiveness.
- For a positive Graph-Twitter input, the method captures the key phrase/subgraph “amazing lady gaga I love” leading to positiveness.
- The reported examples show ProtGNN+ identifying input regions associated with prototype-based classification decisions.
Hyper-parameters Analysis
The analysis examines prototype count and training losses, showing diminishing accuracy gains beyond five prototypes and important effects from diversity, clustering, and separation constraints.
- Choosing the Number of Prototypes per Class: Accuracy increases dramatically as the number of prototypes per class m increases, then its slope flattens after m exceeds 5.
- Choosing the Number of Prototypes per Class: The authors choose m = 5 because larger prototype counts make the model harder to train and comprehend while providing only marginal improvement.
- Diversity Regularization: Without diversity regularization, prototype cosine similarities are much larger and can approach 1, indicating nearly identical learned prototypes.
- Cluster and Separation Losses: The cluster and separation constraints affect ProtGNN performance, with λ1 = 0.10 and λ2 = 0.05 producing the best BBBP performance.