Research map / Graph learning / GNN architectures

Faithful and Accurate Self-Attention Attribution for Message Passing Neural Networks via the Computation Tree Viewpoint

AAAI 2025 · Graph learning › GNN architectures · approach: Graph rewiring and scalable message passing · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes GAtt, a training-free method that derives edge attributions from GAT-style attention weights by aggregating attention flows over the computation tree, and shows it is more faithful and accurate than naive layer-averaged attention.

Problem

Naive use of attention weights (layer-wise averaging) as edge explanations in attention-based message passing GNNs (Att-GNNs) is unfaithful and inaccurate, undermining attention's potential as an interpretation.

Approach

Edge attribution is computed by summing attention weights over all occurrences of an edge in the computation tree, each re-weighted by the product of attention weights on the path toward the target node (proximity effect and contribution adjustment); a matrix form makes it deterministic and hyperparameter-free.

Key results

• On Cora 2-layer GAT, GAtt achieves Delta_PC Pearson 0.8468 versus 0.1764 for AvgAtt.
• On Infection with GAT, GAtt reaches AUROC 0.9976, above all post-hoc baselines such as IG (0.9472) and GNNExplainer (0.9272).
• GAtt is up to 58.05x faster than PGExplainer when computing attributions for 10,000 nodes.

Measured effects reported in the paper

Surprising findings

• On BA-Shapes, GAtt tends to emphasize edges closer to the target even within house motifs, a pitfall noted in prior work.
• Simple layer-wise averaging of attention (AvgAtt) sometimes performs worse than random attribution on confidence-change metrics.

Limitations

• Only single-head node-level experiments are presented in the main text; multi-head and graph-level results are in appendix.
• Does not analyze how different attention weight designs interact with GAtt.
• Evaluated only on GAT, GATv2 and SuperGAT; graph transformers are out of scope.

Experimental setup

Datasets: BA-Shapes Infection Cora Citeseer Pubmed Arxiv Cornell Texas Wisconsin

Benchmarks: BA-Shapes Infection Cora Citeseer Pubmed Arxiv Cornell Texas Wisconsin

Metrics: Pearson correlation for Delta_PC and Delta_NE AUROC for Delta_P AUROC for explanation accuracy

Baselines: AvgAtt Random Saliency Guided Backpropagation Integrated Gradients GNNExplainer PGExplainer GraphMask FastDnX

Builds on: GAT GATv2 SuperGAT attention rollout

Closest papers by meaning

• Evaluating Attribution for Graph Neural Networks (NeurIPS 2020 · similarity 0.87)
• Self-Interpretable Graph Learning with Sufficient and Necessary Explanations (AAAI 2024 · similarity 0.86)
• Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective (ICML 2025 · similarity 0.86)
• GOAt: Explaining Graph Neural Networks via Graph Output Attribution (ICLR 2024 · similarity 0.85)
• Redundancy Undermines the Trustworthiness of Self-Interpretable GNNs (ICML 2025 · similarity 0.85)
• How to Probe: Simple Yet Effective Techniques for Improving Post-hoc Explanations (ICLR 2025 · similarity 0.85)