acceptodds
Under review as a conference paper at ICLR 2027

StableGX: Stable Global Explanations for GNNs on Large Heterogeneous and Heterophilic Graphs

Abstract

Graph Neural Networks (GNNs) are increasingly deployed on large real-world graphs, where global explanations should remain consistent across the different graph samples required for scalable analysis. Existing global GNN explainers can produce different explanations from different samples of data for the same black-box GNN model and face additional challenges on heterogeneous and heterophilic graphs with large, irregular neighborhoods and rich node features. We introduce StableGX, a global explainer for node-classification GNNs that targets both fidelity and stability across explanation samples. StableGX maps each node and its multi-hop neighborhood to a fixed-dimensional, interpretable representation of node features and neighborhood statistics, and identifies representative exemplar populations in the GNN embedding space. It then learns logical signatures for these populations using boundary-aware sampling, which identifies candidate points near the population boundary and applies max–min selection to improve boundary coverage. We theoretically relate boundary approximation error to fidelity and stability, and establish a bound on the approximation error induced by the proposed sampling procedure. Experiments across homogeneous and heterogeneous, homophilic and heterophilic graphs show that StableGX produces faithful and stable global explanations. In particular, it improves over GNNXemplar on large heterogeneous and heterophilic graphs, while GNNXemplar remains stronger on simpler homogeneous graph benchmarks.

Primary area:
interpretability and explainable AI
Keywords:
graph neural networks, explainability, heterogenous graphs

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_eiFxOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studied global explanations for node-classification GNNs, focusing on fidelity and stability across sampled explanation graphs. StableGX followed an exemplar-based framework and summarized nodes through fixed-dimensional node and hop-wise neighborhood statistics, separated by node type for heterogeneous graphs. It identified locally mixed population-boundary candidates in this feature space and selected dispersed samples for learning decision-tree signatures. Boolean symbolic regression combined these signatures into class-level explanations. The evaluation covered twelve graph benchmarks, comparisons with GNNXemplar and GLGExplainer, and analyses of sampling strategy, sampling ratio, and tree depth.

Critical strengths

Boundary-aware sampling offers some innovation at the application level by combining local population-membership information with dispersed sample selection for global GNN explanation.

Critical weaknesses

W1) Limited methodological novelty and insufficient graph-specific justification: Among the three proposed modules, the fixed-dimensional representation was the only one whose construction directly uses graph structure. Equations (12)-(14) computed feature means or category-wise counts and neighborhood sizes, then concatenated these summaries with target-node features; the heterogeneous extension groups them by hop and node type. This is a straightforward statistical aggregation, without a new mechanism for modeling connectivity within groups or interactions between relations. The remaining sampling and rule-learning designs operated on feature vectors or Boolean outputs and can be transferred to other XAI domains. While boundary-aware sampling provided some application-level integration, the paper did not establish a substantive methodological advance or sufficiently justify its design for large, heterogeneous, and heterophilic graphs.

W2) Insufficient experimental support for the proposed components: The related work section discussed several global GNN explanation methods, but Table 1 compared fidelity with only GNNXemplar and GLGExplainer, and stability with only GNNXemplar. GLGExplainer yielded fidelity results on only two of the twelve datasets. This limited and asymmetric baseline coverage was not adequately justified and weakened the evidence for the claimed gains in both fidelity and stability. The main controlled ablation addressed boundary-aware sampling. There was no comparable removal or replacement study for the fixed-dimensional representation or the signature-extraction/class-level-explanation module. Appendix C varied the sampling ratio and tree depth, but these analyses mainly measured hyperparameter sensitivity rather than establish the necessity of the proposed components. Controlled removal or substitution with existing designs, under comparable sampling budgets and rule complexity, is needed to isolate the contributions of the other two modules. Without these controls, the reported gains do not establish which designs are effective or substantiate the claimed mechanisms.

Questions for authors

Q1) What specific technical limitations prevent existing global GNN explainers from efficiently extracting interpretable rules from diverse nodes and complex structures? Identify the affected methods and operations. For the sampling-stability challenge, which source of variation is central, and why must large, heterogeneous, and heterophilic settings be considered together?

Q2) How do the proposed designs overcome the limitations identified in Q1? Could the authors provide non-trivial analysis or targeted empirical evidence showing that the serialized statistics retain information needed for faithful rules, and that locally mixed, dispersed samples capture the boundary regions responsible for instability? How do the assumptions of the conditional theory apply to the actual representation, sampler, and learner?

Q3) The paper explicitly stated that the exemplar selection algorithm follows existing work, yet Appendix E separately presented this inherited algorithm. What additional insight does this section provide into StableGX's proposed designs? Is its inclusion necessary beyond the implementation details needed for reproducibility?

Q4) The boundary-aware sampling and signature-learning mechanisms appear applicable beyond graph data. Why is the evaluation restricted to graph tasks?

Q5) The paper emphasized large, heterogeneous, and heterophilic graphs, but it is unclear which design components carry an inductive bias for these properties. In particular, which mechanism specifically addresses heterophily? Could the authors clarify which components are tailored to each property, and why?

5 comments

Changes are marked in green in the draft or otherwise specifically mentioned here in the comments.

Q1. What specific technical limitations prevent existing global GNN explainers from efficiently extracting interpretable rules from diverse nodes and complex structures? Identify the affected methods and operations. For the sampling-stability challenge, which source of variation is central, and why must large, heterogeneous, and heterophilic settings be considered together?

Ans 1

  • We thank the reviewer for this question and clarify the two challenges below.
  • Technical limitations of existing explainers. Different methods face distinct challenges when applied to large heterogeneous graphs. GNNXemplar relies on LLM-based signature generation and refinement, where representing complex heterogeneous neighborhoods can exceed the available context window, as observed on Pokec. GLGExplainer relies on subgraph-based explanations, with its subgraph-isomorphism operations incurring substantial memory and runtime costs, resulting in failures on several datasets (Table 1). Furthermore, diverse node attributes and variable-sized neighborhoods make it challenging to extract compact, recurring patterns that characterize the GNN's behavior.
  • Source of sampling instability. We clarify that our focus is on variation in the sampled training points used for explanation learning. For a fixed exemplar and its population, different random samples of population members and non-members may represent the population boundary differently, resulting in inconsistent learned signatures.
  • To investigate this, we added an analysis in Appendix A.5, evaluating signature-level membership F1 separately on held-out boundary and interior points. Random sampling achieves lower boundary F1 than interior F1 on three of the four datasets, whereas boundary-aware sampling consistently improves boundary F1 across all four datasets. Although a gap between boundary and interior performance remains on some datasets, this is expected since boundary regions contain locally mixed membership labels, making them more challenging to characterize. These results highlight the importance of explicitly representing boundary regions. Improvements in stability across independent explanation runs are further evaluated in Section 6.3.
  • Why consider these graph characteristics together? Large graphs require sampling for scalable explanation extraction, heterogeneity introduces diverse node types, relations, and attributes, while heterophily makes simple neighborhood-label patterns less reliable. These challenges frequently coexist in real-world graphs, making it important to evaluate scalability, fidelity, and stability in their combined setting. Our experiments on IEEE-CIS, Pokec, PDNS, and RCDD specifically address this setting.
  • We also include heterophilic graphs because homophilic graphs can sometimes admit relatively simple explanations based on neighborhood similarity. For example, if 80% of a paper's neighbors belong to the "Neural Networks" category, the target paper is also likely to belong to that category. While such explanations can be meaningful, they may provide limited insight into more complex patterns learned by the GNN. Heterophilic graphs offer a more challenging setting where such straightforward neighborhood-label relationships are less reliable.

Q2. How do the proposed designs overcome the limitations identified in Q1? Could the authors provide non-trivial analysis or targeted empirical evidence showing that the serialized statistics retain information needed for faithful rules, and that locally mixed, dispersed samples capture the boundary regions responsible for instability? How do the assumptions of the conditional theory apply to the actual representation, sampler, and learner?

Ans 2

  • We thank the reviewer for this question. We have conducted additional experiments during the rebuttal to provide empirical support for the proposed design choices and expanded the discussion of our theoretical assumptions.
  • 1. Effectiveness of serialization. We added a new experiment (Table 9, Appendix B), inspired by Rubio-Madrigal and Burkholz (ICML 2026), to evaluate whether the serialized representations retain information relevant to GNN predictions. We train random forest classifiers on serialized features to reproduce the GNN's predictions using 5-fold cross-validation. The results show macro-F1 scores of 0.848, 0.832, and 0.917 on IEEE-CIS, RCDD, and PDNS, respectively, with lower performance on Pokec (0.580). These results provide empirical evidence that serialization retains substantial GNN-predictive information on three of the four evaluated heterogeneous datasets.
  • 2. Effectiveness of boundary-aware sampling. As discussed in our response to Q1, we added a new analysis comparing signature membership F1 on boundary and interior regions, providing empirical support for the motivation behind boundary-aware sampling. Additionally, we conducted a new ablation (Table 10, Appendix D.1) to isolate the contribution of max–min diversification. Keeping the boundary-candidate pool and sampling budget fixed, max–min selection improves performance by approximately 1–2% over random selection from the same candidates. Together with the global fidelity and stability improvements in Figure 1(b), these results support the effectiveness of our sampling procedure.
  • 3. Applicability of theoretical assumptions. We have expanded Appendix H.1 to clarify how assumptions A1–A4 relate to the proposed method. A1 concerns controlled interior error, while A2 characterizes how the signature learner responds to improved boundary information. The additional experiments discussed in Q1 provide empirical support for these behaviors, although they do not directly establish A2's geometric error-confinement condition. A3 is a regularity assumption on the probability mass near the population boundary in the serialized feature space. A4 concerns the proximity and coverage of boundary candidates: our k-NN procedure identifies locally mixed membership regions, while max–min selection controls the covering radius over the identified candidates (Proposition 2).
  • We emphasize that our theoretical guarantees are conditional on these assumptions. The new rebuttal experiments provide additional empirical support for the proposed components, while the theoretical analysis in Section 4 and Appendix H establishes their relationship to fidelity and stability under the stated conditions.

Q3. The paper explicitly stated that the exemplar selection algorithm follows existing work, yet Appendix E separately presented this inherited algorithm. What additional insight does this section provide into StableGX's proposed designs? Is its inclusion necessary beyond the implementation details needed for reproducibility?

Ans 3 It is just included for complete implementation detail and to enable reproducibility.


Q4. The boundary-aware sampling and signature-learning mechanisms appear applicable beyond graph data. Why is the evaluation restricted to graph tasks?

Ans 4 We agree with the reviewer that boundary-aware sampling and signature learning are not inherently limited to graph data. While this paper focuses on global GNN explainability, we recognize the broader applicability of our approach and are actively exploring its extension to other domains.

Q5. The paper emphasized large, heterogeneous, and heterophilic graphs, but it is unclear which design components carry an inductive bias for these properties. In particular, which mechanism specifically addresses heterophily? Could the authors clarify which components are tailored to each property, and why?

Ans 5

  • We thank the reviewer for this question. Different components of StableGX address different challenges:
  • Large graphs: Fixed-dimensional neighborhood serialization and sampling enable scalable explanation extraction without processing large subgraphs directly or relying on LLM-based rule generation.
  • Heterogeneity: We aggregate neighborhood statistics separately for each node type and hop (Section 5.1, Appendix F), preserving interpretable information about different types of neighboring entities.
  • Heterophily: Our method does not assume that neighboring nodes belong to the same class. Instead, it retains self-features and hop-wise neighborhood statistics separately and identifies exemplar populations using the trained GNN's embeddings. The resulting signatures are learned to approximate the GNN's behavior rather than relying on neighborhood-label agreement.

Additionally, boundary-aware sampling (Section 5.2) improves the representation of exemplar-population boundaries, which is useful when different patterns must be captured reliably across explanation samples. This mechanism is not restricted to heterophilic graphs but addresses the sampling-stability challenge across graph settings.

Thus, while StableGX does not explicitly introduce a heterophily-specific inductive bias, its design allows explanations to capture patterns beyond simple neighborhood homophily. We will clarify the roles of these components in the methodology section.

Reviewer_SVbJOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes StableGX, a global GNN explainer designed to produce stable explanations across different graph samples. It combines interpretable neighborhood statistics, exemplar identification, boundary-aware sampling, and logical rule extraction. Experiments on twelve datasets demonstrate improved fidelity and stability, particularly on large heterogeneous and heterophilic graphs.

Critical strengths

S1. The paper addresses the practical challenge of generating stable global explanations for large and complex graphs. S2. The proposed boundary-aware sampling strategy provides an intuitive approach to improving explanation consistency. S3. The experiments cover diverse graph settings and demonstrate promising improvements over existing global explainers on large heterogeneous graphs.

Critical weaknesses

W1. The evaluation lacks class-wise fidelity analysis on highly imbalanced datasets such as RCDD (11:1), making it difficult to distinguish meaningful explanations from majority-class agreement. W2. The heterogeneous neighborhood representation aggregates features by node type but does not explicitly preserve edge types, potentially losing information used by relation-aware GNNs. W3. The ablation experiments compare boundary-aware sampling with random sampling but do not isolate the contributions of boundary candidate identification and max–min selection. W4. Although scalability is a central motivation, the experiments do not provide sufficient runtime and memory comparisons on the largest datasets.

Questions for authors

Q1. Could the authors report class-wise fidelity and compare against a majority-class rule baseline, particularly for IEEE-CIS and RCDD? Q2. Would incorporating edge-type-specific neighborhood statistics improve explanation fidelity on heterogeneous graphs? Q3. Could the authors separately evaluate boundary candidate selection without max–min diversification to clarify which component contributes most to the improvements? Q4. Could the authors report end-to-end explanation extraction time and peak memory consumption on the large heterogeneous datasets?

3 comments

Changes are marked in Red in the draft or otherwise specifically mentioned here in the comments.

W1/Q1. Could the authors report class-wise fidelity and compare against a majority-class rule baseline, particularly for IEEE-CIS and RCDD?

Ans 1 We have added macro F1, class-wise F1 and majority class rule's F1 for all the heterogeneous and heterophilic datasets in Appendix A.4 (Table 5). The trend remains similar as we observed in accuracy.


W2/Q2. Would incorporating edge-type-specific neighborhood statistics improve explanation fidelity on heterogeneous graphs?

Ans 2

  • We thank the reviewer for this important observation. We agree that incorporating edge-type-specific neighborhood statistics could preserve additional relational information and potentially improve explanation fidelity.
  • However, in three of our four heterogeneous datasets (IEEE-CIS, Pokec, and RCDD), each directed node-type pair has a unique edge type. Consequently, node-type-specific aggregation already captures these relation distinctions at the first hop. PDNS is an exception, where multiple edge types connect the same node-type pair. We therefore evaluated edge-type-specific aggregation on PDNS but observed no significant improvement in explanation fidelity.
  • Nevertheless, we agree that this is a valuable extension, particularly for graphs with richer relational structures. We have incorporated edge-type-specific aggregation as an optional component of our serialization procedure, it allows the representation to distinguish relations when multiple edge types connect the same node types. Please see Section 5.2 and Appendix G.

W3/Q3. Could the authors separately evaluate boundary candidate selection without max–min diversification to clarify which component contributes most to the improvements?

Ans 3

  • We thank the reviewer for this suggestion. We have added a new ablation in Appendix D.1 (Table 10) to isolate the contribution of the max–min diversification step.
  • Specifically, we first identify the same set of boundary candidates and then compare two selection strategies: (i) random selection from the boundary candidates and (ii) greedy max–min selection, using the same sampling budget. This differs from the experiment in Section 6.3, where boundary-aware sampling is compared against random sampling from the entire dataset.
  • The results show a modest improvement of approximately 1–2 percentage with max–min selection. This suggests that identifying boundary candidates is an important component of our sampling strategy, while max–min diversification provides an additional benefit by selecting candidates with better coverage of the boundary regions.

W4/Q4. Could the authors report end-to-end explanation extraction time and peak memory consumption on the large heterogeneous datasets.

Ans 4

  • We thank the reviewer for this suggestion. We have added a computational cost analysis in Appendix A.6, reporting peak RAM consumption and runtime breakdowns across all four large heterogeneous datasets.
  • We report both end-to-end memory usage, including GNN inference (5.6–23.2 GiB), and explanation-only memory usage (2.7–5.3 GiB). The explanation extraction time ranges from 90.0 seconds on PDNS to 906.6 seconds on Pokec, with a breakdown of the major computational stages in Table 7. These results provide a clearer picture of the computational requirements and scalability of StableGX.

Dear reviewer SVbj

Since we are at the last few hours of the rebuttal, we wanted to check if all your concerns are addressed by our response and see if you have any followups questions. Answering your questions has significantly improved the quality of the manuscript and we are ready to address any additional clarification/questions.

Thank you The Authors

Dear reviewer SVbj

As the last few minutes of the review remain, we wanted to kindly check if all your concerns were addressed by our response. If you have no further questions or clarifications, we would be very grateful if you could consider updating your score to reflect your current assessment of the revised manuscript.

Thank you again for your valuable feedback and consideration.

The Authors

Reviewer_uBLbOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This paper proposes StableGX, a global explanation method for graph neural networks (GNNs), aiming to generate stable and interpretable class-level explanations for large and complex graphs. The method first converts nodes and their multi-hop neighborhoods into feature and node-type statistics. It then identifies representative exemplar populations and learns interpretable rules through boundary-aware sampling and depth-constrained decision trees. Finally, these rules are combined to generate class-level explanations. Theoretically, the authors analyze the relationship between boundary approximation error, explanation fidelity, and stability, and provide corresponding theoretical guarantees. Experiments are conducted on 12 node classification datasets, covering homogeneous and heterogeneous graphs as well as homophilic and heterophilic graphs. The method is compared with approaches such as GNNXemplar and GLGExplainer. The results show that StableGX achieves good fidelity and stability on several datasets.

Critical strengths
  1. The paper focuses on global GNN explanations for large-scale heterogeneous and heterophilic graphs. It addresses the limitations of existing methods in scalability and explanation stability, making the research practically valuable.
  2. The paper proposes StableGX, a global explanation method that combines multi-hop neighborhood statistics, representative exemplar identification, and boundary-aware sampling with decision trees and symbolic regression to generate interpretable global logical rules.
  3. The paper establishes a theoretical relationship between boundary approximation error, explanation fidelity, and stability. It also analyzes how max–min selection helps control boundary approximation error, providing theoretical support for the proposed method.
  4. The paper conducts extensive experiments on 12 node classification datasets, covering homogeneous and heterogeneous graphs as well as homophilic and heterophilic graphs. This broad evaluation allows the method to be assessed under different graph structures.
Critical weaknesses
  1. The paper lacks an overall method framework diagram, making the multi-stage algorithmic pipeline less intuitive and hindering readers from quickly understanding the relationships and connections between different components.
  2. The theoretical guarantees on fidelity and stability rely on assumptions A1-A4. In particular, A4 requires the selected boundary samples to be close to the true boundary and to cover different regions of it, but the authors have not demonstrated that the proposed sampling method can satisfy this requirement. In addition, the assumptions A1-A3 lack sufficient empirical validation. The paper also does not systematically discuss whether the theoretical guarantees remain valid or how the method's performance may degrade when these assumptions are violated.
  3. The theoretical analysis primarily focuses on individual exemplar membership decision rules, whereas the final class-level explanations require multiple rules to be combined through symbolic regression. The authors have not proved that the fidelity and stability guarantees for individual rules carry over to the final class-level explanations, leaving the theoretical analysis insufficiently comprehensive for the complete method.
  4. The paper constructs fixed-dimensional representations using node features and multi-hop neighborhood statistics. Although this design helps improve scalability, it may lose neighborhood connectivity patterns, complex node interactions, and differences in feature distributions. The authors have not sufficiently evaluated the actual impact of this potential information loss on explanation fidelity.
  5. On homogeneous and homophilic graph datasets such as TAGCora, Citeseer, and ogbn-arxiv, StableGX achieves noticeably lower fidelity than GNNXemplar. However, the paper provides only a brief explanation for this gap and lacks a more detailed analysis of the underlying causes. The applicability and limitations of StableGX across different types of graph datasets therefore remain insufficiently clarified.
  6. The paper identifies explanation stability as a key contribution, but the stability evaluation is primarily based on five independent explanation runs. A systematic analysis of the reliability of the stability estimates and stability under different experimental conditions is lacking. Therefore, the experimental evaluation does not sufficiently validate the stability of the proposed method.
  7. The ablation studies in the paper remain insufficient. Although the authors compare boundary-aware sampling with random sampling and investigate the effects of the sampling ratio and decision-tree depth, they lack systematic ablation studies of core components such as the multi-hop neighborhood serialization representation. Therefore, the specific contributions of these design choices to overall performance have not been sufficiently validated.
Questions for authors

See Critical Weaknesses.

7 comments

Relevant changes in blue or specified below

C1 The paper lacks an overall method framework diagram, making the multi-stage algorithmic pipeline less intuitive and hindering readers from quickly understanding the relationships and connections between different components.

Ans 1 We thank the reviewer for the feedback, we have added an overall method diagram at start of Appendix, which will help readers to quickly understand the paper's method outline.


C2 The theoretical guarantees on fidelity and stability rely on assumptions A1-A4. In particular, A4 requires the selected boundary samples to be close to the true boundary and to cover different regions of it, but the authors have not demonstrated that the proposed sampling method can satisfy this requirement. In addition, the assumptions A1-A3 lack sufficient empirical validation. The paper also does not systematically discuss whether the theoretical guarantees remain valid or how the method's performance may degrade when these assumptions are violated.

Ans 2 Justification of A1-A3 and details about A4.

  • A1 requires the signature learner to maintain bounded classification error away from the true population boundary. To empirically examine this assumption, we identify approximate interior-region nodes using the k-NN membership criterion and evaluate decision-tree performance on these nodes. We have added Table 6 in the appendix, reporting F1 scores separately for interior and boundary regions across all four heterogeneous datasets. The numbers clearly show the learners ability to characterize interior regions while also showing that boundary aware sampling does not sacrifice interior points.

  • A2 (Local boundary recovery). We also use the boundary-region results in Table 6 to examine A2. The F1 scores improve consistently with boundary-aware sampling across all four datasets, indicating that the decision trees benefit from better representation of boundary regions. While this does not directly verify the geometric error confinement in A2, it supports the underlying idea that improved boundary information helps the learner make more accurate predictions near the boundary. We acknowledge that this behavior depends on the learner's capacity to approximate the boundary and have clarified this limitation in the appendix after A2.

  • A3 holds under common regularity conditions, such as bounded density around a sufficiently smooth boundary, where the boundary mass is O(r)O(r) . Thus, the assumption primarily excludes irregular settings where substantial probability mass remains concentrated arbitrarily close to the boundary. We have clarified this in Appendix below A3.

  • A4 (Boundary-candidate accuracy). We would like to clarify that A4 has two components: boundary proximity and boundary coverage. The first is directly supported by our k-NN procedure. Since every identified candidate has at least one opposite-class neighbor, its distance from the true boundary is bounded by its k-NN radius (under Euclidean distance). For the second, we use a larger randomly sampled pool for boundary identification than the final signature-training budget, increasing the likelihood of representing different boundary regions. We then apply greedy max–min selection to retain a diverse subset, with a covering radius at most twice the optimal value over the identified candidates (Proposition 2). While this does not guarantee complete coverage of the true boundary, it explains how our procedure supports the conditions in A4. We have added the mathematical details and clarified the scope of this assumption in App H.1.


C3 The theoretical analysis primarily focuses on individual exemplar membership decision rules, whereas the final class-level explanations require multiple rules to be combined through symbolic regression. The authors have not proved that the fidelity and stability guarantees for individual rules carry over to the final class-level explanations, leaving the theoretical analysis insufficiently comprehensive for the complete method.

Ans 3

  • We agree that the theoretical guarantees are established at the exemplar-signature level and do not directly extend to the final class-level explanations. Our analysis focuses on boundary-aware sampling, which is the main contribution of this work. Improving the fidelity and stability of individual signatures provides more reliable inputs to symbolic regression, although the final performance also depends on how these signatures are combined.
  • To evaluate this, we measure the fidelity and stability of the complete pipeline after symbolic regression. Table 1 reports the global results across all datasets, while Figure 1(b) specifically shows that boundary-aware sampling improves both global fidelity and stability compared to random sampling. We will clarify the scope of our theoretical guarantees and this distinction in the revised manuscript at the end of section 5.3.

C4 The paper constructs fixed-dimensional representations using node features and multi-hop neighborhood statistics. Although this design helps improve scalability, it may lose neighborhood connectivity patterns, complex node interactions, and differences in feature distributions. The authors have not sufficiently evaluated the actual impact of this potential information loss on explanation fidelity.

Ans 4

  • We agree that aggregating neighborhood information can lead to information loss, particularly for complex structural patterns and feature interactions. However, as also observed by Rubio-Madrigal and Burkholz (ICML 2026), fixed multi-hop neighborhood aggregations can retain sufficient information for effective prediction on several evaluated graph datasets, especially if the hops are not too deep (under 3-4 hops).
  • To examine this in our setting, we added an experiment (Table 9) where we train a random forest on serialized representations to reproduce the GNN's predictions. We evaluate both the complete representation and selected top-k features, reporting accuracy and macro-F1 over ten seeds.
  • The results show strong agreement with GNN predictions on three of our four heterogeneous datasets, achieving macro-F1 scores of 0.848 on IEEE-CIS, 0.832 on RCDD, and 0.917 on PDNS. Performance is lower on Pokec (0.580), indicating that serialization may lose information relevant to the GNN's predictions in some settings, which aligns with lower overall numbers on Pokec dataset in our main table (Table 1).
  • These results do not establish that serialization is information-preserving in general. Rather, they show that for three of the four evaluated heterogeneous datasets, the serialized features retain substantial information needed to reproduce the GNN's predictions, supporting their use as an interpretable representation in our explanation framework.

C5 On homogeneous and homophilic graph datasets such as TAGCora, Citeseer, and ogbn-arxiv, StableGX achieves noticeably lower fidelity than GNNXemplar. However, the paper provides only a brief explanation for this gap and lacks a more detailed analysis of the underlying causes. The applicability and limitations of StableGX across different types of graph datasets therefore remain insufficiently clarified.

Ans 5

  • We acknowledge that GNNXemplar achieves higher fidelity on several homogeneous and homophilic datasets. One possible explanation is its LLM-based signature extraction, which can generate relatively complex logical rules and iteratively refine them using validation feedback. This can be particularly effective when node attributes carry meaningful semantic information, as in TAGCora and ogbn-arxiv. In contrast, StableGX uses depth-constrained decision trees, prioritizing compact and interpretable rules at the cost of expressiveness.
  • However, this advantage becomes harder to exploit on large heterogeneous graphs. GNNXemplar relies on passing neighborhood summaries to an LLM, where high-dimensional numerical attributes and diverse node types can make rule generation more challenging. The input size can also become a practical limitation, as observed in the out-of-context failure on Pokec. StableGX instead learns rules directly from numerical neighborhood statistics, avoiding LLM-based extraction.
  • Thus, we do not claim that StableGX is preferable across all graph settings. Our results suggest that GNNXemplar remains particularly effective on the evaluated homogeneous benchmarks, whereas StableGX offers advantages on larger heterogeneous and heterophilic graphs. We have expanded Section 6.2 to clarify this trade-off and the limitations of our approach.

Reference:

Rubio-Madrigal, Celia and Rebekka Burkholz. "Fixed Aggregation Features Can Rival GNNs." In Proceedings of the 43rd International Conference on Machine Learning (ICML), 2026.

C6 The paper identifies explanation stability as a key contribution, but the stability evaluation is primarily based on five independent explanation runs. A systematic analysis of the reliability of the stability estimates and stability under different experimental conditions is lacking. Therefore, the experimental evaluation does not sufficiently validate the stability of the proposed method.

Ans 6

  • We would like to clarify that our work specifically studies stability under sampling, as defined in Section 3 and discussed in the Introduction. Our objective is to evaluate whether explanations learned from different samples of the same graph remain consistent in their predictions.
  • To isolate this effect at the signature level, we keep the exemplar and its associated population fixed across runs. We then independently sample different subsets of members from the exemplar population and non-members from outside it to train the decision trees. Thus, each run learns a signature for the same underlying exemplar population, with only the training samples changing. We measure stability by evaluating the agreement between these independently learned signatures on a common held-out set.
  • For global stability, we report the average pairwise agreement across five independent explanation runs. Additionally, Table 11 examines how global stability changes under different boundary-sampling ratios. These experiments directly evaluate the sampling-induced variability that our method aims to address. Robustness to other perturbations falls outside the scope of this work.

C7 The ablation studies in the paper remain insufficient. Although the authors compare boundary-aware sampling with random sampling and investigate the effects of the sampling ratio and decision-tree depth, they lack systematic ablation studies of core components such as the multi-hop neighborhood serialization representation. Therefore, the specific contributions of these design choices to overall performance have not been sufficiently validated.

Ans 7

  • We have added two additional experiments to better evaluate the contributions of the individual components.
  • 1. Neighborhood serialization. As discussed in our response to the concern regarding information loss during serialization, we added an experiment inspired by Rubio-Madrigal and Burkholz (ICML 2026). We train random forest classifiers on the serialized representations to reproduce the GNN's predictions, using 5-fold cross-validation. The results (Table 9, Appendix B) show strong agreement on three of the four heterogeneous datasets, with macro-F1 scores of 0.848 on IEEE-CIS, 0.832 on RCDD, and 0.917 on PDNS. Performance is lower on Pokec (0.580). This provides empirical support for the suitability of our serialized representations on the evaluated datasets, while also highlighting their limitations.
  • 2. Greedy max–min selection. We have also added a more focused ablation to isolate the contribution of max–min selection (in Appendix D.1). Unlike the existing comparison between boundary-aware sampling and random sampling from the entire dataset, this experiment first identifies the same boundary-candidate pool and then compares greedy max–min selection against random selection from these candidates under an identical sampling budget. This allows us to evaluate the benefit of the coverage-based selection step independently of boundary-candidate identification.
  • Together with the existing sampling-ratio and decision-tree-depth ablations, these experiments provide further insight into the contributions of the key design choices in StableGX.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Updates

Dear Reviewers and Area Chair,

We thank the reviewers for their thoughtful and constructive feedback. The reviews have been very helpful in identifying areas where our paper could benefit from additional empirical evidence and clearer explanations. To address these concerns, we have conducted several new experiments and made updates to the manuscript.

We summarize the major updates below.

  1. Validation of neighborhood serialization: We have added a new experiment to evaluate how effectively the serialized representations retain information relevant to GNN predictions.
  2. Additional sampling ablation: Added analysis comparing boundary and internal performance, along with a separate experiment to isolate the contribution of max-min selection from boundary aware sampling.
  3. Detailed metrics: We have added F1 fidelity scores (instead of just accuracy), class wise f1 scores and a majority class baseline for clear comparison.
  4. Computational cost analysis: We have added detailed runtime and peak memory measurements for StableGX including a breakdown of the explanation extraction pipeline.
  5. Clarifications of assumption: We have added discussion for assumptions A1-A4, along with supporting evidences which are visible in experiments throughout the manuscript.
  6. Methodology figure: We have added methodology figure in Appendix for ease of understanding of reader.

We have provided detailed responses to each reviewer's comments and referred to the corresponding additions in the revised manuscript. Thank you again for all of your feedback and looking forward to getting feedback on the updated manuscript.

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.