Spectral Limits of Polynomial Graph Filters on the Long-Range Ising Model Benchmark

Amin Najafgholizadeh; Mohsen Afsharchi

cs.LGOct 15, 2026

Spectral Limits of Polynomial Graph Filters on the Long-Range Ising Model Benchmark

Authors: Amin Najafgholizadeh, Mohsen Afsharchi

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	${-}28.85$	${-}28.71$	${-}28.08$	${-}27.43$	${-}27.03$
The learned quadratic readout	${-}12.47$	${-}12.29$	${-}12.21$	${-}12.17$	${-}11.21$
The larger strided filter, fitted to the training labels	–	${-}6.75$	${-}7.41$	${-}7.60$	${-}7.58$
The fifty-coefficient strided filter, fitted to the training labels	–	${-}6.57$	${-}6.97$	–	–
The floor for a filter polynomial in the adjacency	${-}2.48$	${-}2.68$	${-}2.95$	${-}3.23$	${-}3.52$

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

+1.16

at 4 096 nodes, against

+1.22

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

\mu(k)=(\cos k_{x}+\cos k_{y})/2

drawn over it; on the right is

\mu

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

\mu=0

, where the two marked modes carry target values of

{-}1.00

and

{-}0.41

. The weighted variance of the target along that curve is the floor of Proposition 1 . Drawn at 1 024 nodes.

reach radius	coefficients	logMSE
$4$	9	${-}0.665$
$8$	31	${-}1.688$
$16$	113	${-}3.659$
$22.7$	152	${-}27.410$

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

\mu

, 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
$L=16$	40 000	48	240	136	2 020 145	52	296 297
$L=32$	40 000	48	240	116	1 955 529	44	282 393
$L=64$	25 000	12	38	104	1 962 481	40	291 441
$L=128$	25 000	3	$9.4$	96	2 005 057	36	283 177
$L=256$	15 000	2	$3.8$	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

2\times 10^{-3}

, a cosine schedule to zero and the gradient norm clipped at

1.0

, 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	$L=16$	$L=32$	$L=64$	$L=128$	$L=256$
Dilated CNN	2.0 M	${-}4.96\pm 0.11$	${-}4.86\pm 0.08$	${-}4.33\pm 0.08$	${-}3.92\pm 0.03$	${-}3.44\pm 0.05$
every dilation one	2.0 M	–	${-}4.69\pm 0.11$	–	${-}2.88\pm 0.004$	–
at a quarter of the learning rate	2.0 M	–	${-}5.16\pm 0.02$	–	${-}4.36\pm 0.21$	–
at twice the steps	2.0 M	–	–	–	${-}4.38\pm 0.05$	${-}3.99\pm 0.09$
with the target’s gate, one model	2.0 M	${-}5.02$	${-}5.09$	–	–	–
Small dilated CNN	0.3 M	${-}4.91\pm 0.04$	${-}4.92\pm 0.12$	${-}4.60\pm 0.07$	${-}4.12\pm 0.26$	${-}3.75\pm 0.17$

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

7.4

7.8

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, $K=8$
	$L=16$	$L=32$	$L=64$
Gated linear filter, least squares	${-}1.632$	${-}1.179$	${-}1.010$
SIGN, mean of three models	${-}1.691$	${-}1.211$	${-}1.044$
Best polynomial of degree eight (closed form)	${-}1.636$	${-}1.179$	${-}1.012$
As many rounds as the side of the lattice, $K=L$
Gated linear filter, least squares	${-}1.968$	${-}1.923$	${-}1.907$

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.

K

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

0.002

in every cell.

Model	$L$	training	layers $\times$ width	parameters	each model, test			mean	s.d.	published
GatedGCN	16	standard	20 $\times$ 104	1 995 553	${-}2.906$	${-}2.970$	${-}2.977$	${-}2.951$	$0.039$	${-}3.844$
	16	$4\times$ steps	20 $\times$ 104	1 995 553	${-}3.747$	${-}3.975$	${-}3.736$	${-}3.819$	$0.135$	${-}3.844$
	32	standard	32 $\times$ 84	2 087 905	${-}3.249$	–	–	${-}3.249$	–	${-}4.087$
per-direction	16	standard	20 $\times$ 80	1 965 121	${-}2.989$	${-}3.035$	${-}3.042$	${-}3.022$	$0.029$	–
	32	standard	32 $\times$ 64	2 019 585	${-}3.283$	–	–	${-}3.283$	–	–
per-direction, strided	16	standard	20 $\times$ 64	1 929 473	${-}3.620$	${-}3.372$	${-}3.376$	${-}3.456$	$0.142$	–

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

2,4,\ldots,L/2

(strided). Rows at

L=32

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	$L=16$	$L=32$	$L=64$	$L=128$	$L=256$	note
Closed forms: the operator solved exactly, and the floors
Least squares on the coupling, 152 coefficients	–	${-}27.410$	–	–	–	fitted to the kernel, not the labels
Least squares on the labels, symmetric kernel	${-}28.849$	${-}28.709$	${-}28.076$	${-}27.426$	${-}27.034$	the square’s symmetries
Least squares on the labels, free kernel	${-}28.850$	${-}28.709$	${-}28.077$	${-}27.434$	${-}27.043$	$L^{2}$ coefficients
The coupling $J$ , applied to the spins	${-}28.947$	${-}28.624$	${-}28.059$	${-}27.365$	${-}26.998$	in double precision
Larger strided filter	–	${-}6.752$	${-}7.410$	${-}7.605$	${-}7.583$	83 to 101 coefficients, fitted to the labels

Appendix

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

\dagger

are size transfers, except the entries marked

\ddagger

, the diagonal of the published transfer table, where the model was trained and tested at that size, so the number is in-domain.

Model	$L$	width	parameters	each model, test			mean	s.d.	validation	hours
Dilated CNN	16	136	2 020 145	${-}4.915$	${-}5.091$	${-}4.883$	${-}4.963$	$0.112$	${-}4.973$	1.0
	32	116	1 955 529	${-}4.777$	${-}4.886$	${-}4.928$	${-}4.864$	$0.078$	${-}4.868$	3.9
	64	104	1 962 481	${-}4.282$	${-}4.420$	${-}4.289$	${-}4.330$	$0.078$	${-}4.332$	2.5
	128	96	2 005 057	${-}3.909$	${-}3.893$	${-}3.947$	${-}3.916$	$0.028$	${-}3.918$	2.8
	256	88	1 964 689	${-}3.491$	${-}3.393$	${-}3.450$	${-}3.445$	$0.049$	${-}3.444$	5.4
Small dilated CNN	16	52	296 297	${-}4.899$	${-}4.953$	${-}4.877$	${-}4.910$	$0.039$	${-}4.917$	0.3

Appendix

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	$2\times 10^{-3}$ (standard)	${-}4.778$	–
	$10^{-3}$	${-}5.017$	${-}0.238$
	$5\times 10^{-4}$	${-}5.143$	${-}0.365$
FNO	$2\times 10^{-3}$ (standard)	${-}3.644$	–
	$10^{-3}$	${-}3.467$	$+0.177$
	$5\times 10^{-4}$	${-}2.910$	$+0.733$

Appendix

Table 9: The learning-rate check at

L=32

, 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	${-}29.26$	${-}28.74$	${-}27.78$	${-}27.47$	${-}26.97$
The larger strided filter, fitted to the training labels	–	${-}8.76$	${-}9.41$	${-}9.20$	${-}9.15$
The fifty-coefficient strided filter, fitted to the training labels	${-}8.58$	${-}8.34$	${-}8.30$	${-}8.22$	${-}8.21$
The floor for a filter polynomial in the adjacency	${-}2.53$	${-}2.79$	${-}3.07$	${-}3.35$	${-}3.65$
A dilated CNN	${-}5.36\pm 0.08$	${-}5.47\pm 0.02$	${-}5.08\pm 0.09$	${-}4.96\pm 0.06$	${-}4.43\pm 0.06$

Appendix

Table 10: The benchmark at its easier coupling, exponent

1.5

, 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	$-6.5$ or better with the larger strided basis at every size, $-11$ 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 $L=256$
The best polynomial filter in the adjacency, at four sizes	within 0.3 of $-1.9$ at every size	a size outside that band	partly met: at degree 128 it holds at $L=64$ and $L=128$ and fails at $L=16$ and $L=32$ ; at degree 64 it holds at $L=32$ , 64 and 128 and fails at $L=16$ . The floor of Proposition 1, exact for the training spectrum, replaces the band

Appendix

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 $L=256$ , where it scores ${-}3.445$ against a floor of ${-}3.518$ ; met at the other sizes
The dilated CNN lands between $-5.3$ and $-3.3$ at $L=32$	70 %	met: ${-}4.864$
The dilated CNN beats the best published in-domain result at $L=16$ and $L=32$	45 %	met: ${-}4.963$ against ${-}4.345$ (the benchmark’s transfer table, trained and tested at $L=16$ ) and ${-}4.864$ against ${-}4.134$ ; against the stronger results published since, ${-}4.963$ against ${-}4.701$ and ${-}4.864$ against ${-}4.852$ , ahead by $0.26$ and $0.01$ (the second within the spread of seeds)
The dilated CNN is at least $1.5$ below our eight-layer baseline at $L=64$ , 128 and 256	75 %	met: by $3.24$ , $2.99$ , $2.46$
The dilated CNN stays at least $1.5$ above the larger strided filter from $L=32$ on	95 %	met: $1.89$ to $4.14$ above
The small dilated CNN is worse than the dilated CNN at $L=32$ by $0.1$ to $1.2$	60 %	not met: it is $0.056$ better

Appendix

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 $L=32$ and $L=128$
The same network with every dilation one is worse than the dilated CNN by at least $0.3$ at $L=32$	65 %	not met: ${-}4.687$ against ${-}4.864$ , $0.18$ worse
The same network with every dilation one is worse than the dilated CNN by at least $0.5$ at $L=128$	75 %	met: ${-}2.881$ against ${-}3.916$ , $1.04$ worse
Its shortfall against the dilated CNN is larger at $L=128$ than at $L=32$	70 %	met: it is $1.04$ worse at $L=128$ and $0.18$ worse at $L=32$
At $L=128$ it lies no more than $0.5$ below the reference for a filter of its reach	65 %	met: ${-}2.881$ against a reference of ${-}2.955$
At $L=32$ it passes the polynomial floor	80 %	met: ${-}4.687$ against ${-}2.678$

Appendix

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 $L=16$ and $L=32$
GatedGCN at $L=16$ lands within $0.5$ of its published value	60 %	not met: ${-}2.951$ against ${-}3.844$ , $0.89$ above
The per-direction GatedGCN is at least $0.3$ better than GatedGCN at $L=16$	65 %	not met: ${-}3.022$ against ${-}2.951$ , $0.07$ better
The per-direction GatedGCN is at least $0.3$ better than GatedGCN at $L=32$	60 %	not met: ${-}3.283$ against ${-}3.249$ , $0.03$ better
The strided GatedGCN lies within $0.3$ of the dilated CNN at $L=16$ and at $L=32$	50 %	not met: at $L=16$ , ${-}3.456$ against ${-}4.963$ , $1.51$ above; at $L=32$ , ${-}3.363$ against ${-}4.864$ , $1.50$ above
GPS with RWSE is not more than $0.3$ better than GatedGCN at $L=16$	60 %	not met: ${-}3.451$ against ${-}2.951$ , $0.50$ better

Appendix

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

2,4,\ldots,L/2

. 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 $L=16$ , $32$ and $64$
The gated linear filter lies within $0.05$ of the best polynomial of its degree at every size, for $K=8$ and for $K=L$	90 %	met: within $0.005$ everywhere
SIGN at $K=L$ does not beat the floor by more than $0.1$ at any size	65 %	met: $0.42$ , $0.70$ , $1.00$ above the floor
SIGN at $K=L$ lies within $0.3$ of the best polynomial of degree $L$ at every size	50 %	met: $0.08$ , $0.06$ , $0.05$ below it
SIGN at $K=8$ lies within $0.3$ of the best polynomial of degree eight at every size	55 %	met: $0.06$ , $0.03$ , $0.03$ below it
The easier coupling, exponent $1.5$ , at every size

Appendix

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.

K

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.

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

Oct 2, 2026

Get a GRIP, this will be a long TRIP: A Quantifiable Long-Range Framework for Verifying Over-squashing

Empirical claims about the connection between over-squashing and long-range interactions in GNNs, can only be trusted if the benchmarks used to validate them genuinely require long-range interactions. The de-facto standard, the Long Range Graph Benchmark, has been repeatedly shown to be saturated by tuned short-range models, with existing synthetic alternatives being tied to specific topologies. As such, there is a lack of principled certificate of long-rangedness on arbitrary graphs. This state reflects the absence of a precise characterization of long-ranged benchmarks. We address this fundamental gap by introducing four verifiable axioms: Predictability, Tightness, Strictly

k

-Range, and Topology-Invariance, that any task claiming to test

k

-hop interactions must satisfy. We formally prove that violating any one of them admits failure modes that undermine conclusions drawn from the task. Based on these axioms, we introduce TRIP (Truly Ranged Interactions Problem) and its generalisation GRIP (Generally Ranged Interactions Problem), constructive procedures that turn any graph into a provably long-ranged task by drawing features from stable distributions. Moreover, by construction, GRIP admits a closed-form, per-range Maximum-Likelihood oracle that yields the first a priori per-range lower bound on test error available on any benchmark. Using our framework, we: (i) audit 4 common long-range benchmarks and identify their failures modes with respect to our axioms; (ii) on TRIP-instantiated topologies, we find a popular notion of curvature is uncorrelated with GNN performance, supporting topological-vs-computational bottleneck distinction; and (iii) we show that a novel benchmark's over-squashing measures factors beyond pure long-rangedness. Code to use the framework and reproduce experiments is released https://github.com/ferranhernandezc/graph-grip.

Ferran Hernandez Caralt, Simon Heilig, Adrián Bazaga +3

Department of Computer Science and Technology, University of Cambridge, UK · Faculty of Computer Science, Ruhr University Bochum, Germany · Microsoft, London, UK +1

Long-Range Graph Learning Over-Squashing in GNNs Graph Neural Networks Graph Representation Learning GNN Expressivity

Ask PDF

Sep 27, 2026

Reachability is not enough: Diagnosing long-range behavior in GNNs

Graph neural networks (GNNs) are often called long-range because their architecture can connect distant nodes, but this does not show whether they use distant information correctly. We introduce a framework that measures how strongly inputs at each graph distance affect predictions and separates limitations due to architecture, finite approximation, training, and numerical execution. Our analysis shows that local message-passing can spread influence slowly, so a finite implementation may rely mainly on nearby inputs even when the ideal computation uses the whole graph. We also explain why mathematically equivalent filters can differ in how easily they are learned and how reliably they run. Across controlled tasks, models with similar architectural reach use distant information very differently, while low average error can hide failures on distant interactions. Together, these results show that long-range capability depends on learning to use information at the distances required by the task and preserving that use during computation.

Filippo Maria Bianchi

UiT The Arctic University of Norway · NORCE Norwegian Research Centre

Graph Neural Networks GNN Expressivity Message Passing Neural Networks Long-Range Graph Learning

Ask PDF

Sep 24, 2026

Spectral Graph Neural Networks with Hermite Polynomials: A Comprehensive Study

We study spectral graph neural networks built from Hermite polynomials and propose HermNet, a simple model that combines a nodewise predictor with normalized Hermite propagation. Its sparse recurrence requires neither eigendecomposition nor a learned basis. We distinguish the basic model from optional coordinate calibration, response normalization and Gaussian derivative regularization. Hermite and other complete polynomial bases span the same degree-bounded filter space, but their coordinates can produce different optimization behavior under limited training budgets. We analyze this behavior through spectral signal energy, label sampling, changes in learned features and the bias--variance trade-off of regularization. Controlled synthetic experiments identify a regime in which plain HermNet outperforms matched polynomial-basis alternatives, including with a jointly trained nonlinear predictor. Curvature regularization further improves HermNet when the same functional penalty is available to every comparator. Fixed-predictor controls support the advantage under short training budgets, but longer training removes the plain-model lead. Matched real-data comparisons show accuracy deficits, and architectural and numerical studies identify further limits. Together, the analysis and experiments clarify when Hermite propagation is useful and how calibration and regularization affect its performance.

Shuang Wu

UCLA

Graph Neural Networks Spectral Graph Convolution

Ask PDF

Abstract

GNN Expressivity

Explore similar work

Get a GRIP, this will be a long TRIP: A Quantifiable Long-Range Framework for Verifying Over-squashing

Reachability is not enough: Diagnosing long-range behavior in GNNs

Spectral Graph Neural Networks with Hermite Polynomials: A Comprehensive Study