Many graph neural networks work like audio equalizers. They split a node signal into "graph frequencies" and learn how much of each band to keep. Low frequencies are patterns that vary smoothly across edges; high frequencies are sharp differences between neighbors. Current filters are learned as a function of the raw frequency value $\lambda$, an eigenvalue of the graph Laplacian. That makes sense on a fixed graph. On a graph that grows and densifies over time, the same raw $\lambda$ stops meaning the same thing, because the distribution of eigenvalues shifts. A filter trained on last year's graph can quietly turn into a different filter on this year's graph. We hypothesize that it often becomes more aggressively smoothing, so node representations collapse toward a few directions. This is over-smoothing, the loss of distinct node identities, and here it arrives through the passage of time rather than through network depth.
We propose to define learned filters on the quantiles of the current graph's spectrum instead of on raw eigenvalues. The filter learns "keep the lowest 10% of frequencies, attenuate the top 30%," and that instruction is re-applied to each new snapshot through a cheap estimate of the snapshot's eigenvalue distribution. No eigendecomposition is needed, and the cost per snapshot stays the same as an ordinary polynomial filter. In two sentences: learned spectral filters drift when the graph's spectrum drifts, and that drift shows up as time-dependent representation collapse. Reparameterizing the filter in spectral-quantile coordinates, estimated in linear time, should keep it calibrated without retraining.
Core Claim
The research file frames dynamic spectral learning mainly as a re-computation problem. Eigenbases are invalidated by every edge change, as with precomputed operators like LD2. That framing is partly a straw man. Polynomial filters such as learned generalized PageRank weights in GPR-GNN or Chebyshev and Bernstein expansions never touch eigenvectors. They can be applied to any new Laplacian in time linear in the number of edges.
The real problem is subtler. Such a filter is a fixed function $g_\theta(\lambda)$, and the energy it passes on snapshot $t$ is roughly $\int g_\theta(\lambda)^2\, dF_t(\lambda)$, where $F_t$ is the cumulative eigenvalue distribution of the snapshot's normalized Laplacian. When $F_t$ changes, the effective filter changes even though $\theta$ does not.
Densification gives a concrete mechanism. For random-graph-like regions of a normalized Laplacian, the non-structural bulk of eigenvalues concentrates around 1 with width shrinking roughly like $2/\sqrt{d}$ as mean degree $d$ grows; this follows from semicircle-law scaling. A filter learned when the bulk was wide may pass a band that the bulk later abandons. Representations are then dominated by the few remaining low-frequency directions, which is exactly the rank collapse measured in Are we measuring oversmoothing in graph neural networks correctly?.
Our claim has two parts. The first is diagnostic: across real dynamic graphs, the accuracy decay of fixed learned filters over test time correlates with the Wasserstein distance between training and test spectral distributions, and with the decline of the outputs' effective rank (Erank). The second is a fix: a filter of the form $g_\theta(F_t(\lambda))$ removes most of that decay.
Relation to Prior Work
Several papers motivate the gap, and each stops at the static case. AdaSpec perturbs self-loops to break repeated eigenvalues and explicitly leaves dynamic graphs to future work. WaveGC learns wavelet scales on a fixed eigendecomposition and likewise leaves time-evolving graphs open. The Bakry-Émery Laplacian of Advection-Diffusion on Graphs controls the spectral gap through a learned node potential (Barbell mean squared error 0.87 to 0.02), but only on static graphs.
Our proposal does not change the operator. It changes the coordinate system in which the filter is expressed. That makes it compatible with any of these filters and orthogonal to them.
The closest dynamic spectral works make different choices. STSGNN learns joint space-time Bernstein filters but keeps the spatial graph fixed. SILD applies Fourier transforms along each node's temporal trajectory, not over the spatial Laplacian. SPEDGNN uses power-method singular value decompositions of event histories to keep representations well-conditioned. None of the three asks whether a learned spatial filter keeps its meaning as the spatial spectrum moves.
The measurement side comes from Are we measuring oversmoothing in graph neural networks correctly?. It shows that Dirichlet energy misses collapse in trained networks, while effective rank tracks accuracy (average Pearson correlation 0.91). We reuse its rank metrics, applied over time rather than depth. We also heed its warning that high rank alone is not sufficient, which is why rank is always paired with task accuracy.
Two results constrain the design. Temporal Graph Benchmark shows that a moving-average heuristic beats TGN on tgbn-reddit, and KEAT shows that cheap time-decay kernels fix much of the temporal blurring in attention. Any spectral method that cannot at least match these is not worth deploying, so our model includes the heuristic as an input it can fall back on.
Research Program
Spectral distribution estimate. For each snapshot we estimate the eigenvalue density of the normalized Laplacian with the kernel polynomial method. This computes Chebyshev moments $m_k = \frac{1}{N}\mathrm{tr}\, T_k(L_t)$ for $k \le K$ using a few random probe vectors (Hutchinson's trace estimator). The cost is $O(K p |\mathcal{E}_t|)$ for $p$ probes. Integrating the smoothed density gives an estimate $\hat F_t$ of the cumulative distribution.
The filter itself. We parameterize the response $h_\theta(u)$ on $u \in [0,1]$ with a Bernstein polynomial and set $g_t(\lambda) = h_\theta(\hat F_t(\lambda))$. For each snapshot, $g_t$ is projected onto Chebyshev polynomials in $\lambda$; this is a scalar computation costing $O(K^2)$. The filter is then applied by the usual recurrence:
$$ y_t = \sum_{k=0}^{K} c_k(\theta, \hat F_t)\, T_k(L_t)\, x_t , $$
where $x_t$ are node features at snapshot $t$, $T_k$ is the $k$-th Chebyshev polynomial, and $c_k$ are the projected coefficients. Gradients flow through $c_k$ to $\theta$. The estimate $\hat F_t$ is treated as a constant.
Temporal component. Filtered snapshot outputs feed a small recurrent unit (a GRU) shared across all spectral variants we compare, together with the moving-average heuristic's prediction as an extra input. That way spectral variants differ only in how the filter is expressed.
Analysis. We will characterize when quantile coordinates should fail. One case is when task-relevant structure lives at a fixed absolute frequency, for example a community gap that stays put while the bulk moves. For that case we test a hybrid that mixes raw-$\lambda$ and quantile responses with a learned gate. We also derive a simple bound linking the change in passed energy to the Wasserstein-1 distance between $F_{t}$ and $F_{t'}$, scaled by the Lipschitz constant of $h_\theta$. This is what makes the drift diagnostic predictive rather than merely descriptive.
Baselines
Naive reference points. The do-nothing reference is the non-learning Moving Average heuristic from Temporal Graph Benchmark, run with the benchmark's own code. On tgbn-reddit it is also the strongest number in the file: NDCG@10 of 0.559, against 0.315 for TGN. Beating it on tgbn-reddit means exceeding 0.559 under the official streaming protocol, across five seeds, with non-overlapping confidence intervals.
Strongest learned competitor. This is KEAT-TGN from KEAT. It reports a 6.9% NDCG@10 gain over vanilla TGN on tgbn-trade, but no absolute value is given in the file. We will rerun KEAT-TGN and TGN ourselves on tgbn-trade, tgbn-reddit and tgbn-genre, giving every method the same hyperparameter-search budget of 30 trials and the same GPU-hour cap. On Collab, Yelp and Aminer we compare against SILD. The file reports only that SILD is "about 2%" above the previous best, with no absolute value, so we rerun SILD under its released splits.
Raw-coordinate filter. The ablation that isolates our key ingredient is the identical architecture with $h_\theta$ applied to raw $\lambda$, rescaled by each snapshot's $\lambda_{\max}$ as in ChebNet. Same order $K$, same temporal unit, same tuning. A second ablation feeds the spectral moments $m_k$ to a small network that outputs raw-coordinate coefficients, which tests whether "conditioning on the spectrum" in any form suffices.
Other filter families. We include GPR-GNN-style learned PageRank weights and AdaSpec self-loop perturbation, both recomputed per snapshot, to show the effect is not specific to Bernstein filters.
Upper bound. An oracle that retrains the raw-coordinate filter on each new snapshot shows how much of the gap quantile coordinates close.
Why not just…?
Why not just retrain or fine-tune the filter on each new snapshot? If labels arrive continuously and compute is free, this will likely match or beat us. That is why it appears as an oracle upper bound and not as a competitor we expect to beat. The benchmark protocol in Temporal Graph Benchmark forbids test-time backpropagation, and that reflects real deployments where labels lag. The proposal is worthwhile only if quantile filters close most of the gap between the frozen raw filter and the oracle. If they close less than half, the idea should be dropped in favor of cheap periodic retraining.
Why not just rescale by the largest eigenvalue, as ChebNet already does? Rescaling aligns the endpoints of the spectrum but not its interior. Our mechanism concerns bulk mass moving inward under densification, which endpoint rescaling cannot see. The raw-coordinate ablation is exactly this alternative. If it shows no time-dependent rank or accuracy decay, our diagnostic claim is false.
Why not just use time-decay attention like KEAT? KEAT shows that cheap edge-recency kernels give large gains (up to 18.8% MRR on tgbl-review), and this is a real threat on link ranking. Time decay, however, reweights which edges count. It does not control what frequency band a stacked aggregator passes once the graph densifies. We expect our advantage to concentrate on node-affinity tasks with strong densification, and to be small elsewhere. We will report results stratified by measured spectral drift rather than averaged.
Why not just feed spectral statistics to a hypernetwork? This is the most plausible equal competitor, because a flexible network could in principle learn the quantile mapping itself. The moment-conditioned ablation settles it. We specifically test extrapolation, where test-time spectra fall outside the range seen in training. A fixed reparameterization should extrapolate there; a learned map from moments to coefficients may not.
Proposed Experiments
Controlled test. We first use synthetic stochastic block models whose mean degree grows over 20 snapshots while community structure stays fixed. This lets us verify the predicted pattern. The raw-coordinate filter should lose Erank and accuracy roughly in proportion to Wasserstein drift, and the quantile filter should hold flat. A variant moves the community eigenvalue gap instead of the bulk, to expose the predicted failure mode of quantile coordinates and test the gated hybrid.
Real data. We then move to tgbn-trade, tgbn-reddit and tgbn-genre, snapshotted at the benchmarks' natural update intervals and scored with NDCG@10. We also use Collab, Yelp and Aminer under SILD's temporal-shift splits.
Logged quantities. For every model and snapshot we record task score, NumRank and Erank of the outputs, and the Wasserstein-1 distance between the training and current estimated spectral distributions.
Decisive checks. There are three. First, frozen raw-coordinate filters must show a statistically significant negative correlation between spectral drift and accuracy; without it the premise fails. Second, quantile filters must flatten that slope and recover at least half of the oracle's advantage. Third, the full model must clear the Moving Average heuristic's 0.559 on tgbn-reddit and match or exceed our rerun of KEAT-TGN. Wall-clock time per snapshot will be reported against the heuristic, since inference latency is a known weakness of dynamic models.
References
- LD2: Scalable Heterophilous Graph Neural Network with Decoupled Embeddings
- Adaptive Universal Generalized PageRank Graph Neural Network
- Are we measuring oversmoothing in graph neural networks correctly?
- AdaSpec: Adaptive Spectrum for Enhanced Node Distinguishability
- A General Graph Spectral Wavelet Convolution via Chebyshev Order Decomposition
- Advection-Diffusion on Graphs: A Bakry-Emery Laplacian for Spectral Graph Neural Networks
- Designing Specialized Two-Dimensional Graph Spectral Filters for Spatial-Temporal Graph Modeling
- Spectral Invariant Learning for Dynamic Graphs under Distribution Shifts
- Well-Conditioned Spectral Transforms for Dynamic Graph Representation
- Temporal Graph Benchmark for Machine Learning on Temporal Graphs
- Kernelized Edge Attention: Addressing Semantic Attention Blurring in Temporal Graph Neural Networks