- 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
Q2 - Q4
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
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.
Q1
Changes are marked in green in the draft or otherwise specifically mentioned here in the comments.
Ans 1