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

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.