TL;DR
This paper introduces GATT, a novel method for interpreting Graph Neural Networks (GNNs) that use self-attention. By analyzing the "computation tree" of these models, GATT provides more faithful and accurate explanations of which graph edges are most important for a GNN's prediction, overcoming limitations of previous, simpler attribution methods.
What Problem Does This Paper Address?
Graph Neural Networks (GNNs) are powerful tools for analyzing graph-structured data, but like many deep learning models, they are often treated as "black boxes." To address this, researchers have explored using the self-attention mechanisms within certain GNNs (Att-GNNs) as a form of built-in explanation. The idea is that the attention weights, which indicate how much a model focuses on different parts of the input, can reveal important features. However, existing methods for extracting these explanations from Att-GNNs are often too simplistic, essentially averaging attention weights across layers. This "naïve" approach can lead to inaccurate or misleading interpretations, undermining the potential of attention for explaining GNN behavior. This paper aims to bridge this gap by proposing a more sophisticated method for deriving edge attributions from self-attention in GNNs.
Methods
The core of this paper is the introduction of GATT (Graph Attention Tree), a method for calculating edge attribution scores. GATT's novelty lies in its use of the computation tree viewpoint. A computation tree is a rooted tree that visualizes the flow of information within a GNN layer by layer, with the target node as the root.
GATT is guided by two key design principles derived from observing these computation trees:
- Proximity Effect (P1): Edges closer to the target node are generally more influential because they appear more frequently in the computation tree.
- Contribution Adjustment (P2): The contribution of an edge should be adjusted based on its position within the computation tree, considering the influence of subsequent edges in the path towards the root.
GATT integrates these principles by summing the attention weights of a target edge across all its occurrences in the computation tree, while also multiplying these weights by a factor that accounts for the attention weights of subsequent edges in the path. This ensures that the final attribution score reflects both the edge's presence and its downstream impact. The paper also proposes an efficient matrix-based computation for GATT, making it practical for large-scale applications.
Datasets
The paper evaluates GATT on several datasets:
- Synthetic Datasets: BA-Shapes and Infection. These are used for evaluating explanation accuracy against known ground truth.
- Real-World Citation Datasets: Cora, Citeseer, Pubmed, Cornell, Texas, Wisconsin, and Arxiv. These are used for evaluating the faithfulness of the explanations.
Key Insights and Ideas
- Computation Tree is Key: The paper argues that understanding the flow of information through a GNN's computation tree is crucial for accurate attention-based explanations, moving beyond simple layer-wise averaging.
- Beyond Raw Attention: Raw attention weights, while informative, are not direct explanations. They need to be processed through a framework like GATT to reveal meaningful attributions.
- Proximity and Position Matter: The two design principles (P1 and P2) highlight that both how often an edge appears (proximity) and its role in the information flow path (position) are critical for determining its importance.
- GATT is Hyperparameter-Free: A significant advantage of GATT is that it's a post-processing method that doesn't require additional training or hyperparameter tuning, making it easy to integrate.
Key Results
- Faithfulness: GATT consistently and substantially improves the faithfulness of edge attributions compared to AVGATT (a baseline averaging method) and random attribution across various datasets and GNN architectures (2-layer and 3-layer GAT/GATv2). For example, on the Cora dataset, GATT achieves a Pearson's coefficient of 0.9755 for APC, significantly higher than AVGATT's 0.7251.
- Explanation Accuracy: On synthetic datasets with ground truth explanations, GATT demonstrates superior performance. It often outperforms AVGATT and even several popular post-hoc explanation methods (like Saliency, Integrated Gradients, and GNNExplainer) in terms of AUROC scores. For instance, on the BA-Shapes dataset, GATT achieves an AUROC of 0.8477, while AVGATT is only 0.1768.
- Ablation Study: Removing either the proximity effect (P1) or the contribution adjustment (P2) in GATT variants (GATTsim and GATTavg) leads to a noticeable degradation in performance, validating the importance of both design principles.
- Efficiency: The proposed matrix-based computation for GATT is highly efficient, achieving up to 58.05 times faster runtime than PG-Explainer for edge attribution calculation on 10,000 nodes.
Limitations and Future Work
- Focus on GAT/GATv2: While the paper claims GATT is generally applicable to Att-GNNs, the primary empirical validation is on GAT and GATv2 models. Further exploration with other Att-GNN architectures could be beneficial.
- Interaction of Attention Designs: The paper acknowledges that a systematic analysis of how different attention weight designs (e.g., multi-head attention, different normalization schemes) interact with GATT is left for future work.
- Graph Transformers: The study explicitly excludes graph transformers, which have already been extensively analyzed for explainability. Future work could explore extending GATT's principles to these architectures.
Summary updated