TopInG: Topologically Interpretable Graph Learning via Persistent Rationale Filtration

Authors: Fan Xu, Cheng Xin, Xin Ding, Jie Gao, Jiaxin Ding
Primary area: learning on graphs and other geometries & topologies
Keywords: topological data analysis, persistent homology, graph neural network, interpretability, explainability, filtration learning

Abstract:
Graph Neural Networks (GNNs) have shown remarkable performance in various scientific domains, but their lack of interpretability limits their applicability in critical decision-making processes. Recently, intrinsic interpretable GNNs have been studied to provide insights into model predictions by identifying rationale substructures in graphs. However, existing methods face challenges when the underlying rationale subgraphs are complicated and variable. To address this challenge,
we propose TopIng, a novel topological framework to interpretable GNNs that leverages persistent homology to identify persistent rationale subgraphs.
Our method introduces a rationale filtration learning technique that models the generating procedure of rationale subgraphs, and enforces the persistence of topological gap between rationale subgraphs and complement random graphs by a novel self-adjusted topological constraint, topological discrepancy. We show that our topological discrepancy is a lower bound of a Wasserstein distance on graph distributions with Gromov-Hausdorff metric. 
We provide theoretical guarantees showing that our loss is uniquely optimized by the ground truth under certain conditions.
Through extensive experiments on varaious synthetic and real datasets, we demonstrate that TopIng effectively addresses key challenges in interpretable GNNs including handling variiform rationale subgraphs, balancing performance with interpretability, and avoiding spurious correlations. 
Experimental results show that our approach improves state-of-the-art methods up to 20%+ on both predictive accuracy and interpretation quality.

Decision: reject
Reviewer scores: 6, 5, 6, 6

Reviews and discussion:
<thread>
creation date:
1729701551135

thread_type:
official_review

<thread_object>
creator: reviewer_xsrv

<content>
summary:
This paper proposes a framework TOPING for XGNN, which is similar to the GSAT pipeline. It introduces a rationale filtration learning technique and a topological discrepancy constraint to separate important subgraphs from random ones. The method offers theoretical guarantees and improves both accuracy and interpretability, outperforming existing approaches by over 20% in experiments. However, the comparison with other methods is potentially unfair due to differences in evaluation metrics or datasets.

strengths:
1. This paper introduces an existing method based on the assumption, "either explicitly or implicitly that the subgraph rationales are nearly invariant across different instances within the same category of graphs." This is a reasonable and novel aspect of the problem. However, there are few experiments to support this idea.
2. This paper introduces the $p$-homology functor to XGNN, which is a novel approach to addressing this problem.

weaknesses:
1. Some expressions are confusing. For example, in Equation 3, the meaning of $\mathcal{R}$ is unclear. In Figure 2, the meaning of $L_{topo}$ is also not explained.
2. In subsection 3.2, the distribution of the prior is determined by the hyperparameters $\mu$ and $r$. However, $\mu$ is a pre-defined parameter, raising the question of how to set this parameter. Additionally, $r$ is a learnable parameter. Will this setting lead to a trivial solution, where the divergence between $\mathcal{N}(\mu_1,r_1)$ and $\mathcal{N}(\mu_2,r_2)$ is small?
3. The comparison is potentially unfair. In Appendix C.2.1, all baselines are based on the GIN backbone, while TOPING uses the CINpp backbone, which could result in biased comparisons.

questions:
1. In Figure 1, the meaning of the row lines is unknown.
</content>
</thread_object>

</thread>
<thread>
creation date:
1729764247015

thread_type:
official_review

<thread_object>
creator: reviewer_rszd

<content>
summary:
This paper proposes an interpretable GNN framework that leverages techniques from topological data analysis, specifically persistent homology. The method splits an input graph into a rationale subgraph (important subgraph) and a noise subgraph, where the rationale subgraph is used for both predicting the target and providing an explanation for the prediction. The authors introduce a novel loss function that quantifies the topological discrepancy between the rationale and noise subgraphs and jointly optimize this loss along with the prediction loss. The framework is evaluated using several synthetic datasets and two real-world molecular datasets, demonstrating its effectiveness.

strengths:
1.	This paper introduces an innovative use of topological analysis to provide intrinsically explainable GNNs, offering a promising direction for future research.
2.	The authors proved that the method can optimize to the true important subgraph under certain conditions, providing a solid mathematical foundation for the approach.

weaknesses:
1.	The writing is difficult to follow due to unclear definitions of the mathematical symbols used (see questions below). The figures are not well-explained and can be confusing, especially for readers with limited knowledge of topological analysis.
2.	The experimental datasets are limited, focusing only on synthetic and relatively simple molecular datasets. Additionally, qualitative visualizations for the MUTAG dataset are missing, which reduces the clarity of the results.

questions:
1. What is $\beta_1$ in Fig. 1?
1. In Eq. 3, what is $\mathcal R$?
2. What is the difference between $f_{\phi}, h_{\phi}$? In Fig.2 they are all equal to $GNN_\phi$ so they are the same? And is $\phi$ the parameters of GNN?
3. After reading Sec 3 I still have problem understanding how the model predicts. In Fig.2 it seems that the model first generates a subgraph $G_X$ according to the edge score from $f_\phi(G)$, feed it into a GNN $h_\phi$, somehow concatenate with $\mathcal T_X, \mathcal T_\epsilon$, and use a classifier to get the final prediction. What is $\mathcal T_X, \mathcal T_\epsilon$ and how are they concatenated with output of GNN $h_\phi$? A more detailed explanation of Fig.2 is needed.
4. Row 267-269:the defined $\mathcal G, \mathcal F(\mathcal G)$ are never used.
5. Does the measure of topological discrepancy also consider the node/edge features? It would be interesting to see how the method performs on graphs where not only topological structure but also node/edge features are relevant.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730409812270

thread_type:
official_review

<thread_object>
creator: reviewer_gpkc

<content>
summary:
The paper introduces TOPING, a novel intrinsically interpretable framework for GNNs that uses topological data analysis (TDA) to identify stable rationale subgraphs. TOPING addresses key limitations in existing interpretable GNN models by using a rationale filtration learning approach. Extensive experimentation shows improvements over state-of-the-art interpretability and predictive performance.

strengths:
S1. Using TDA for intrinsically interpretable GNNs is interesting. 

S2. The authors provide theoretical guarantees to show that topological discrepancy optimally captures rationale subgraphs. 

S3. The authors present extensive experiments across multiple datasets.

weaknesses:
W1. The mathematical notation and presentation could be improved, as some definitions and descriptions are unclear or ambiguous. Clarifying these elements would enhance the paper’s readability for readers less familiar with topological data analysis. 

W2. The paper would benefit from a detailed time complexity analysis and runtime study, particularly in comparison with baseline methods. This addition would clarify whether TOPING’s performance improvements come at the cost of efficiency. 

W3. Since TOPING requires learning a filtration function that assigns values to each edge, this method may become impractical for large graphs due to the need to compute and store $|E|$ values. Further discussion on how TOPING might be adapted or approximated for larger graphs would be valuable.

questions:
Q1. The explanation of TDA in Section 2.2 is unclear. In Figure 1, the subgraph $G_{t}$ appears to have more edges as $t$ decreases. However, in line 170, it seems that $G_{t}$ should contain more edges as $t$ increases. Could the authors clarify this apparent discrepancy?

Q2. In line 271, the term "topological invariants $\tau$ " is introduced without a clear mathematical definition. Could the authors provide a formal definition for $\tau$ to improve understanding?

Q3. In line 278, Equation (3) is not properly referenced. Besides, it appears disconnected from the context. Could the authors clarify its relevance here?

Q4.  The authors state that $f_\phi$ and $h_\phi$ share parameters. However, $f_\phi$ is defined as a function mapping to $[0,1]^{|E|}$, while $h_\phi$ seems to map to $\mathbb{R}^{|V|}$. Could the authors explain how parameter sharing is feasible between these two functions with distinct output spaces?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730524122892

thread_type:
official_review

<thread_object>
creator: reviewer_nh1h

<content>
summary:
In this paper, the authors propose a graph explanation method based on the persistent homology to identify stable rational subgraphs via persistent rationale filtration learning. Specifically, they propose a topological discrepancy loss to achieve the goal. Experimental results seem to outperform state-of-the-art models in most datasets.

strengths:
- The idea of using topological data analysis for graph explanation is novel and interesting. 

- The derivation of the proposed method seems to be solid with theoretical insights.

weaknesses:
- The preliminary, especially the TDA, is not very clear, making it hard for readers without the knowledge of persistent homology (I don’t think it is necessarily a prerequisite knowledge for graph explainability). What is the difference of $H$ between the $p$-homology functor $H_p (\mathcal{F} (G))$ and $H_p (G_{\le t})$? Figure 1 is also not easy to understand with a clear explanation of the homology groups. The caption is over lengthy and not illustrating the intuitive idea very well. It will be better to segment the long caption into several parts to make it more readable.

- In the introduction, they mention one challenge that exists in current graph explanation models: that different graphs may contain different core subgraphs even within the same category. Yet, I don’t see why the proposed method can tackle this problem well. The training procedure involves learning a filtration function to separate the graph. How such a mechanism can tackle the challenge and why the separating method in other methods cannot are not well discussed. It is recommended to add more analysis (or examples) to demonstrate why the proposed method can address this challenge and others cannot.

- The prior regularization seems to be empirical. The hyperparameters of the prior are not trivial. This raises concern whether the proposed method is sensitive to the selection of the prior and the corresponding parameters. More discussion is encouraged.

questions:
- See the weakness above

- The results of MUTAG are not impressive in terms of both interprebility and accuracy. Further analysis for these results are required for better understanding the proposed method.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732486629848

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We sincerely thank all reviewers for their thorough reviews and constructive feedback. The reviewers highlighted several strengths of our work, including: (1) the innovative application of topological data analysis to interpretable GNNs (Reviewer nH1H, gpKc, rSzd, xsRV); (2) the solid mathematical foundation and theoretical guarantees for optimizing to ground truth rationale subgraphs (Reviewer nH1H, gpKc, rSzd);

There are two common concerns raised by multiple reviewers. Here we will first address them in the general response (individual reviewer-specific concerns will be addressed in separate responses later):

1. (Review nH1H, gpKc, rSzd) Clarity of the TDA preliminaries and mathematical notations: multiple reviewers noted that the TDA concepts, especially persistent homology and some mathematical notations, need clearer and more intuitive explanations. 

- [Answer:] We have revised Section 2.1 to make some key concepts of TDA including graph filtrations, persistent homology, and topological feature comparison more accessible to a general audience. For interested readers, we also provide more detailed discussion in Appendix B. 
We have also improved the notation clarity in Section 3 regarding topological discrepancy definition and loss functions. These revisions can be found in the pdf (highlight in blue) [(pdf link)](https://anonymous.4open.science/r/TopoEx-1EE2/OpenReview/rebuttal_update.pdf)


2. (Review nH1H, xsRV) Prior regularization design choices: Several reviewers questioned the prefixed choices and sensitivity of the hyperparameters $\mu$ in our prior regularization. 

- [Answer:] Our choice of $\mu$ parameters was not empirically tuned - we set these values once and used them consistently across all experiments due to the theoretical robustness of our approach. As shown in the Table 1, varying these parameters has minimal impact on performance. The key insight is that our prior regularization acts as a clustering mechanism of edges into two clusters on [0,1], where the exact cluster centers ($\mu_1$, $\mu_2$) matter less than their separation since the edge filtration is learned and used in the topological discrepancy, thanks to the stability property of persistent homology. Any choice where $|\mu_1-\mu_2|>0$ maintains a reasonable gap should work effectively, as demonstrated by our experimental results. This differs fundamentally from previous approaches like GSAT[1] and GMT[2], offering better stability and robustness to parameter choices.

We would also like to include more example results for illustration (see [pdf link](https://anonymous.4open.science/r/TopoEx-1EE2/OpenReview/MoreInterpretationVisualization.pdf)).


Table 1: TopInG's performance on BA-2motifs with different settings of $\mu$.   
| ($\mu_1$, $\mu_2$) | Interpretation (AUC) |
|-------------------|-------------------|
| (0.15, 0.65)       | 99.60 ± 0.48 |
| (0.25, 0.75)       | 100.00 ± 0.00 |
| (0.20, 0.70)       | 100.00 ± 0.00 |
| (0.30, 0.80)       | 100.00 ± 0.00 |



Reference:

[1] Miao, Siqi, et al. "Interpretable and generalizable graph learning via stochastic attention mechanism." International Conference on Machine Learning. PMLR, 2022.

[2] Chen, Yongqiang, et al. "How Interpretable Are Interpretable Graph Neural Networks?." arXiv preprint arXiv:2406.07955 (2024).
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces TOPING, an interpretable GNN framework leveraging topological data analysis (TDA), particularly persistent homology, to identify stable rationale subgraphs. By employing rationale filtration learning and a novel topological discrepancy loss, TOPING separates input graphs into rationale (important) and noise subgraphs, optimizing for both prediction accuracy and interpretability. Experimental results on synthetic and real-world datasets demonstrate significant improvements over state-of-the-art methods, achieving over 20% performance gains. However, potential evaluation inconsistencies with existing methods warrant further investigation. The approach offers theoretical guarantees and addresses key limitations in current interpretable GNN models, advancing both predictive and explanatory capabilities.

Interpreting GNNs using topological data analysis is an interesting approach. However, as many reviewers pointed out, the writing can be significantly improved. Even if the negative review is discounted, the average score is 6, with all reviews being weak accepts. This indicates that the paper is a weak accept. Moreover, the paper requires significant rewriting; it is difficult to accept in its current form. Therefore, I encourage the authors to revise the paper based on the reviewers' comments and resubmit it to a reputable ML venue.