Research map / Graph learning / GNN architectures
GraphTrail: Translating GNN Predictions into Human-Interpretable Logical Rules
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 GraphTrail, an end-to-end global post-hoc GNN explainer that mines Shapley-ranked computation-tree concepts and fits boolean formulas over them via symbolic regression to translate GNN predictions into logical rules.
Problem
Global explanation of graph neural networks: existing explainers are instance-level or depend on instance explainers, and fail to recover the combinatorial logic a GNN learns over subgraph concepts across a dataset.
Approach
Reduce the subgraph concept space to unique computation trees of a message-passing GNN, rank them with Shapley values using negated cross-entropy as the value function, and map the top-k concept vectors to a boolean formula per class via evolutionary symbolic regression over AND, OR, NOT and XOR.
Key results
- Average fidelity on BAMultiShapes 0.87 ± 0.02 for GraphTrail vs 0.48 ± 0.02 for GLGExplainer; on MUTAG 0.82 vs 0.74.
- Across GNN architectures and pooling layers, GraphTrail fidelity on BAMultiShapes reaches up to 1.00 (GAT, SUM) vs 0.93 for GLGExplainer.
- Random computation-tree selection drops fidelity to 0.54 on BAMultiShapes vs 0.86 with Shapley-based selection.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace GLGExplainer with GraphTrail | global GNN explanation · BAMultiShapes | fidelity: 0.48 ± 0.02 -> 0.87 ± 0.02 | Helped |
| replace GLGExplainer with GraphTrail | global GNN explanation · MUTAG | fidelity: 0.74 ± 0.10 -> 0.82 ± 0.09 | Helped |
| replace GLGExplainer with GraphTrail | global GNN explanation · Mutagenicity | fidelity: 0.62 ± 0.03 -> 0.72 ± 0.01 | Helped |
| replace GLGExplainer with GraphTrail | global GNN explanation · NCI1 | fidelity: 0.57 ± 0.04 -> 0.72 ± 0.02 | Helped |
| use exact rather than sampling-based Shapley computation (ablation) | GraphTrail · BAMultiShapes | fidelity: 0.86 ± 0.01 -> 0.87 ± 0.02 | Helped |
| use exact rather than sampling-based Shapley computation (ablation) | GraphTrail · MUTAG | fidelity: 0.78 ± 0.08 -> 0.82 ± 0.09 | Helped |
| use exact rather than sampling-based Shapley computation (ablation) | GraphTrail · Mutagenicity | fidelity: 0.72 ± 0.01 -> 0.72 ± 0.01 | No clear effect |
| use exact rather than sampling-based Shapley computation (ablation) | GraphTrail · NCI1 | fidelity: 0.72 ± 0.02 -> 0.72 ± 0.02 | No clear effect |
| select concepts using Shapley values rather than at random (ablation) | GraphTrail · BAMultiShapes | fidelity: 0.54 ± 0.03 -> 0.86 ± 0.02 | Helped |
| select concepts using Shapley values rather than at random (ablation) | GraphTrail · MUTAG | fidelity: 0.68 ± 0.04 -> 0.82 ± 0.09 | Helped |
| select concepts using Shapley values rather than at random (ablation) | GraphTrail · Mutagenicity | fidelity: 0.55 ± 0.01 -> 0.72 ± 0.01 | Helped |
| select concepts using Shapley values rather than at random (ablation) | GraphTrail · NCI1 | fidelity: 0.54 ± 0.02 -> 0.72 ± 0.02 | Helped |
Surprising findings
- GLGExplainer's reported Mutagenicity results appear inflated by test data leakage from excluding training graphs lacking NO2/NH2 motifs when generating explanations.
- GLGExplainer clusters of instance explanations are impure, with graphs in the same cluster often structurally dissimilar.
Limitations
- Cannot capture multiplicity of a concept's occurrence within a graph; only presence or absence.
- Concepts lowered to computation-tree level are mapped back to subgraphs, which trades off interpretability against faithfulness to GNN computation.
- Shapley computation is a computational bottleneck on datasets with many graphs, motivating GraphTrail-S.
Experimental setup
Datasets: BAMultiShapes MUTAG Mutagenicity NCI1
Benchmarks: BAMultiShapes MUTAG Mutagenicity NCI1
Metrics: fidelity precision recall F1-score accuracy vs ground truth
Baselines: GLGExplainer GLGExplainer-iso GraphTrail-S
Builds on: GLGExplainer PGExplainer SHAP (Kernel-SHAP) symbolic regression evolutionary algorithm (PySR-style)
Closest papers by meaning
- The Graph Concept Bottleneck: Decoding Combinatorial Reasoning in GNNs for Interpretability (NeurIPS 2026 · similarity 0.92)
- Global Explainability of GNNs via Logic Combination of Learned Concepts (ICLR 2023 · similarity 0.92)
- Self-Interpretable Graph Learning with Sufficient and Necessary Explanations (AAAI 2024 · similarity 0.91)
- Stratified GNN Explanations through Sufficient Expansion (AAAI 2024 · similarity 0.90)
- Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective (ICML 2025 · similarity 0.90)
- Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks (ICLR 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.