Research map / Graph learning / GNN architectures
GnnXemplar: Exemplars to Explanations - Natural Language Rules for Global GNN Interpretability
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 GnnXemplar, a global GNN explainer that selects exemplar nodes via greedy reverse-kNN coverage maximization and uses self-refining LLM prompts to turn exemplar neighborhoods into natural-language rules.
Problem
Global explanation of GNN node classification on large, attributed graphs, where motif-based global explainers designed for small graph classification break down.
Approach
Identify representative nodes (exemplars) in the GNN embedding space by greedy coverage maximization over reverse k-nearest neighbors, then derive natural-language boolean rules per exemplar with a self-refine LLM loop (generate code, get feedback on misclassified nodes, refine), and OR them into class-level explanations.
Key results
- GnnXemplar achieves fidelity of 0.83 on TAGCora, 0.92 on Citeseer, 0.78 on WikiCS, 0.84 on ogbn-arxiv, versus at most 0.56 for baselines where they produce output.
- In a 60-participant user study (300 A/B comparisons), text explanations were preferred 200 vs 100 over subgraph visualizations (binomial p<0.0001; McNemar p=0.0001).
- Baselines such as GCNeuron and GLGExplainer run out of memory on several large datasets, while GLGExplainer produces no formula on TAGCora and Citeseer.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Rev-k-NN exemplar selection instead of equal-sized random exemplar selection (ablation) | GnnXemplar · node-classification benchmarks | fidelity | Helped |
| Use iterative self-refinement instead of zero-shot rule generation (ablation) | GnnXemplar · all datasets | fidelity | Helped |
| Increase Rev-k-NN neighborhood size from 1 to 5 (ablation) | GnnXemplar · WikiCS | fidelity: 0.72 to 0.78 | Helped |
| Increase Rev-k-NN neighborhood size from 5 to 20 or 100 (ablation) | GnnXemplar · WikiCS | fidelity: 0.72 at 20, 0.69 at 100 | Hurt |
| Increase Rev-k-NN neighborhood size from 5 to 100 (ablation) | GnnXemplar · Questions | fidelity: 0.92 at k=5; 0.86 at k=100 | Hurt |
| Use a training sample size of 20 rather than smaller or excessively large samples (ablation) | GnnXemplar self-refinement · WikiCS | fidelity: 0.78 | Helped |
| Use a training sample size of 20 rather than smaller or excessively large samples (ablation) | GnnXemplar self-refinement · Questions | fidelity: 0.92 | Helped |
| Compute Rev-k-NN prototypes using 5–10 % of nodes rather than full sampling (ablation) | GnnXemplar exemplar selection · WikiCS and Questions | runtime: 0.7 s → 690 s on WikiCS; 0.01 s → 41.6 s on Questions | Helped |
| Present explanations as text rather than subgraph visualizations | GnnXemplar explanations · user preference across five A/B test questions | preference for text: 200/300; p-value <0.0001 | Helped |
| Apply GnnXemplar to TAGCora using GAT rather than GraphSAGE backbone | GnnXemplar · TAGCora | fidelity: 76.75 to 83.00 | Helped |
Surprising findings
- High-fidelity explanations on Questions (0.92) coexist with a rule for the inactive class that points to homophily, which reflects a GNN failure mode (misclassification of inactive nodes) rather than an explanation error.
- Explanations for the user study were deliberately made feature-neutral (structure only) to control for content differences between modalities.
Limitations
- Operates only with access to GNN embedding space, so no fine-grained mechanistic understanding of feature-topology interactions.
- Fidelity is measured on the GNN predictions only and rule quality depends on LLM output; results shown with a single LLM (gemini-1.5-flash).
Experimental setup
Datasets: TAGCora Citeseer WikiCS ogbn-arxiv Amazon-ratings Minesweeper Questions BA-Shapes
Benchmarks: TAGCora Citeseer WikiCS ogbn-arxiv Amazon-ratings Minesweeper Questions BA-Shapes
Metrics: fidelity precision recall F1 runtime
Baselines: GNNInterpreter GCNeuron GLGExplainer
Builds on: Exemplar Theory Self-Refine GLGExplainer GNNInterpreter GCNeuron
Closest papers by meaning
- Stratified GNN Explanations through Sufficient Expansion (AAAI 2024 · similarity 0.90)
- EiG-Search: Generating Edge-Induced Subgraphs for GNN Explanation in Linear Time (ICML 2024 · similarity 0.89)
- COMRECGC: Global Graph Counterfactual Explainer through Common Recourse (ICML 2025 · similarity 0.89)
- Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective (ICML 2025 · similarity 0.89)
- Higher Order Structures for Graph Explanations (AAAI 2025 · similarity 0.88)
- GNNX-BENCH: Unravelling the Utility of Perturbation-based GNN Explainers through In-depth Benchmarking (ICLR 2024 · similarity 0.88)
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.