cs.LGOct 15, 2026
SaveSpectral Limits of Polynomial Graph Filters on the Long-Range Ising Model Benchmark
Organizations: University of Zanjan.
Abstract
The Long-Range Ising Model benchmark (LRIM) guarantees long-range dependence by construction: each label is the node's spin times the spin field convolved with a power-law coupling, so any model's distance from the target is measurable. We prove that a readout whose filter is a polynomial in the adjacency, the linear core of isotropic message passing and spectral graph networks, leaves an error floor that no degree lowers, because the target varies along a level set of the spectrum on which every such filter is constant. Computed exactly, the floor and the best filter of each degree predict two spectral networks adapted from published architectures to within a tenth of a decade. A filter escapes the floor only if it weighs separately the offsets the adjacency lumps together, and must still resolve the coupling across the whole lattice. A strided filter of about fifty coefficients does both: fitted to the training labels, its test error is 52 times below the best published network's. A dilated convolutional network beats the best published result at 256 nodes, matches it at 1,024, and gives the first in-domain results at the three larger sizes, while a Fourier neural operator with its standard modes falls further behind as the lattice grows. At its standard budget the dilated network stays two to four orders of magnitude short of a larger strided filter fitted to the labels. The analysis carries over to the benchmark's second coupling.
Figures & tables
| nodes | |||||
| 256 | 1 024 | 4 096 | 16 384 | 65 536 | |
| The operator, fitted to the training labels | |||||
| The learned quadratic readout | |||||
| The larger strided filter, fitted to the training labels | – | ||||
| The fifty-coefficient strided filter, fitted to the training labels | – | – | – | ||
| The floor for a filter polynomial in the adjacency | |||||
Table 1: The benchmark on one axis, in logMSE at the harder of the benchmark’s two couplings ( Table 10 gives the other); lower is better. The operator is a kernel with the symmetries of the square, fitted to the official training labels by least squares without the coupling and scored on the test split. The learned quadratic readout has the same form, trained by gradient descent. The larger strided filter is a readout of the target’s form with 83 to 101 coefficients and offsets out to radius twelve, fitted to the training labels and scored on the test split; at 256 nodes its basis spans every symmetric kernel, so that cell is empty. The fifty-coefficient filter of Section 4 has offsets out to radius eight ( Section 4.1 ), and its row is fitted and scored the same way. The floor is the best that any filter polynomial in the adjacency can do. The dilated CNN and the FNO are the means and standard deviations of three models, trained with one fixed budget per size ( Section 5 ). The two published rows give the best published result in each cell, from any architecture; at every size it is the hierarchical recurrent network of Carotti et al. (2026) , with a gated core except at 4 096 nodes, where its GIN core leads. The eight-layer GCN is ours, trained end to end on the same data and for the same number of steps as the dilated CNN, but with a constant learning rate, no clipping of the gradient and two models per size ( Section 5 ). The last two rows are trivial references: predicting zero scores the label’s power (predicting the training mean scores at 4 096 nodes, against for zero), and a kernel of radius four fitted to the known coupling already removes most of that power at 1 024 nodes. Appendix B gives every number behind this table.
Figure 1: Why a polynomial filter leaves a floor. Both panels are the lattice’s frequency square. On the left is the target’s symbol, with the level sets of drawn over it; on the right is itself, the only quantity a filter polynomial in the adjacency can respond to. Such a filter takes one value along each curve. On this grid of modes the target, too, takes one value on every level set except , where the two marked modes carry target values of and . The weighted variance of the target along that curve is the floor of Proposition 1 . Drawn at 1 024 nodes.
| reach radius | coefficients | logMSE |
|---|---|---|
| 9 | ||
| 31 | ||
| 113 | ||
| 152 |
Table 2: The closed forms behind Section 3 and Section 4 : how far the filter has to reach, the degree ladder for polynomials in the adjacency with its floor, what each change to the strided basis is worth, where the floor comes from, and what each level of strides adds. Every part uses the known coupling, not the labels, and the spin spectrum of 2 000 training configurations. The text describes every part.
Figure 2: Fits to the known coupling, weighted by the spin spectrum of 2 000 training configurations. (a) The best filter that is a polynomial in the adjacency, against its degree, one line per lattice size; the dashed line in the same color is that size’s floor ( Proposition 1 ). At every size the fit reaches the floor at the last degree, one less than the number of distinct values of , which runs from 41 to 8 321, and at the three larger sizes it first levels off above the floor. Markers are the degrees at which the fit was computed, and the lines join them; the best fit cannot rise as the degree grows. (b) The strided filter of Section 4.1 fitted to the coupling, starting from its fine offsets and adding one level of strides at a time ( Table 2 , part e), at the two sizes where that ladder was computed, with the polynomial floor at each size dashed in the same color. The circled points are the full bases, whose top level reaches half the lattice; the gain of a level depends on the order in which levels are added. Lower is better in both panels.
Figure 3: The fifty-coefficient strided basis on the lattice of 1 024 nodes, drawn around one center node. The shaded sites inside the dashed circle are the fine offsets, which the basis groups into one kernel per class of offsets related by a symmetry of the square. Each set of markers is one level of strides: a five-by-five stencil whose step doubles from level to level, so that the farthest taps of the top level lie on the dashed square at half the side of the lattice. On the torus the opposite edges of that square are the same sites, and the taps drawn on both edges are one set. Where levels share a site, the markers are nested. The markers are the centers of the taps only: each level’s kernels are smoothed by a binomial filter that widens with the level, so the coarse levels spread their weight over a wide patch around each marked site. With the fine offsets, these levels give 49 kernels, of rank 43, which a least-squares fit weighs separately.
| dilated CNN | small dilated CNN | ||||||
|---|---|---|---|---|---|---|---|
| Size | steps | batch | epochs | width | parameters | width | parameters |
| 40 000 | 48 | 240 | 136 | 2 020 145 | 52 | 296 297 | |
| 40 000 | 48 | 240 | 116 | 1 955 529 | 44 | 282 393 | |
| 25 000 | 12 | 38 | 104 | 1 962 481 | 40 | 291 441 | |
| 25 000 | 3 | 96 | 2 005 057 | 36 | 283 177 | ||
| 15 000 | 2 | 88 | 1 964 689 | 36 | 330 121 | ||
Table 3: The step budget and batch at each size, which every network of Section 5.2 uses at the standard budget, the passes over the 8 000 training graphs that they make (steps times batch over 8 000), and the width and parameter count of the two dilated networks. Every model trains with Adam at , a cosine schedule to zero and the gradient norm clipped at , except the eight-layer GCN, which uses a constant rate and no clipping. The polynomial spectral networks have their own budget ( Section 5.2 ).
| params | ||||||
|---|---|---|---|---|---|---|
| Dilated CNN | 2.0 M | |||||
| every dilation one | 2.0 M | – | – | – | ||
| at a quarter of the learning rate | 2.0 M | – | – | – | ||
| at twice the steps | 2.0 M | – | – | – | ||
| with the target’s gate, one model | 2.0 M | – | – | – | ||
| Small dilated CNN | 0.3 M |
Table 4: Standard architectures on the official test split, in logMSE at the harder coupling, lower is better: the mean and standard deviation of three models trained at each size, with the parameter count at 1 024 nodes. The dilated network with every dilation one is the matched control of Section 6.1 ; the rows at a quarter of the learning rate and at twice the steps are the checks of Section 6.4 ; the row with the target’s gate is the single model of Section 6.5 at each size. The eight-layer GCN is the mean of two models, trained on the same data and for the same number of steps as the dilated network, but with a constant learning rate and no clipping of the gradient. The best published results are those of Carotti et al. (2026) . Table 8 gives every model.
Figure 4: Where models stand, at every lattice size; lower is better. The dilated network matches or beats the published results and stays above the larger strided filter fitted to the training labels at every size where both exist; the Fourier neural operator falls from beside it at the smallest size to above the polynomial floor from 4 096 nodes. The learned quadratic readout sits to orders of magnitude below the best published in-domain results, and the operator fitted to the training labels is marked at the bottom edge. The published transfer line gives the best published result at each size for a model trained at 256 nodes. Our eight-layer GCN had the same data and number of steps as the dilated network, with a constant learning rate, no clipping and two models per size.
| Eight rounds of propagation, | |||
|---|---|---|---|
| Gated linear filter, least squares | |||
| SIGN, mean of three models | |||
| Best polynomial of degree eight (closed form) | |||
| As many rounds as the side of the lattice, | |||
| Gated linear filter, least squares | |||
Table 5: Polynomial spectral networks on the official test split, in logMSE at the harder coupling, lower is better, with the closed forms of Table 2 as references. is the number of rounds of propagation, the highest power of the adjacency the channels reach. The gated linear filter is fitted by least squares and has no seeds; each SIGN entry is the mean of three models, whose standard deviation is below in every cell.
| Model | training | layers width | parameters | each model, test | mean | s.d. | published | |||
|---|---|---|---|---|---|---|---|---|---|---|
| GatedGCN | 16 | standard | 20 104 | 1 995 553 | ||||||
| 16 | steps | 20 104 | 1 995 553 | |||||||
| 32 | standard | 32 84 | 2 087 905 | – | – | – | ||||
| per-direction | 16 | standard | 20 80 | 1 965 121 | – | |||||
| 32 | standard | 32 64 | 2 019 585 | – | – | – | – | |||
| per-direction, strided | 16 | standard | 20 64 | 1 929 473 | – | |||||
Table 6: Graph networks under our protocol, in test logMSE at the harder coupling, lower is better. Each runs at the depth its benchmark configuration uses, with the width set for about two million parameters. The standard rows use the dilated network’s optimizer and step budget; the rows at four times the steps use half its learning rate. The indented rows are GatedGCN with a separate weight for each edge direction (per-direction), and that network with edges at one more stride in each layer, cycling through (strided). Rows at are single models. The published column is the in-domain result for the same architecture from the benchmark’s main table, not the diagonal of its transfer table.
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
| Model or bound | note | |||||
| Closed forms: the operator solved exactly, and the floors | ||||||
| Least squares on the coupling, 152 coefficients | – | – | – | – | fitted to the kernel, not the labels | |
| Least squares on the labels, symmetric kernel | the square’s symmetries | |||||
| Least squares on the labels, free kernel | coefficients | |||||
| The coupling , applied to the spins | in double precision | |||||
| Larger strided filter | – | 83 to 101 coefficients, fitted to the labels | ||||
Table 7: Every number on the benchmark at the harder coupling that we could place on one axis, in logMSE, lower better; the text above describes each block. The runs at a quarter of the learning rate and at twice the steps are in Tables 4 and 8 , and the learning-rate check in Table 9 . Entries marked are size transfers, except the entries marked , the diagonal of the published transfer table, where the model was trained and tested at that size, so the number is in-domain.
| Model | width | parameters | each model, test | mean | s.d. | validation | hours | |||
| Dilated CNN | 16 | 136 | 2 020 145 | 1.0 | ||||||
| 32 | 116 | 1 955 529 | 3.9 | |||||||
| 64 | 104 | 1 962 481 | 2.5 | |||||||
| 128 | 96 | 2 005 057 | 2.8 | |||||||
| 256 | 88 | 1 964 689 | 5.4 | |||||||
| Small dilated CNN | 16 | 52 | 296 297 | 0.3 | ||||||
Table 8: Every baseline model on the official test split, in logMSE, lower is better: the three models, their mean and sample standard deviation, the mean on the validation split, and the longest training time of the three in hours on one NVIDIA T4 (for a run split in two, the total). The rows below the operator with grid coordinates are the matched control without strides, the dilated network at twice the steps and at a quarter of the learning rate, and the operator that keeps every mode at a second size. The mode floor binds the linear part of the operator at 12 modes per axis.
| Model | learning rate | validation | against the standard rate |
|---|---|---|---|
| Dilated CNN | (standard) | – | |
| FNO | (standard) | – | |
Table 9: The learning-rate check at , one model per rate, read on the validation split. The last column is the validation logMSE at that rate minus the validation logMSE of the same seed at the standard rate; positive is worse.
| nodes | |||||
| 256 | 1 024 | 4 096 | 16 384 | 65 536 | |
| The operator, fitted to the training labels | |||||
| The larger strided filter, fitted to the training labels | – | ||||
| The fifty-coefficient strided filter, fitted to the training labels | |||||
| The floor for a filter polynomial in the adjacency | |||||
| A dilated CNN | |||||
Table 10: The benchmark at its easier coupling, exponent , in test logMSE, lower is better. Each row is defined as in Table 1 . At 256 nodes the basis of the larger strided filter spans every symmetric kernel, so that cell is empty. The dilated network is the mean and standard deviation of three models. The best published results come from the benchmark’s in-domain table.
| Experiment | What we expected | What would have counted against it | What happened |
|---|---|---|---|
| The learned quadratic readout, at all five sizes | or better with the larger strided basis at every size, or better with the free multiplier wherever it fits in memory | a size where either target is missed | met at every size; the free multiplier also fits at |
| The best polynomial filter in the adjacency, at four sizes | within 0.3 of at every size | a size outside that band | partly met: at degree 128 it holds at and and fails at and ; at degree 64 it holds at , 64 and 128 and fails at . The floor of Proposition 1, exact for the training spectrum, replaces the band |
Table 11: What we expected from each experiment on the closed forms, what would have counted against it, and what happened.
| What we expected | probability | What happened |
|---|---|---|
| The dilated CNN passes the polynomial floor at every size | 75 % | not met at , where it scores against a floor of ; met at the other sizes |
| The dilated CNN lands between and at | 70 % | met: |
| The dilated CNN beats the best published in-domain result at and | 45 % | met: against (the benchmark’s transfer table, trained and tested at ) and against ; against the stronger results published since, against and against , ahead by and (the second within the spread of seeds) |
| The dilated CNN is at least below our eight-layer baseline at , 128 and 256 | 75 % | met: by , , |
| The dilated CNN stays at least above the larger strided filter from on | 95 % | met: to above |
| The small dilated CNN is worse than the dilated CNN at by to | 60 % | not met: it is better |
Table 12: What we expected of the standard baselines, the probability we gave each expectation before the runs it concerns, and what happened on the official test split, except for the learning-rate check, which is read on validation. The outcome of the third expectation is scored against the best published results at the time of registration, and then against the stronger results of Carotti et al. (2026) published since.
| What we expected | probability | What happened |
| The same network with every dilation one, at and | ||
| The same network with every dilation one is worse than the dilated CNN by at least at | 65 % | not met: against , worse |
| The same network with every dilation one is worse than the dilated CNN by at least at | 75 % | met: against , worse |
| Its shortfall against the dilated CNN is larger at than at | 70 % | met: it is worse at and worse at |
| At it lies no more than below the reference for a filter of its reach | 65 % | met: against a reference of |
| At it passes the polynomial floor | 80 % | met: against |
Table 13: What we expected of the additional experiments, the probability we gave each expectation before the runs it concerns, and what happened on the official test split. The reference for a filter of its reach, in the first block, is the best readout of the target’s form whose filter is confined to the square the network without dilations can reach; it is a reference, not a bound on a nonlinear network.
| What we expected | probability | What happened |
| Four graph networks under the same protocol, at and | ||
| GatedGCN at lands within of its published value | 60 % | not met: against , above |
| The per-direction GatedGCN is at least better than GatedGCN at | 65 % | not met: against , better |
| The per-direction GatedGCN is at least better than GatedGCN at | 60 % | not met: against , better |
| The strided GatedGCN lies within of the dilated CNN at and at | 50 % | not met: at , against , above; at , against , above |
| GPS with RWSE is not more than better than GatedGCN at | 60 % | not met: against , better |
Table 14: What we expected of the graph networks and of the gated dilated CNN, the probability we gave each expectation before the runs it concerns, and what happened on the official test split. The per-direction GatedGCN has a separate weight for each edge direction, and the strided GatedGCN is that network with edges at one more stride in each layer, cycling through . The expectations at four times the steps were written for one model of each and are read on that model; the third block reads the means of three. The gated dilated CNN multiplies the dilated CNN’s output by the node’s spin and adds a learned constant; one model at each size.
| What we expected | probability | What happened |
| Two polynomial spectral networks, at , and | ||
| The gated linear filter lies within of the best polynomial of its degree at every size, for and for | 90 % | met: within everywhere |
| SIGN at does not beat the floor by more than at any size | 65 % | met: , , above the floor |
| SIGN at lies within of the best polynomial of degree at every size | 50 % | met: , , below it |
| SIGN at lies within of the best polynomial of degree eight at every size | 55 % | met: , , below it |
| The easier coupling, exponent , at every size | ||
Table 15: What we expected of the polynomial spectral networks and at the easier coupling, the probability we gave each expectation before the runs it concerns, and what happened on the official test split. is the number of rounds of propagation. The fifty-coefficient filter is the strided filter of Section 4.1 , fitted to the training labels at the easier coupling; the dilated CNN entries are means of three models.
More in this topic
GNN Expressivity
Graph neural network expressivity studies which graph structures and functions a model can distinguish or represent, and how its design shapes those limits.
See all 55 papers