acceptodds
Under review as a conference paper at ICLR 2027

What Graph Neural Tangent Kernels Forget: Preserving Attribute–Structure Interactions

Abstract

Graph classification can depend on the relationship between node attributes and local graph topology. In MUTAG, we identify molecules with opposite mutagenicity labels and different attachment positions despite identical atom counts and degree histograms. We study the ability of graph neural tangent kernels (GNTKs) to distinguish such attribute–structure relations. For GNTKs with self-looped, symmetrically normalized propagation and mean readout, we construct graph families that remain indistinguishable at every depth, even when pooled outputs from all layers are combined. On a balanced binary classification task defined over these graphs, any classifier using these GNTK representations is limited to chance accuracy. We propose Fixed-Memory GNTK (FM-GNTK), which combines a multi-depth GNTK with a memory kernel built from products of original node attributes at pairs of nodes, weighted by finite-step graph propagation. At a fixed memory order, the retained input-based interaction statistics remain unchanged as network depth increases. This memory admits a perfect separator for the constructed task. We further prove that fusion with positive weights on both normalized branches preserves every graph distinction captured by either branch.Experiments on ten TU and three large molecular benchmarks evaluate predictive performance, component contributions, and Nyström approximation fidelity. Matched comparisons and independently tuned controls show that the predictive benefits of combining the branches depend on the dataset and comparison setting.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph neural tangent kernels, Graph classification, Graph representation learning, Attribute-structure interactions

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_WGE3OpenReview ↗
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
AuthorsOpenReview ↗

Response to Reviewer WEG3: Memory Contributions, Controlled Ablations, and Real-Data Evidence (W1/Q1)

The revision adds three direct comparisons:

  • Theory: a uniform one-layer margin advantage over the specified independent-center NTK, on a family that both methods already separate.
  • Independently optimized alternatives: Full has the highest mean among the listed controls on nine of ten TU datasets under their respective selection procedures.
  • Positive-order Memory in prediction: replacing it with M0M_0 at Full's selected settings changes COX2 accuracy from 82.30% to 80.95%. A held-out pair shows the corresponding prediction correction; its Dynamic-JK distance is nonzero.

W1 / Q1 — What Memory adds beyond the studied GCN backbone

Reviewer 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.

Reviewer 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.

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 MpM_p 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,wu,w, 2\sqrt{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)/4P=(A+I)/4, write DK(G,H)=2−2Kˉ(G,H)D_K(G,H)=2-2\bar{K}(G,H). With equally weighted M0,M1M_0,M_1 Memory and its fusion with the submitted backbone at depth one and η=4/5\eta=4/5, we prove, for every α>0\alpha>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\sqrt{D_K}/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.

AuthorsOpenReview ↗

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.

DatasetFM-GNTKDynamic-JKDynamic + M0Independent centerInput residualTuned self-loop
MUTAG89.76 ± 0.0386.47 ± 1.1587.00 ± 1.3488.06 ± 1.3588.06 ± 0.3287.52 ± 0.31
PTC_MR64.85 ± 1.3762.50 ± 2.8061.81 ± 1.3762.80 ± 1.0560.56 ± 1.4662.59 ± 2.37
BZR88.85 ± 1.4088.00 ± 1.4988.57 ± 1.0387.83 ± 0.5187.09 ± 1.0088.24 ± 1.49
COX282.95 ± 0.4681.58 ± 0.9882.37 ± 1.6382.44 ± 1.3982.58 ± 0.6881.81 ± 1.90
PROTEINS76.07 ± 0.6874.33 ± 0.4373.92 ± 0.7874.55 ± 0.2674.34 ± 0.3874.69 ± 0.23
IMDB-B74.90 ± 0.9674.50 ± 0.2674.27 ± 0.1574.20 ± 0.7273.83 ± 0.4774.07 ± 0.32
IMDB-M51.21 ± 0.3750.40 ± 0.2050.73 ± 0.6451.00 ± 0.4750.60 ± 0.7350.51 ± 0.38
PTC_FM66.24 ± 2.1663.19 ± 2.3463.37 ± 1.1565.48 ± 2.9963.85 ± 1.2863.38 ± 1.47
PTC_FR69.24 ± 1.5069.19 ± 1.5767.57 ± 1.2868.43 ± 0.8768.33 ± 0.3369.76 ± 0.17
PTC_MM69.18 ± 2.7566.19 ± 2.5568.16 ± 2.0365.99 ± 1.1466.08 ± 2.5565.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 M0M_0, 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.

AuthorsOpenReview ↗

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 10−510^{-5}. These are SVM decision scores, not probabilities or accuracies: negative predicts class 0, positive class 1.

VariantGraph 51, true label 0Graph 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 M0M_0, 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 1.007×10−31.007\times10^{-3}, 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 10−310^{-3} to 10−510^{-5}.

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 M0M_0 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 10−510^{-5}) on p. 44, and Table 10 (all-seed outcomes) on p. 45.

Reviewer_5t3vOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies which attribute-structure relations a graph neural tangent kernel (GNTK) with self-looped symmetric normalization and mean readout can distinguish. It constructs regular graph families with one-hot attributes that collide at every depth, even when the pooled outputs of all layers are combined, while fixed input moments that pair original attributes with propagated attributes separate them; further witnesses show that higher-order moments and nonlinear depth each separate pairs that the other misses. Based on this, FM-GNTK combines a multi-depth GNTK with a fixed memory kernel of these moments through a convex mixture of separately normalized kernels. Experimental results show that FM-GNTK outperforms selected graph-kernel and neural baselines on ten TU datasets and three large molecular benchmarks.

Critical strengths
  1. Comprehensive theory. Every result is correctly argued, and the witness families cleanly separate what fixed moments and nonlinear recursion each capture.

  2. Transparent reporting. The paper discloses its inherited baselines and development reuse, and reports fold-contained controls even where they do not favor the method.

Critical weaknesses
  1. The experiments do not support the motivation. The collisions exist only on constructed regular graphs, the paper's own MUTAG analysis finds no real instance, and under fold-contained selection the full kernel does not beat its dynamic component, its zero-order control, or a reweighted self-loop.

  2. The baselines are unreliable and incomplete. The baseline numbers are inherited rather than rerun and do not match their cited sources, and the closest published kernels and recent graph kernels are not compared.

Questions for authors
  1. The abstract (lines 011 to 014) and the Introduction (lines 038 to 044) motivate the work with MUTAG graphs 117 and 119, but Appendix E.1 reports that Dynamic-JK separates all 31 opposite-label matched pairs, which "are not instances of the constructed GNTK collision" (lines 1660 to 1664), and the remark after Corollary 11 says the task result does not identify a bottleneck in MUTAG, AMES, or another natural dataset (lines 769 to 771). On the 15 held-out pairs, Full and Dynamic-JK each rank 11 correctly and Full selects its dynamic endpoint in 7 of 10 outer fits (lines 1666 to 1671). On which benchmark does the studied GNTK collide on a non-isomorphic pair that memory separates, and how often?
  2. Theorems 1 and 9 and Proposition 4 require regular graphs, equitable attribute partitions, one-hot inputs, and a unit or integer self-loop weight, while the benchmarks use irregular graphs with a degree channel and nodewise ℓ2 normalization (lines 383 to 384). Proposition 12 shows that any other self-loop weight separates the constructed pair, Appendix A.2 covers only integer weights (lines 791 to 792), and the depth-attenuation result is proved only for the linear GNTK (lines 270 to 273). Does a collision family exist for a real-valued self-loop weight, a GIN-style (1 + ε) center term, or the GNTK of Du et al. [1]?
  3. In Table 8, Self-loop weight 2 is above Full on all four datasets (MUTAG 88.30 vs 86.17), and Dynamic + zero order, whose memory keeps only label and degree co-occurrence counts (lines 841 to 842), is equal to or above Full on all four. Five of the ten TU configurations use P = 1 with γ = 0.1 (Table 3), which gives the first-order interaction a weight of 0.1, and Table 4 has no Dynamic + zero order row. How much of the Table 4 gain comes from attribute-structure interactions rather than from the zero-order term, and why is a separate memory branch preferable to tuning the self-loop weight?
  4. "Matched comparisons favor Full overall" (lines 479 to 480) rests on Table 4, where the structure is selected for Full and the components reselect only their classifier (lines 1246 to 1247) on graphs already used for development (lines 1210 to 1213). Under fold-contained selection (Table 8), Full is below Dynamic-JK on three of four datasets and 2.0 to 4.3 points below its own Table 4 accuracy (MUTAG 86.17 vs 90.50); the IMDB-M and AMES intervals span zero, the N-O diagnostic fails (lines 459 to 462), and Full minus Dynamic-JK on molhiv is +0.016 (line 426). Fold-contained results on all ten TU datasets, with each method tuning its own kernel and input parameters, are necessary.
  5. Appendix C.1 states that the Table 1 and Table 2 baselines come from "the authors' prior benchmark record", were not rerun, and that the citations do not verify their provenance (lines 1277 to 1290). The GNTK† row does not match its source: Du et al. [1] report PTC 67.9, IMDB-B 76.9, IMDB-M 52.8, and PROTEINS 75.6, against 58.1, 75.4, 51.4, and 74.2 here, and against the published values FM-GNTK (67.0, 76.1, 52.0) is lower on PTC, IMDB-B, and IMDB-M. The FM-GNTK SDs are across seed means (0.3 to 1.2), the baselines' are fold-level (up to 9.9). What are the results when the GNTK of [1] and the kernel baselines are rerun under the same protocol?
  6. The molhiv GCN and GIN values in Table 2 (76.06 and 75.58) match the OGB baselines of Hu et al. (2020), which are trained on the training split only, while FM-GNTK refits on training plus validation (lines 1206 to 1209). The sources of the PC-3 and MCF-7 baseline numbers are not given, the neural baselines date from 2017 to 2019, and no graph-kernel baseline is run on the three large datasets. Which baselines were run under the shared protocol?
  7. The closest published kernels are not compared. GCKN [2], which the paper cites for summing path and multilayer kernels (lines 135 to 136), is absent from Table 1; Appendix A.4 places the memory in the walk-kernel framework (lines 821 to 829), yet no walk-based kernel [3, 4] is compared; the GCN NTK with skip connections [5] is the published input-retaining kernel, while the paper's own input-retaining comparator appears only in the four-dataset audit; and recent graph kernels such as DHGAK [6] and DHTAGK [7] are missing. How does FM-GNTK compare with them under the same protocol?
  8. The Reproducibility Statement says the supplement includes "archived summary tables" (line 489), but the supplement contains no result tables and its own notes state that historical results and the final tables are not bundled; the benchmark record behind Tables 1 and 2 is not provided either. Appendix B.1 gives the candidate grids for L and P but not for η, γ, w_d, or C, and does not define the "boundary audits" (lines 1200 to 1202). Where are these tables and grids?
  9. The four main-text theories are not proved in proof blocks: Theorem 1 (Appendix A.7), Proposition 4 (A.8), Proposition 6 (A.3), and Theorem 5 (A.9 and A.10) are argued in running text without a restated statement or an end mark.

[1] Simon S. Du, Kangcheng Hou, Barnabás Póczos, Ruslan Salakhutdinov, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In NeurIPS, 2019 (cited in the paper).

[2] Dexiong Chen, Laurent Jacob, and Julien Mairal. Convolutional kernel networks for graph-structured data. In ICML, 2020 (cited in the paper).

[3] Nils M. Kriege. Weisfeiler and Leman go walking: Random walk kernels revisited. In NeurIPS, 2022.

[4] Marion Neumann, Roman Garnett, Christian Bauckhage, and Kristian Kersting. Propagation kernels: Efficient graph kernels from propagated information. Machine Learning, 102(2):209-245, 2016.

[5] Mahalakshmi Sabanayagam, Pascal Esser, and Debarghya Ghoshdastidar. Analysis of convolutions, non-linearity and depth in graph neural networks using neural tangent kernel. Transactions on Machine Learning Research, 2023.

[6] Shuhao Tang, Hao Tian, Xiaofeng Cao, and Wei Ye. Deep hierarchical graph alignment kernels. In IJCAI, 2024.

[7] Xinya Qin, Lu Bai, Lixin Cui, Ming Li, Ziyu Lyu, Hangyuan Du, and Edwin Hancock. DHTAGK: Deep hierarchical transitive-aligned graph kernels for graph classification. In IJCAI, 2025.

22 comments
AuthorsOpenReview ↗

Response to Reviewer 5t3v: Theoretical Clarifications and Expanded Benchmark Evaluation(W1/Q1)

The revision addresses three main concerns:

  • Real-data evidence: 31 shallow numerical near-collisions across six datasets, plus a controlled COX2 replacement testing positive-order Memory.
  • Predictive comparisons: independently tuned nested evaluation on all ten TU datasets and shared-protocol reruns on the three large molecular datasets.
  • Reproducibility and theory: method-specific search procedures, baseline sources/adaptations, machine-readable table exports and available records, and explicit proof blocks.

W1 / Q1 — Representation-level evidence on real datasets

Reviewer W1

The experiments do not support the motivation. The collisions exist only on constructed regular graphs, the paper's own MUTAG analysis finds no real instance, and under fold-contained selection the full kernel does not beat its dynamic component, its zero-order control, or a reweighted self-loop.

Reviewer Q1

The abstract (lines 011 to 014) and the Introduction (lines 038 to 044) motivate the work with MUTAG graphs 117 and 119, but Appendix E.1 reports that Dynamic-JK separates all 31 opposite-label matched pairs, which "are not instances of the constructed GNTK collision" (lines 1660 to 1664), and the remark after Corollary 11 says the task result does not identify a bottleneck in MUTAG, AMES, or another natural dataset (lines 769 to 771). On the 15 held-out pairs, Full and Dynamic-JK each rank 11 correctly and Full selects its dynamic endpoint in 7 of 10 outer fits (lines 1666 to 1671). On which benchmark does the studied GNTK collide on a non-isomorphic pair that memory separates, and how often?

Response

At depth L=1L=1, the screen finds 31 qualifying pairs across six datasets. With degree-feature weight 1 and nodewise ℓ2\ell_2 normalization, each pair has opposite labels, verified attribute-preserving non-isomorphism, squared normalized Dynamic-JK and zero-order Memory distances at most 10−1210^{-12}, and cumulative Memory distance through order 3 greater than 10−810^{-8}.

DatasetAll opposite-label pairsPairs satisfying all three conditions
MUTAG7,8752
PTC_MR29,1842
BZR27,4345
COX237,23019
PTC_FM29,4582
PTC_FR27,8301

The denominator includes all opposite-label pairs; the remaining four datasets have no qualifying pair. These 31 pairs differ from the submission's 31 matched MUTAG pairs. Screening uses inputs and kernel distances, not predictions; labels identify the opposite-label subset. The zero-order condition isolates distinctions supplied by propagation-dependent interactions.

These are finite-depth numerical near-collisions, not all-depth mathematical collisions. At depths 3 and 6, no pair satisfies the same criteria at degree-feature weight 1. Appendix G.1 and the evidence files give graph indices, distances, and the full depth/threshold analysis. Prediction is tested separately in Q3.

Changes in the revised PDF. Section 5.4, p. 10, lines 501–515; Appendix G.1, p. 43, lines 2270–2298, and the separately identified prediction cases in Appendix G.2, pp. 43–45.

AuthorsOpenReview ↗

Response to Reviewer 5t3v: Theoretical Clarifications and Expanded Benchmark Evaluation(Q2)

Q2 — Applicability beyond the constructed graph families

Reviewer Q2

Theorems 1 and 9 and Proposition 4 require regular graphs, equitable attribute partitions, one-hot inputs, and a unit or integer self-loop weight, while the benchmarks use irregular graphs with a degree channel and nodewise ℓ2 normalization (lines 383 to 384). Proposition 12 shows that any other self-loop weight separates the constructed pair, Appendix A.2 covers only integer weights (lines 791 to 792), and the depth-attenuation result is proved only for the linear GNTK (lines 270 to 273). Does a collision family exist for a real-valued self-loop weight, a GIN-style (1 + ε) center term, or the GNTK of Du et al. [1]?

Response

Exact collisions extend to arbitrary nonnegative real self-loop weights under normalized propagation, including independent center channels. This construction does not cover GIN-style unnormalized sums; the revised proofs state that boundary explicitly.

Applicability of Memory. Regularity, equitable partitions, and one-hot attributes are assumptions of the collision witnesses, not of the Memory kernel. Memory is a linear kernel on a nonnegatively weighted stack of MpM_p, so it applies to irregular graphs and real-valued attributes, including the degree-augmented, nodewise-normalized inputs used in our experiments. Positive branch self-kernels make diagonal normalization well-defined; positive-weight fusion preserves separation in either normalized branch. Proposition R1 also gives an attributed 1-WL upper bound under the stated shared input transformations.

Real-valued self-loops and independent center weights. For any fixed c≥0c\geq0, take G=C2mG=C_{2m} and H=Km,mH=K_{m,m}, m≥3m\geq3, with the same nonzero attribute xx at all 2m2m nodes and no degree augmentation. With

$ P_c=D_c^{-1/2}(A+cI)D_c^{-1/2}, $

where DcD_c contains the row sums of A+cIA+cI, regularity gives Pc1=1P_c\mathbf{1}=\mathbf{1}. Thus the independently parameterized recurrence

$ H^{\ell+1} =\sigma!\left(H^\ell W_c^\ell+P_cH^\ell W_n^\ell\right) $

keeps every node in both graphs at the same state at every layer. Equal graph sizes give identical sum/mean outputs for every shared parameter setting, identical tangent features wherever differentiable, and identical corresponding GNTK limits whenever they exist. Attributed 1-WL separates the graphs in one round because their degrees are 22 and mm.

The argument also applies to Du et al.'s mean-aggregation variant. It does not transfer to GIN-style unnormalized sums or Du et al.'s sum variant, which expose the degree difference. Memory also collides on this pair, with Mp=xx⊤M_p=xx^\top; the construction identifies a limitation of normalized aggregation, not a Memory advantage.

A one-layer margin advantage when the center channel already separates. On the original family, use binary one-hot attributes, P=(A+I)/4P=(A+I)/4, and the bias-free, one-hidden-layer comparator

$ z_v=\frac{\sqrt{\alpha},u^\top x_v+w^\top(PX)_v}{\sqrt{1+\alpha}}, \qquad \alpha>0, $

with independent standard Gaussian projections, 2\sqrt{2}-ReLU, mean pooling, and both projections and the linear output trained under standard NTK scaling. For the diagonally normalized squared distance DK=2−2Kˉ(G,H)D_K=2-2\bar{K}(G,H), the analytic bound holds uniformly over α>0\alpha>0:

$ D_{\mathrm{center}}\leq\frac{2(\pi-137/60)}{2\pi+1}<0.236, \qquad D_{\mathrm{Memory}}=\frac{4}{13}, \qquad D_{\mathrm{Full}}=\frac{16}{65}>0.236. $

Here Memory stacks M0,M1M_0,M_1 with equal weights; Full fuses it with the colliding submitted dynamic branch at depth one and η=4/5\eta=4/5. For two oppositely labeled unit feature vectors, the maximum geometric margin is DK/2\sqrt{D_K}/2. Full therefore has a larger two-point margin than this specified one-layer center-aware comparator, even though the comparator distinguishes the graphs. Appendix A.13 gives the pooling calculation and bound. The depth-attenuation result remains restricted to the linear GNTK.

Changes in the revised PDF. Section 3, p. 6, lines 270–288; Propositions R1–R3, pp. 26–28, lines 1355–1511. The fixed-memory feature-map proof is Appendix A.3, p. 17.

AuthorsOpenReview ↗

Response to Reviewer 5t3v: Theoretical Clarifications and Expanded Benchmark Evaluation(W1/Q3)

W1 / Q3 — What positive-order Memory contributes beyond M0

Reviewer Q3

In Table 8, Self-loop weight 2 is above Full on all four datasets (MUTAG 88.30 vs 86.17), and Dynamic + zero order, whose memory keeps only label and degree co-occurrence counts (lines 841 to 842), is equal to or above Full on all four. Five of the ten TU configurations use P = 1 with γ = 0.1 (Table 3), which gives the first-order interaction a weight of 0.1, and Table 4 has no Dynamic + zero order row. How much of the Table 4 gain comes from attribute-structure interactions rather than from the zero-order term, and why is a separate memory branch preferable to tuning the self-loop weight?

Response

Positive-order Memory improves the selected COX2 model in the controlled replacement test. The separate independently tuned comparison evaluates zero-order Memory and self-loop alternatives.

P=1P=1 includes M1M_1: γ=0.1\gamma=0.1 weights the unnormalized Memory kernel, not its accuracy contribution. Branch normalization and the fitted classifier also matter, motivating a controlled replacement.

The diagnostic uses three repetitions of five-fold outer CV with three-fold inner selection, dynamic depth 1, degree-feature weight 1, and Memory through order 3. Within each outer-training set, we select Full, replace Memory by M0M_0, and refit while holding its backbone, fusion weight, and classifier settings fixed.

Controlled replacement on COX2:

Memory used in the otherwise matched modelAccuracy (%)
Cumulative Memory through order 382.30 ± 0.86
Replaced by zero-order Memory M080.95 ± 0.56

The mean difference is 1.35 percentage points, positive in each of the three seed-level comparisons. Retaining M0M_0 tests positive-order information under the selected Full configuration.

Self-loop tuning changes recursive propagation; Memory retains explicit input interactions. To test their relative performance, Table 3 independently tunes Dynamic+M0M_0 and self-loop controls across ten datasets. That comparison is separate from the fixed-configuration replacement.

Changes in the revised PDF. Section 5.3, p. 9, lines 469–479; independently tuned controls in Table 3, p. 10, lines 487–498; frozen-component case scores at solver tolerance 10−510^{-5} in Table 9, p. 44, lines 2367–2375.

Reviewer_7rWpOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies Graph Neural Tangent Kernels (GNTKs) with self-looped, symmetrically normalized GCN propagation and mean readout, and shows that even in the infinite width limit they can lose interactions between node attributes and graph structure. The authors construct families of attributed graph pairs (Thm 1, Prop 4, Thm 5) that the GNTK cannot distinguish at any depth, even when the pooled outputs of all layers are combined. On a balanced task built from these pairs any classifier using the GNTK is at chance (Cor 2). Real data enters as motivation: MUTAG graphs 117 and 119 have the same atom counts and degree histogram but opposite labels.

As a fix they propose FM-GNTK, which adds to a multi-depth GNTK a fixed memory kernel built from the attribute structure moments Mp(G)=X⊤PpX/nM_p(G) = X^\top P^p X / n. The memory separates the constructed pairs, and fusing the two normalized branches with positive weights keeps every distinction made by either branch. Experiments on ten TU and three large molecular datasets show small gains in the main tables, which the authors themselves describe as dependent on the dataset and the comparison setting.

Critical strengths
  1. The paper is well written and addresses a real question, namely which interactions between attributes and structure a GNTK can see. The math is clean and correct. The collisions in Thm 1, Prop 4 and Thm 5 are explicit symmetry arguments, and the exact values, e.g. ∥Mp(G+)−Mp(G−)∥F2=4−p\|M_p(G^+)-M_p(G^-)\|_F^2 = 4^{-p} for odd p, check out.

  2. The fix is simple and provably separates the constructed task, and the paper is transparent about where its results stop. The authors show that a different self-loop weight already breaks the first family (Prop 12, lines 775-792), and that the MUTAG pairs are not instances of the collision (lines 1660-1663). They also report a nested CV audit (Tables 7 and 8) that weakens their own headline numbers.

Critical weaknesses
  1. The expressivity result is narrow and is not placed relative to WL. All witness pairs are labeled regular graphs, and all of them are separated by 1-WL with the node labels as initial colors (at rounds 1, 2 and 3 for the three pairs). So the collision is a property of an aggregation that is weaker than 1-WL on these inputs, coming from the shared weight for a node and its neighbors. A different self-loop weight already separates the first family (Prop 12), and line 629 says the construction does not extend to center preserving architectures. The paper never states this relation to 1-WL. The real data also does not show the failure, since Dynamic-JK separates all 31 matched MUTAG pairs and they "are not instances of the constructed GNTK collision" (lines 1660-1663).

  2. The evaluation does not support a predictive benefit. In the authors' own nested CV (Table 8, line 1621), FM-GNTK has a mean of 79.84 over the four datasets, below Dynamic-JK (80.09) and the plain self-loop weight 2 control (80.63). The Full row of Table 4 is 2.0 to 4.3 points above the Full row of Table 8 on the same datasets, which suggests optimism from tuning on the same graphs. The GNTK row in Table 1 (line 414) does not match Du et al. (2019), e.g. 58.1 vs 67.9 on PTC, and App. C.1 (lines 1277-1281) says the inherited baseline numbers were not checked for provenance. On AMES the gain over Dynamic-JK is +0.21 AUROC with an interval that includes zero.

Questions for authors

Clarifications that could change my assessment:

  1. Is there any GNTK collision on a pair that 1-WL with node labels separates, once the center is kept with its own weight? Otherwise the result is about the normalization choice rather than about GNTKs in general.

  2. The memory MpM_p is a walk statistic between attribute classes. Is it bounded by 1-WL with node labels? If so, please say it, since then FM-GNTK also stays within 1-WL.

  3. Please rerun GNTK under your own protocol for Table 1, or explain why the GNTK row differs from Du et al. (2019).

  4. Can you report the main comparison of Table 1 under the nested protocol of Table 8 for all methods, so the headline numbers are not tuned on the same graphs?

Suggestions for future work (not part of my assessment):

  1. A real dataset where the collision actually occurs would make the motivation much stronger.
16 comments
AuthorsOpenReview ↗

Response to Reviewer 7rWp: Architectural Analysis and Shared-Protocol Comparisons (W1/Q1)

The revision makes three changes:

  • Theory: an attributed 1-WL upper bound, an independent-center collision under normalized propagation, and a uniform one-layer margin advantage on the original family.
  • Evaluation: shared-protocol nested comparisons on all ten TU datasets replace inherited baseline entries. Sixteen baselines and independently tuned controls are reported, with Full's expanded search, kernel averaging, and threshold selection disclosed.
  • Real graphs: numerical screening identifies shallow near-collisions separated by positive-order Memory, with graph indices, distances, and depth/threshold checks supplied in the revision.

W1/Q1 — Independent center weights and the scope of the collision results

Reviewer W1

The expressivity result is narrow and is not placed relative to WL. All witness pairs are labeled regular graphs, and all of them are separated by 1-WL with the node labels as initial colors (at rounds 1, 2 and 3 for the three pairs). So the collision is a property of an aggregation that is weaker than 1-WL on these inputs, coming from the shared weight for a node and its neighbors. A different self-loop weight already separates the first family (Prop 12), and line 629 says the construction does not extend to center preserving architectures. The paper never states this relation to 1-WL. The real data also does not show the failure, since Dynamic-JK separates all 31 matched MUTAG pairs and they "are not instances of the constructed GNTK collision" (lines 1660-1663).

Reviewer Q1

Is there any GNTK collision on a pair that 1-WL with node labels separates, once the center is kept with its own weight? Otherwise the result is about the normalization choice rather than about GNTKs in general.

Response

Yes: independently weighted centers still permit an all-depth collision under normalized propagation. Memory also collides on that pair; the separate margin comparison below establishes a Memory advantage on the original family.

Collision. Give Gm=C2mG_m=C_{2m} and Hm=Km,mH_m=K_{m,m}, m≥3m\geq3, identical constant nonzero attributes xx, without degree augmentation. Their equal sizes are 2m2m; degrees 22 versus mm let 1-WL separate them in one round. Use

$ H^{\ell+1}=\sigma\left(H^\ell W_c^\ell+P H^\ell W_n^\ell\right), \qquad P=D^{-1/2}(A+I)D^{-1/2}, $

with independent center/propagation parameters and DD containing row sums of A+IA+I. Since P1=1P\mathbf{1}=\mathbf{1}, induction gives identical states and sum/mean outputs at every depth and shared parameter setting, including pooled-layer combinations. Tangent features coincide wherever differentiable, as do existing GNTK limits. Unnormalized sums expose the degrees. Memory gives Mp=xx⊤M_p=xx^\top on both graphs: this is not a Memory advantage.

One-layer margin comparison. On the original family Gm±G_m^\pm in Theorem 1, the finite-width GCN collision persists in the GNTK limit, while Memory restores separation. An independent center also separates this family. For the bias-free, one-hidden-layer comparator

$ z_v=\frac{\sqrt{\alpha},u^\top x_v+w^\top(PX)_v}{\sqrt{1+\alpha}},\qquad \alpha>0, $

use independent standard Gaussian u,wu,w, 2\sqrt{2}-ReLU, mean pooling, and trained projections and linear output under standard NTK scaling. With binary one-hot inputs, P=(A+I)/4P=(A+I)/4, and DK=2−2Kˉ(Gm+,Gm−)D_K=2-2\bar{K}(G_m^+,G_m^-), R3 proves

$ D_{\mathrm{center}}\leq B:=\frac{2(\pi-137/60)}{2\pi+1}<0.236, \qquad D_{\mathrm{mem}}=\frac{4}{13}, $

uniformly over α>0\alpha>0. Equally weighted M0,M1M_0,M_1, fused with the colliding submitted backbone at depth one, memory order one, and η=4/5\eta=4/5, give DFull=16/65>BD_{\mathrm{Full}}=16/65>B. For oppositely labeled unit feature vectors, the maximum geometric margin is DK/2\sqrt{D_K}/2, so this configuration has a strictly larger normalized two-point margin than the specified one-layer comparator. R3 supplies the pooled-NTK and series derivation.

Theorem 5 explicitly states separation at depth four; the MUTAG examples motivate attribute–topology relationships. The attributed 1-WL bound is addressed next.

Changes in the revised PDF. Section 3, p. 6, lines 270–288; Propositions R2–R3 and proofs, pp. 26–28, lines 1403–1511. The depth-four statement remains in Theorem 5 (p. 5).

AuthorsOpenReview ↗

Response to Reviewer 7rWp: Architectural Analysis and Shared-Protocol Comparisons(Q2&Q3)

Q2 — The attributed 1-WL upper bound

Reviewer Q2

Is it bounded by 1-WL with node labels? If so, please say it, since then FM-GNTK also stays within 1-WL.

Response

Yes. Proposition R1 proves that Memory and FM-GNTK stay within attributed 1-WL, including irregular graphs, shared degree augmentation, and nodewise normalization.

Stable 1-WL classes have matching counts nin_i, attribute matrix FF, neighbor counts BijB_{ij}, and degrees di=∑jBijd_i=\sum_j B_{ij}. For shared self-loop weight c>0c>0, their common normalized quotient is

$ Q_{ij}=\frac{B_{ij}+c,\mathbf{1}_{{i=j}}}{\sqrt{(d_i+c)(d_j+c)}}. $

With common graph size nn, every integer p≥0p\geq0 satisfies

$ M_p(G)=F^\top\operatorname{diag}(n_i/n)Q^pF=M_p(H). $

The dynamic output functions also agree. Tangent features coincide wherever differentiable; existing GNTK limits, well-defined diagonal normalization, and fixed shared fusion preserve equality. R1 gives the full matrix proof. Extra identifiers or positional encodings are excluded: our witnesses recover distinctions within this upper bound.

Changes in the revised PDF. Section 3, p. 6, lines 270–275; Proposition R1 and proof, p. 26, lines 1355–1401.

Q3 — The GNTK source discrepancy and a shared-protocol rerun

Reviewer Q3

Please rerun GNTK under your own protocol for Table 1, or explain why the GNTK row differs from Du et al. (2019).

Response

We reran GNTK under a shared nested protocol. The inherited 58.1±1.758.1\pm1.7, from our benchmark summary, is withdrawn as evidence of an advantage over the published GNTK; Du et al. (2019), Table 1 reports 67.9±6.967.9\pm6.9.

The accelerated implementation is numerically checked against the authors' release. Both methods use the same 344 PTC_MR graphs, node-label inputs and saved splits, without edge labels or Nyström: three repetitions of 10-fold outer CV, three-fold inner CV, independently selected from 336 kernel configurations and seven shared SVM CC values. GNTK varies aggregation, depth, MLP depth, JK, and normalization; selection uses outer-training data only.

MethodAccuracy (%)
GNTK, checked against the official implementation63.94 ± 1.55
FM-GNTK65.15 ± 1.95

SDs use the three seed-level CV means; the mean difference is 1.211.21 percentage points.

For both methods, a configuration–CC combination is eligible only if all three inner fits converge within 10810^8 iterations. Selected outer refits all converge within the shared 10910^9 cap. At inner cap 10710^7, GNTK gives 64.23±1.3564.23\pm1.35 (Appendix F.3).

Our graph version and protocol differ from Du et al.’s: this is a shared-protocol comparison, not a reproduction.

Changes in the revised PDF. Appendix F.3, p. 40, lines 2136–2149; the distinct five-fold headline comparison is Table 1, p. 9.

AuthorsOpenReview ↗

Response to Reviewer 7rWp: Architectural Analysis and Shared-Protocol Comparisons (W2/Q4)

W2/Q4 — Nested-CV comparisons across all ten TU datasets

Reviewer W2

The evaluation does not support a predictive benefit. In the authors' own nested CV (Table 8, line 1621), FM-GNTK has a mean of 79.84 over the four datasets, below Dynamic-JK (80.09) and the plain self-loop weight 2 control (80.63). The Full row of Table 4 is 2.0 to 4.3 points above the Full row of Table 8 on the same datasets, which suggests optimism from tuning on the same graphs. The GNTK row in Table 1 (line 414) does not match Du et al. (2019), e.g. 58.1 vs 67.9 on PTC, and App. C.1 (lines 1277-1281) says the inherited baseline numbers were not checked for provenance. On AMES the gain over Dynamic-JK is +0.21 AUROC with an interval that includes zero.

Reviewer Q4

Can you report the main comparison of Table 1 under the nested protocol of Table 8 for all methods, so the headline numbers are not tuned on the same graphs?

Response

Yes. The revised headline comparison extends independently tuned nested evaluation from four to all ten TU datasets, with 16 rerun baselines: SP, WL subtree, GNTK, WWL, GAWL, ASP, FWL, MMD-GK, GraphQNTK, GCKN, NCW, Propagation kernels, TWWL, SkipNTK, DHGAK, and DHTAGK.

Protocol. Methods share files and saved splits: three repetitions of stratified five-fold outer CV, with method-specific three-fold inner selection within outer training. Learned representations and preprocessing are training-fold-contained; no edge labels are used. Accuracy (%) is mean ± sample SD across three repetition-level means, each averaging five outer folds.

Full's expanded search uses two inner-CV repetitions to select one kernel or an equal-weight average of three or five, classifier settings, and a binary decision threshold. All choices stay within outer-training data; Appendix F specifies each method's search.

Results. The last column selects the highest-mean baseline among the 16.

DatasetFM-GNTKGNTKHighest-mean baseline
MUTAG89.76 ± 0.0385.83 ± 1.10WWL: 89.17 ± 0.82
PTC_MR64.85 ± 1.3763.85 ± 2.20WWL: 65.30 ± 1.17
BZR88.85 ± 1.4087.82 ± 0.14ASP: 88.72 ± 1.22
COX282.95 ± 0.4681.45 ± 1.57SkipNTK: 82.51 ± 1.60
PROTEINS76.07 ± 0.6874.66 ± 0.79SP: 76.04 ± 0.66
IMDB-B74.90 ± 0.9673.33 ± 0.57ASP: 75.00 ± 1.35
IMDB-M51.21 ± 0.3750.53 ± 0.94GAWL: 50.89 ± 0.34
PTC_FM66.24 ± 2.1661.33 ± 2.06WWL: 66.20 ± 2.01
PTC_FR69.24 ± 1.5067.80 ± 1.25WWL: 68.47 ± 1.58
PTC_MM69.18 ± 2.7566.96 ± 3.43WWL: 69.04 ± 1.05

Full has the highest mean on eight of ten datasets and exceeds GNTK's mean on all ten. Q3's PTC_MR experiment uses ten outer folds and different search settings.

Table 3 independently tunes controls on the same ten datasets/splits. Full's mean exceeds Dynamic-JK and Dynamic + zero-order Memory on all ten, and tuned self-loops on nine; PTC_FR favors self-loops, 69.76% versus 69.24%.

Submitted Table 4 used matched configurations developed on these graphs; Table 8 already used independent nested selection. Revised Tables 1, 3, and 4 share identical Full entries. The unchanged originals remain in Revision_Evidence/historical/ ; Appendix D retains Full's lower mean than Dynamic-JK on three of four degree-selectable datasets and than fixed-self-loop/zero-order controls on all four.

AMES still does not establish a positive Full–Dynamic-JK gain: its interval includes zero (Appendix E.3). The new comparisons and controlled experiments assess predictive benefit separately.

Tables 1 and 4 give the complete comparison. Appendix F documents grids/rules and adaptations: graph-level SkipNTK, the TWWL formula port, and training-fold-contained DHGAK/DHTAGK. The package includes table exports and available protocol/split records. DGK is excluded because its original release was unavailable.

Changes in the revised PDF. Section 5.1, p. 8, lines 403–423; Tables 1–2, p. 9, and Table 3, p. 10; additional PTC results in Table 4, p. 30, lines 1567–1583. Selection and implementation details: Appendix F, pp. 38–42. Earlier control findings remain in Appendix D, p. 34, lines 1820–1827.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Updated PDF with highlighted revisions

Dear Reviewers and Area Chair,

We have uploaded the revised PDF with clearer revision highlighting. Blue headings indicate added or substantially revised sections, and blue Table/Figure labels identify updated items.

This upload changes only revision highlighting and the AI-use statement. The scientific content, numerical results, and page/line locations in our latest navigation message remain unchanged.

For the remaining discussion, we would especially appreciate your consideration of the additional experimental updates already posted in the response threads. Thank you for your time and careful evaluation.

Best regards, The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.