- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper tries to ask whether the attention matrices of Graph Transformers converge to a stable limit object (a graphon) as the number of nodes grows. By assuming each head’s pre-softmax scores are symmetrized, shifted by a constant c and passed through a sigmoid, they derived two variance bounds and came out a canonicalize-then-block-average estimator pads each matrix to a common size, sorts nodes by degree, block-averages, and averages across graphs. Finally, they used experiments to validate the variance decreases, estimated kernels stabilize and linear time of transerability.
Critical strengths
1.It's an interesting and novel direction to do research to give a size-agnostic description of what attention heads learn.
2.They do have an interesting observation that post-softmax attention graphs converge to the zero graphon for every model and dataset, so the choice of attention object matters and the naive choice is uninformative.
3.The authors have done many works based on different architectures, sensitivity to block size and to the canonicalization method, runtime, and an exact factorization of block-constant attention and they are transparent about negative cases.
Critical weaknesses
1.The theory part is not about attention architecture and have a strong assumption to make it close to trivial. First, the study object is symmetrized and sigmoid-transformed logits which is not the attention the model actually uses, although they have said somehow this kinds of assumption have been used in other papers, considering their theorem is also not so novel and exact bound, the whole theorem is not so good. And theorems 3.1 and 3.2 are generic graphon sampling results. They hold for any matrix drawn from a (Hölder) graphon, and no element of the Transformer (queries, keys, softmax, training) enters them.
2.The experimental evidence can not validate the teory so well. The experiments measure the dispersion of padded per-graph estimates around their mean. Theorem 3.2 bounds a different quantity (‖θ̂ − θ‖_□ on a single sample), and no result connects the two. The predicted size dependence is not clearly observed either: there are only four sizes per dataset, size is confounded with population, and the curves are flat or non-monotone on several datasets (Fig. 7). The experiments show that a scale-dependent statistic is small, not that attention concentrates at the predicted rate.
Questions for authors
1.Theorem 3.2 bounds ‖θ̂ − θ‖_□ on a single sample, while the experiments measure the dispersion of padded per-graph estimates around their mean. Can you derive a bound for the tested statistic, or measure the bounded quantity directly?
2.The theorem requires k = ⌈n^{1/(α'+1)}⌉ and depends on α and C, but the experiments fix k = 64, α = 1 and C = 1. Can you estimate α and C from the data, or report results with the theorem’s k?
3.Can you check empirically that trained attention satisfies the theory’s assumptions, namely a strictly monotone degree function and a descriptor distribution that is stable across n?
7 comments
W2 – Empirical validation
Thank you for this detailed comment. You are right that Thm. 3.2 bounds the error on a single sample, and that Fig. 7 has four sizes per dataset. We first show that the tested statistic is bounded by the quantities of Thm. 3.2, then explain how the synthetic families fix the population, and finally address the flat curves and give further evidence of a stable limit.
The tested statistic is bounded by the quantities of Thm. 3.2. By triangle inequality, the dispersion of the per-graph estimates around their mean is controlled by their distances to the common graphon. Each of these distances splits into the block-approximation error bounded in Appx. C and the deviation of the main-text statement. For Lipschitz kernels both are of order , so the statistic has the order of our threshold, as we derive in our answer to your Q1.
The synthetic families fix the population. The test is decided at each size, so four sizes give four separate checks of the bound. We agree that a denser sweep would make the trend easier to read, but on MUTAG, IMDB-MULTI, NCI1 and NCI109 the sizes span less than a factor of three (Fig. 7), which leaves little room for more. We will add the larger sizes we ran on the synthetic families and ModelNet10, whose population is fixed by construction: the variance keeps decreasing up to 4096 nodes (full results in Appx. H, Table R4, revised PDF).
| Variance | n=1024 | n=2048 | n=4096 |
|---|---|---|---|
| cSBM | 9.42e-6 | 1.87e-6 | 1.13e-6 |
| ModelNet10 | 3.27e-6 | 2.12e-6 | 9.14e-7 |
| 1/n | 9.77e-4 | 4.88e-4 | 2.44e-4 |
Flat curves are consistent with the bound. The bound caps the variance but says nothing about the shape of the curve below the cap. In Fig. 7, the variance decreases overall on seven of the nine datasets and stays below on all but REDDIT-MULTI-5K. It also stays below with four heads on all twelve datasets (Fig. 14) and for Graphormer-GD and GRIT (Figs. 16 and 17).
The test is not our only evidence of a stable limit. The estimated kernels stabilize as grows for all three architectures (Figs. 8 and 10–13), and the transfer gap shrinks with the training size on most datasets (Figs. 4, 18 and 19). It does not shrink on REDDIT-MULTI-5K, the only dataset where our test indicates that attention does not settle to a common graphon.
Q1 – Regularity-aware bound
Yes, and we thank you for this precise question. The tested statistic is bounded by the per-graph errors that Thm. 3.2 controls, so it inherits the same rate in , independently of the number of graphs . For completeness, we derive the bound depending on below in two steps, and will add the derivation to Appx. C of the revised paper.
Step 1: the variance is bounded by the average per-graph error. Under the null, let be the common graphon, the per-graph estimates at one size, with nodes in latent order (Assumption C.6), and their mean. Since is an average of the , the triangle inequality gives The empirical variance in Eq. (29) is thus at most 8 times the average squared error of the individual estimates.
Step 2: each per-graph error follows the rate of Thm. 3.2. The error of one estimate splits into the estimation error of the block averages and the discretization error from sampling latent positions. For Lipschitz kernels, the first is of order by Cor. C.11. The second is at most , where is the largest gap between the sorted latent positions and a uniform grid, of order in probability. Each squared error is therefore of order .
In summary, the tested statistic is of order in probability, the order of our threshold, and the number of graphs only enters through a constant at most 8.
Q2 – Theorem assumptions and hyperparams
Thank you for this question on the settings of our experiments. You are right that the experiments take and the fastest rate, but they do not fix . We clarify the block size first, and then explain why our conclusions hold whatever the value of , and for the values of that our estimates indicate.
The experiments do not fix . Sec. 4.2 sets , which equals on graphs with at most 64 nodes and lies, at every size we evaluate, in the range of resolutions that Thm. 3.2 admits as ranges over , as stated in l. 296–298. Fig. 26 also runs the test with the theorem's own resolution for , , which lowers the variance only at the smallest sizes and keeps it far below the threshold.
On , the fastest rate is the saturated one. The rate of Thm. 3.2 depends on , so it saturates at for every (Sec. 3.2), and any gives a higher threshold at every size. Our conclusions rest on non-rejections, so they hold whatever the value of .
depends on the regularity of the kernel, and our conclusions hold for the values our estimates indicate. In the proof, grows with the Hölder bound of the kernel (Thm. C.9), and the Lipschitz constants we estimate for each dataset, between about 6 and 65 (Table 1), indicate that is well above 1. A larger only raises the threshold, so the non-rejections hold under such an estimate, and wherever the test does not reject in Fig. 7, the variance is more than an order of magnitude below at every size. The value in the paper only fixes the units across datasets (Appx. E).
In summary, our block sizes lie in the range that Thm. 3.2 admits, and its own block size gives the same conclusions. The fastest rate is the hardest setting for these conclusions, and the values of that our estimates indicate only raise the threshold.
Q3 – Degree and descriptor assumptions
Yes, and we thank the reviewer for this question. Both assumptions are checked empirically in the paper, the first by changing the node ordering and the second by our test.
Our conclusions do not depend on the degree ordering. Strict monotonicity of the degree function is what makes sorting nodes by degree recover their latent order. To check that our results do not rely on it, we repeated the analysis with a spectral ordering based on the Fiedler vector, which does not use degrees. The test reaches the same decisions on all datasets (Fig. 27). The assumption itself is the standard identifiability condition of nonparametric graphon estimation (Bickel & Chen, 2009), under which the sort-and-smooth estimator we build on is consistent (Chan & Airoldi, 2014). It is a condition on the graphon, which Assumption C.6 formalizes for the proof (Sec. 4.2).
Our test checks that the node representations have the same distribution across sizes. In our model of attention (Sec. 4.1), each head computes the score of a pair of nodes from their representations through a fixed function, , where is the representation of node entering the attention layer. The assumption is that these representations follow the same distribution at every graph size. If this distribution changed with , the attention graphs would not concentrate around a common graphon, and the test would reject (Sec. 4.3). The test does reject on REDDIT-MULTI-5K, which shows that it detects such cases. On the other datasets, it does not reject, and the estimated kernels stabilize as grows (Figs. 2 and 8).
In summary, the test reaches the same decisions without the degree ordering, and it directly checks that the node representations have the same distribution across sizes, rejecting where this fails.
References:
Ataee Tarzanagh et al. Max-margin token selection in attention mechanism. NeurIPS, 2023.
Bickel and Chen. A nonparametric view of network models and Newman–Girvan and other modularities. PNAS, 2009.
Chan and Airoldi. A consistent histogram estimator for exchangeable graph models. ICML, 2014.
Courtois et al. Symmetric dot-product attention for efficient training of BERT language models. Findings of ACL, 2024.
Edelman et al. Inductive biases and variable creation in self-attention mechanisms. ICML, 2022.
Kitaev et al. Reformer: The efficient transformer. ICLR, 2020.
Tian et al. Scan and snap: Understanding training dynamics and token composition in 1-layer transformer. NeurIPS, 2023.
Yang et al. Partially shared query-key for lightweight language models. NeurIPS ENLSP Workshop, 2024.
We thank you for the considerate review and for appreciating the paper's novelty, theoretical observations, experimental depth and transparency regarding its limitations.
We address each point from your review below.
W1.1 – The symmetric attention model, novelty and bound tightness
Thank you for these comments. You are right that we study the sigmoid of the symmetrized pre-softmax scores. As is common in theory development, we start from a simpler model class - symmetric attention - and establish foundations there before moving to the general asymmetric case. Note however that symmetric attention is neither artificial nor far from practice for three reasons:
Symmetric attention is used in practice. Symmetric attention is an established model class (Sec. 2.1). Kitaev et al. (2020) tie query and key weights, Yang et al. (2024) and Courtois et al. (2024) train symmetric attention more efficiently at equal performance, and Edelman et al. (2022), Ataee Tarzanagh et al. (2023) and Tian et al. (2023) analyze it.
Trained attention is close to symmetric. We train the GT on the downstream task, freeze it, and only then estimate the graphon from each head's symmetrized pre-softmax scores (Eq. 7). On these trained models, attention differs from its symmetrized version by a small amount which is in fact negligible on several datasets as we show (Table 6). In the datasets we considered, the symmetric part thus carries most of what the model learns.
The sigmoid step loses no information. Graphons take values in [0,1], so we map the pre-softmax scores to this range before estimating the graphon. Among the possible normalizations, we use a sigmoid because it is invertible (Eq. 7). We can thus estimate the graphon, sample a graph from it, apply the inverse sigmoid to recover pre-softmax scores, and pass these through the softmax as usual (Prop. 2.1).
In summary, our findings describe exactly the attention of symmetric-attention models. On the datasets considered, they also describe the attention of standard trained models up to a small, measured asymmetry. Extending the framework to asymmetric attention, e.g., through directed graphons, is a natural next step that we state explicitly in Sec. 6.
We further address the two readings regarding tightness and novelty:
The test is valid without a tight bound. Thm. 3.2 is an upper bound on the variance, and the paper makes no tightness claim. The test rejects when the empirical variance exceeds a threshold taken from this bound (Sec. 4.3), so any rejection is valid whether or not the bound is tight. Tightness affects the power of the test, since a looser bound rejects less often. In practice, the bound is informative enough to reject on REDDIT-MULTI-5K at its two largest sizes (l. 384–386).
The contribution is the application to attention. The paper builds on existing sampling and estimation results for graphons, which we present as prior work (Sec. 3). To the best of our knowledge, Thm. 3.2 is the first result on the concentration of Graph Transformer attention around a graphon, and the first to use such a bound as a diagnostic for trained models. We would be glad to discuss any related work the reviewer has in mind.
In summary, Thm. 3.2 does not need to be tight for the test to be valid, its looseness only reduces power, and the test rejects where attention does not settle to a common graphon. Its novelty lies in bringing graphon concentration to the analysis of trained attention.
W1.2 – Graphon theory and the bridge to attention
The reviewer is right that Thms. 3.1 and 3.2 are graphon sampling results that hold for any matrix drawn from a graphon. This generality is by design. The theorems are the generic step of the argument, and the elements of the Transformer enter through the kernel to which the theorems are applied.
The theorems are general because the kernel of a trained head is not known in advance. Thm. 3.1, a corollary of the second sampling lemma, holds for every graphon. Thm. 3.2 trades this generality for a faster rate, on Hölder graphons and in the cut norm.
Queries, keys, softmax and training determine the kernel. For a frozen head, the score of a pair of nodes depends only on the representations of these two nodes, so Aij=W(ωi,ωj) for node descriptors ωi and one graphon W per head (Sec. 4.1). The queries and keys define this kernel through their symmetrized product, training fixes it, and the softmax attention is recovered from it by inverting the sigmoid (Prop. 2.1). Moreover, the score is bilinear in the representations and the sigmoid is smooth, so the kernel is Lipschitz in bounded descriptors, which connects the architecture to the regularity assumed in Thm. 3.2.
In summary, the Transformer determines which kernel the attention graphs approach, and the theorems quantify how fast they approach it, whichever kernel training produces.