- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper investigates the loss of attribute–structure interactions in GCN based Graph Neural Tangent Kernels (GNTKs). The authors construct graph pairs that remain indistinguishable under the studied GNTK regardless of depth, while certain fixed-order interaction statistics can distinguish them. Based on this observation, they propose FM-GNTK, which combines a multi-depth GNTK with an additional kernel constructed from the original node attributes and their propagated features. The paper provides theoretical separation results and evaluates the proposed method on several graph classification benchmarks.
Critical strengths
The paper provides a thorough theoretical analysis with explicit graph constructions and all-depth collision results. The distinction between interaction order and nonlinear depth is also interesting. The additional architectural controls and independently tuned experiments help assess the proposed method, although their results are not always favorable.
Critical weaknesses
My main concern is whether the proposed solution is sufficiently motivated. While the main experimental results seem encouraging, several of the more informative comparisons and diagnostics are in the appendix, and they give a less convincing picture of the method's practical benefits. Sec. 5.3 briefly acknowledges these limitations, but I think they deserve more attention given their importance to the paper's contribution.
W1. The theoretical analysis focuses on a rather specific GCN-based GNTK, and the underlying representation issue seems closely related to known expressivity limitations of GCN-style aggregation [1]. The authors establish all-depth collisions, including a construction for each fixed positive integer self-loop weight, but it is unclear how much broader insight this provides beyond existing expressivity results. There is also no theoretical comparison establishing what the proposed memory mechanism offers over more general center-preserving or input-retaining architectures.
W2. The proposed method does not show a consistent advantage over simpler alternatives. The main ablations use structural hyperparameters selected for FM-GNTK, which is reasonable for studying component contributions but less convincing for comparing independently optimized methods. In Appendix Table 8, FM-GNTK performs worse than Dynamic-JK on three of four datasets. Simply changing the self-loop weight to 2 achieves higher mean accuracy on all four, while the zero-order memory variant matches or exceeds FM-GNTK. This raises questions about how much the additional positive-order interaction statistics actually contribute to predictive performance.
W3. The practical relevance of the theoretical representation failure is also unclear. Appendix E.1 shows that Dynamic-JK already distinguishes all 31 examined opposite-label MUTAG pairs at depths 3 and 6. On the 15 pairs used in the held out prediction analysis, FM-GNTK also shows no improvement over Dynamic-JK. The constructed examples establish a valid theoretical limitation, but the paper does not convincingly demonstrate that this particular information loss is an important source of prediction errors on real datasets.
Overall, the theoretical results are technically interesting, but I find the contribution rather narrow. The empirical results also do not provide sufficient evidence that the additional memory mechanism is preferable to simpler alternatives.
References
[1] Xu et al., How Powerful Are Graph Neural Networks? ICLR 2019.
Questions for authors
Q1. Can the authors provide a more direct theoretical comparison with center-preserving or input-retaining GNTK architectures? It is unclear whether the proposed memory mechanism offers any expressive advantage over these alternatives, beyond the specific GCN formulation considered in the paper.
Q2. Can the authors identify cases in real datasets where the proposed memory features resolve an ambiguity in Dynamic-JK that leads to an actual improvement in classification? The results in Appendix E.1 do not seem to demonstrate this.
15 comments
Response to Reviewer WEG3: Memory Contributions, Controlled Ablations, and Real-Data Evidence (W2)
W2 — Independently optimized alternatives and positive-order Memory
Reviewer W2
The proposed method does not show a consistent advantage over simpler alternatives. The main ablations use structural hyperparameters selected for FM-GNTK, which is reasonable for studying component contributions but less convincing for comparing independently optimized methods. In Appendix Table 8, FM-GNTK performs worse than Dynamic-JK on three of four datasets. Simply changing the self-loop weight to 2 achieves higher mean accuracy on all four, while the zero-order memory variant matches or exceeds FM-GNTK. This raises questions about how much the additional positive-order interaction statistics actually contribute to predictive performance.
Response
Full has the highest mean among the listed controls on nine of ten datasets under their respective selection procedures; tuned self-loops lead on PTC_FR. A separate fixed-setting COX2 replacement tests what positive-order Memory contributes within a selected model.
All methods share saved outer splits: three repetitions of five-fold outer CV with three-fold inner CV, selecting parameters within outer training. Full uses two inner-CV repetitions to choose one Full kernel or an equal-weight average of three or five, classifier settings and a binary decision threshold. The controls use their respective independent searches. Section 5.1 and Appendix F specify these distinct procedures and search spaces.
Values below are accuracy (%) ± sample standard deviation across the three seed-level CV means. The Full column is the same as in the revised headline table.
| Dataset | FM-GNTK | Dynamic-JK | Dynamic + M0 | Independent center | Input residual | Tuned self-loop |
|---|---|---|---|---|---|---|
| MUTAG | 89.76 ± 0.03 | 86.47 ± 1.15 | 87.00 ± 1.34 | 88.06 ± 1.35 | 88.06 ± 0.32 | 87.52 ± 0.31 |
| PTC_MR | 64.85 ± 1.37 | 62.50 ± 2.80 | 61.81 ± 1.37 | 62.80 ± 1.05 | 60.56 ± 1.46 | 62.59 ± 2.37 |
| BZR | 88.85 ± 1.40 | 88.00 ± 1.49 | 88.57 ± 1.03 | 87.83 ± 0.51 | 87.09 ± 1.00 | 88.24 ± 1.49 |
| COX2 | 82.95 ± 0.46 | 81.58 ± 0.98 | 82.37 ± 1.63 | 82.44 ± 1.39 | 82.58 ± 0.68 | 81.81 ± 1.90 |
| PROTEINS | 76.07 ± 0.68 | 74.33 ± 0.43 | 73.92 ± 0.78 | 74.55 ± 0.26 | 74.34 ± 0.38 | 74.69 ± 0.23 |
| IMDB-B | 74.90 ± 0.96 | 74.50 ± 0.26 | 74.27 ± 0.15 | 74.20 ± 0.72 | 73.83 ± 0.47 | 74.07 ± 0.32 |
| IMDB-M | 51.21 ± 0.37 | 50.40 ± 0.20 | 50.73 ± 0.64 | 51.00 ± 0.47 | 50.60 ± 0.73 | 50.51 ± 0.38 |
| PTC_FM | 66.24 ± 2.16 | 63.19 ± 2.34 | 63.37 ± 1.15 | 65.48 ± 2.99 | 63.85 ± 1.28 | 63.38 ± 1.47 |
| PTC_FR | 69.24 ± 1.50 | 69.19 ± 1.57 | 67.57 ± 1.28 | 68.43 ± 0.87 | 68.33 ± 0.33 | 69.76 ± 0.17 |
| PTC_MM | 69.18 ± 2.75 | 66.19 ± 2.55 | 68.16 ± 2.03 | 65.99 ± 1.14 | 66.08 ± 2.55 | 65.39 ± 1.14 |
Replacing positive-order Memory lowers COX2 accuracy from 82.30 ± 0.86% to 80.95 ± 0.56%. This diagnostic fixes depth one and degree-feature weight 1, with Memory through order three. Within each outer fold, we select Full on the training data, replace Memory with , retain its selected backbone, fusion weight and classifier settings, and refit on the same training graphs.
Across three repetitions of five-fold CV, the mean difference is 1.35 percentage points, positive in each seed-level mean. This fixed-setting contribution is distinct from the independently optimized procedures above, where expanded Full selection gives 82.95% on COX2. Section 5.3 presents both comparisons.
Changes in the revised PDF. Section 5.1, p. 8, lines 411–417; Section 5.3, p. 9, lines 469–483; Table 3, p. 10, lines 487–498. Full selection and control grids: Appendix F.1, pp. 38–39, lines 2001–2076.
Response to Reviewer WEG3: Memory Contributions, Controlled Ablations, and Real-Data Evidence(W3/Q2)
W3 / Q2 — A real-data case connecting positive-order Memory to classification
Reviewer W3
The practical relevance of the theoretical representation failure is also unclear. Appendix E.1 shows that Dynamic-JK already distinguishes all 31 examined opposite-label MUTAG pairs at depths 3 and 6. On the 15 pairs used in the held out prediction analysis, FM-GNTK also shows no improvement over Dynamic-JK. The constructed examples establish a valid theoretical limitation, but the paper does not convincingly demonstrate that this particular information loss is an important source of prediction errors on real datasets.
Reviewer Q2
Can the authors identify cases in real datasets where the proposed memory features resolve an ambiguity in Dynamic-JK that leads to an actual improvement in classification? The results in Appendix E.1 do not seem to demonstrate this.
Response
Yes. On a held-out COX2 pair, Full correctly predicts both labels, while Dynamic-JK predicts class 0 for both; removing positive-order Memory makes Full miss the positive graph. This is a prediction ambiguity, not a representation collision: Dynamic-JK's representations are distinct.
Graphs 51 and 449 have labels 0 and 1 and share the test fold for seed 44, outer fold 3; indices are zero-based. The saved refits below use tolerance . These are SVM decision scores, not probabilities or accuracies: negative predicts class 0, positive class 1.
| Variant | Graph 51, true label 0 | Graph 449, true label 1 |
|---|---|---|
| Full, Memory through order 3 | -0.695368 | +0.251015 |
| Replace Memory with M0 | -0.539594 | -0.875494 |
| Remove Memory | -0.521606 | -1.171806 |
| Truncate Memory to order 1 | -0.648990 | -0.129242 |
| Truncate Memory to order 2 | -0.650473 | +0.160555 |
Replacing Memory with , removing it, or truncating at order one makes the positive graph incorrect; order two restores it. Each refit changes only the Memory component, retaining Full's training-selected backbone, fusion weight, SVM regularization, class weighting and zero threshold.
Both graphs have 38 nodes, 40 edges, and identical node-label, degree and joint node-label/degree counts. Their zero-order moments agree,
$ M_0(G)=M_0(H), $
whereas positive-order moments differ. Their one-layer squared normalized Dynamic-JK distance is approximately , so this pair is not a representation collision.
The case was identified retrospectively from frozen out-of-fold predictions. Model selection and refitting used only the corresponding training graphs. Independent reproduction from saved splits and parameters preserves the correction and its disappearance under the controls when tightening tolerance from to .
A second example is PTC_FR graphs 192 and 332, seed 42, outer fold 2 (zero-based). Full predicts their labels 0 and 1; Dynamic-JK, the replacement and Memory removal predict 0 for both. Order one misses the positive graph, while orders two and three classify both correctly.
Together with the COX2 replacement experiment, these cases support a prediction-level contribution from positive-order Memory under the reported settings. Section 5.4 presents the main case; Appendix G.2 gives its visualization, signed scores and all-seed outcomes. Table 3 separately compares independently optimized procedures.
Reference cited in Reviewer WGE3's comments
[1] Xu et al., How Powerful Are Graph Neural Networks? ICLR 2019.
Changes in the revised PDF. Section 5.4, p. 10, lines 508–515; Appendix G.2, pp. 43–45, lines 2301–2405, including Figure 8 and Table 9 (signed decision scores at tolerance ) on p. 44, and Table 10 (all-seed outcomes) on p. 45.
Response to Reviewer WEG3: Memory Contributions, Controlled Ablations, and Real-Data Evidence (W1/Q1)
The revision adds three direct comparisons:
W1 / Q1 — What Memory adds beyond the studied GCN backbone
Reviewer W1
Reviewer Q1
Response
Memory has a larger one-layer normalized margin than the specified independent-center NTK on the first witness family, uniformly over the relative center strength. The center channel already separates this pair; the comparison quantifies its geometry. The original constructions identify input interaction moments Mp that increasing depth or combining pooled outputs cannot recover, with chance-level classification on the balanced task versus a perfect Memory separator. They also distinguish the contributions of propagation order and nonlinear depth.
Consider the bias-free, one-hidden-layer architecture
$ z_v= \frac{\sqrt{\alpha},u^\top x_v+w^\top(PX)_v} {\sqrt{1+\alpha}}, \qquad \alpha>0, $
with independent standard Gaussian u,w, 2-ReLU, mean pooling, and trained projections and linear output under standard NTK scaling. At this layer, the center channel directly retains the original input. On the first witness family, with binary one-hot attributes and P=(A+I)/4, write DK(G,H)=2−2Kˉ(G,H). With equally weighted M0,M1 Memory and its fusion with the submitted backbone at depth one and η=4/5, we prove, for every α>0,
$ D_{\mathrm{center}} \leq B:=\frac{2(\pi-137/60)}{2\pi+1} <0.236<\frac{16}{65}=D_{\mathrm{Full}}, \qquad D_{\mathrm{mem}}=\frac{4}{13}. $
For two oppositely labeled unit feature vectors, the maximum geometric margin is DK/2. Proposition R3 and its proof in Appendix A.13 derive the bound by evaluating the pooled ReLU NTK on the four attribute/propagation states and bounding its positive even-power expansion.
Changes in the revised PDF. Section 3, p. 6, lines 270–288; Proposition R3 and proof, pp. 27–28, lines 1429–1511.