TopInG: Topologically Interpretable Graph Learning via Persistent Rationale Filtration

Thanks for the explanation and experiments.

For the Weakness 2, would you like to present the final $r_1$ and $r_2$? In the global response, "The key insight is that our prior regularization acts as a clustering mechanism of edges into two clusters on [0,1]", this sentence is suitable for all explainers. For my understanding, GSAT also uses a Marginal Distribution as the prior. It would be helpful to find out the difference between yours and GSAT.

We appreciate the reviewer's feedback.

Weakness 1 and Question 1:

[Answer:] We have clarified our notation and visualizations:

• $\mathcal{R}$ in Equation 3 represents the cross-entropy loss between predicted label $\bar{y}_G$ and ground truth label $y_G$
• The topological loss $L_{topo}=d_{topo}$ is implemented through our topological discrepancy measure
• In Figure 1, the horizontal lines form a persistent barcode -- a complete discrete representation of persistent homology. Each line represents a basic cycle's lifecycle (birth---death) in the graph filtration

For more detailed explanations of notation and TDA concepts, please refer to pdf link.

Weakness 2

• Regarding the setting of the hyperparameter $\mu$, please refer to our answer to the second common concern in the general response.
• Regarding the learnable parameter $r$: We minimize the KL-divergence between the learned edge distribution and the prior distribution, or equivalent maximize the log-likelihood. Since $\mu_1$ and $\mu_2$ are fixed, the log-likelihood is enlarged when the edge distribution are more concentrated around those two means $\mu_1$ and $\mu_2$, which also increases the divergence between $\mathcal{N}(\mu_1, r_1)$ and $\mathcal{N}(\mu_2, r_2)$. The only degenerate case we need to prevent is the mode collapse where all points cluster around a single center. We add a simple penalty term to penalize very small variance. While more sophisticated approaches exist, this straightforward solution works effectively for our model.

Thank you for the follow-up comments.

Regarding $r_1$ and $r_2$

• [Answer:] We checked our model train on the dataset BA-HouseOrGrid-2Rnd as an example, the learned $(r_1, r_2)=(0.2144,0.2167)$. We also uploaded two plots of some example distributions of edge filtrations.
  • Fig1 is one example distribution of the edge filtration values.
  • Fig2 is an average 10 distributions of edge filtration values on 10 sample graphs.

Regarding the question about prior regularization and comparison with GSAT:

• [Answer:] We appreciate the insightful observation about clustering mechanisms in explainable GNN models. While there are surface similarities between our prior regularization and GSAT's approach, there are fundamental differences in both design and functionality:

  • Role of Prior Regularization: In GSAT, the information bottleneck loss (info-loss) serves as the primary mechanism for identifying rationale subgraphs. We consider that the "workload" of this info-loss extends significantly beyond a simple clustering mechanism. As such, its parameter $r$ requires careful consideration during training (including techniques like warm-up or gradual decay). In contrast, our topological discrepancy loss is the primary driver for interpretation, with the prior regularization playing a supportive clustering role.
  • Architectural Differences: Our bimodal Gaussian prior naturally encourages separation between rationale and non-rationale edges without requiring precise parameter tuning. The two modes at $μ_1 = 0.25$ and $μ_2 = 0.75$ provide clear separation points, while the learnable variances $(r1, r2)$ allow flexibility in the clustering boundary.
  • Stability and Robustness: Because our model's interpretability primarily stems from the topological discrepancy loss, it is less sensitive to the exact values of the prior regularization parameters, which makes the training process stable and robust across different datasets, without careful hyperparameter tuning.

• While investigating the broader implications of bimodal or even multi-modal versus unimodal priors in interpretable GNNs would be fascinating, it extends beyond the scope of this work. We consider one of our main contributions is introducing topological methods to this domain, and we believe this will benefit interpretable GNN problems in general.

We appreciate the reviewer's constructive feedback.

Weakness 1, Question 2,3,4:

• Regarding the preliminary introduction to TDA, mathematic definitions,notations in equation (3) and clarification of loss functions and the architecture of our model, please refer to our answer to the first common question in the general response for a complete revision. Here we give some short answers for spedific clarification:

• [Answer to Q2:] $\mathcal{R}$ in the origical Eq. 3 represents the standard cross-entropy loss between the predicted label $\bar{y}_G$ and the ground truth label $y_G$. We have revised the equation as Eq. 2 in Section 3 in pdf link.

• [Answer to Q3:] Strictly speaking, while $f_\phi$ and $h_\phi$ aren't identical, they share a substantial common component in the backbone $GNN_\phi$. Specifically:

  • $GNN_\phi(G)$ processes the input graph to produce permutation-equivalent representations (node/edge embeddings)
  • $f_\phi = MLP_f \circ h_\phi$ reduces $GNN_\phi(G)$'s output to a 1-dimensional permutational equivalent representation via a multi-layer perceptron $MLP_f$
  • $h_\phi = MLP_h \circ Pool \circ GNN_\phi$ applies pooling to $GNN_\phi(G)$ for graph-level representation, followed by prediction MLP

  Here we omit the details of parameters in $MLP$ models for simplicity. For a complete discussion, please see Section 3 in pdf link.

• [Answer to Q4:]
  $T_X$ and $T_\epsilon$ are persistent homology representations on filtrations of $G_X$ and $G_\epsilon$ respectively. These permutation-invariant graph representations are concatenated with the pooled graph representation output by $Pool \circ GNN_\phi$. Then they are altogether fed into the final classifier $MLP_h$. Please refer to the last paragraph in Section 3 in pdf link for a more detailed explanation of the loss function and architecture of our model.

Weakness 2: Regarding datasets.

• We have added some example results of MUTAG dataset in pdf link. We have also added more illustrative example results on different datasets in pdf link.
• We acknowledge the limited availability of benchmark datasets for interpretable GNNs in general, as they require both graph and rationale subgraph labels. Our evaluation uses most of the standard benchmark datasets employed by baseline methods, most of which are synthetic or semi-synthetic. Creating comprehensive benchmark datasets would be valuable future work for advancing this field.

Question 1 Regarding $\beta_1$ in Fig. 1:

• [Answer:] $\beta_1$ here indicates the dimension of each 1-st homology vector space $H_1(G_{\leq t})$, presented in the boxes under each subgraph. Essentially, $\beta_1$ counts the number of basic cycles in the graph. In the revised version of the Fig. 1 in pdf link, we have replaced it with $H_1$ for clarity. We have explained them in the revised caption.

Question 5: Regarding unused notations.

• [Answer:] Yes, we have removed them in the version.

Question 6 Regarding node/edge features

• [Answer:] Yes, TopInG is able to takes node/edge features into account. In the real datasets Mutag and Benzene, each atom (node) and bond (edge) of the chemical molecules has distinct features derived from AtomEncoder and BondEncoder (provided by OGB). TopInG utilizes these actual features to obtain importance scores for each atom and molecule through rationale filtration learning. For the Mutag dataset, the functional groups -NO2 and -NH2 can be differentiated using TopInG as indicators, in contrast to -CH2 or -CO2, which share a similar topological structure with the ground-truth mutagens. In the case of Benzene, the carbon atoms in the benzene rings can also be identified using TopInG, distinguishing them from a random ring of six atoms.

We appreciate your thorough review and hope we have adequately addressed all your concerns. If you have any additional questions or would like further clarification on any point, we welcome continued discussion.

We appreciate the reviewer's constructive feedback.

Weakness1 Regarding the preliminary introduction to TDA: Please refer the first answer to the first common concern in the general response.

Weakness2 Regarding time complexity analysis and runtime study.

• [Answer:] The theoretical time complexity of the computation of persistent homology on graphs is known to be relatively efficient - $O(n\log n)$ where $n$ is the total number of nodes and edges in the graph [1,2]. However, we acknowledge that our current implementation is slower than the fastest baseline methods (5X to 20X slower). This performance gap stems primarily from the lack of optimized GPU implementations for persistent homology computation, which we view as an important open challenge for both the TDA and ML communities.
• Importantly, we also want to note that since ground truth rationale subgraphs are never used during training or validation, the interpretation performance cannot be artificially improved simply through larger parameter spaces or longer inference times.

Weakness 3: Regarding edge filtration learning and large graphs in practice.

• [Answer:] First, it is worth noting that all interpretable baseline methods also learn and store 1-dimensional edge embeddings as filtration functions.
• For larger graphs, we acknowledge the computational challenges of TDA-based methods, as mentioned above. We see two promising directions for improvement: (1) Development of efficient GPU implementations. (2) Using carefully designed GNN models to approximate persistent homology computations [3]

Q1: Figure 1 Clarification.

• [Answer:] We have revised both the TDA preliminary introduction and Figure 1 (see our response to common concerns). Regarding the discrepancy between descending t values in Figure 1 and ascending t values in line 170: In our model, $t=1-f$ since we add edges from higher to lower importance, where importance is measured by filtration value $f(e)$. Thus, while filtration values $f(e)$ decrease in our graph filtration, t increases. We've updated Figure 1 to use $f(e)$ instead of t to avoid confusion.

Q2 and Q3: Regarding the definition of topological invariant and our loss function in Equation (3).

• [Answer:] The topological invariant refers to our persistent homology representations. We have provided clearer definitions of both topological invariant and topological discrepancy (equation (1)), with accompanying explanations. Please see Section 3 in pdf link) for complete details.

Q4: Regarding the confusion of the shared parameters between $f_\phi$ and $h_\phi$.

• [Answer:] While $f_\phi$ and $h_\phi$ aren't identical, they share a substantial common component in the backbone $GNN_\phi$. Specifically:

  • $GNN_\phi(G)$ processes the input graph to produce permutation-equivalent representations (node/edge embeddings)
  • $f_\phi = MLP_f \circ h_\phi$ reduces $GNN_\phi(G)$'s output to a 1-dimensional permutational equivalent representation via a multi-layer perceptron $MLP_f$
  • $h_\phi = MLP_h \circ Pool \circ GNN_\phi$ applies pooling to $GNN_\phi(G)$ for graph-level representation, followed by prediction MLP

  Here we omit the details of parameters in $MLP$ models for simplicity. For a complete discussion, please see Section 3 in pdf link).

Reference

[1] Edelsbrunner, H., Letscher, D., & Zomorodian, A. (2000). Topological Persistence and Simplification. Discrete & Computational Geometry, 28, 511-533.

[2] Tamal Krishna Dey and Yusu Wang. Computational Topology for Data Analysis. Cambridge University Press, 2022.

[3] Zuoyu Yan, Tengfei Ma, Liangcai Gao, Zhi Tang, Yusu Wang, and Chao Chen. Neural approximation of graph topological features. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 9781713871088.

Dear Reviewer gpKc,

As we approach the end of the discussion period, we would greatly appreciate your assessment of whether our detailed responses have fully addressed your concerns. If you feel your concerns have been satisfactorily resolved, we respectfully request that you consider updating your rating to reflect this. We remain available to address any remaining questions or provide additional clarification if needed.

Thanks again for your review and consideration.

Best regards,

The Authors

We appreciate your thorough review and hope we have adequately addressed all your concerns. If you have any additional questions or would like further clarification on any point, we welcome continued discussion.

Weakness 2: regarding the challenge of varriform rational subgraphs, why our method works while other methods cannot.

[Answer: ] Thank you for this insightful question. We will address how TopInG handles variiform rationale subgraphs from three perspectives: theoretical guarantees, intuitive understanding, and empirical validation.

Theoretical Perspective

• Previous methods implicitly or explicitly assume low variance in rationale subgraphs within each category. For instance, GSAT's theoretical guarantee (Theorem 4.1, (Miao et al., 2022)) assumes that the label $y_G$ is determined by an invertible function $y_G = f(G_X^*) + noise$, implying that $f^{-1}(y_G)$ must be nearly a delta-distribution with small noise. GMT (Chen et al., 2024) inherits this limitation from GSAT. DIR (Wu et al., 2022) is designed to be robust against background noise. It also assumes invariant causal structures (Theorem 2 and Corollary 1 in Appendix C). In contrast, TopInG's theoretical guarantees make no such restrictive assumptions, allowing it to handle variiform rationale subgraphs in theory.

Intuitive Understanding

• The key distinction lies in how rationale subgraphs are identified. Existing methods (GSAT, GMT, DIR) rely on global threshold parameters (e.g., r=0.7 for GSAT/GMT, r=0.4 for GMT) to control rationale subgraph size or information content. This approach works well when rationale subgraphs have low variance but struggles with high variability. In contrast, TopInG identifies rationale subgraphs through statistical and topological differences between the rationale and complement (noise) subgraphs across the entire dataset. This self-adjusting approach naturally accommodates variable rationale structures without requiring them to conform to specific size or complexity constraints. Also, as discussed in our previous answer to the concern regarding the hyperparameter choices of our prior regularization, the choice of $\mu$ in our prior regularization is very robust and enjoys great flexibility. Our model's optimality does not depend on a specific threshold value, which is very different from previous approaches.

Empirical Validation

• Our experiments on the BA-HouseOrGrid-nRnd dataset (Figure 3 in our original paper) demonstrate this difference empirically. As the number of possible rationale subgraphs increases, the performance of existing methods degrades significantly, while TopInG maintains robust performance. This validates our theoretical conjecture that methods depending on global thresholds struggle with variiform rationales, while our topological approach remains effective.

Question: regarding the result of MUTAG

[Answer:]

• The results of MUTAG can be attributed to the uniquely simple structure of MUTAG's rationale subgraphs. MUTAG's rationale subgraphs consist of just two edges sharing a common node (the functional groups -NO2 and -NH2). This represents the simplest possible non-trivial subgraph structure, lacking the topological complexity present in other datasets. Specifically:

  • There are no cycles (1-homology features)
  • The 0-homology structure (connectivity) is nearly trivial
  • The rationale can be identified primarily through node/edge features rather than topological structure

• In such cases, our topological discrepancy measure, which excels at capturing complex structural patterns, may introduce unnecessary complexity by analyzing features (like cycle bases) that aren't relevant to the true rationale. The model ends up relying more heavily on the prediction loss other than the interpretability regularization.

We appreciate the reviewer's constructive feedbacks.

Weakness 1

Regarding the preliminary introduction to TDA, please refer to our answer to the first common concern in the general response.

Regarding the different of $H$ between $H_p(\mathcal{F}(G))$ and $H_p(G_{\leq t})$:

• $H$ is simply a notation representing homology, without any concrete meaning on its own. The key difference lies in what it's applied to:

  • $H_p(G_{\leq t})$ is the homology group (vector space) of a single graph $G_{\leq t}$

  • $H_p(\mathcal{F}(G))$ represents the persistent homology of a graph filtration $\mathcal{F}(G)$ (a chain of nested subgraphs of $G$). It is a richer algebraic structure consisting of:

    1. A collection of homology vector spaces ${H_p(G_{\leq t})}$
    2. Linear maps between these spaces ${H_p(G_{\leq t_1}) \to H_p(G_{\leq t_2})}$

Regarding Figure 1, we have enhanced its clarity in several ways:

• We've added more explanation of homology groups (vector spaces) in Appendix B.

• We've restructured the lengthy caption into three more digestible parts:

  1. The first part serves as an illustrative example of persistent barcode on a graph filtration, now included in the preliminary introduction to TDA (see the last part of the "Persistent Homology" paragraph in Section 2.1 in pdf link).
  2. The second part remains as a concise caption for Figure 1.
  3. The third part appears at the beginning of the experiment section, demonstrating "what could be learned by our topological discrepancy" (see Section 4 in pdf link).

Weakness 3

Regarding the hyperparameter settings of our prior regularization, please refer to our answer to the second common concern in the general response.

Thanks again for your time and careful review. If you think we have resolved all your concerns, we will kindly ask you to consider reassessing the rating.

Based on an insightful discussion with some reviewer regarding our prior regularization, we would like to share some example distributions of our edge filtration (learned on BA-HouseOrGrid-2Rnd dataset):

• Fig1 illustrates the distribution of learned edge filtration on a single graph.
• Fig2 displays an averaged distributions across 10 sample graphs

Intuitively, the distribution resembles a mixture of two Gaussians as expected: a wider one on the left corresponding to $G_\epsilon$ and a narrower one on the right corresponding to $G_X$. We believe these illustrative examples help understand what has been learned in our model.