# GnnXemplar: Exemplars to Explanations -- Natural Language Rules for Global GNN Interpretability

arXiv: https://arxiv.org/abs/2509.18376 · HTML: https://mlsanity.com/paper/2509.18376/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 57 references that are in the map.
- First posted on arXiv 22 Sep 2025.

## Builds on (most cited first, 30 of 39)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networks](https://mlsanity.com/paper/2007.02901/) (2020)
- [One for All: Towards Training One Graph Model for All Classification Tasks](https://mlsanity.com/paper/2310.00149/) (2023)
- [XGNN: Towards Model-Level Explanations of Graph Neural Networks](https://mlsanity.com/paper/2006.02587/) (2020)
- [PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2010.05788/) (2020)
- [GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2001.06216/) (2020)
- [Explainability Techniques for Graph Convolutional Networks](https://mlsanity.com/paper/1905.13686/) (2019)
- [Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking](https://mlsanity.com/paper/2010.00577/) (2020)
- [Higher-Order Explanations of Graph Neural Networks via Relevant Walks](https://mlsanity.com/paper/2006.03589/) (2020)
- [Generative Causal Explanations for Graph Neural Networks](https://mlsanity.com/paper/2104.06643/) (2021)
- [Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoning](https://mlsanity.com/paper/2202.08816/) (2022)
- [Global Explainability of GNNs via Logic Combination of Learned Concepts](https://mlsanity.com/paper/2210.07147/) (2022)
- [GraphSVX: Shapley Value Explanations for Graph Neural Networks](https://mlsanity.com/paper/2104.10482/) (2021)
- [RelEx: A Model-Agnostic Relational Model Explainer](https://mlsanity.com/paper/2006.00305/) (2020)
- [Entropy-based Logic Explanations of Neural Networks](https://mlsanity.com/paper/2106.06804/) (2021)
- [GStarX: Explaining Graph Neural Networks with Structure-Aware Cooperative Games](https://mlsanity.com/paper/2201.12380/) (2022)
- [GNNInterpreter: A Probabilistic Generative Model-Level Explanation for Graph Neural Networks](https://mlsanity.com/paper/2209.07924/) (2022)
- [Global Concept-Based Interpretability for Graph Neural Networks via Neuron Analysis](https://mlsanity.com/paper/2208.10609/) (2022)
- [Global Counterfactual Explainer for Graph Neural Networks](https://mlsanity.com/paper/2210.11695/) (2022)
- [How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension](https://mlsanity.com/paper/2410.05298/) (2024)
- [DAG Matters! GFlowNets Enhanced Explainer For Graph Neural Networks](https://mlsanity.com/paper/2303.02448/) (2023)
- [Task-Agnostic Graph Explanations](https://mlsanity.com/paper/2202.08335/) (2022)
- [Distill n' Explain: explaining graph neural networks using simple surrogates](https://mlsanity.com/paper/2303.10139/) (2023)

## Built on by (most cited first, 2 of 2)

- [Exploring Concept Subspace for Self-explainable Text-Attributed Graph Learning](https://mlsanity.com/paper/2604.11986/) (2026)
- [Controllable GNN Explanations via Multi-Metric Preference Selection](https://mlsanity.com/paper/2609.32436/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are widely used for node classification, yet their opaque decision-making limits trust and adoption. While local explanations offer insights into individual predictions, global explanation methods, those that characterize an entire class, remain underdeveloped. Existing global explainers rely on motif discovery in small graphs, an approach that breaks down in large, real-world settings where subgraph repetition is rare, node attributes are high-dimensional, and predictions arise from complex structure-attribute interactions. We propose GnnXemplar, a novel global explainer inspired from Exemplar Theory from cognitive science. GnnXemplar identifies representative nodes in the GNN embedding space, exemplars, and explains predictions using natural language rules derived from their neighborhoods. Exemplar selection is framed as a coverage maximization problem over reverse k-nearest neighbors, for which we provide an efficient greedy approximation. To derive interpretable rules, we employ a self-refining prompt strategy using large language models (LLMs). Experiments across diverse benchmarks show that GnnXemplar significantly outperforms existing methods in fidelity, scalability, and human interpretability, as validated by a user study with 60 participants.