- Rating
- 2(+1)
- Confidence
- 3
- Informativeness
- 2(+1)
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper introduces AMIGA, an extension of the self-interpretable model GNAN, which discovers structural motifs as a vocabulary and decomposes contributions into feature, structural, and feature-structure interaction channels.
Experiments on graph classification/regression datasets show that the proposed method outperforms its predecessor GNAN and achieves performance closer to standard black-box GNNs.
Critical strengths
- Using a motif vocabulary to capture structural signals is a sound and natural design.
- This paper identifies several limitations of the existing model GNAN and presents a non-trivial extension.
Critical weaknesses
-
Considering the number of motifs, features, and motif-feature interactions, the resulting contributions may still be difficult to analyze, even if each component is individually interpretable. This limits the practical interpretability of the proposed method.
-
As the proposed method does not generally outperform standard black-box GNNs, further validation of its explanation capability beyond BA-based synthetic datasets would help strengthen the significance of this work. For example, the GNNExplainer paper[1] also incorporates tree-based graphs with ground-truth explanations.
-
The complexity of the motif-based approach is concerning for larger motifs or graphs. Currently, the paper only incorporates graphlets of up to five nodes, potentially limiting its ability to capture more complex structural patterns.
[1]: GNNExplainer: Generating explanations for graph neural networks
Questions for authors
- Could the authors briefly discuss the computational complexity of the proposed method, particularly motif discovery, with respect to graph size and the number/size of graphlets?
5 comments
References:
[1] Efficient detection of network motifs. IEEE/ACM transactions on computational biology and bioinformatics. 2006.
[2] Efficient graphlet kernels for large graph comparison. Artificial intelligence and statistics. 2009.
[3] Graft: An efficient graphlet counting method for large graph analysis. IEEE Transactions on Knowledge and Data Engineering. 2014.
[4] Scalability of network visualisation from a cognitive load perspective. IEEE transactions on visualization and computer graphics. 2020
[5] Pinar Yanardag and S. V. N. Vishwanathan. The Structurally Smoothed Graphlet Kernel, 2014.
I appreciate the clarifications and the additional effort the authors put into the additional datasets. My concerns (mainly W1 and the explanation ability of the proposed method) have been addressed.
However, I remain concerned about the heavy limitations of using graphlet motifs. For example, the computational complexity is linear if the maximum node degree is bounded, while this assumption does not hold for many types of graphs, such as BA graphs. Furthermore, motifs require sufficient statistical support to be meaningful, which limits their applicability to small, local structural patterns.
Overall, I have raised my rating to 2.
Response to Reviewer rHYP: Practical Interpretability, Additional Datasets, and Motif Scalability
Thank you for your detailed review and your valuable time. Below, we address your concerns.
W1: Practical Interpretability
Thank you for raising this concern. We agree that inspecting all feature–motif contributions as a flat list could be difficult. However, AMIGA explanations can be better interpreted hierarchically, where users first compare the graph-level feature, structural, and interaction contributions (ΦF,ΦS,ΦI), and then rank them by magnitude and inspect only the leading terms within the dominant channel. We provide two concrete examples of this below:
Example 1: Consider a trained AMIGA on the TREE–GRID dataset. For this example, the prediction is entirely driven by the structural channel (ΦS=6.84 ), while the feature and interaction channels make no contribution (ΦF=0 and ΦI=0 ). Therefore, the explanation can focus exclusively on the graph structure.
Example 2: Consider a trained AMIGA on the MUTAGENICITY dataset. For a graph predicted as non-mutagenic, the structural channel provides the largest contribution to the prediction, accounting for 93.8% of the total. In contrast, for a graph predicted as mutagenic, the interaction channel dominates, accounting for 95.9% of the total contribution. This illustrates how AMIGA decomposes individual predictions and identifies which aspects of the graph drive each outcome.
The number of inspectable elements is further limited by:
We added this remark and the additional experiments in the revised manuscript, in Section 4.4 and Appendix C.2.
W2: Additional datasets
We thank the reviewer for the comment. Following your suggestion, we included two additional tree-based graph-classification experiments: tree versus tree + cycle, and tree versus tree + grid. Each dataset contains 1,000 balanced examples, with comparable node-count distributions and constant features. The planted motif nodes provide, therefore, ground-truth explanations and evaluate explanation AUROC on all positive test graphs for five seeds.
Under the evaluated configurations, AMIGA and GIN both achieve near-perfect predictive AUROC, but their explanation AUROC differs, and AMIGA achieves the best performance in both datasets. We added these additional experiments in Appendix C.1 of the revised manuscript.
W3/q1: Computational Complexity and Motif Scalability.
Thank you for raising this concern. We have expanded the complexity discussion and added the following results to Appendix B.2:
Computational cost. To enumerate graphlets, we use RAND-ESU [1]. For fixed graphlet size q and bounded degree, the complexity scales linearly with the number of nodes [2]. We report runtimes on ER graphs with increasing ∣V∣ for q∈{3,4,5,6} in Appendix B.2. For a fixed graph with 10,000 nodes, the results show a runtime ranging from 0.008 for q=3 up to 1.8 seconds for q=6, with an approximately linear trend.
On our largest benchmark (QM9), enumerating all 29 candidates over the 91,581 training graphs takes 2.52 seconds. Note that this cost is for the motif discovery part, which is paid once at pre-processing time.
Motif size. Although AMIGA is not restricted to a particular motif size and can use any motif vocabulary supplied by the counting backend, we choose qmax=5 for our experiments. This choice is mainly motivated by the following:
Thank you again; your remark helped in making our paper more rigorous! Please let us know if our answers address your concerns, or whether we can provide further clarifications.