acceptodds
Under review as a conference paper at ICLR 2027

Attention Graphons: A Graph Limit Perspective on Graph Transformers

Abstract

Graph Transformers produce, for each attention head, a dense matrix of learned pairwise interactions. We ask a fundamental question: do these attention-induced graphs converge to a stable limit object as grows, or does the learned interaction pattern remain unstructured and size-dependent? We answer this using dense graph limit theory, treating each attention matrix as a finite sample from an underlying kernel — an attention graphon — and studying concentration around this limit under the cut-distance. We derive a worst-case variance bound requiring no assumptions on the graphon, and a sharper regularity-aware bound based on nonparametric estimation theory. To operationalize the theory, we propose a canonicalize-then-block-average pipeline for estimating dataset-level attention graphons, and a variance-based diagnostic for testing whether attention admits a stable continuum description. Experiments across multiple graph benchmarks show that learned attention stabilizes to dataset-specific graphon structure on several datasets, empirical cut-distance and cut-norm variance decreases with consistent with our bounds, and attention graphons transfer to larger graph sizes with error decreasing in .

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Transformers, Graphons, Attention-induced graphs

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_85a6OpenReview ↗
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

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)A_{ij}=W(\omega_i,\omega_j) for node descriptors ωi\omega_i and one graphon WW 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.


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 ∥Wn−W∥□\Vert W_n-W\Vert_{\square} of the main-text statement. For Lipschitz kernels both are of order n−1/2n^{-1/2}, so the statistic has the n−1n^{-1} 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).

Variancen=1024n=2048n=4096
cSBM9.42e-61.87e-61.13e-6
ModelNet103.27e-62.12e-69.14e-7
1/n9.77e-44.88e-42.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 n−1n^{-1} on all but REDDIT-MULTI-5K. It also stays below n−1n^{-1} 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 NN 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 nn, independently of the number of graphs mm. For completeness, we derive the bound depending on mm 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 WW be the common graphon, W^1,…,W^m\hat W_1,\ldots,\hat W_m the per-graph estimates at one size, with nodes in latent order (Assumption C.6), and Wˉ\bar W their mean. Since Wˉ\bar W is an average of the W^r\hat W_r, the triangle inequality gives 1m−1∑r=1m∥W^r−Wˉ∥□2≤4mm−1⋅1m∑r=1m∥W^r−W∥□2.\frac{1}{m-1}\sum_{r=1}^m\Vert\hat W_r-\bar W\Vert_{\square}^2 \le \frac{4m}{m-1}\cdot\frac{1}{m}\sum_{r=1}^m\Vert\hat W_r-W\Vert_{\square}^2 . 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 nn latent positions. For Lipschitz kernels, the first is of order n−1/2n^{-1/2} by Cor. C.11. The second is at most 2M(ϵn+1/n)2M(\epsilon_n+1/n), where ϵn\epsilon_n is the largest gap between the sorted latent positions and a uniform grid, of order n−1/2n^{-1/2} in probability. Each squared error is therefore of order n−1n^{-1}.

In summary, the tested statistic is of order n−1n^{-1} 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 C=1C=1 and the fastest rate, but they do not fix k=64k=64. We clarify the block size first, and then explain why our conclusions hold whatever the value of α\alpha, and for the values of CC that our estimates indicate.

The experiments do not fix k=64k=64. Sec. 4.2 sets k=min⁡(64,N)k=\min(64,N), which equals NN on graphs with at most 64 nodes and lies, at every size we evaluate, in the range [⌈N⌉,N][\lceil\sqrt N\rceil,N] of resolutions that Thm. 3.2 admits as α\alpha ranges over (0,1](0,1], as stated in l. 296–298. Fig. 26 also runs the test with the theorem's own resolution for α≥1\alpha\ge1, k=⌈n⌉k=\lceil\sqrt n\rceil, which lowers the variance only at the smallest sizes and keeps it far below the threshold.

On α\alpha, the fastest rate is the saturated one. The rate of Thm. 3.2 depends on min⁡(α,1)\min(\alpha,1), so it saturates at n−1n^{-1} for every α≥1\alpha\ge1 (Sec. 3.2), and any α<1\alpha<1 gives a higher threshold at every size. Our conclusions rest on non-rejections, so they hold whatever the value of α\alpha.

CC depends on the regularity of the kernel, and our conclusions hold for the values our estimates indicate. In the proof, CC grows with the Hölder bound MM of the kernel (Thm. C.9), and the Lipschitz constants we estimate for each dataset, between about 6 and 65 (Table 1), indicate that CC is well above 1. A larger CC 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 n−1n^{-1} at every size. The value C=1C=1 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 CC 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, Aij=W(ωi,ωj)A_{ij} = W(\omega_i, \omega_j), where ωi\omega_i is the representation of node ii entering the attention layer. The assumption is that these representations follow the same distribution at every graph size. If this distribution changed with nn, 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 nn 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.

Reviewer_YmcnOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates whether the attention score matrix of Graph Transformer converges to a stable continuous limit as the graph size increases. The paper models the symmetrized pre-softmax attention matrix of each attention head as a finite sample of an underlying graphon and proposes the concept of an attention graphon. The paper derives a general upper bound on variance in cut-distance and a faster variance convergence rate under the Hölder regularity condition in cut-norm. Practically, a graphon estimation pipeline named canonicalize-then-block-average is proposed. The paper verifies whether attention variance decreases with growing graph size on multiple real-world graph datasets and synthetic datasets, and further explores the utility of attention graphon in cross-graph-size transfer and efficient inference. Experiments show that the attention kernel in multiple datasets tends to stabilize as graph size grows.

Critical strengths

S1. The paper introduces a relatively novel perspective to investigate the problem: whether the attention of Graph Transformer admits a stable continuous limit across graph sizes. Instead of directly comparing attention matrices of different sizes, the authors leverage a graphon to map attention structures of varying graph sizes into a shared function space, enabling unified comparisons of attention patterns across different graph sizes. S2. In addition to deriving theoretical convergence results for cut-distance and cut-norm, the paper designs an attention graphon estimation pipeline consisting of degree sorting, block averaging, and cross-sample aggregation. It validates the theoretical predictions by examining how cut-norm variance changes with graph size. The appendix further examines factors including block size, canonicalization methods, multi-head attention, different model architectures, as well as bootstrap, permutation tests, and synthetic null. This demonstrates that the authors have systematically inspected potential confounding factors in the estimation procedure.

Critical weaknesses

W1. There is a mismatch between the graphon sampling assumption in theory and the generative mechanism of attention in real Graph Transformers. The variance upper bound of the paper is built on the premise that node latent variables are sampled from a fixed distribution. In contrast, attention scores in real Graph Transformers are generated by network-transformed queries and keys. These representations generally depend on the full graph structure, positional encoding, and other factors. Hence, it is not obvious that they satisfy the independent latent sampling or size-invariant kernel assumptions. The present work regards attention graphon more as a proxy model, instead of a mechanism rigorously derived from the architecture of Graph Transformers. W2. The variance bound provided by Theorem 3.2 is an asymptotic order O(p-n),with an unknown constant, where the constant depends on graphon regularity and canonicalization. However, the experiments directly set C=1,and adopt the fastest n-1 rate as the theoretical threshold without knowing the smoothness parameter α. Analyses for different choices of C and αshould be conducted.

Questions for authors

Q1. The variance bound in Theorem 3.2 involves an unknown constant that depends on graphon regularity and canonicalization. Nevertheless, the practical evaluation fixes C=1 and uses n-1 as the theoretical proxy. Could the authors report the stability of hypothesis-testing conclusions under different values of C and reasonable choices of α?

3 comments

We thank you for the positive assessment and for recognizing the fresh perspective of our work, as well as its theoretical and empirical depth.

We address each point from your review below.


W1 – Model mismatch

Thank you for this observation. You are right that queries and keys are computed by the network and depend on the full graph structure, the positional encodings and other factors. We explain below how these factors enter a kernel that the trained architecture defines and that is the same across sizes, and why the sampling of the node descriptors is the hypothesis our test checks.

The kernel follows from the architecture of the trained model. We first train the GT on the downstream task, freeze it, and only then estimate one graphon per head from the sigmoid of its symmetrized pre-softmax scores (Eq. 7). With frozen weights, the score of a pair of nodes depends only on the representations of these two nodes, and the features, the positional encodings and the graph structure all shape these representations. Hence Aij=W(ωi,ωj)A_{ij}=W(\omega_i,\omega_j), with one kernel WW per head, set by the trained weights, and node descriptors ωi\omega_i that combine features and structural role, as stated in l. 255–258. Table 5 shows that the structure enters this kernel: on SmoothW and SharpW, whose features are random-walk encodings of the topology, replacing them with noise destroys concentration. Moreover, pre-softmax scores carry no normalization over the nodes (l. 229–230), so the kernel is the same across sizes.

The sampling of the descriptors is a hypothesis, which our test checks. The architecture does not fix how the input graphs, and hence the descriptors, are distributed, so we state the sampling as a hypothesis (l. 253–254). This hypothesis is plausible when the input graphs resemble samples from a graphon (which attention matrices do, as they are dense). Each descriptor depends on the rest of the graph through aggregates such as degrees, random-walk encodings and attention-weighted averages. Since these typically concentrate as the graph grows (Chan & Airoldi, 2014; Keriven et al., 2020; Ruiz et al., 2020), each descriptor should then concentrate around a function of each node's latent variable. Whether real datasets behave this way is an empirical question which our diagnostic answers per dataset. The test can reject, and does so on REDDIT-MULTI-5K at its two largest sizes (l. 384–386), indicating that attention over the graphs in that dataset does not settle to a common graphon.

In summary, the trained weights fix one kernel per head that does not depend on graph size, and the graph structure, features and positional encodings enter through the node descriptors. Whether these descriptors behave as independent samples depends on the data, not the architecture. Concentration makes this plausible when the input graphs share a common large-scale structure, and our test checks this on each dataset.


W2 – On the choice of graphon regularity and canonicalization parameters

Thank you for raising this point. You are right that the experiments set C=1C=1 and use the fastest rate n−1n^{-1} without estimating α\alpha. We explain below why the fastest rate is the hardest setting for our conclusions, and why the values of CC that our estimates indicate do not change them.

The fastest rate is the one that saturates with the choice of α\alpha. The rate n−2min⁡(α,1)/(min⁡(α,1)+1)n^{-2\min(\alpha,1)/(\min(\alpha,1)+1)} of Thm. 3.2 saturates at n−1n^{-1} for every α≥1\alpha\ge1 and is slower for every α<1\alpha<1, which raises the threshold at every size. Taking n−1n^{-1} thus gives the smallest threshold and makes rejection easiest (l. 320–323). This is the hardest setting for our conclusions, which rest on non-rejections.

CC depends on the regularity of the kernel. In the proof, CC grows with the Hölder bound of the kernel (Thm. C.9). The Lipschitz constants we estimate for each dataset (Table 1), which range from 6 to 65, point to values of CC well above 1. So, a larger CC only raises the threshold, and our concentration conclusions hold under these estimates. On the log scale of our plots, CC shifts the threshold line without changing its slope, so it does not affect the comparison of rates, i.e., a variance that decays faster than n−1n^{-1} falls below Cn−1Cn^{-1} for large nn, whatever C>0C>0. As explained in l. 1104–1105, C=1C=1 only fixes the units of the comparison. Furthermore, the permutation test on the slope of the variance and the synthetic null of Appx. H, which you mention in S2, do not involve CC, so their evidence is independent of it.


Q1 – Robustness to the chosen parameters

Yes, and we thank you for the question. Fig. 7 gives this analysis without new runs.

Wherever the test does not reject in Fig. 7, the variance stays more than an order of magnitude below n−1n^{-1} at every size, so these non-rejections hold for every C≥0.1C\ge0.1, a range that contains the values our Lipschitz estimates indicate (see W2). Since α<1\alpha<1 only raises the threshold at a given CC, they also hold for every α>0\alpha>0. We added this analysis to Appx. E.

Thus, the non-rejections of Fig. 7 hold for every C≥0.1C\ge0.1 and every α>0\alpha>0.


References:

Chan and Airoldi. A consistent histogram estimator for exchangeable graph models. ICML, 2014.

Keriven et al. Convergence and stability of graph convolutional networks on large random graphs. NeurIPS, 2020.

Ruiz et al. Graphon neural networks and the transferability of graph neural networks. NeurIPS, 2020.

AuthorsOpenReview ↗

Request for feedback on our responses

Dear Reviewer Ymcn,

With the discussion period ending soon, we wanted to briefly follow up on our response.

Thank you again for your positive assessment of the paper and for recognizing its theoretical and empirical contributions. In particular, you asked:

“Could the authors report the stability of hypothesis-testing conclusions under different values of CC and reasonable choices of α\alpha?”

We therefore followed your guidance and analyzed this directly, while also strengthening the connection between the graphon model and trained Graph Transformer attention:

  • Robustness to CC and α\alpha: wherever the test does not reject in Fig. 7, the variance remains more than an order of magnitude below n−1n^{-1} at every size. Consequently, these non-rejections remain unchanged for every C≥0.1C \geq 0.1 and every α>0\alpha>0. We added this analysis to Appendix E.
  • Connection to the trained architecture: after training and freezing the model, the learned queries and keys determine one fixed kernel per head. Graph structure, positional encodings, and node features enter through the node representations. The stability of the descriptor distribution across graph sizes is therefore the hypothesis being tested empirically rather than something assumed to follow automatically from the architecture.
  • Additional evidence on what is learned: in the experiments added later in the discussion, we rebuilt each model at initialization using the same seed. At every dataset and size, the trained kernel is more spread than its initialization and farther from a constant, providing direct evidence that the estimated structure is a consequence of training rather than simply the estimation pipeline.
  • Further robustness checks: we also evaluated the theorem-consistent block size k=⌈n⌉k=\lceil\sqrt{n}\rceil, which gives the same test conclusions, and a spectral ordering instead of degree sorting, which gives the same decisions on all datasets.

These additions directly address the two issues you raised: the robustness of the diagnostic to CC and α\alpha, and the connection between the graphon model and the attention generated by a trained Graph Transformer.

We believe the new analysis and experiments materially strengthen the paper. We hope you find our responses and the new evidence satisfactory, and that you will consider revising your score.

Thank you again for your time and for the constructive review.

Best regards,
The Authors

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

The authors consider the attention matrix of each Graph Transformer head as a dense weighted graph. The paper investigates whether, as the number of nodes increases, these matrices converge to a dataset-specific graphon: a function summarising the strength of interactions between latent node types. The authors develop theoretical bounds, an estimation procedure, and a diagnostic test, and investigate whether the estimated graphon supports transfer to larger graphs.

Critical strengths

I really appreciated the idea of turning an abstract concept from graph limit theory into an estimator and a diagnostic tool for attention matrices. This perspective could open up useful directions for analysing the stability of learned attention across graph sizes.

Critical weaknesses
  • The analysis concerns a transformed version of attention rather than the original attention mechanism. In particular, symmetrisation removes directional information, which limits how directly the findings can be interpreted as properties of the model’s actual attention.
  • Although the paper includes sensitivity analyses, it remains difficult to distinguish how much of the observed stability comes from learned attention and how much is introduced by the sorting and averaging procedure. The diagnostic measures the variance of distances between individual kernel estimates and their mean. Low variance alone does not establish that these distances decrease or that the estimates approach a common limit. Although the authors acknowledge this limitation, it weakens the evidence supporting convergence.
  • In the transfer experiment, comparison with a model trained on large graphs does not isolate the effect of the graphon approximation. A comparison of the same small-graph-trained model on large graphs, using either its original attention or the graphon approximation, would clarify the trade-off
Questions for authors

Have you compared, for individual attention heads on real-world datasets, the predictive performance obtained using the original attention, attention reconstructed from symmetrised logits, and the graphon approximation?

4 comments

We thank you for the thoughtful review and for appreciating the paper's novelty.

We address each point from your review below.


W1 – Symmetric attention and sigmoid normalization

The reviewer is right that our analysis concerns a symmetrized version of attention and that symmetrization sets aside directional information. 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.


W2 – Stability of the estimates and evidence of convergence

Thank you for raising these concerns. We address both points (sorting/averaging and interpretation of low variance) with controls on the pipeline and with a direct measure of the distances.

Numerical evidence shows the sort-and-smooth (SAS) pipeline does not create the stability. We ran two controls that keep the SAS pipeline fixed and change only its input. First, we replaced the node features of the synthetic families by noise, so that attention has no structure to learn. In that case, the variance rises by orders of magnitude (Table 5), indicating that SAS alone cannot make unstable attention look stable. Second, random symmetric matrices give a variance that stays flat as the graphs grow (Fig. 15), so SAS is not to blame for the variance decreasing with size. Finally, in our ablation the results hold across a range of values of the block size K (Fig. 25).

The estimates move closer together as the graphs grow. We really appreciate this point, and agree that a vanishing variance alone does not establish convergence, though it is a necessary condition (but not sufficient). To address your concern, we measured the mean distance between the individual estimates and their mean. From the smallest to the largest size, this distance falls on 8 of the 9 datasets of Fig. 7 (full results in Appx. H, Table R1, revised PDF). Our other results also support this conclusion. Specifically, a permutation test shows that the decrease of the variance with size is statistically significant on several datasets (Appx. H), and the estimated kernels visibly stabilize as the graphs grow for every architecture we tested (Figs. 2, 8 and 10–13).

DatasetMean distance, smallest → largest size
MUTAG2.95e-3 → 1.38e-3
PROTEINS4.00e-2 → 3.10e-2
NCI11.54e-2 → 9.41e-3
NCI1092.95e-3 → 1.43e-3
IMDB-MULTI1.44e-2 → 4.62e-2
COLLAB4.40e-2 → 2.19e-2
REDDIT-MULTI-5K1.12e-1 → 6.71e-2
ModelNet101.27e-2 → 2.86e-3
cSBM1.59e-2 → 5.32e-3

In summary, numerical evidence shows that: (i) the stability of the estimated attention graphons, and its increase with graph size, come from the learned attention rather than sorting-and-smoothing; and (ii) the distance between each dataset's estimated graphon and the average graphon shrinks as the graphs grow on 8 of the 9 datasets.


W3 – On the transferability experiments

Your reading is understandable, since our wording suggested a comparison with a model trained on large graphs. We clarify the experiment and thank you for the proposed comparison, which we ran.

The experiment compares one model with itself. We follow the standard transferability setting (Ruiz et al., 2020, 2023). The model trained on graphs with 128, 256, 512 or 1024 nodes is evaluated, without retraining, both on the corresponding training graph and on a graph with n=1024n=1024 nodes, using attention sampled from the model's estimated attention graphon (Prop. 2.1). The gap in Fig. 4 compares the accuracy of the same model at its training size with its accuracy on the large 1024-node graph. Our wording in the submission (l. 422–423 and the caption of Fig. 4) referred instead to "a baseline trained on the large-scale dataset." The revised PDF reads "the accuracy of the same model at its training size" (caption of Fig. 4 and l. 419–426).

The graphon approximation costs little accuracy. As the reviewer proposed, we evaluated each small-graph GT on the large graphs in two ways. In the first, attention is computed as usual from the model's query and key weights. In the second, attention is sampled from the estimated attention graphon. The model, the training size and the test graphs are the same in both runs, so any difference in accuracy is due to the graphon approximation alone. On SmoothW and SharpW, the two runs give identical accuracy at every training size. The graphon approximation therefore costs no accuracy, and the gap in Fig. 4 comes entirely from the change in size.

Own / graphon attentionn=128n=256n=512
SmoothW0.941 / 0.9410.948 / 0.9480.945 / 0.945
SharpW0.800 / 0.8000.826 / 0.8260.873 / 0.873

On the eleven real datasets of Figs. 18 and 19, the two accuracies differ by at most 1.6 percentage points at every training size on seven. On the other four, the difference is larger. Among these four is REDDIT-MULTI-5K, where our convergence test indicates that attention does not settle to a common graphon so transfer is not expected there. Full results are in Appx. H, Table R2 of the revised PDF.

In summary, numerical evidence shows that where the convergence test supports a graphon limit, replacing the model's attention by its graphon approximation costs little accuracy, and the transfer gap mainly reflects the change in size.


Q1 – Per-head predictive performance

Yes, and we thank the reviewer for the suggestion. We ran this comparison at test time on the trained single-head models.

Symmetrization and the graphon approximation cost little accuracy. In each trained model, we replaced the head's original attention in two ways. In the first, attention is the softmax of the symmetrized logits, so the only change from the original attention is the symmetrization. In the second, attention is sampled from the estimated graphon. On 7 of the 8 real-world datasets of Fig. 7, test accuracy changes by at most 1.3 percentage points in the first case and 2.8 in the second. On REDDIT-MULTI-5K, where our convergence test indicates that attention does not settle to a common graphon, the drops are 24.1 and 16.9 points. Full results are in Appx. H, Table R3 of the revised PDF.

DatasetsSymmetrized logitsGraphon
The 7 others-1.3 to +1.2-2.8 to +0.8
REDDIT-MULTI-5K-24.1-16.9

The graphon approximation is also cheaper. Applying attention means multiplying the n×nn \times n attention matrix by the n×dn \times d value matrix, which costs O(n2d)O(n^2 d). Attention sampled from a graphon with KK blocks is constant on each pair of blocks, so we can first average the values within each block, mix the KK block averages, and assign the result back to the nodes. This costs O(nKd)O(nKd), which is linear in the number of nodes nn. In Table 4, this factorized product matches the dense one to numerical precision while running several times faster.

In summary, on the datasets where the convergence test supports a graphon limit, replacing a head's attention by its graphon approximation preserves predictive performance at a lower inference cost.

References:

Ataee Tarzanagh et al. Max-margin token selection in attention mechanism. NeurIPS, 2023.

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.

Ruiz et al. Graphon neural networks and the transferability of graph neural networks. NeurIPS, 2020.

Ruiz et al. Transferability properties of graph neural networks. IEEE TSP, 2023.

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.

AuthorsOpenReview ↗

Request for feedback on our responses

Dear Reviewer pT8r,

With the discussion period ending soon, we wanted to briefly follow up on our response.

We thank you again for your thoughtful review and for appreciating the novelty of the paper. In particular, you asked:

“Have you compared, for individual attention heads on real-world datasets, the predictive performance obtained using the original attention, attention reconstructed from symmetrised logits, and the graphon approximation?”

We therefore followed your guidance and ran exactly this experiment, together with the additional controls motivated by the concerns in your review:

  • Original vs. symmetrized vs. graphon attention: on 7 of the 8 real-world datasets, replacing the original attention by symmetrized attention changes accuracy by at most 1.3 percentage points, and replacing it by graphon attention by at most 2.8 points. On REDDIT-MULTI-5K, where our convergence diagnostic rejects, the corresponding drops are much larger, 24.1 and 16.9 points.
  • The same-model transfer comparison you proposed: we evaluated each small-graph-trained model on the same large graph using either its original attention or its estimated graphon attention. On SmoothW and SharpW, the two give identical accuracy at every training size. Across the 11 real datasets, the difference is at most 1.6 points at every training size on 7 datasets.
  • Do the estimates actually move closer together? Following this concern, we directly measured the mean distance between the individual graphon estimates and their dataset-level mean. From the smallest to the largest graph size, this distance decreases on 8 of the 9 datasets in Fig. 7.
  • Does sorting and averaging create the apparent stability? We kept the estimation pipeline fixed and changed only its input. Replacing structured features by noise increases the variance by orders of magnitude, while random symmetric matrices show variance that stays flat as graph size increases. These controls show that the decreasing trend is not produced by the sort-and-smooth pipeline alone.

Thus, the new experiments directly test the issues you raised: the effect of symmetrization, the faithfulness of the graphon approximation, whether the estimates move closer with graph size, whether the estimation pipeline creates the trend, and the isolated cost of replacing a model’s own attention by graphon attention.

We believe these results materially strengthen the paper and directly address the main concerns in your review. We hope you find our responses and the new evidence satisfactory, and that you will consider revising your score.

Thank you again for your time and for the constructive review.

Best regards,
The Authors

Comments on the paper

2 comments
AuthorsOpenReview ↗

General comment

We thank all the reviewers for their careful evaluations and for their suggestions, which helped us clarify important details of our paper. We uploaded a revised PDF in which all changes are highlighted in blue. During the rebuttal, we ran 4 new experiments and 2 new analyses: they add Tables R1 to R4, a corollary regarding Appx. C and a paragraph in Appx. E, and clear up the description of the transfer experiment. Below, we list each change with its location and the reviewers who asked for it, and the main points we clarified.

Experiments

  • Distance of the per-graph estimates to their mean at each size (Table R1, Appx. H; asked by pT8r)
  • Own versus graphon attention for the same small-graph model on the large graphs (Table R2, Appx. H; asked by pT8r)
  • Per-head accuracy with the original, symmetrized and graphon attention (Table R3, Appx. H; asked by pT8r)
  • Variance up to 4096 nodes on the synthetic families and ModelNet10 (Table R4, Appx. H; asked by 85a6)

Analyses

  • Bound on the tested statistic by the errors that Thm. 3.2 controls (asked by 85a6)
  • Robustness of the non-rejections to CC and α\alpha (Appx. E; asked by Ymcn, 85a6)

Claims and clarifications

  • The transfer gap compares the same model at two sizes (Fig. 4, Sec. 5.2; asked by pT8r)
  • Symmetric attention is an established model class, close to trained attention, and the sigmoid loses no information (Sec. 2.1, Table 6, Prop. 2.1; asked by pT8r, 85a6)
  • The sort-and-smooth pipeline does not create the stability (Table 5, Fig. 15; asked by pT8r)
  • Training fixes one kernel per head, and the sampling of the node descriptors is the hypothesis our test checks (Sec. 4.1; asked by Ymcn, 85a6)
  • The block size k=min⁡(64,N)k=\min(64,N) lies in the range of Thm. 3.2, and k=⌈n⌉k=\lceil\sqrt n\rceil gives the same decisions (Sec. 4.2, Fig. 26; asked by 85a6)
  • The test reaches the same decisions with a spectral ordering instead of degree sorting (Fig. 27; asked by 85a6)
  • The test needs only the upper bound of Thm. 3.2, so tightness affects its power, not its validity (Sec. 4.3; asked by 85a6)

We look forward to your feedback and hope that our responses help clarify our contributions.

Hi Reviewers,

We are now near the end of the rebuttal period. If you haven't done so yet, please review the authors' responses and post a reply addressing whether their clarifications or new results resolve your concerns. Even if your score or recommendation remains unchanged, a brief note confirming what did or didn't shift your assessment—and why—is essential for the discussion and final decision. Thank you for your time and engagement.

Best regards,

Area Chair

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.