GnnXemplar: Exemplars to Explanations - Natural Language Rules for Global GNN Interpretability
Authors: Burouj Armgaan
Eshan Jain
Harsh Pandey
Mahesh Chandran
Sayan Ranu
Venue: NeurIPS 2025 oral ()
Keywords: graph neural network
graph machine learning
explainability
xai
global explanation
text-based explanation
exemplar
exemplar theory
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We generate global text-based explanations using representative nodes (exemplars) in the embedding space. The exemplars are selected via coverage maximization, and their signatures are explained using natural language rules from a self-refining LLM.

Abstract: 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.

GNNXEMPLAR: Exemplars to Explanations Natural
Language Rules for Global GNN Interpretability
Burouj Armgaan Dept. of CSE, IIT Delhi cs22280010iitd.ee in
Eshan Jain Dept. of CSE, IIT Delhi eshan2928gmail.com com
Harsh Pandey
Fujitsu Research of India, Bangalore Harsh, pêfujitsu. com
Mahesh Chandran
Sayan Ranu
Fujitsu Research of India, Bangalore
Dept. of CSE and Yardi ScAL, IIT Delhi sayanramuGiitd.cc ac.
Mahesh. Chandran thandran@fujji an@fujitsu. com
Abstract
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 char- acterize an entire class, remain underdeveloped. Existing global explainers rely on motif discovery in small graphs, an approach that breaks down large, real-world settings where subgraph repetition is rare, node attributes high-dimensional, and predictions arise from complex structure-attribur interactions. GNNXEMPLAR, novel global explainer inspired from Exemplar Theory from cognitive science. GNNXEMPLAR identifies representative nodes in the GNN em- bedding space, exemplars, and explains predictions using natural language rules derived from their neighborhoods. Exemplar selection is framed as a coverage maximization problem
propose
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 (LLMMs). Experiments across diverse benchmarks show that GNNXEMPLAR significantly outperforms existing methods in fidelity, scalability, and human interpretability, validated by user study with 60 participants.
Introduction and Related Works
Node classification using Graph Neural Networks (GNNs) has found wide-ranging applications across diverse domains. including protein function prediction [13, 30], user profiling [47, 11]. and fraud detection [22]. Despite their success, GNNS, like other deep learning models, are often re- garded black boxes: they achieve high performance, but the reasoning behind their predictions remains largely opaque. To address this, GNN explainers aim to illuminate the decision-making process by identifying the substructures and features in the input graph that the model relies on for its predictions [1. 2, 48, 24, 39, 18, 42, 16, 17].
1.1 Existing Works and Open Challenges
Existing methods for GNN explanation be broadly categorized into two types: local and global. Fig. 4 in the Appendix provides the detailed taxonomy.
1. Local explanations focus on individual predictions. They aim to explain why a specific in- put graph (or node) received particular label. While informative, these explanations are often instance-specifie and do not generalize beyond the particular case being analyzed.
contrast, seek to uncover general patterns that apply across multiple instances. They aim to explain the conditions under which a GNN assigns any input to particular class, producing a single, interpretable explanation per class.
Global explanations,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

While local explanation techniques are relatively mature, global GNN explainers remain an emerging area of research, as evident from Fig. 4. In this work, we advance this direction by proposing a global explanation framework for node classification based on exemplar theory [28].
Exemplar theory, rooted in cognitive psychology, explains how humans categorize objects and ideas. It posits that individuals make category judgments by comparing new stimuli with previously en- countered instances, called exemplars, stored in memory. These exemplars are not arbitrary; they tend to represent typical members of category [28]. A new stimulus is assigned to a category based on the number and degree of similarities it shares with exemplars from that category.
We adapt this idea to GNN-based node classification by treating certain representative nodes in the embedding space exemplars: nodes that encapsulate the characteristics of many others in the same class. For each exemplar, we extract an interpretable signature describing the distribution of features and/or structural patterns that characterizes the exemplar and the population of nodes it represents in the embedding space. Then, for any unseen node, we explain the GNN 's prediction by referencing the signature of the exemplar it most closely resembles. This approach enables global yet instance-relevant explanations grounded in learned graph structure and semantics.
Existing global GNN explainers [50, 42, 51, 45, 1, 2, 25] have primarily targeted graph classification tasks on small-scale datasets such as molecular graphs. These methods typically aim to identify recurring substructures, commonly referred to as motifs or concepts, that the GNN being explained detects to classify graphs [50, 42, 51, 45, 25] Some explainers [1. 2] go further by constructing the Boolean logic rules over motifs that aligns with the model's predictions. However, these motif-based explanation strategies face significant challenges when extended to node classi- fication in large, real-world graphs with rich node attributes (Ex. citation and linked documents, financial networks, etc.)
Open Challenges:
Attribute- Attribute-oopology Interaction: In large graphs, GNN predictions are typically complex func- tion of both the graph structure and high-dimensional node attributes. This makes motif discovery difficult because the classical definition of a motif, grounded in graph isomorphism, handles only discrete node labels. Moreover, in real-world graphs, the repetition of the exact same subgraph with identical node attributes rare, making the very notion of a motif ambiguous. This calls for shift from exact, symbolic subgraph matching to an approximate space where repetitions of structurally and semantically similar patterns can be meaningfully observed. We address this by identifying recurring combinations of structure and attributes not in the raw input graph but in the GNN embedding space by locating dense neighborhoods.
Computational Complexity: Motif discovery involves solving the subgraph isomorphism prob- lem, which is NP-hard, making them prohibitively expensive on large graphs. The problem is further exacerbated when accounting for both topology and node attributes. Consequently, as we will show later in $ 4, existing global GNN explainers often fail to scale on large graphs.
Cognitive and Visual Overload: In small graphs, like molecules, motifs (e.g., functional groups) are compact and human-interpree inmaaninterpretable. However, in large real-world graphs, even the 2-hop neigh- borhood of node can include hundreds or thousands of nodes. Visualizing interpreting such patterns quickly becomes unwieldy and exceeds human cognitive limits.
1.2 Contributions
In this work, we present GNNXEMPLAR, which addresses the limitations outlined above.
Effective explanations of GNN predictions must satisfy two key criteria: (1) they should be faithful, meaning they accurately reflect the model's decision-making process, and (2) they should be interpretable, allowing humans to understand the reasoning behind predic- tions despite the underlying complexity of the graph modality. To address these dual objectives, we take inspiration from Exemplar Theory [28]. Exemplar theory posits that humans categorize new instances by comparing them representative examples (exemplars) previously encountered. By adapting this principle, we explain the GNN 's prediction for a node by referencing similar, representative nodes in the embedding space - its exemplars. Furthermore, to enhance inter- pretability, we move beyond subgraph visualizations which are inherently ineffective in large, dense graphs due to their complexity and scale. Instead, we distill the defining characteristics of each exemplar and its associated population into textual explanations. This shift to natural language enables more accessible and cognitively manageable insights into the GNN 's decision- making process. We validate this claim through a user survey ($ 4.7).
Problem formulation:

---

Novel methodology: We develop GNNXEMPLAR, which integrates several innovative compo- nents. First. exemplar identification cast as a coverage maximization problem over reverse k-nearest neighbor relationships. We prove that this problem is NP-hard and submodular, and accordingly propose greedy algorithm with a (1 =) approximation guarantee to the optimal solution. To uncover the signature characteristies of each exemplar and the population it rep- resents, we leverage LLMs to iteratively propose and refine interpretable logical rules that are consistent with the GNN'S predictions.
Empirical analysis: We conduct extensive experiments on a diverse suite homophilous and heterophilous graphs. Our analysis reveals that: (1) existing GNN explainers inadequate for node classification on large graphs with complex node attributes; (2) GNNXEMPLAR provides figh-fidelity explanations of GNN predictions; and (3) the text-based explanations are preferred over subgraph visualization, as validated through a user study involving 60 participants.
Preliminaries and Problem Formulation
Definition 1 (Graph). A graph is defined G (V,E,X) over node set V, edge set & = {(u, v) u v & V} and node altributes X = =xx= E V} where X E Rd is the set of features characterizing each node.
(Node Classification). In node classification, are given single input graph = (V,EX),, where a subset of nodes Ver C is associated with known class labels from the set (y,,... -Yo)- The objective is train a GNN model t such that, for any node v V Van, the prediction error of its class label is minimized.
Definition 2
Error may be measured using known metries such as cross-entropy loss, negative log- biglliiel,ood,, etc.
Definition 3 (Exemplars). Exemplars refer representative nodes within the graph that embody prototypical structural and attribute characteristies shared by many other nodes in the same class. In the context of node classification, these exemplars serve as anchors for human-unde uumaan-nndrstandable explanations. Each exemplar, e, is associated with subset of training nodes, R. S Vtr. which represents the population that e exemplifies. node e E Vrr called an exemplar for the class E y if Rel Z T, where
((e) =
Rs U VEV
( C,
d(ze, 20) S
where: 2, E E is the GNN-learned embedding of node d(ze, zw) is some distance function, IR is a distance threshold, and E is a minimum population size hyperparameter.
As we will see later, the thresholds will automatically be discovered from the data by exploiting the k-nearest neighbor relationship along with greedy selection algorithm.
Definition 4 (Exemplar Signature). The signature of exemplar denoted as o is boolean for- mula composed of interpretable conditions over the structural and attribute properties of the local neighborhood of e. This formula is constructed such that its truth value approximates & predic- tions over Ra, i.e., with high probability Ve Rey; (v( = ((v). The signature oa of exemplar from class is a boolean function [ (T())),,)()......(((() (v))
E {0, 1}, such that, with high probability, Vo Re(a 1, iff ((v) = c. Here, n; are the predicates that evaluate Boolean conditions over interpretable properties such as:
Node features (e.g., [age 30)
Local structure (e.g., degree(v) 2 3)
Neighborhood composition (e.g. fractionClasstee hop 1, ) 0.6)
For instance, exemplar of fraudulent nodes in a transaction graph, might be account that makes frequent, low-value transfers to many recently created accounts that show no further activity. Assuming each node has attributes indicating the average transaction value and average frequency of transactions per week, its signature could rule like: "Has an average transaction amount below $100, performs more than 10 transactions per week, and is dissimilar in transaction frequency from the majority of its neighbors"
Problem (Global GNN Explanation through Exemplar Signatures). Let T be a trained GNN that assigns to each node u E V class label from (Vr," .....,lle .ee). For each class yo let & S V denote
3

---

Iet the
GNN
Find IKNKA
Graph
Embeddinga
Distances
HNN
cover
Signaturea
Bolf
Exemplara
HKNN seis
Figure 1: The pipeline of GNNXEMPLAR.
selected set of exemplar nodes that are representative of class yı and let de be the boolean signature associated with exemplar &
The goal is to construct global explanation in the form of a Boolean formula fü for each class yo such that:
Se(v) = V oe(v)
eEE.
where, Yo E Vtr: F(u) - + [+)) = TRUE. Each Si serves as the global explanation for class
ye built by aggregating exemplar-level signatures via logical OR. Each exemplar signature free to use all Boolean operators.
The formulation of explanation through exemplars presents two central challenges:
1. How do identify optimal set of exemplars? Exemplar selection is combinatorial op- timization problem over the space of all nodes the graph. Choosing too many exemplars compromises both interpretability and computational efficiency. small, well-chosen exemplar set enables concise global explanations, as the final explanation takes the form of disjunction over exemplar-specific rules.
2. How do we derive boolean logic signatures for each exemplar? The space of candidate logical expressions, composed of node attributes and structural features, is exponentially large, rendering exhaustive search intractable. Additionally, these rules must strike a balance between fidelity to the GNN's predictions and human interpretability. A further challenge arises from the need to express these logical rules as natural language descriptions requiring semantic precision.
3 Methodology
Fig. 1 presents the pipeline of GNNXEMPLAR. There are two distinct components: first, we identify a budget-constrained set of exemplars, next, we extract boolean rules, expressed in natural language, through iterative self-refining using LLM. We next detail each of these steps.
3.1 Exemplar Identification.
GNNXEMPLAR aims to identify set of b exemplar nodes that optimally represent the full training set; is a tunable This selection process is guided by two critical criteria:
balancing complexity of the explanation with higher expressivity.
Representativeness: Each exemplar node should close large number of other nodes shar- ing the same GNN- predicted class label in the embedding space, thereby capturing common struc- tural and attribute patterns learned by the model. We quantify representativeness using the notion of reverse k-nearest neighbors (S 3.2) in the GNN embedding space. Specifically, if node ap- pears frequently the k-NN sets other nodes with the same predicted label, considered representative of those nodes' learned semantics. Such nodes are prioritized for inclusion in the exemplar set, as they enable coverage of large regions of the embedding space and are likely to approximate the model's 's behavior over similar instances.

---

Diversity: The selected exemplars should be well spread out in the GNN embedding space to ensure a wide range of model behaviors are covered ($ 3.3).
By jointly optimizing for representativeness and diversity, GNNXEMPLAR ensures that the selected exemplars collectively span broad range of the model's learned representations.
3.2 Quantifying Representativenes: through Reverse k-NN
The representative power of a node defined as follows.
Definition (Reverse k-NN and Representative Power). Let h, denote the GNN embedding of node v. The k nearest neighbors of node u, denoted as k-NN(u), are the nodes from the train set with embeddings closest to h, and sharing the same GNN predicted class label (we use L2 distance, but other distances may also be used). The reverse k-NN of node v is the set of nodes for which appears in their k-NN set. Formally,
Rev-k-NN(o) = {u Ver k-NN(u), 2(0) $(u))
The representative power of node is then defined
(Rv---NN(())
II(1)= H VTr 2(6) {())
A high value of [I(r) indicates that node frequently appears in the k-NN sets of many other nodes, implying it resides in a dense region of the embedding space and captures shared representational
characteristics. Thus, is a strong candidate for inclusion in the exemplar set.
3.2.1 Sampling for Scalable Computation of Reverse k--N
Computing the nearest neighbors for each node consumes (n log k) x (()) time, since < n and n |Verl is the number of nodes. Thus, computing k-NN for all nodes and then constructing the Rev-k-NN requires O(n2) time, which becomes prohibitively expensive on large-scale graphs.
To address this, adopt sampling-based strategy that enables scalable approximation of reverse k-NN with thcoretical [12]. Let S C Vor be a uniformly sampled subset 2 < n nodes. We compute the k-NN only for nodes in S, which reduces the computational cost to O(z)).
We then define the approximate reverse k-NN of a node v E Ver as Rev-k-NN(u) = {u E S u k-NN(u), @(u) = ((u)). Hence, the approximate representative power of is
(Rev-k-NN())
fī(v) = Hu E S ((v) = {(u))
Here, [T()) estimates how broadly node v is retrieved as a nearest neighbor across the sample set. The sample size controls the trade-off between accuracy and efficiency. Leveraging Chernoff bounds, we establish that even a small & yields high-confidence approximations:
Lemma 1. Given error threshold 0 and confidence level 5, it suffices to sample 2
la (2)22)) nodes to ensure that for any u E Vtr, P ((T(w)) mTv)) s 2
PROOF, See App. A.3.
This result has two key implications:
The required number of samples is independent of the number of nodes in the train set, i.c., V-rl- Since a scales logarithmically with In(1/5), even small sample ensures high-probabilig bounds. Thus, the overall computation cost for reverse k-NN be comes O(n) instead of (n?)).
While we use the notations Rev-k-NN (v) and II(v) in the subsequent discussion, approximate vari- ants via sampling may be used in practice. We evaluate the quality-efficiency trade-off in App. $A.7.
3.3 Coverage Maximization
We aim to identify subset of exemplar nodes that collectively offer the broadest coverage over the training set in the GNN embedding space.
5

---

Algorithm Greedy Node Selection
Require: Graph budget Bex-k-NN sets of nodes
Ensure: exemplar set & of size
1: 4- 0
2: while [A] < do
3: t- arg max ITA (x]) (TAA)
4: +- & {o
5: Return
Definition 6 (Exemplar Set). Let the representative power of a set of exemplar nodes A V be
defined as:
/
IIAA=
U Rev-k-NN(U)
|
(1)
IEEA
Here, Rev-k-NN(v) denotes the reverse k nearest neighbors of node v in the GNN embedding space.
Given a node set V and budget b, we seek a subset of train nodes & E Ver of size b that maximizes:
A
arg
max
I1(A)
(2)
& Ver.lAl=b
Theorem 1. Maximizing the representative power Eq. is Na-hard.
PROOF. See App. A.4 for a reduction from the classic Set Cover Problem [5].
Fortunately, the objective (T) monotone and submodular, making it amenable to greedy approx- imation.
Theorem 2. The greedy algorithm (Alg. 1) guarantees llAggreedy)) 2 (1 2) II(A)).
PROOF. App. A.5 shows the monotonicity and submodularity of [I(A). An analogous proof for the case using the approximate Rev-KNN is provided in App. A.6.
Alg. 1 iteratively selects nodes that maximize marginal gain in coverage. By exploiting the transi- tivity of proximity in the embedding space, this greedy strategy avoids redundancy: if two nodes share most of their reverse k-NN sets, selecting one reduces the marginal utility of the other. Thus, the algorithm promotes both coverage and diversity within the budget.
3.4 Discovery of Exemplar Signatures
Our goal is analyze the embeddings of an exemplar node and its Rev-k-NN set, and derive sym- bolic Boolean rule, expressed in natural language, that closely matches the GNN'S predictions on this population (see Prob.1). To this end, we leverage the reasoning capabilities of large language models (LLMs), motivated by two key factors. (1) LLMs have demonstrated strong mathematical and causal reasoning abilities, including over graph-structured data[55, 6, 26, 49]. (2) Given our aim to express logical rules in natural language, LLMs are particularly well suited due to their well-established strengths in linguistic articulation. Self-refinement paradigm: Fig. 2 presents the pipeline of the signature discovery process of an exemplar, which leverages the self-refine platform [26]. We select an initial sample of positive and negative nodes. The positive sample contains nodes from the Rev- k-NN set, and the negative sample contains those not in the Rev-k-NN. Both samples are drawn uniformly at random. The sample size a hyperparameter. These node sets are further divided into training and validation sets. Instead of asking the LLM to directly output the boolean rule in natural language, we decouple into two steps. The LLM is first asked to generate a python code, that takes input node and its associated information, passes it through a boolean logic, and returns a True/False answer. The ideal rule returns True for all positive nodes and False for negative nodes. The rule encoded in the Python code is then translated to natural language by the LLM. Initially, the Python code is a trivial solution, such as returning True for any input node, which iteratively improved through feedback. The iterations stop when either the accuracy of the code (rule) exceeds a certain accuracy threshold on the validation set or the number of iterations reaches an upper limit.
Prompt specification: The prompt includes the following components; visual overview is pro- vided in Fig. 10 (query), Fig. 11 (feedback), and Fig. 12 (refinement) in the Appendix.

---

START
TRAINING
PRONPT
SHELETON
PYTHON CODE
TEXT DESCRIPTIN TION
REFINE
EVALUATION
VES
CALCULATE
VALIDATION
PREDICTIONS
TEXT DESCRIPTION
PREDICTIONS
Figure 2: Pipeline of signature discovery through iterative self-refinement of LLM output.
Training and validation nodes: As discussed above, provide a set of positive and negative nodes. If the GNN being explained is É layers deep, then the embedding of a node is a function of its f-hop neighborhood only [44]. Hence, we provide summary of the ε-hop neighhorhoods each node in the positive and negative samples. The summary a node includes: (1) the attributes of the node, (2) the normalized frequency distribution of GNN predicted class labels for all nodes in each hop from to É, (3) the average L1 distance per attribute between the exemplar and all nodes each hop level from 1 to l. While GNN class distribution signals the degree of homophily-biae learned by the GNN, the average attribute-wise distance offers insight into feature relevance the embedding space. Specifically, if the average distances to positive and negative nodes are similar for given attribute, it suggests that the feature contributes little to the embedding representation. Note that, since we only provide distribution-leve information, the context size remains independent of the graph's 's density. This property is crucial for ensuring that large graphs do not exceed the L.M'' context window capacity.
Code skeleton: The skeleton of the python code that the LLM is supposed to fill in. The skeleton contains the function definition that takes as input the summary of node and the output specifi- cation, which should return a boolean value.
Feedback: This includes the Python code and associated natural language rule from the last iteration and the summary of all nodes where the latest rule failed to match the GNN prediction.
4 Experiments
In this section, we benchmark GNNXEMPLAR and establish:
Limitations Existing Explainers: Current explainers, primarily designed for graph classifica-
tion small graphs, fail to generalize effectively to node classification in large-scale graphs.
High-Fidelity explanations: GNNXEMPLAR bridges this gap by consistently achieving high fi- delity across both homophilic and heterophilic graph benchmarks.
User Preference for Textual Explanations: Our user survey involving 60 participants shows a statistically significant preference for textual explanations graph-based visualizations.
4.1
Experimental Setup
The details of our hardware and software platform, soper-parameters, LLM engine, training details of the black-box GNN and their accuracies are discussed in App. A.1 and App. A.2. Our codebase shared at https://gttuu..com/iiii hwtp://w..oo..daaaaaaaaaaaaaaaaa iitt///nneeppllaggiiiii Xangre/uie.ccmeeeeiiiiinnnnnnnne
Datasets: Table presents the benchmark datasets we use. Wherever available, we adopt the
standard train/validation/ees. splits from PyTorch Geometric the original data releases, preserving class balance. We train GAT for TAGCora and GCN for the rest.
Baselines: As discussed in $ 1, there are no existing explainers designed to handle node classifi- cation on large graphs. Hence, we adapt state-of-the-art explainers originally developed for graph classification. To enable a fair comparison, we reframe the node classification task as graph classi- fication problem by extracting the ê-hop subgraph around each target node and assigning the node's label to the entire subgraph; & denotes the number of layers in the GNN. We compare against the following baselines:

---

Table 1: Dataset statistics. Detailed descriptions of each dataset are in App.A.9
Homophilous
Heterophilons
Name
#nodes
#edges
#features
#classes
Name
#nodes
#edges
#features
#elasses
TAGCora [21]
2,708
556
1433
Amazon-ratings [32]
192
93,050
300
Citeseer [10]
3,327
9, 104
3703
Minesweeper [32]
10,000
39,407
WikiCS (29]
11, 701
216, 123
300
10
Questions [32)
48, 98,921
153, 5/0
301
ogbn-arxiv [14]
343
1, 143,
128
40
BA-Shupes [48]
300
4110
GNNInterpreter [42]: A generative model trained to synthesize class-repressnntatiee graphs using
reinforcement learning.
GCNeuron [45]: A neuron-level explainer that identifies high-level subgraph concepts that acti-
vate neurons within a GNN.
GLGExplainer [2]: The only prior global logical explainer that fits a Boolean formula to GNN outputs by clustering local explanation subgraphs (e.g., PGExplainer [24]) around prototypes and learning a formula over those prototypes using ELEN [4].
Since both GNNInterpreter and GCNeuron identify representative subgraphs without generating explicit Boolean rules, we construct a rule by taking a logical OR over all identified subgraphs for each class label. We do not compare with GraphTrail [1] since it only considers graphs with discrete node labels. MAGE [50] is also omitted since is specific to molecular graphs.
Metrics: We evaluate each explainer by applying its generated Boolean formula to the test set of each dataset. The alignment between the formula and the GNN'S predictions is quantified using the following metrics: Fidelity (the proportion of test nodes where the formula's output matches the GNN's ' prediction), Precision, Recall, and Fl-score.
4.2 Fidelity
Table reports the fidelity of each explainer on node classification tasks. Precision, recall and F- score for the same experiments are reported in Tables 6. 7 and 8 in the Appendix. Several key observations emerge. (1) GNNXEMPLAR consistently achieves the highest fidelity, establishing a new benchmark for global explanation in node classification. (2) Explainers for graph classification demonstrate brittle performance when adapted to node classification, confirming that exact subgraph repetition is rare in real-world graphs. (3) motif-based explainers reliant subgraph isomorphism fails to scale on large graphs. We elaborate below.
NAs: The NA cases occur when an explanation is generated but cannot be applied or evaluated on any specific node (or neighborhood subgraph) instance. This limitation arises from the reliance of GNNInterpreter on subgraph-based rules. Its only mode of application is through subgraph iso- morphism, which severely constrains its generalizability. Subgraph isomorphism can only function when node features either absent purely discrete (c.g., scalars). With continuous or high- dimensional node features, determining whether two nodes, or their neighborhoods, are "identical" becomes ill-defined, rendering the explanation unusable in most real-worle settings.
NFs: NF stands for "No Formula Generated," which is encountered in GLGExplainer. GLGEx- plainer first trains surrogate model to mimic the black-box GNN and then attempts to distill this surrogate into interpretable boolean logic. However, we find that several datasets, either the sur- rogate model fails to approximate the GNN, or the boolean distillation step breaks down. In both scenarios, GllEEilaierr outputts an empty string. This failure indicates that GL.GExplainer is brittle when faced with noisy, irregular, or highly entangled graph patterns.
Inferior Baseline Performance. Even when the baselines produce actionable rules, all three yield significantly lower fidelity. This is primarily because they rely on identifying common subgraph patterns per class, an assumption that rarely holds in complex, real-world graphs. In contrast, GN- NXEMPLAR is grounded in exemplar theory and computes distributional distances to strategically selected exemplars in the GNN embedding space. This approach avoids subgraph isomorphism while remaining faithfully aligned with the GNN'S predictive behavior. Scalability: Both GLGEX- PLAINER and GCNEURON frequently encounter out-of-memory (OOM) errors on large or dense graphs, with GLGGEXPLAINE, failing because of its reliance on subgraph-isomorphiss and GC- NEURON due to exhaustive neuron-activation pattern enumeration. contrast, GNNXEMPLAR is explicitly designed to avoid subgraph isomorphism and scales gracefully.
8

---

Table 2: Fidelity of the GNNXEMPLAR and the various baselines. OOM indicates out-of-memore NA indicates "Not Applicable", and NF indicates the case where the algorithm failed to generate a formula. GNNInterpreter assumes discrete node attributes only, and hence, for datasets with contin- nous attributed notes, it is not applicable.
Homophilons
Hcterophilons
TAGCora
Citeseer
WIKICS
nrxiv
Amazon-R
Questions
Minesweeper
BA-Shapes
GNNInterpreter
NA
0.50 0.0
NA
NA
NA
NA
0.50 0.0
0.47 + 0.0
GCNeuron
0.51 +
0.50 8.O
0OM
0OM
0.36 0.D
00M
0.54 = 0.0
0.50 :: 0.0
GLGExplainer
NF
NF
00M
00M
NF
0OM
0.22 = 0.07
0.30 2: 0.09
GNNXEMPLAR
0.83 0.01
0.92 0.03
+
0.84
0.82 0.01
0.92
+
4.3 Ablation Study
To quantify the contributions of our two key innovations, exemplar selection through Rev-k-NN and iterative self-refinement using LLM, we conduct two controlled ablations.
Rev-k-NN vs. Random Exemplar Selection:
Here, we replace our Rev-k-NN based exemplar se- lection with an equal-sized set of randomly sampled nodes (exemplars) per class. This change yields a noticeable fidelity decrease, as random prototypes fail to capture the dense, semantically coherent neighborhoods that Rev-k-NN provides (see Fig. 3-Left subplot).
Self-Refinement vs. Zero-Shot: In the zero-shot variant, we bypass the structure self-refining pipeline discussed in $ 3.4 and directly ask the LLM to predict the rule (signature) in one go. Ablation results in Fig. 3 (Right subplot) demonstrate that this zero-shot approach yields notice- ably lower fidelity and higher variance on every dataset. This reveals that the full self-refinement pipeline systematically identifies misclassified instances and adjusts the rules accordingly, produc- ing significantly more accurate and robust explanations with reduced variance across runs.
4.4
Impact of Parameters and GNN architectures
App. A.7 studies the impact of parameters l in Rev-k-NN, sample size in Rev-k-NY approximation, and the training-set sample size in self-refine. App. A.8 evaluates robustness to GNN architectures.
4.5
Case Study: Visual Analysis of Rules
To demonstrate the interpretability and domain-alignmenn of our global explanations, we show rep- resentative rule sets from TAGCora (homophilous) (Fig. 14) and BAShapes (heterphilous) (Fig. 15).
TAGCora (Fig. 14) In the TAGCora citation network, topic (class) assignments are driven by both textual features and neighborhood context. For instance, Nearal Networks papers are identified by the presence of domain-specife, terms like "hackpropagation" and "activation functions". Further- more, the rule also discovers homophillic associations with other "Neural Network" papers among 1 and 2-hop neighbors. The rule further comments that the presence of ICA and HMM words in the abstracts of the neighbors further reinforces the class assignment.
BAShapes (Fig. 15) On the synthetic BAShapes graph, membership in each geometric role is de- termined solely by local connectivity patterns. GNNXEMPLAR is successfully able to identify these purely structural and heterophilic associations, such as nodes belonging to the class "not in a house" have at least six "non-house" neighbors and minimal ties to other roles.
Rev-k-NN
Randon
Self Refine
Zero
1.0
1.0
0.8
0.8
Fidelity
0.6
Fidelity
0.6
0.4
0.4
0.2
0.2
0.0
0.0
Citeseer Wikics
agbn arxiv
Anazon ret ratings
Mine sweeper
Citeseer M1KiC5
ogbn arxiv
Anazon ratings
Mine sweeper
Figure 3: Ablation study on GNNXEMPLAR, Left: Impact of Rev-k-NN based exemplar selection.
Right: Impact of self-refinement strategy vs. zero-shot rule discovery.
9

---

Table 3: Results of one-sided binomial tests assessing user preference for text-based explanations over subgraph-bas based explanations across five A/B test questions. Bolded p-values indicate a statis- tically significant preference for the text modality (p 0.05).
Q1
Q3
Q4
Q5
Total
Datasct
TAGCora
Questions
Questions
BAShapes
BAShapes
Prefer text
43
36
42
38
200
Prefer subgraph
19
24
18
22
100
p-value
0.0005
0.0031
0.0775
0.0013
0.0259
0.0001
4.6 Application: Diagnostic Power in Failure Cases
In Questions, active users exhibit homophilous behavior-they tend connect to other active users. Inactive users, in contrast, behave heterophilously by connecting primarily to active users. Interest- ingly, our explanation rule for the inactive class does not reflect this expected heterophily. Instead, it points toward a homophilous pattern even for inactive users. At first glance, this seems contradic- tory: how can an explanation be so seemingly incorrect and still achieve high fidelity (see Table 2)?
To investigate, we visualized 2-hop neighborhoods of inactive nodes: once with ground-truth labels, and once with GNN predictions (see example in Fig. 5). The results were revealing: the GNN predicts even the neighbors of inactive nodes as inactive, indicating that it has learned an incorrect homophilous pattern for the inactive class as well. This behavior is likely driven by the dataset's ss class imbalance - most nodes are active, so homophily becomes statistically advantageous shortcut for the model.
Far from being flawed, the explanation is insightful-it it does not mimic the ground truth, but rather points to the root cause of why the inactive class is often misclassified with low precision of 0.68: the GNN has failed to capture the intended heterophilous behavior.
4.7 Human Evaluation: User Survey
In this work, we advocate shift from conventional subgraph-based visualizations to natural lan- guage explanations. Our motivation stems from the hypothesis that presenting dense graph neigh- borhoods with high-dimensional node attributes in full detail can overwhelm human cognitive ca- pacity. To test this, we conducted a user study with 60 participants, each responding to 5 A/B test questions, resulting in 300 total comparisons. Each question presented the same explanation for model prediction in both textual and subgraph form, and participants were asked to indicate their preferred modality. See App. B for survey design details and example sereenshots.
We analyzed the results using the Binomial test [37] and McNemar's 's test [27]. The Binomial test, applied to the aggregate responses (200/300), evaluates whether one modality was preferred signif- icantly more often overall. This yielded a highly significant result (p-value < 0.0001), indicating that text-based explanations were favored by participants at the population level. Table 3 presents the per-question binomial test results, showing that this preference was consistent and statistically significant in all except Q3. While Q3 does not reach statistical significance, this was by design: we deliberately selected an explanation where the subgraph visualization was small and simple. The goal was to verify that participants were not blindly preferring the text modality due to any prior bias.
To assess within- partiinpprticipannt consistency, we additionally conducted McNemar's 's test using the 'exact Binomial' method. Out of 60 participants, 45 chose text more often, while only 15 preferred sub- graph more often. This difference was also statistically significant (p-value = 0.0001), confirming that the preference for text was not only strong but consistent across individuals.
5 Conclusions, Limitations and Future Works
In this work, we presented GNNXEMPLARR novel framework for global explanation of node classi- fication in GNNS. Unlike prior explainers that rely on brittle motif discovery and struggle with scale, GNNXEMPLAR explains through exemplar nodes, which serve as semantic anchors for model behav- ior. To generate human-undersee understandable explanations, we leveraged LLMs to distill the defining char- acteristics of each exemplar and its neighborhood into concise natural language rules, Our empirical evaluations demonstrate that GNNXEMPLAR outperforms existing methods in fidelity, scalability, and user interpretability, with user study confirming strong preference for textual explanations.
Limitations and Future Works: GNNXEMPLAR operates in a setting with access only to the GNN'S embedding space, limiting visibility into how feature-topology interactions influence internal activations. As a result, fine-grained mechanistic understanding of the model's decision process remains out of reach. We plan to study this aspect through the lens of mechanistic interpretability.
10

---

Acknowledgements
The collaborative research with IIT Delhi was supported by Fujitsu Research of India. Burouj Armgaan also acknowledges support from Prime Minister's Research fellowship during this research and the generous travel grant received from ACM/IARCS to support his participation in NeurIPS 2025.
References
[1] Burouj Armgaan, Manthan Dalmia, Sourav Medya, and Sayan Ranu. Graphtrail: Translat- ing gnn predictions into human-interppetable logical rules. Advances in Neural Information Processing Systems, $7:123443-122477 2024. (Cited on pp. 2, 8, and 21 <-)
[2] Steve Azzolin, Antonio Longa, Pietro Barbiero, Pietro Lio, and Andrea Passerini. Global ex- plainability of GNNs via logic combination of learned concepts. In The Eleventh International Conference Learning Representations, 2023, (Cited on pp. 1, 2, and 21 42)
[3] Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional networks. arXiv preprint arXiv: / 1686,, 2019. (Cited on p. 21 (-)
[4] Pietro Barbiero, Gabriele Ciravegna, Francesco Giannini, Pietro Lió, Marco Gori, and Stefano Melacci. Entropy-based logic explanations of neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, 2022. (Cited on p. {-)
[5] Thomas H. Cormen, Charles E. Leiserson, Ronald L.. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. (Cited on pp. 6 and 24 (-)
[6] Xinnan Dai, Haohao Qu, Yifei Shen, Bohang Zhang, Qihao Wen, Wenqi Fan. Dongsheng Li, Jiliang Tang, and Caihua Shan. How do large language models understand graph patterns? a benchmark for graph pattern comprehension. In The Thirteenth International Conference Learning Representations, 2025. (Cited on p. 6 ())
[7] Alexandre Duval and Fragkiskos D Malliaros. Graphsvx: Shapley value explanations for graph neural networks. In Machine Learning and Knowledge Discovery Databases. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13-17, 2021, Proceedings, Part 21, pages 302-318. Springer, 2021. (Cited on p. (2)
[8] Qizhang Feng, Ninghao Liu, Fan Yang, Ruixiang Tang, Mengnan Du, and Xia Hu. Degree: Decomposition based explanation for graph neural networks. In International Conference on Learning Representations, 2022. (Cited on p. 21 ())
[9] Thorben Funke, Megha Khosla, Mandeep Rathee, and Avishek Anand. Z. orro: Valid, sparse, and stable explanations in graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 2022. (Cited on p. 21 (-)
[10] C Lee Giles, Kurt D Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital libraries, pages 89-98, 1998. (Cited on p. ())
[11] Anjali Gupta, Prashant Kumar, Aniket Mishra, Abhishek Singh, Surender Kumar, Muthusamy Chelliah, Abhijnan Chakraborty, and Sayan Ranu. Persona identification in e-commerce with scarce labels and in-context graph learning. Proceedings of the 31st ACM SIGKDD Con- ference on Knowledge Discovery and Data Mining V. 2, pages 778-789, 2025. (Cited on
+)
[12) Mridul Gupta, Samyak Jain, Vansh Ramani, Hariprasad Kodamana, and Sayan Ranu. Bonsai: Gradient-free graph condensation for node classification. In ICLR, 2025. (Cited on p. 5 +>)
[13] William L. Hamilton, Rex Ying, and Jure Leskovee. Inductive representation learning on large graphs. In Proceedings of the s1 International Conference on Neural Information Processing Systems, NIPS' 17, page 1025-1035, Red Hook, NY, USA, 2017. Curran Associates Inc. (Cited on ())
11

---

[14] Weihua Hu, Matthias Fey, Marinka Zitmik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118-2211 2020. (Cited on 8
()
[15] Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. Graphlime: Local interpretable model explanations for graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 2022. (Cited p. 21 <-)
[16] Zexi Huang, Mert Kosan, Sourav Medya, Sayan Ranu, and Ambuj Singh. Global counterfac- tual explainer for graph neural networks. Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pages 141-149, 2023. (Cited on p. 1))
[17] Mert Kosan, Zexi Huang, Sourav Medya, Sayan Ranu, and Ambuj Singh. Gefexplainer: Global counterfactual explainer for graph neural networks. ACM Trans. Intell. Syst. Technol., 16(5), August 2025. (Cited on p. 1 +))
[18] Mert Kosan, Samidha Verma, Burouj Armgaan, Khushbu Pahwa, Ambuj Singh, Sourav Me- dya, and Sayan Ranu. plainers through in-depth benchmarking. In The Twelfth International Conference on Learning Representations, 2024. (Cited on p. 1 (-)
Unravelling the utility of perturbation- GNN ex-
[19] Wenqian Li, Yinchuan Li, Zhigang Li, Jianye Hao, and Yan Pang. Dag matters! gflownets enhanced explainer for graph neural networks. In The Eleventh International Conference Learning Representations, 2023. (Cited on p. 21)
[20] Wanyu Lin, Hao Lan, and Baochun Li. Generative causal explanations for graph neural net- works. In International Conference on Machine Learning, pages 6666-6679. PMLR, 2021. (Cited on p. 21 +2)
[21] Hao Liu, Jiarui Feng, Lecheng Kong, Ningyue Liang. Dacheng Tao, Yixin Chen, and Muhan Zhang. One for all: Towards training one graph model for all classification tasks. In The Twelfth International Conference on Learning Representations, 2024. (Cited on pp. 8 and 21 ()
[22] Yajing Liu, Zhengya Sun, and Wensheng Zhang. Improving fraud detection via hierarchical attention-based graph neural network. arXiv preprint 2tl.:22022009996. 2022. (Cited on p.
[23] Shengyao Lu, Keith G Mills, Jiao He, Bang Liu, and Di Niu. GOAt: Explaining graph neural networks via graph output attribution. In The Twelfth International Conference on Learning Representations, 2024. (Cited on p. 21 +))
[24] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in neural information processing systems, 13:19620-19631, 2020. (Cited on pp. 1, 8, and 21 ())
[25] Ge Lv and Lei Chen. On data-aware global explainability of graph neural networks. Proceed- ings of the VLDB Endowment, 16(1 16(11):3447-2 -4600, 2023. (Cited on pp. 2 and 21 (-)
[26] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegr- effe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bod- hisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self-feedback. In Thirty-sevnnth Conference Neural Information Processing Systems, 2023. (Cited on +-)
[27] Quinn McNemar. Note on the sampling error of the difference between correlated proportions or percentages. Psychometrika, 153-517 1947. (Cited on p. 10 (2)
[28] Douglas I. Medin and Michael M Schaffer. Context theory of classification learning. Psycho- logical Review, 2573)2007-238, 1978. (Cited p. 2 +))
12

---

[29] Péter Mernyei and Cătälina Cangea. Wiki-es: A wikipedia-based benchmark for graph neural networks. In The Thirty-Sevente International Conference on Machine Learning. 2020. (Cited on pp. 8 and 21 {-)
[30] Sunil Nishad, Shubhangi Agarwal, Amnb Bhattacharya, and Sayan Ranu. Graphreach: Position-aware graph neural network using reachability estimations. IJCAI, 2021. (Cited on
p.
[31] Tamara Pereira, Erik Nascimento, Lucas E Resck, Diego Mesquita, and Amauri Souza. Distill explain: explaining graph neural networks using simple surrogates. In International Confer- ence on Artificial Intelligence and Statistics, pages 6199-6214. PMLR, 2023. (Cited on p. 21
()
[32] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look the evaluation of gnns under heterophily: Are we really making progress? In The Eleventh International Conference on Learning Representations, 2023. (Cited on p. (-)
[33] Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoff- mann. Explainability methods for graph convolutional neural networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10772-10781,
2019. (Cited on p. (-)
[34] Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov. Interpreting graph neural networks for nlp with differentiable edge masking. International Conference on Learning Representa- tions, 2021. (Cited on 21 (-)
[35] Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T Schütt, Klaus- Robert Müller, and Grégoire Montavon. Higher-order explanations of graph neural net- works via relevant walks. IEEE transactions on pattern analysis and machine intelligence, 14(11):7581-758) 2021. (Cited on +))
[36] Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li. Reinforcement learning enhanced explainer for graph neural networks. In NeurIPS 2021, December 2021. (Cited on
p. 21
[37] David Sheskin. Handbook of parametric and nomparametric statistical procedures. Chapman and hall/CRC, 2003. (Cited p. 10 +-)
[38] Juntao Tan, Shijie Geng, Zuohui Fu, Yingqiang Ge, Shuyuan Xu, Yunqi Li, and Yongfeng Zhang. Learning and evaluating graph neural network explanations based counterfactual and factual reasoning. In Proceedings of the ACM Web Conference 2022, WWW '22, page 1018-1027, 2022. (Cited on p. 21 (2)
[39] Samidha Verma, Burouj Armgaan, Sourav Medya, and Sayan Ranu. InduCE: Inductive coun- terfactual explanations for graph neural networks. Transactions Machine Learning Re- search, 2024. (Cited on p. 1 ()
[40] Minh Vu and My Thai. Pgm-explaines Probabilistic graphical model explanations for graph neural networks. Advances in neural information processing systems, 33: 33:12225-1223 2020. (Cited on p. 21 ())
[41] Xiang Wang. Yingxin Wu. An Zhang, Xiangnan He, and Tat-Seng Chua. Towards multi- grained explainability for graph neural networks. Advances in Neural Information Processing Systems, 14:18446-1845, 2021. (Cited on p. 21 +))
[42] Xiaoqi Wang and Han Wei Shen. GNNInterpreter: A probabilistic generative model-level explanation for graph neural networks. In The Eleventh International Conference on Learning Representattinss, 2023. (Cited pp. 1, 2, 8, and 21 +-)
[43] Yaochen Xie, Sumeet Katariya, Xianfeng Tang, Edward Huang, Nikhil Rao, Karthik Subbian, and Shuiwang Ji. Task-agnostic graph explanations. NeurIPS, 2022. (Cited on p. 21 <>)
13

---

[44] Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. (Cited on p. 7 +
[45] Han Xuanyuan, Pietro Barbiero, Dobrik Georgiev, Lucie Charlotte Magister, and Pietro Liò. Global concept-based interpretability for graph neural networks via neuron analysis. In Pro- ceedings of the AAAI conference on artificial intelligence, 37. (Cited on pp. and 8 (-)
[46] Han Xuanyuan, Pietro Barbiero, Dobrik Georgiev, Lucie Charlotte Magister, and Pietro Lió. Global concept-based interpretability for graph neural networks via neuron analysis. In AAAI, 2023. (Cited on 21 {2)
[47] Rex Ying, Ruining Hc, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In KDD, page 974-983, 2018. (Cited on +-)
[48] Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnex- plainer: Generating explanations for graph neural networks. Advances neural information processing systems, 32, 2019. (Cited on pp. 1, 8, and 21 {2)
[49] Yuxin You, Zhen Liu, Xiangchao Wen, Yongtao Zhang, and Wei Ai. Large language models meet graph neural networks: A perspective graph mining. Mathematics, 13(7), 2025. (Cited on p. (-)
[50] Zhaoning Yu and Hongyang Gao. Mage: Model-level graph neural networks explanations via motif-based graph generation. In The Thirteenth International Conference on Learning Representations, 2025. (Cited on pp. 2, 8, and 21 (-)
[51] Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 430-438, 2020. (Cited on pp. 2 and 21 {²)
[52] Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In ICML, pages 12241-12252. PMLR, 2021. (Cited on
2)
[53] Shichang Zhang, Yozen Liu, Neil Shah, and Yizhou Sun. Gstarx: Explaining graph neural net- works with structure-aware cooperative games. In Advances Neural Information Processing Systems, 2022. (Cited on 21 +))
[54] Yue Zhang, David Defazio, and Arti Ramesh. Relex: A model-agnostic relational model explainer. In Proceedings of the 2021 AAAI/ACM Conference on Al, Ethics, and Society, pages 1042-1049, 2021. (Cited on p. 21 +*)
[55] Yuzhe Zhang, Yipeng Zhang, Yidong Gan, Lina Yao, and Chen Wang. Causal graph dis- covery with retrieval- -uureval-augmeeteed generation based large language models. arXiv preprint a0X1v:2402.15301, 2024. (Cited on p. 6 {2)
14

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Sec. 2, 3, 4
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much results can be expected to generalize to other settings, is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification:
Sec. 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to viola- tions of these assumptions (e.g.. independence assumptions, noiseless settings, model well- specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with a few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address prob- lems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by review- ers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: App. 1, 1,2
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
15

---

Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main exper- imental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: App. A.1
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
example, if the contribution
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility. which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (c.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes]
Justification: Sec. 4
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (httpss/hips..c//uubiccguuuu CodeSSubmissionPolley for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed run repro- duce the results. See the NeurlPS code and data submission guidelines https://nips..c/pubbii quides/CoaeSuumisiiooooolcc
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
16

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparame- ters, how they chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: App. A.1
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Tab. 2, 6, 8. Fig.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main
claims of the paper.
The factors of variability that the error are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to
library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). If error bars are reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments compute resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the exper- iments?
Answer: [Yes]
Justification: App. A.1
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs as well as estimate the total compute.
The paper should disclose whether the full rescarch project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, every respect, with the NeurIPS Code of Ethics http://heermpsscc/mmlic/ttiitiii Answer: [Yes]
Justification: All sections.
17

---

Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure preserve anonymity (e.g., if there is special consideration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Sec.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, is legitimate to point out that improvement in the quality of generative models could be used generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster. The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strate- gies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
Relcased models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not re- quire this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL..
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
18

---

For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswitheode.. http:witthoode.ccoddttttttttt has curated licenses for some datasets. Their licensing guide can help determine the license of dataset. For existing datasets that are re-packaged, both the original license and the license of the de- rived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Sec. 4
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submis-
sions via structured templates. This includes details about training. license, limitations, etc. The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [Yes]
Justification: Fig. 6, 8, 9
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should included in the main paper.
According to the NeurlPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/revieww based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This study involved minimal-risk user survey where participants were not asked to provide any sensitive information. Participation was voluntary and anonymous. Based on institutional policy, IRB approval was not required for this type of research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country which research conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and lo- cations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if appli- cable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMSs an important, original, or non- standard component of the core methods in this research? Note that if the LLM is used only
19

---

for writing, editing, or formatting purposes and does not impact the core methodology, scientific nigorousness, or originality of the research, declaration is not required.
Answer: [Yes]
Justification: Sec. 3
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, or non-standard components.
Please refer to our LLM policy http::/iieuuig..ccooooeeemesssss for what should or should not be described.
20

---

A Appendix
Explainers
Explainers
Explainers
Goneration
Gradients/
Decompoeltion
Porturbation
Surrogate
Subgraph
RGExpisinor
SA Guided-EP
CAM Exoltation-80 GNN-LRP GOAT
GNNExploiner PGExplainer GF-2 GraphMaek Reflne
GraphLIME RaLex PGMExp iimno Drix GraphSVX
XGNN @CNauron ONNintarppatal DA@Explainer
OLGExplainer
GFlowExplalner
GraphTrall
GEM
MAGE
SubgraphX Gatark
TABExpleiner
Figure 4: Taxonomy of factual GNN explainers. Generation: RGExplainer [36], GFlowExplainerr
[19]. GEM [20]: Gradient: SA [3], Guided-BP [3), Grad-CAM [33]; Decomposition: CAM [33],
Excitation [33], DEGREE [8], GNN-LRP [35], GOAT [23]; Perturbation: GNNExplainer [48],
PGExplainer [24]. CF [38]. GraphMask [34], ReFine [41], Zorro [9], SubgraphX [52], GstarX [53],
TAGExplainer [43]; Surrogate: GraphLime [15], ReLex [54], PGM--xplainee [40], DnX [31],
GraphSVX [7]; Subgraph sets: XGNN [51], GCNeuron [46], GNNInterpreter [42), DAGExplainer
[25], MAGE [50]; Subgraph formulae: GLGExplainer [2], GraphTrail [1].
A.1
Experimental setup
Hardware details All experiments were performed on Intel(R) Xeon(R) Gold 6426Y: 64 cores, 126 GB RAM, 2 NVIDIA-L40S GPUs, 45 GiB each running on Ubuntu 20.04.6 LTS.
We provide the hyper-parametts values choose for current pipeline. In sec. 3.2 we fist picked for k-NN and Reverse k-NN, for all the datasets in experiment we choose k 5. Next in sec. 3.3 for coverage maximization instead of selecting number of points set the stopping criterion based on coverage of points, when the coverage becomes 2 95%. Then for sec. 3.4 used 'gemini-1.5-ffash LLM from google's generativeai package. Then for sampling positive and negative points which will be used in self-refinement we set the sample size = 50 each. We split these samples in training and validation set in the ratio of respectively. Finally for stopping criteria of self-refinement process we stop the iteration when either the accuracy 2 95 if the number of iterations reaches 5.
A.2 Training Details of GNNs
We first write the details about the GNNs we use for all the datasets,
For TAGCora, pick the GAT model (with 2 layers and 64 hidden dimension) from paper [21] where they officially use this dataset.
For WikiCS dataset we pick the official implementation of GCN used in their paper [29]. And use
2 layer model with a hidden dimension 64.
For ogbn-arxiv,
pick the official GCN from ogb repository for node classification arxiv, used 3 layered version
with hidden dimension as 256.
For Citeseer, amazon amazon-ratings, questions and minesweeper we use the same model as use in ogbn-
arxiy dataset and for all these datasets we use 3 layers with hidden dimension of 64.
For BA-Shapes,
the model use in the paper [48] with layers, a hidden dimension of 20.
Since none of above implementations provide trained model weights so we train the GNNs on these datasets from scratch. For training all the GNNs we use the standard training pipeline of pytorch which resembles closely to what all the above models use in their implementation, We train all the models for 250 epochs and choose the learning rates from the set {0.005, 0.01) with Adam
21

---

Inactive Active
2
2
Ground Truth
GNN Predictions
Inactive
Active
3
3
Ground Truth
GNN Predictions
Figure 5: Subgraphs from the Questions dataset. Notice how active nodes 1, 2, and surrounded by inactive nodes are predicted as inactive. This misclassification pattern is the signal that GNNXEM- PLAR picks up when learning the signature the inactive class.
optimizer and a weight decay of 5e We report the best accuracies of trained GNNs in table 4. Although we try to get as close as possible to the quoted numbers in the datasets official papers there could still be some deviation because of random initialization of model weights.
Table 4: GNN performance
Homophilous
Heterophilous
Name
Accuracy
Name
Accuracy
TAGCora
73.84
Amazon-ratings
46.43
Citeseer
66.20
Minesweeper
80.36
WikiCS
78.40
Questions
97.07
ogbn-arxiv
62.58
BA-Shapes
95.71
22

---

A.3 Proof of Lemma
Let 8 S Ver be set of nodes sampled uniformly at random from the full training node Ver- For fixed node o E Vir, define the indicator random variable X for each u E S such that:
if k-NN(u)
(3)
otherwise
The total number of times appears in the k--N lists of sampled nodes is given by:
X Σ
= fT(v))
(4)
WEB
Since nodes sampled independently and uniformly, we have E[X*] I[(e), where (1(v))
is the true representative power of node v. Thus. X" follows Binomial distribution: X (mnomia((2111())))
Applying Chermoff bounds for any 2
2 =ll(v) -
E²
Upper tail:
P(X" 2 (1+ +)=ll(v)) S exp
- -()01(1))
2 =II(u)
Lower tail: P(X" < (1 c)=lI(()) S exp
(6)
Combining both bounds:
6²
P(X -I[(e]] czIl(v)) S exxp
:II(v)
2+ e
+ P (|iī(()) - - 2 <z)l(w)) s 2xxp
2 + =11(v)
(8)
+ pP( ( - m(v) 2 ell(w)) < 2exp
2 + =Il(v)
Substituting 0 = ell(v) from Lemma in Eq. 9, we rewrite Eq. 9 as:
P P(TT(v) m()) 20) s 2exp
IT(2))
21T (v)
(10)
2 + #
IT(e
@
< 2xpp
(11)
(2IT(v) 0)
Since II(v) < obtain:
02
P (((()) IIv)) 2 20) s exx
2 2
(12)
To ensure this probability is at most 6, we solve:
0
exp
88
(13)
+ 0
2
82
In
<
(14)
+ 0
In (2) (2 (2+0 0)
* >
(15)
In (2++0)
Hence, if we sample at least 2
nodes in S, then for any v E V:
82
ii(r) E [I( 0, II(v) + 0]
with probability at least 1 - 8.
(16)
23

---

A.4 NP-hardness: Proof of Theorem 1
PROOF. We prove NP-hardness of the representative node selection problem by a reduction from the classical Ser Cover problem [5].
Definition 7 (Set Cover). Given budget b and collection of subsets S (S Sml of universe U = {ui,..., ) such that S; C U for all i, the Set Cover problem asks whether there exists a subcollection 8 C of size |S' b such that Us,es S U.
Given an instance of Set Cover (S, U' b, we construct graph G = (V, E) and corresponding node embeddings such that solving our representative selection problem on this graph is equivalent to solving the Set Cover instance.
We create training node set V., Vy U Vs, where:
For each element Uy E U, we create a node Va, E Vu. For each subset S₁ E S, we create node us, Vs.
We define the k-NN relationship over the learned GNN embeddings such that for each uj E Si, node us, E k-NN(uu,)) ie., Vay E Rev-k-NN(uvs)) This means that us. represents all Vay for which Uy E St.
Now, consider the exemplar selection problem: choose a set A C V of size b that maximizes the representative power:
IT(A) Hu E Ver 1eve E A such that e E Rev-k-NN(o')
(17)
Verl
Our construction ensures that ([A = Poll and only if all nodes in Vy are covered by reverse T
k-NNs of nodes in A. This is equivalent to finding b nodes from Vs (i.e., subsets in the original Set Cover instance) whose reverse k--NS jointly cover all nodes in Vy (i.e., elements in U). Thus, there exists set cover of size if and only if there exists a node subset C Vtr of size such that
(TA))
Iul
Ve.l
A.5 Proofs Monotonicity and Submodularity
Theorem (Monotonicity). Let la S A be two subsets of nodes in the graph. Then,
II(A' - II(A) 2 0
Proof. Recall that II(A) 1U Rev-K-NN(wi] [V_1] The denominator [Vrr is constant, only need
show that the numerator is monotonic.
Since A' 2 A. we have:
U Rev---NN(() 2 U Rev-k-NN(r))
vEA'
wEA
because the union operator is monotonic under set inclusion. Therefore, the size of the covered set cannot decrease as A grows. This implies:
ITAA) 2 IT(A)
Theorem (Submodularity). Let A C A' and v be any node in the graph not already in A'. Then, IT(A' U (v)) - IT(A") s ITAA (v]) IT(A)
PROOF BY CONTRADICTION. Assume instead that: [TAA' U (v)) - IT(A/) > II {n}) IT(A)
(18)
Let R2 Rev-k-NN(y) denote the set of nodes that consider among their k nearest neighbors. The marginal gain of adding v to set is:
R, \ U Rev-K-NN(('))
o'EA

---

Inequality (18) implies:
R U Rev-k-NN(e') |R, U
Rev-K-NN(e')
N'EW/
t'EA
But since A' 2 A. we have:
U Rev-K-NN(O') S U Rev-k-NN((1)
o' E'EA
v'EA'
which implies the reverse inequality:
RR
U Rev-K-NN(C') & |R, U
Rev-A-NNN('))
N'EA'
v'EA
This contradicts our assumption in Eq. (18), completing the proof.
A.6 Proof of Monotonicity and Submodularity under Estimated Rev-k-NN
Let Rev-k-NN(r) denote the approximate reverse k-NN set of node and IT(A) denote the ap- proximate coverage function computed using these sets. The greedy algorithm Theorem 2 pro- vides a (1 - apprroxixmiin to the maximization of II(A)) since the proof relies solely on submodularity and monotonicity of the input function-bbot both of which are preserved under the ap- proximation (as the union of approximate sets still yields a valid set function).
To relate this back to the true optimum IIAA),, we leverage the uniform error bound from Lemma (Appendix A.3), which ensures that for any set A:
[Ī(A) [(A) < with high probability(2 - 5).
Let À be the set returned by greedy maximization over Ii, and A be the optimal set under the true objective The greedy guarantee gives:
i(A) (1 ( i(A*).
By the uniform bound, we know ri(A*) 2 11(A") - 0, so:
m(A) 2 (1 (1-
1 (TT (TT(*)) 0) (1 (1-2) IT(A)) (1-2) a.
Thus, even when using approximate Rev-k-NN sets, the greedy algorithm achieves the following guarantee on estimated coverage:
īi(A) 2 1 11- II(A)) - -11- 0
A.7 Impact of parameters
All experiments in this section are conducted on two large-scale benchmarks- (ho- mophilous) and Questions (heterophilous) to evaluate three critical hyperparameters:
Rev-k-NN neighbourhood size (k). Fig. 17 shows that moderate choice of i maximizes fidelity for both WikiCS and Questions. On WikiCS, increasing & from 1 to 5 raises mean fidelity from 0.72 to 0.78, after which fidelity declines (0.72 at 20, 0.69 100). Likewise on Questions, fidelity peaks at 0.92 for A: = 5 and then falls to 0.86 at k = 100. These trends indicate that too small prototype set under-covers the class distribution, while too large set introduces noisy, less representative examples.
25

---

Table 5: Accuracy of the underlying GNN and fidelity of GNNXEMPLAR across different GNN
architectures on TAGCora
Architecture
GNN Accuracy (%)
Fidelity (%)
GraphSAGE
68.91
76.75
GCN
68.71
79.11
GAT
73.84
83.00
Training set sampling size. Fig. 18 evaluates the number of positive and negative nodes used to generate feedback in each self-refinement iteration. Fidelity on both datasets peaks at a sampling size of 20 (0.78 for WikiCS, 0.92 for Questions). Smaller sample sizes (I or 5) under-represent mis- classified patterns, yielding lower fidelity, whereas excessively large samples (100 200) introduce so much data that the LLM struggles to distill the most salient corrective signals
Sampling rate for exemplar selection. Fig. 19 shows fidelity and runtime as a function of the fraction of nodes used to compute Rev-k-NN prototypes. Fidelity rapidly saturates by 5-10 % 0.75-0.78 on WikiCS and 0.86-0.92 on Questions--wile full sampling (100 %) incurs ma-gnniude higher runtimes (0.7 s - 690 s on WikiCS; 0.01 s + 41.6 s on Questions) without significant fidelity gains. This demonstrates that small fraction of the data suffices to produce explanations of near-state-of-the-a fidelity at minimal computational cost.
Practical recommendations. In light these results, we recommend setting = 5, using posi- tive-negative sample size of 20 per iteration, and sampling 5-10 % of nodes for exemplar selection to balance explanation quality and efficiency.
A.8 Robustness Across GNN Architectures
To assess the generalizability to GNN architectures, we apply to three widely-used GNN back- Tanes-GraphSAGEE GCN, and GAT each trained on the same node-classificttion task for the TAGCora dataset. Table summarizes both the GNN'S accuracy and the fidelity of our extracted rules.
Despite differences in representational power and message-passing mechanisms, GNNXEMPLAR achieves consistently high fidelity ranging from 76.8 % for GraphSAGE to 83.0 % for GAT. These results confirm that GNNXEMPLAR reliably translates diverse learned graph representations into interpretable symbolic rules.
A.9 Dataset Descriptions
We evaluate our method on eight established node-classification benchmarks, chosen to span ho- mophilous and heterophilous graphs, text-driven and purely structural domains:
TAGCora A citation network of 2,708 computer-science papers connected by 10,556 directed edges. Fach node corresponds to a paper and is featurized by its title and abstract text. The task is predict one of seven topic categories the node level.
CiteSeer A citation network of 3312 publications partitioned into six topic labels. Edges indicate citation links. Each paper is represented by a 3703-dimensional binary bag-of-words vector. ogbn-arxiv A directed graph of all CS arXiv papers indexed by MAG, with 169343 nodes and 1 1166243 citation edges. Node features are 128- 2is-emmnsio vectors formed by averaging skip- gram embeddings over title and abstract text. The 40 subject-area labels (e.g. cs.Al, cs. cs.LG) yield a 40-way classification task.
WikiCS A homogeneous hyperlink network of 11701 Wikipedia articles across ten computer- science categories, connected by 216123 edges. Node features are 300-dimensional averages of pretrained Glo Ve word embeddings over the article text.
26

---

Amazon-ratings A product co co-purchase graph (24492 nodes, 93050 edges) where edges link
frequently co-bought items. The goal is to predict discretized average review scores (five classes).
Each product is featurized by the mean of fastText embeddings over its description.
Minesweeper synthetic 100 x 100 grid (10000 nodes, R39402 edges) modeling the Minesweeper game. Twenty percent of cells contain mines. Node features are one-hot encod- ings of the true count of adjacent mines, with a binary "unknown" flag on 50% of nodes.
Questions A user-interaction graph from Yandex Q (48921 nodes, 153540 edges), where an edge indicates one user answered another's 's question over one year. The binary classification task pre- dicts which users remain active. Node features combine fastText averages over user-profile text with a binary "no profile" indicator.
BA-Shapes A synthetic heterophilous graph built by attaching 80 five-node "house" motifs to 300-node Barabási-Albert backbone, then adding random edges (10% of number of nodes). Each node is labeled tip, middle, base, or background.
B Human Evaluation
We designed and executed a survey in the form of an A/B test to compare the interpretability of text-based explanations versus traditional subgraph-basedn explanations.
Survey Setup Participants were shown global explanations for the same GNN model, one in the form of a subgraph(s) and the other as a textual rule. Their task was to evaluate both independently and indicate which modality better communicated the model's 's reasoning for classifying particular class of nodes. We explicitly clarified the meaning of global explanations - those meant to summa- rize common decision patterns across all nodes of given class in contrast local explanations that are tailored to individual nodes. To help participants make an informed judgment, we included clear and detailed instructions at the beginning of the survey. These instructions emphasized that:
Each explanation should be evaluated in isolation.
Participants should not attempt to align the textual and subgraph formats.
The goal is to judge which modality stands better on its own in helping them understand the GNN's reasoning.
Participant Demographics We recruited 60 participants with least basic proficiency in ma- chine learning for 5 A/B tests amounting for 300 total comparisons. All respondents came from computer science engineering background, and we deliberately sampled both experts, i.e., searchers actively working on graphs, and non-experts, who may work in other ML domains but still familiar with model reasoning and classification tasks. This balance allowed to assess interpretability across varying levels of familiarity with graph-structured data.
Statistical Tests To evaluate user preferences between the two explanation modalities presented across five A/B questions, we conducted both Binomial test and McNemar's test. The Binomial test, applied to the aggregate responses (275 total comparisons), assesses whether one modality was preferred significantly more often overall. While informative, this test treats each question response as independent and does not account for within-subject consistency. To address this, we additionally used McNemar's test, which considers per-user paired choices across the five questions, capturing whether individuals systematically favored one modality over the other. Together, these tests pro- vide complementary insights: the binomial test reflects population-leva preference strength, while McNemar's 's test confirms the consistency of that preference at the individual level.
Survey Materials and Transparency To ensure full transparency and reproducibility, we include screenshots of key survey components in the Appendix. Fig. 6 shows the welcome page, which introduced the task, explained the distinction between global and local explanations, and outlined the survey objective. Fig. 7 presents the instructional page detailing how to interpret and evaluate the two explanation modalities. Fig. 8 shows representative A/B test question featuring a dataset description and both types of explanations. Finally, Fig. illustrates the evaluation criteria provided before each A/B comparison to guide participants in making modality-specinf judgments. These materials demonstrate the care taken to ensure participants understood the task and the evaluation criteria, lending credibility to the findings reported in Sec. 4.7.
27

---

Controlling for Content Differences Across Modalities The goal of this survey was to compare the modalities of explanation text versus subgraph- not their content richness. Since our textual explanations are generated automatically, we needed to ensure that the subgraph explanations were as close in content as possible to the text ones, so that the only difference being judged by participants was the modality, not the information conveyed.
Our textual explanations include both structural and feature-based insights. For example, Fig. 14 shows the explanation for the Rule Learning class in TAGCora: Publications in "Rule Learn- ing" " contain keywords such as "inductive logic programming." "meta- teeta-knoweedge"" or "hypothesis space," and/or their immediate and 2-hop citation neighborhoods are predominantly Rule Learning papers.
This explanation draws on both graph topology and node features (keywords). However, subgraph visualizations cannot communicate high-dimensional features how would one visually encode 128-dimensional feature vector within a graph view?
To address this mismatch and ensure a fair comparison, we intentionally disabled feature informa- tion while generating the text explanations used in the survey. This ensured that both explanation types were grounded purely in structure, making the comparison about modality alone. Without this control, the text-based explanations would have had an inherent informational advantage, introduc- ing bias into the survey.
This content difference is illustrated in Fig. and 8. The former shows a feature-rich explanation, while the latter corresponds to the feature-neutral version used in the survey.
Table 6: Precision
Homophilous
Heterophilous
TAGCora
Citeseer
WikiCS
ogbn-arxiv
Amazon-rating
Questions
Minesweeper
ShaSes
GNNInterpreter
NA
0.50 0.00
NA
NA
NA
0.50 0.00
0.54
GCNeuron
0.16 0.00
0.75 0.10
G.Epaiieeerrr
NF
NP
0OM
OOM
NF
COM
0.25 + 0.01
0.37 + 0.00
Ours
0.85 + 0.03
0.95 0.05
0.96 + 0.00
0.99 = 0.00
0.81 + 0.05
0.96 = 0.00
0.81 0.02
0.95 + 0.01
Table 7: Recall
Homophilous
Heterophilous
TAGCura
Citeseer
WikiCS
ogba-arxiv
Amazon-ratings
Questions
Minesweeper
BA-Shapes
GNNInterpreter
NA
1.00 = 0.00
NA
NA
NA
NA
1.00 = 0.00
0.29 2: 0.10
GCNeuron
0.17
0.33 0.00
NA
NA
0.27 + 0.00
NA
0.53 0.00
0:33
GLCExplalner
0:49
Ours
0.82 + 0.02
0.80 0.06
0.58 + 0.03
0.67 + 0.02
0.80 + 0.02
0.81 = 0.04
0.96 + 0.00
0.91 + 0.00
Table 8: F1 Score
Homophilous
Heterophilous
TAGCoca
WikiCS
ogba-arxiv
Amazon--aating
Questions
Mineswepper
BA-Shapes
GNNNnterpreter
NA
0.67 1 0.00
NA
NA
NA
NA
0.67 å 0.00
0.34 & 0.10
GCNeuron
0.15 1 0.00
0.22 à: 0.00
NA
NA
0.26 = 0.00
NA
0.45 2 0.00
0.22 0.00
GL.Esphiier
NF
NF
00M
OOM
OOM
0:33
4: 0.11
+
0.08
+
0.77 0.01
=
0.87 0.01
0.93 +
28

---

Comparing global explanation modalities for Graph Neural Networks
Thank you for participating this study on explainability of Graph Neural Networks (GNNs)!
In this study, will explore how a trained GNN classifies nodes into particular classes. For each classification task, you will be presented with:
global explanations of the One the of a subgraph visualization
One as a textual description
Q What Explanations?
explanation tells you why model makes particular prediction what pattern picked up. this survey, explanations take the of subgraph visualizations textual summaries that highlight the patterns the GNN has learned.
Q What "Global" Explanations?
The explanations this survey meant be global explanations this key point:
Unlike explanations, which justify why one specific node was way, resulting in one explanation per node,
Global explanations aim to show the common reasoning the model uses across all nodes of given class, resulting in one explanation class of nodes.
Task
Review both explanations independently.
Decide which modality subgraph or text - better helps you understand how the model thinks about the entire class.
Notes
There are no right wrong answers - we'r interested in your preference.
Just let us know which explanation you find more helpful and understandable.
We appreciate your time and insights!
Target Audience: Individuals an engineering ieliground-preferrbbae in Computer Science-and a foundational understanding of machine learning.
Duration: 7-10 minutes
PS: SurveyCircle receive points for their participation, which can be used to
free survey perticipants SurveyCirole.com
Figure 6: Welcome page of the user study. This page introduced participants the study's objec- tive, explained the distinction between local and global explanations, described the two explanation modalities, and clarified the task expectations. also included details about the target audience, estimated completion time, and participant incentives.
29

---

Instructions
Evalusting Explanations
Interpreting Subgraph Explanations
Subgraph explanation
Yollow nodes: not class
Wodiee proputio leuu menesies eiailnn
Red-wlilee node: unknown node predicted as dass
explanation separstely:
You be shown two tyoes explanation ote tex form and one ns subgraphh Plazae sossss each on own, inckpandenty..
Don't upend matching them:
Avaid
cormiste explanation with explanation: Theat standalone jusiiication.
thi survey you'll come across subgragh explanations as show the figure
above.
Focus on the node marked with white der this reprecenativve examppe.
Imagine each Only explenation
Imagine you're understand caraan nockes labeled explonation
When wewiing text explanation, sesume this information you about models reasoning, Do the some when viewing the subgraph explanation.
tysicaly negettornoods
reprosentatvv
Fosue on what each modality conveye individualy:
Think oricaaly: acceus
explanation, would understand
Note: full graph.
dedisin?
The sutgrriph only shows the local neittoorooo around the whit--dotod rode: Red
nodes near the edge the nungraph may appeer difierent simply because their full context shown. Keep thia when drawing conckisions.
Judgment
reviewing both explanations
which modelity - lext subgruph
more offectivtly communicatie modefs reasoning
Figure 7: Instructions shown participants prior to the survey. These guidelines clarified how to interpret subgraph and text-bat based explanations, emphasized evaluating each modality independently, and explained the concept of global explanations to ensure consistent and meaningful user responses.
CORA
Textual explanation
chaton nelvork where rpprasent papers, edges
between tham Each fuature vector baeed on bap-ch-ceed reprosetation paper's abetret Papers seinngg eeven ciasses
machine leoniing topks However the closs label unknown some sodes, lask to prodict
Class: Rule Learning
Rule learning publications are characterized by strong association with other rule learning publications; significant portion (at least 40-50%) of their 1-hop neighbors, and substantial portion their 2- 2-hop neighbors (at least 40- 90-50%), also fall under the rule learning category. The stronger the association (with least immediate
Learning
belonging Loamnig"
CORA-guph.
Subgraph explanation
node: Rule
Yellow sodka: Not nule leaming nodes
Red white node: unknown node preditted oo rule leaming
50% of 2-hop neighbors being rule learning publications, or even higher percentages), the more likely publication is to be classified as rule learning publication.
Figure 8: Example survey question shown to participants. This page presents the task context for were shown a dataset description followed by two
a global explanation explanation modalities (text-based and subgraph-based) for the model prediction and asked to select their preferred one.
30

---

Answer 1 of 1: Which global explanation do you prefer?
Please consider the following when making your choice:
1. Will the explanation generalize to all nodes of the selected class - not just individual examples?
2. Is the modality (graphical textual) well-suited to how you prefer to interpret information?
How clearly does the explanation communicate the model's reasoning for classifying nodes into this class?
4. If you had to rely on one explanation to understand or trust the model's behavior, which would you choose?
Text
Subgraph
Figure 9: Evaluation guidelines provided before each A/B comparison. Participants were instructed to evaluate each explanation independently, avoid aligning the two modalities, and judge which one more effectively communicates the model's reasoning on its own. These instructions ensured unbiased, modality-specific assessments.
31

---

You given an exemplar node and aet of nodes that belong to its Rev-k-NI nodes that do NOT
(from GNN embedding). Also provided belong to this Rev-x-NN set. Please propose an INITIAL symbolic rule-based formula that outputs 1 for Rev-x-NN set nodes and 0 for non-Rev-K-NN set nodes. Remember that your rules should not be generic and should be specific ONLY node features and local adjacency information. Focus finding what features and structural neighborhood information makes the Rev-k-111 set nodes similar and the non-Rev-k-Ilt set nodes dissimilar to the exemplar node. Use them to form the rules.
the exemplar node and its Rev-k-NN set. Rely
Output your explanation JSDN with a top-level rules list and an interpretation key. Also implement Python function called classify_node __nde() that takes a node_ vode_description as input and returns 1 or 0. Ensure the code dependencies without any errors. Avoid using regex, or importing any more external libraries. Also ensure that the code inside the classify_node function only, and nothing should be outside it.
independently without external file
Exemplar node: 11757
Exemplar node description:
{
modd__id'; 11757,
'features': [0. 067857777 0. 0.11838776, 3. 94833946],
'1-hop': theighbor_class_feee
{1: 1.0)),
'2-hop': ('neighbor_class_fee) {1: 1.0)}
}
Rev-k-NN set nodes: [2593, 9375]
NON-Rev-X-NN set nodes: [32414, 14315]
Descriptions of Rev-x-NN set nodes:
Node 2593: ['node_id': 2593, 'features': : 10.07221082, 0. 1.1122487,
3. 8.92639644], '1-hop': : ('neighbor_clas ceaborr_laas___ freq': {1: 1.0)), '2-hop':
('reighbor_class_free {0: 0. 0.4736842, 1: 0. 5263158))3
Node 9375: {'node_id' 9375, 'features': [o. 13466499, 0. 0414999602,
0. 0.334483,), '1-hop':
saaasbboo__lss__teeeeeeeessessse brnighbor_classffeeee (0: 0.4736842, 1: 5.663318)))
(1: 1.0)), '2-hop':
Descriptions of non-Rev-k-II aet nodes:
Node 32414: {'node_id': 32414, 'featurea': : [0. 05580222, 0.08147032, 06311333)), '1-hop': beeiighor_class_ffee { Nueighhor_cllss_ffee clar__llss____e_ {0: 1.03}}
(0: 1.0)}, '2-hop':
Node 14315: ('node_id' i 14315, 'features': [0. 08261999,,, 507772273, 0.49223183), '1-hop': { ('neighbor wwwpgghhoorrrsass_eeeee freq': class_freq': {0: 1.0)), '2-hop': f'neighbor_cles caarrrcccss____eeeeeeeeeeeeeeeee freq': {0: 1.0}}
Figure 10: Query prompt given to the LLM on the questions dataset
32

---

Below is the CURRENT formula: def classify_node (mode_descriptioon):
try:
if node_ ttte_ddssrrpptioooffetteee [2] 3.0 and
node_ descriptionn'1-toane ['neighbor _aaoorr_llsss_aaeeeeeeeeeeeeeees [req'] "ett'(1 0) > 0.5:
return 1
else:
return
except (KeyError, IndexError): return
was evaluated on Rev-k-NN set nodes (should be and non-Rev-k-Nl set nodes (should be 0). It yielded false negatives and 0 false positives.
False Negatives (Rev-X-NN set nodes misclassified Ron-Rev-k-NI set): Node 1920: ('node_id'; 1920, 'features': array 04922352, 192133117, 0.6143764 1),
'1-hop': ('neighbor_cee theeihhor_class_aae class_free'' (0: 0.5714, 1: 0.42863},
'2-hop': { briighoorclass_freeee {o: 0.9715, 1: 0. 0.0285)}} ('node_id" id'; 15365, 'features'; array O09.5447774 0.19516333,
Node 15365:
0. 0.59393266)),
'1-hop' theighbor_class_fee
(1: 1.0)),
'2-hop': ('neighbor_ ("neighbor_class_fres) cattoo__las__eepee_ (0: 0.25, 1: 0.75))}
False Positives (non-Rev-k-NI nodes misclassified Rev-k-NM set): None.
Your goal is to improve the formula that it does not make these errors while preserving its correct predictions. Provide detailed feedback which condition to add, remove, or modify, and state the single most important change to make. Do not supply the revised code yet.
Figure 11: Feedback prompt given to the LLM on the questions dataset
33

---

Below is the history of previous iterations:
Iteration 0:
Formula:
def classify_node node (node_descriptionn)
try:
if node wtw.derriipcioooffettrreeee [2] 3.0 and
wtw.deerrppionnnt1n ['neighbor_clere claass____sss___aeeeee caaps__frsaa____ get(1, 0) 0.5: return
else:
return 0
except (KeyError, IndexError);
return
Positives Accuracy: 0.480317460317466055, Negatives Accuracy: 1.0
Actionable Feedback:
The single most important change to improve the formula is increase the seeighbor_class__fi
threshold for
0) from 0.5 to 0.7. The current threshold is too lenient, allowing nodes with significant proportion of non-class neighbors be incorrectly classified Rev-k-NI members. Raising
threshold will better discriminate between Rev-k-NN set non-Rev-k-Hli set nodes based on 1-hop neighborhood information.
Further adjustments to the feature threshold might also be beneficial, but addressing the neighbor frequency threshold is the most impactful initial step.
Using the history above, and the last feedback, please produce a REVISED formula in JSON format with top-level 'rules' list and 'interpretation' key. Your goal is to improve the accuracy metrics by addressing the feedback provided. You must achieve least 95% positive and negative accuracy. Also, implement a Python function called classify_node node node_ dedd_ddecription as input and returns 1 or 0. Ensure the code can run independently without external file dependencies and without any errors. Avoid using regez, importing any more external libraries. Also code inside classify node function only, and nothing should outside it.
that takes a
that
Figure 12: Refine prompt given to the LLM on the questions dataset
34

---

def O (
features node_descriptiin. get (taplioonneeetetaaeeeearaaaa ('features', ")
one_hop node_descriptiion get ('1-hop', ()) get (
neighbor_class_freq ())
two_hop zode_description get ('2-hop', ()) .gtt( (*
geighbor_class_freg, ())
Exemplar #1 signature
score1 = 0.5 * int (any (k in features
for k in ['ILP', 'neta-knovvedge',
hypothesis apace
score1 0.3 int (one_ somee_hp.geee hop. 0.8)
score1 += 0.2 * int (two__hoo get (0,0) 0.8)
cond1 (score1 >- 0.5)
Exemplar signature
score2 0.5 int (any (kw in features lover for kw in ['logic program', 'inductive logic programming', I))
score2 int (one_ hop. get get (0,0) > 0.7) score2 0.2 int _hop_ get (0,0) > 0.5)
cond2 (score2 >- 0.5)
cond1 cond2
Class 0 (Rule Learning)
A publication belongs to the Rule Learning class if its text mentions "inductive logic programming." "meta-knowledge." or "hypothesis space," or large majority of its 1-hop and 2-hop citation neighbors also belong to Rule Learning.
Figure 13: Global explanation for TAGCora class 0 (Rule Learning): Top - the Python implementa- tion the OR of two exemplar signatures; Bottom the human-readable description.
35

---

Global Explanations for TAGCORA
Class (Rule Learning)
Publications in "Rule Learning" contain keywords such as "inductive logic programming," "meta-knowledge." "hypothesis space," and/or their immediate and 2-hop citation neigh- borhoods are predominantly Rule Learning papers.
Class (Neural Networks)
Papers in "Neural Networks" mention terms like "neural network," "backpropagation," "neu- rons," " or "activation functions," and/or their and 2-hop neighbors largely in the Neural Networks class, occasional focus on ICA or HMM further reinforces this label, while men- tions of other paradigms reduce likelihood.
Class Base-B
Case Based publications include phrases such as bease-based reasoning," " "adaptation," or "planning," and frequently cite other Case Based works within one or two hops; secondary indicators include words like "learning" and "explanation."
Class (Genetic Algorithms)
Genetic Algorithms papers feature keywords like "genetic algorithm," "evolutionary algo- rithm," or "genetic programming." and/or their 1 1-hop and 2-hop citation graphs are enriched with other Genetic Algorithms publications.
Class (Theory)
"Theory" articles discuss Bayesian methods, classifiers, or decision trees, and/or they are frequently cited by, and cite, other Theory papers within one or two hops; strong Theory neighborhood further disambiguates this class.
Class (Reinforcement Learning) terms such as "real-time," "online," "neuro-evolution" and/or their direct and extended citations predominantly belong to the Reinforcement Learning class.
Reinforcement Learning papers mention "reinforcement learning," "TD learning," related
Class (Probabilistic Methods)
Probabilistic Methods works include keywords like "Bayesian network," "Markov chain," "density estimation," "Gibbs sampling," or "MCMC," and/or at least 20-80% of their 1-hop and 2-hop neighbors are also Probabilistic Methods publications.
Figure 14: High-level, human-readable rule summaries for each class in the TAGCora dataset gen- erated by our global explanation pipeline (see Fig. 13 for the detailed Python implementation and interpretation of the Rule Learning class).
36

---

Global Explanations for BAShapes
Class 0 (Not in House)
Nodes not belonging to a house are characterized by having many (at least 6, often more than 8) neighbors that also don't t belong to house, and only few (at most 2) neighbors in the house structure-reflccting their isolation from any house motifs.
Class (Middle of House)
"middle" node sits on the roof slope: it has exactly one tip neighbor, one base neighbor, and the other middle node motif-neighhors, and at most two additional connections to non-house nodes.
Class 2 (Base of House)
A "base" node is directly connected to exactly one middle node and exactly one other base node, with links any other classes.
Class (Tip of House)
A "'tpp" node occupies the apex of the house motif: it connects exclusively two class- (middle) nodes and has no edges to any other class, forming the roof's peak.
Figure 15: High-level, human human-readable rule summaries for each class in the BAShapes dataset gen- erated by our global explanation pipeline.
Global Explanations for QUESTIONS
Class (Active Users)
Active users Yandex Q are those whose immediate neighbors and 2-hop neighbors also predominantly active, indicating engagement within a highly interactive community,
Class (Inactive Users)
Inactive users exhibit feature profiles closely matching the exemplar node 11757 and have at least 50% of their immediate neighbors inactive, reflecting their embedding within a low- activity subnetwork.
Figure 16: High-level, human-readable rule summaries for each class in the Questions dataset gen- erated by our global explanation pipeline.
WikiCS
Questions
0.78
0.92
0.90
0.76
0.88
Fidelity
Fidelity
0.
0.86
0.84
0.72
0.82
0.70
0.80
is
20
100
15
168
Figure 17: Effect of the Rev-k-NN & on explanation fidelity for WikiCS and Questions. Each subplot plots mean fidelity over five runs as & varies.
37

---

Wikics
Questions
775
0.900-
0.875
Fidelity
725
Fidelity
0.850
0. 700
0.825-
0.675
0.800
0.775
0.758-
Sampling size
Sampling size
Figure 18: Questions.
Impact of the training set sampling size on the explanation fidelity for WikiCS and
WikiCS
Questions
0.78
0.92.
0.
0.90
0.76
0.88
Fidelity
0.75
0.86
0.74
0.82
8.72
0.80
1518
1510
Sampling rate (%)
Sampling rate (%)
(a) Fidelity vs. sampling rale
WikiCS
Questions
48
0.6
0.4
Runt tine
28
0.2:
0.0 0--
1.5 19
100
15:10
189
Sampling rate (%)
Sampling rate (%)
(b) Runtime vs. sampling rate
Figure 19: Trade-off between runtime and fidelity as a function of sampling rate for WikiCS and Questions: (a) Fidelity function of sampling rate; (b) Exemplar selection runtime versus sam- pling rate.
38


Reviews:
[{"review_id": "eqAjhz9cGA", "reviewer": "Reviewer_R8Cq", "summary": "The paper introduces an approach for model-level explanations of GNN\npredictions focused on node classification in large graphs, where\nmotif-based explanations are less likely to be effective (and are\nexpensive to compute). The approach combines the identification of\nexemplars node characterizing the model behavour for each class with\nthe extraction of textual explanations via LLM prompting.", "questions": "- How does the reverse k-NN selection problem differs from coreset identification?\n\n- Can you clarify what precision/recall/f1 represent? are these referring to the classification performance on the explainer? what about the one of the original GNN?\n\n- BAShapes: how are labels incorporated? as additional attributes?", "limitations": "The work does include a paragraph on limitations. However I see a main limitation that is not discussed, with is the strong bias in guiding the LLM to extract explanations, and the difficulty in\nadapting it for truly topological patterns.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\n\n- The approach addresses a poorly explored task, which is model-level\nexplanation in node classification. \n\n- The proposed solution is sensible, well-motivated and explained. \n\n\n# Weaknesses\n\n- The problem of identifying exemplars sound very similar to the one of\ncoreset selection. It would be useful to understand why the authors\ncould not use this well-developed framework and how the proposed\nsolution differs from it. \n\n- The approach sounds like a prototype-based explainability method. I\nguess the PAGE approach [1] is a very relevant piece of work that\nshould be cited and compared with (even if the focus on graph-level\nexplainability remains).\n\n- The key element allowing LLMs to generate interpretable explanations\nis the summary of the node neighborhood. A very strong bias is\nintroduced there, as the topology is flattened into sets of l-hop\nneighbors, and the attributes are treated independently. This is\nreflected in the explanations being generated. I have the impression\nthat this approach would have problems when topology and attribute\nrelationships play a stronger role in the prediction. \n\n# Minor points\n\n- For the sake of consistency, I would use lowercase non-calligraphic letters for individual classes (calligraphic letters indicate sets in the paper)\n\n- Phi is used in Def. 4 before being introduced.\n\n[1] Shin, Y.-M., Kim, S.-W., Yoon, E.-B., & Shin, W.-Y. (2022). Prototype-Based Explanations for Graph Neural Networks (Student Abstract). Proceedings of the AAAI Conference on Artificial Intelligence, 36(11), 13047-13048. https://doi.org/10.1609/aaai.v36i11.21660", "was_revised": true, "final_justification": "The authors addressed my concerns in a satisfactory way in the rebuttal. I expect the main aspects of the feedback to be incorporated in a revised version of the manuscript.", "rebuttal": "We thank the reviewer for the constructive feedback on our work. We hope the proposed revisions and clarifications would address the concerns raised.\n\n-----\n > **q1 and w1. The problem of identifying exemplars sound very similar to the one of coreset selection. It would be useful to understand why the authors could not use this well-developed framework and how the proposed solution differs from it.**\n\n**Ans.** Thank you for the thoughtful observation. While our exemplar selection shares surface similarities with coreset selection—both involve selecting representative data points—their goals, design principles, and outputs differ fundamentally:\n\n1. **Objective Misalignment:**  \n   Coreset selection is primarily geared toward preserving predictive performance. It identifies a subset of training data such that learning on this subset yields comparable accuracy to learning on the full dataset. This means it often prioritizes samples near the decision boundary—those most informative for minimizing training loss.\nIn contrast, our goal is global interpretability, not prediction. We seek exemplars that capture the semantic diversity of a class in the GNN embedding space. The goal is to find prototypical points—not ambiguous ones near the decision boundary—that characterize dense, consistent regions of class semantics.\n\n2. **Coverage vs. Loss Optimization:**  \n   Coreset methods evaluate the *joint effect* of selected points on the training objective. Our method optimizes a *submodular coverage function* (Eq. 2) over reverse k-nearest neighbors, ensuring that diverse regions of each class are well-represented. This leads to greater interpretability, even when using very few exemplars (often 2–3 per class), which would be insufficient for a coreset due to underfitting risk.\n\n3. **Exemplar Populations and Interpretability:**  \n   Our method returns not only exemplars but also their *populations*—i.e., the set of nodes each exemplar represents via reverse k-NN. This is critical for generating *explanation rules* (signatures), as the rule is learned over the exemplar’s population. Coresets do not provide such mappings, and thus cannot support this explanation mechanism.\n\n4. **Interpretability Trade-off:**  \n   Since coreset points may lie near decision boundaries, they tend to be ambiguous or noisy—counterproductive for human interpretation. Our approach deliberately avoids such regions to ensure that selected exemplars yield *clear, faithful, and symbolic* global explanations.\n\n\n> **w2. The approach sounds like a prototype-based explainability method. I guess the PAGE approach [1] is a very relevant piece of work that should be cited and compared with (even if the focus on graph-level explainability remains).**\n\n**Ans:** Thank you for pointing us to PAGE. While it is a relevant prototype-based explainer, it is fundamentally designed for *graph-level* tasks on small datasets with *discrete* features, and does not scale to the *node classification* setting on *large graphs with high-dimensional or continuous node features*.\n\nWe attempted to run PAGE on our benchmarks using the official codebase but encountered crashes on all datasets. The core reasons are:\n\n1. **Scalability Issues:**  \n   PAGE performs prototype search using a Cartesian product across graphs, resulting in a combinatorial explosion (O(n³) for k=3), which is computationally infeasible on large graphs.\n\n2. **Feature Constraints:**  \n   The method assumes one-hot or categorical node features. Most of our datasets use continuous or bag-of-words features, making PAGE incompatible without significant reengineering.\n\n3. **Subgraph Matching Limitations:**  \n   Even if subgraphs are extracted, evaluating fidelity becomes intractable due to the difficulty of subgraph isomorphism over continuous features.\n\n4. **Rigid Output Modality:**  \n   PAGE produces subgraph-based explanations, which—as we discuss in the paper—become unwieldy and less interpretable in large, real-world graphs.\n\nWe will cite PAGE in the related work and include a brief discussion outlining these limitations in the revised version.\n\n> **w3 and Limitations. The key element allowing LLMs to generate interpretable explanations is the summary of the node neighborhood. A very strong bias is introduced there, as the topology is flattened into sets of l-hop neighbors, and the attributes are treated independently. This is reflected in the explanations being generated. I have the impression that this approach would have problems when topology and attribute relationships play a stronger role in the prediction.**\n\n**Ans:** We agree with the reviewer that flattening the neighborhood structure into a set of aggregated l-hop neighbors limits the LLM’s ability to capture fine-grained structure-attribute relationships. However, we clarify that GnnXemplar is not inherently limited to aggregated prompts. This design choice was made for two practical reasons:\n\n1. **LLM context constraints:** Real-world graphs often have large or dense neighborhoods, making it infeasible to encode full adjacency structures within the LLM’s context window. Aggregated representations offer a scalable compromise for such settings.\n2. **Nature of real-world graphs:** As motivated in the paper, most real-world node classification graphs (e.g., citation, product, or social networks) do not contain clear, repeating motifs where explicit structure is predictive. In such cases, preserving exact topological detail is unnecessary and even distracting.\n\nThat said, the self-refine pipeline is flexible. In domains where explicit structure-function relationships are crucial (e.g., molecular graphs), users can customize the initial prompt format to include explicit neighborhood structure and features. For instance, if the graph is small and contains rich structural motifs, the user can override the default aggregation and feed detailed structural information directly. The LLM will then learn to generate structure-aware explanations accordingly.\n\nTo further demonstrate that GnnXemplar can operate effectively even in settings where structure-attribute synergy is essential, we designed a synthetic dataset where flattened neighborhood representations are insufficient, and neither structure nor features alone suffice for explanation.\n\n**Dataset Design**:\nNode features consist of two colors: red and blue. Class labels are defined as follows:\n\n- **Class 0**: A node is in class 0 if it is red and part of a triangle where others are also red.\n- **Class 1**: A node is in class 1 if it is red and it belongs to a diamond structure (a 4-cycle), regardless of the colors of the other nodes in the house.\n- **Class 2**: A node is in class 2 if it is blue and it belongs to a diamond structure (a 4-cycle), regardless of the colors of the other nodes in the house.\n- **Class 3**: Any node not satisfying the above conditions.\n\nTo make the task non-trivial, we deliberately injected confounding impurities, such as:\n- Blue nodes in triangles.\n- Red nodes connected to two red neighbors that don’t form a triangle.\n- Chains of length four to confound diamonds.\n\nClearly, correct classification here requires joint reasoning over both features and topology. Flattened prompts or purely structural/feature-based reasoning would be insufficient.\n\nGnnXemplar, when run with prompts that preserved structural detail, achieved 93% fidelity.\n\nThe generated explanations were:\n```\nClass 0:\nA node belongs to class 0 if it is red, part of a triangle, not part of a diamond, has two or three connections to other nodes.\n\nClass 1:\nA node belongs to class 1 if it is red and part of a diamond shape, but not part of a triangle shape.\n\nClass 2:\nA node belongs to class 2 if it is blue and is part of a diamond shape.\n\nClass 3:\nClass 3 nodes are typically red and part of a triangle, but can also be blue and part of a triangle; nodes that are part of a diamond shape are less likely to belong to this class.\n```\n\nThese explanations demonstrate that GnnXemplar can effectively discover and express complex class-level patterns even when fine-grained structure-feature relationships are required.\n\nWe hope this evidence reassures the reviewer that GnnXemplar is not limited to flattened neighborhood reasoning and can handle datasets with strong structure-function dependencies when prompts are crafted accordingly.\n\n> **q2. Can you clarify what precision/recall/f1 represent? are these referring to the classification performance on the explainer? what about the one of the original GNN?**\n\n**Ans:** All the metrics are calculated against the GNN's predictions, not the ground truth.\n\n> **q3. BAShapes: how are labels incorporated? as additional attributes?**\n\n**Ans:** In BAShapes, as in all our datasets, we do **not** provide ground-truth labels to the LLM. The LLM only receives the **GNN’s predicted labels**, as stated in lines 257–259. By using predicted labels rather than true ones, we ensure that the LLM explanations reflect the **GNN’s learned behavior**, not the dataset’s ground-truth semantics.\n\n> **Minor points**\n\nThank you for pointing them out. We will address them.\n\n[1] Shin, Y.-M., Kim, S.-W., Yoon, E.-B., & Shin, W.-Y. (2022). Prototype-Based Explanations for Graph Neural Networks (Student Abstract). Proceedings of the AAAI Conference on Artificial Intelligence, 36(11), 13047-13048"}, {"review_id": "TrquTsPwNF", "reviewer": "Reviewer_b9jp", "summary": "This paper proposes GNNXEMPLAR, a novel global explanation framework for Graph Neural Networks (GNNs) applied to node classification tasks. The method draws inspiration from exemplar theory in cognitive science, selecting representative nodes (exemplars) in the GNN embedding space and generating global explanations via natural language rules derived from their neighborhoods. Exemplar selection is formulated as a coverage maximization problem using reverse k-nearest neighbors, solved via a greedy algorithm with submodular approximation guarantees. The natural language rule generation employs a self-refining prompting strategy leveraging large language models (LLMs). Extensive experiments across multiple homophilous and heterophilous benchmarks demonstrate GNNXEMPLAR's superiority in fidelity, scalability, and human interpretability.", "questions": "See above weaknesses.", "limitations": "YES", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper addresses a clear gap in GNN interpretability research by focusing on global explanations for node classification on large, real-world graphs with high-dimensional node attributes. The shift from motif-based to exemplar-based explanations is both novel and well-motivated.\n2. The combination of reverse k-NN for exemplar selection and LLM-driven self-refinement for natural language rule discovery is highly innovative. The theoretical formulation, including NP-hardness proofs and submodularity-based greedy optimization, demonstrates methodological rigor.\n3. The experiments are extensive, covering a diverse set of datasets, GNN architectures, and both homophilous and heterophilous graphs. Ablation studies clearly demonstrate the contribution of each module.\n\nWeaknesses:\n1. The explanation of GNNXEMPLAR is actually \"mimicking the output behavior of GNN\", but it does not really restore the decision logic of the internal mechanism of GNN. And the whole method is highly dependent on whether GNN has learned embeddings with semantic distinction ability during training. Once the GNN training effect is poor or overfitting or underfitting, the quality of Exemplar selection and explanation rules will be affected.\n2. The comparison focuses primarily on global explainers adapted from graph classification; comparisons to more recent feature-attribution-based or counterfactual node explainers could provide additional perspective（GOAt，COMRECGC）.\n- [1] Lu S, Mills K G, He J, et al. GOAt: Explaining graph neural networks via graph output attribution[J]. arXiv preprint arXiv:2401.14578, 2024.\n- [2] Fournier G, Medya S. COMRECGC: Global Graph Counterfactual Explainer through Common Recourse[J]. arXiv preprint arXiv:2505.07081, 2025.\n3. The current framework operates only on the embedding space and lacks full visibility into the internal feature-topology interactions of GNNs, limiting its mechanistic interpretability.", "was_revised": false, "final_justification": "", "rebuttal": "We really appreciate your detailed comments. They have improved our work.\n\n----\n> **w1a. The explanation of GNNXEMPLAR is actually \"mimicking the output behavior of GNN\", but it does not really restore the decision logic of the internal mechanism of GNN.**\n\n**Ans:** We agree that GNNXEMPLAR does not recover the internal decision logic of the GNN in a mechanistic sense. We will clearly note this limitation in the revised version.\n\nThat said, GNNXEMPLAR is not simply mimicking GNN outputs through a detached surrogate model. Its exemplar selection operates directly over the GNN’s latent embedding space, leveraging reverse k-nearest neighbor (rKNN) relationships to identify points that capture the semantic structure induced by the model. The resulting explanations reflect how the GNN partitions and organizes the embedding space to encode task-relevant decision making.\n\nThis connection between embedding distances with GNN prediction logic is now supported by the ICML 2025 paper `WILTing Trees: Interpreting the Distance Between MPNN Embeddings`, which shows that:\n> *“MPNN distances after training are aligned with the task-relevant functional distance of the graphs and that this is key to the high predictive performance of MPNNs.”*\n\nThey further observe that MPNNs align embeddings more with *functional* than *structural* similarity.\n\n>**w1b ..And the whole method is highly dependent on whether GNN has learned embeddings with semantic distinction ability during training. Once the GNN training effect is poor or overfitting or underfitting, the quality of Exemplar selection and explanation rules will be affected.**\n\nThe reviewer is again correct in observing that GnnXemplar depends on the GNN learning embeddings with semantic separation.  The exemplar selection assumes that the GNN organizes the latent space meaningfully. Therefore, if the GNN underfits the data, and the embeddings are effectively noise, GnnXemplar will struggle to extract meaningful exemplars and subsequent explanations.\n\nHowever, the situation is different in the case of overfitting. When the GNN picks up spurious correlations and learns incorrect patterns, GnnXemplar is able to surface these faithfully, providing valuable diagnostic insight into the model’s flawed decision process. This was demonstrated in our case study in Section 4.6, where class imbalance led the GNN to learn an incorrect oversimplified rule. GnnXemplar followed the GNN's decision logic which revealed that the GNN's logic was misaligned with the intended class semantics. Such insights underscore GnnXemplar's strength as a failure analysis tool as it faithfully surfaces what the model has actually learned, regardless of whether that learning is correct wrt. the ground truth.\n\n>**w2.  The comparison focuses primarily on global explainers adapted from graph classification; comparisons to more recent feature-attribution-based or counterfactual node explainers could provide additional perspective（GOAt，COMRECGC).**\n> - [1] **Lu S, Mills K G, He J, et al. GOAt: Explaining graph neural networks via graph output attribution[J]. arXiv preprint arXiv:2401.14578, 2024.**\n> - **[2] Fournier G, Medya S. COMRECGC: Global Graph Counterfactual Explainer through Common Recourse[J]. arXiv preprint arXiv:2505.07081, 2025.**\n   \nWe thank the reviewer for highlighting these recent methods. We agree that they are valuable contributions to the explainability landscape but note that both **GOAt** and **COMRECGC** target substantially different tasks and assumptions, making a direct comparison to **GNNXEMPLAR** unsuitable:\n\n1. **GOAt** is a *local* explainer that attributes predictions to individual nodes/edges/features via analytical decomposition. In contrast, **GNNXEMPLAR** is a *global* explainer that derives class-level rules using exemplar populations and natural language. The methods differ in scope (local vs. global), output (numeric masks vs. symbolic rules), and mechanism (per-instance attribution vs. population-based abstraction). Aggregating GOAt's outputs into coherent global rules is hence non-trivial. Thus, a direct comparison is not meaningful due to the fundamental differences in objective, output, and interpretability granularity. Nonetheless, we will definitely cite this work and discuss the differences.\n\n2. **COMRECGC** is a *counterfactual global explainer* operating under assumptions that do not align with our problem setting:\n   - It relies on *graph edit distance*, which is undefined for graphs with continuous, high-dimensional node features—common across our benchmarks.\n   - It assumes recurring structural motifs across input graphs, while **GNNXEMPLAR** is explicitly designed for settings where such motifs are rare or absent (e.g., citation or social networks).\n   - COMRECGC focuses on *recourse-based explanations*, requiring binary \"accept\" and \"reject\" classes. This framing does not generalize well to multiclass node classification, where defining a privileged positive class introduces arbitrary asymmetry and limits interpretability.\n   - Despite the above differences, we attempted to run COMRECGC on our datasets, but encountered implementation challenges due to the reasons above—particularly the absence of recurring substructures and the inapplicability of GED in our setting.\n   - Finally, we note that **COMRECGC was published in ICML just weeks back**, which is **two months after the NeurIPS submission deadline**. Nonetheless, we will ensure it is properly cited and discussed in the revised version.\n\n>**w3. The current framework operates only on the embedding space and lacks full visibility into the internal feature-topology interactions of GNNs, limiting its mechanistic interpretability.**\n\nThis connects to our response to w1a. Once again, we accept this limitation and shall explicitly mention it in the final version of our paper."}, {"review_id": "lWNmRsDGzC", "reviewer": "Reviewer_pgJY", "summary": "The manuscript proposes a new framework for GNN explainability built on several main ideas: i) use of exemplars for global explanations (representative nodes), ii) application of an LLM to generate a disjunction of exemplar-specific rules for global explanations, and iii) using ideas from k-nearest neighbor and clustering methods to select exemplars.", "questions": "- Q1: [W1] The definitions are somewhat vague. Specifically, Definitions 3 and 4 are high level descriptions of an idea rather than concrete definitions. Can you provide more concrete definitions for the exemplar and signature? \n- Q2: [W2] It would be helpful to comment on how the results of Theorem 2 would change if an estimate of Rev-k-NN is used (as in practical implementations here) instead of the actual Rev-k-NN. \n- Q3: I wonder if a comparison with instance-level baselines such as GNNExplainer and PGExplainer on synthetic datasets such as BA Shapes can be provided as follows. Since the aforementioned explainers are instance-level, they need to be transformed into global explainers. Can they be combined with the LLM idea in this work, such that the explanation outputs of GNNExplainer and PGExplainer are input to the LLM to output the global rule? If so, how would the accuracy compare with the proposed explainer?", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths: \n\n- S1: The idea of using exemplars for global explanations is novel and quite interesting. \n- S2: The manuscript complements the novel idea of using exemplars with several key innovations which enables a practical approach to exemplar generation including use of reverse k-means for exemplar selection, use of LLMs to generate the logical proposition for exemplar-specific rules, and the way the LLM is used to generate the Python code rather than a natural language explanation directly. Each of these ideas are novel and crucial in constructing an implementable and practical framework.\n-  S3: The manuscript is well-written and contains useful examples and intuitive explanations, e.g., the example after Definition 4 is helpful.\n- S4: The theoretical results, while straightforward to prove, novel and insightful. For instance, Theorem 2, providing a lower bound on the performance of the greedy algorithm is a useful result. \nWeaknesses:\n- W1: The definitions are somewhat vague. Specifically, Definitions 3 and 4 are high level descriptions of an idea rather than concrete definitions. \n- W2: It would be helpful to comment on how the results of Theorem 2 would change if an estimate of Rev-k-NN is used (as in practical implementations here) instead of the actual Rev-k-NN.", "was_revised": true, "final_justification": "As mentioned in my response to the author's rebuttal, the responses have addressed all of my questions. I believe this is a novel and interesting work, and the manuscript is well-written.\n\nWith respect to the review score, I have maintained my evaluation at an Accept, which reflects the manuscript’s high quality and merit. However, I also believe it closely approaches the threshold for a Strong Accept.", "rebuttal": "We appreciate the reviewer's constructive feedback and have revised the manuscript accordingly. We would these changes address the concerns raised. \n\n----\n\n> **q1 / w1: The definitions are somewhat vague. Specifically, Definitions 3 and 4 are high level descriptions of an idea rather than concrete definitions. Can you provide more concrete definitions for the exemplar and signature?**\n\nTo improve precision and clarity, we will supplement our definitions with the following mathematical formulations:\n\n**Definition 3 (Exemplars)**\nA node $e \\in \\mathcal{V}_{\\text{tr}}$ is called an exemplar for the class $c \\in \\mathcal{Y}$ if $|R_e| \\geq \\tau$, where\n\n$$\nR_e = \\left\\\\{ \nv \\in \\mathcal{V}_{\\text{tr}} \\\\ \\middle|\n\\begin{aligned}\n    &\\Phi(e) = c, \\\\\\\\\n    &\\Phi(v) = c, \\\\\\\\\n    &d(z_e, z_v) \\leq \\delta\n\\end{aligned}\n\\right\\\\}\n$$\nwhere $z_v \\in \\mathbb{R}^d$ is the GNN-learned embedding of node $v$, $d(z_e, z_v)$ is some distance function, $\\delta \\in \\mathbb{R}$ is a distance threshold, and $\\tau \\in \\mathbb{N}$ is a minimum population size hyperparameter. As we will see later,  the thresholds will automatically be discovered from the data by exploiting the $k$-nearest neighbor relationship along with a greedy selection algorithm.\n\n**Definition 4 (Exemplar Signature)**\nThe signature $\\sigma_e$ of exemplar $e$ from class $c$ is a boolean function $f(\\pi_1(v), \\pi_2(v), \\dots, \\pi_k(v)) \\in \\{0,1\\}$, such that, with a high probability, $\\forall v\\in R_e, \\sigma_e(v) = 1$, iff $\\Phi(v)=c$. Here, $\\pi_i$ are the predicates that evaluate to Boolean conditions over interpretable properties such as:\n- Node features (e.g., $x_v[\\texttt{age}] > 30$)\n- Local structure (e.g., $\\texttt{degree}(v) \\geq 3$)\n- Neighborhood composition (e.g., $\\texttt{fractionClass}(v, \\  \\texttt{hop}=1, \\\\ c') > 0.6$)\n\n>**q2/w2. It would be helpful to comment on how the results of Theorem 2 would change if an estimate of Rev-k-NN is used (as in practical implementations here) instead of the actual Rev-k-NN.**\n\nLet $\\widetilde{\\text{Rev}}{\\text{-}k\\text{-NN}}(v)$ denote the approximate reverse k-NN set of a node $v$, and $\\widetilde{\\Pi}(A)$ denote the approximate coverage function computed using these sets. The greedy algorithm in Theorem 2 provides a $(1 - 1/e)$-approximation **to the maximization of $\\widetilde{\\Pi}(A)$**, since the proof relies solely on submodularity and monotonicity of the input function—both of which are preserved under the approximation (as the union of approximate sets still yields a valid set function).\n\nTo relate this back to the *true* optimum $\\Pi(A^*)$, we leverage the uniform error bound from Lemma 1 (Appendix A.3), which ensures that for any set $A$:\n\n$$\n|\\widetilde{\\Pi}(A) - \\Pi(A)| \\leq \\theta \\quad \\text{with high probability (≥ $1 - \\delta$)}.\n$$\n\nLet $\\widetilde{A}$ be the set returned by greedy maximization over $\\widetilde{\\Pi}$, and $A^*$ be the optimal set under the true objective $\\Pi$. The greedy guarantee gives:\n\n$$\n\\widetilde{\\Pi}(\\widetilde{A}) \\geq \\left(1 - \\frac{1}{e} \\right)\\widetilde{\\Pi}(A^*).\n$$\n\nBy the uniform bound, we know $\\widetilde{\\Pi}(A\\^{\\*}) \\geq \\Pi(A\\^{\\*}) - \\theta$, so:\n\n$$\n\\widetilde{\\Pi}(\\widetilde{A}) \\geq \\left(1 - \\frac{1}{e} \\right)(\\Pi(A\\^{\\*}) - \\theta) \n= \\left(1 - \\frac{1}{e} \\right)\\Pi(A\\^{\\*}) - \\left(1 - \\frac{1}{e} \\right)\\theta.\n$$\n\n**Thus, even when using approximate Rev-k-NN sets, the greedy algorithm achieves the following guarantee on estimated coverage:**\n\n$$\n\\boxed{\n\\widetilde{\\Pi}(\\widetilde{A}) \\geq \\left(1 - \\frac{1}{e} \\right)\\Pi(A^*) - \\left(1 - \\frac{1}{e} \\right)\\theta\n}\n$$\n\nWe will include this clarification in the revised version. We also have a supporting experiment in the paper for the same. Please refer Appendix A.6 \"Sampling rate for exemplar selection\".\n\n> **q3. I wonder if a comparison with instance-level baselines such as GNNExplainer and PGExplainer on synthetic datasets such as BA Shapes can be provided as follows. Since the aforementioned explainers are instance-level, they need to be transformed into global explainers. Can they be combined with the LLM idea in this work, such that the explanation outputs of GNNExplainer and PGExplainer are input to the LLM to output the global rule? If so, how would the accuracy compare with the proposed explainer?**\n\nIn principle, instance-level explainers like GNNExplainer and PGExplainer could be used to generate local explanations for a collection of representative nodes, and their outputs could then be aggregated and passed to an LLM to produce a global explanation. However, there are fundamental challenges with this approach:\n\n1. **Local explanations do not guarantee semantic convergence:**  \n   Local explainers aim to explain the prediction on a specific instance (node/graph) by identifying the most relevant subgraph or features. There is no incentive or regularization encouraging consistency across local explanations for nodes in the same class. As a result, local explanations often differ substantially across instances—even within a single class—due to variations in neighborhood structure or optimization noise.\n\n   Consequently, when such varied and potentially inconsistent explanations are provided to an LLM, the output global rule may be incoherent, fragmented, or overfit to specific patterns that do not generalize.\n\n2. **Our method ensures explanation consistency by design:**  \n   In contrast, GNNXEMPLAR selects exemplars based on the GNN’s learned semantic space and associates each with a *population*—a reverse-kNN set of nodes whose representations are similar. This promotes semantic alignment across the class and ensures that the LLM receives a *coherent and representative subset* from which it can learn generalizable rules. Moreover, this design enables the LLM to learn global discriminative patterns rather than instance-specific artifacts.\n\n**Experiment:** To empirically support this argument, we conducted the experiment as suggested by the reviewer. We applied PGExplainer on the BA-Shapes dataset to generate local explanations for nodes from each class. These explanations were then passed to an LLM with the goal of producing global rules.\n\nDespite careful filtering of spurious explanations (e.g., restricting to explanations with <30 edges), the resulting fidelity was only 46%."}, {"review_id": "4ZN28d9Lcv", "reviewer": "Reviewer_PJzR", "summary": "This paper presented GNNXEMPLAR, a novel framework for global-concept-based GNN explanation of node classification in large graph. To achieve this, the author first accesses the GNN’s embedding space to identify exemplar nodes. Finally, to generate human-understandable explanations, they leverage LLMs to distill the defining characteristics of each exemplar and its neighborhood into concise natural language rules. As a result, this approach enables global yet instance-relevant explanations grounded in learned graph structure and semantics.", "questions": "Please refer to the above weakness section for suggestions.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n- The paper provides a fresh perspective on global-concept-based GNN explanation, with sufficient theoretical analysis. It is interesting to use LLM to extract rules. \n- The method shows significant improvements in fidelity, scalability, and human interpretability across diverse benchmarks.\n- The paper is well-written.\n\n**Weaknesses:**\n- GraphTrail can be compared on graph datasets with discrete node labels, and the same applies to MAGE. GNNs can transform discrete node labels into continuous embeddings. So, why can't GNNXEMPLAR be applied?", "was_revised": true, "final_justification": "I recommend a score of **5**. The concerns of other reviewers mainly lie in providing additional analyses, while the core claims of the paper are already supported by sufficient arguments. My main confusion is also solved: the authors have shown that GNNXEMPLAR can indeed run on small graphs like MUTAG (albeit with 68% fidelity versus GraphTrail’s 87%) and have clearly defined its intended domain—large, high-dimensional graphs without obvious motif structure. Overall, the method’s novelty and clear presentation are strong points, though there is an empirical limitation on small graphs.", "rebuttal": "We thank the reviewer for the constructive feedback. Please find below our response to the query made during the review. We remain open for any further discussion.\n\n---\n1. > **GraphTrail can be compared on graph datasets with discrete node labels, and the same applies to MAGE. GNNs can transform discrete node labels into continuous embeddings. So, why can't GNNXEMPLAR be applied?**\n\n Indeed, GNNXEMPLAR can be applied to datasets like MUTAG used in GraphTrail. However, small graphs with discrete node labels are not the primary focus of our work, as several strong explainers (e.g., GraphTrail, MAGE) already perform well in that setting. Our goal is to address a more challenging and underexplored problem: explaining predictions in complex graphs with rich, high-dimensional node and edge attributes. For a detailed discussion of the associated challenges, please refer to lines 50–74 in our manuscript.\n\nNonetheless, we conducted the requested experiment. We ran our method using the pre-trained GCN from GraphTrail (84% accuracy) and obtained a fidelity of 68%, compared to GraphTrail’s 87%. While GNNXEMPLAR correctly surfaced relevant substructures (e.g., NO2 groups), it fell short of capturing the precise motif-level patterns needed for high-fidelity explanation in this setting. For instance, here is an example output for the mutagenicity class:\n\n```\nClass: Mutagenic\nThe graph is classified mutagenic if it has at least 12 nodes, at least 12 carbon nodes, at least 1 nitrogen node, at least 2 oxygen nodes, at least 1 aromatic ring, and fewer than 2 halogen atoms (Cl, Br, F).\nThese features are common among the class, while the presence of multiple halogen atoms is more characteristic of non-mutagenic graphs.\"\n```\n\nThese explanations are chemically meaningful but less granular than those recovered by GraphTrail, which is tailored to detect frequent subgraph motifs.\n\nThis result highlights a broader point: `in small graphs where predictions hinge on discrete, recurring structural patterns, motif-centric methods like GraphTrail are more appropriate. In complex real-world networks characterized by high-dimensional, continuous features and lacking clear motif structures, such methods tend to fail.` GNNXEMPLAR is specifically designed for this latter setting, which remains underexplored. Thus, we believe this underperformance does not dilute the contribution of GNNXEMPLAR, but rather clarifies its intended use case."}]

Author rebuttal:

Meta-review: This paper presents GnnXemplar, a global explainer inspired by Exemplar Theory from cognitive science. GnnXemplar identifies representative nodes in the GNN embedding space, called exemplars, using reverse-kNN. Then, Exemplar Signatures are discovered through iterative self-refinement of LLM outputs, leveraging their strong reasoning abilities and established strengths in linguistic articulation. The pipeline of GnnXemplar is clearly described in Figure 1, and explanations are derived from the exemplars' neighborhoods.

Although local explanations for individual cases have been proposed, developing a global explainer to characterize an entire class has remained difficult. The validity of the proposed explainer has been demonstrated experimentally using eight datasets and three GNN architectures: GnnXemplar consistently showed the highest fidelity scores, while previous approaches often suffered from out-of-memory issues or subgraph isomorphism. In addition, a user study involving 60 participants showed a clear preference for textual explanations.

All the reviewers were positive about the paper’s technical novelty and theoretical depth, and they were satisfied with the experimental validations. As shown in Table 2 and Figure 3, the stability and superiority of GnnXemplar are clear (e.g., fidelity scores of 0.92 for both Citeseer and Questions). Although the reviewers were already positive before the authors’ rebuttals, the rebuttal comments further deepened their understanding of this paper.

This work demonstrates clear novelty by introducing a fundamentally new paradigm for global GNN interpretability: shifting from motif-based subgraph discovery to exemplar-based natural language rules. It exhibits strong technical contributions to the machine learning community, with theoretical guarantees (NP-hardness, submodularity, and approximation bounds), carefully designed algorithms (reverse k-NN exemplar selection with greedy optimization), and comprehensive experiments including ablation studies, robustness across GNN architectures, and a comprehensive human user study. Its broad significance to the NeurIPS community lies in bridging GNN interpretability and large language models. The approach not only advances methodological foundations but also provides practical insights for failure diagnosis and trustworthy AI, which are timely and critical issues in the community.

For these reasons, the paper will give great influence in explainable graph learning, attract wide interest across both theoretical and industrial aspects, and stimulate further exploration of exemplar and language-based interpretability paradigms. Therefore, I recommend that the paper should be accepted as an oral presentation.
Decision: Accept (oral)