In a temporal graph (a network whose edges are time-stamped events, such as user–item clicks or Wikipedia edits), much of what distinguishes one node from another is when it acts. Some users post in daily bursts. Some accounts fire at machine-regular intervals. Some items are touched once a week. Temporal graph models build each node's representation by averaging information from its recent neighbors. That averaging behaves like a low-pass filter across the graph, so after a couple of hops, nodes with very different rhythms end up with similar summaries. This is a temporal version of over-smoothing, the known tendency of stacked neighbor-averaging layers to make all node representations look alike. The time-series literature already shows that careless transformations such as jittering, cropping and reversal destroy the timing structure that carries meaning. We argue that neighbor averaging is one more such transformation, and nobody has checked what it does to timing.
The proposal is to summarize each node's event history with a small set of decayed Fourier coefficients computed directly on raw, irregular timestamps. We call this a spectral sketch. It updates in constant time per event and needs no interpolation onto a grid. Sketches are passed across hops through two channels: an ordinary averaging channel, and a "difference" channel that records how a node's rhythm departs from its neighborhood's. The prediction is specific. On benchmarks where most test edges are new, and memorizing old edges cannot help, the difference channel should let deeper neighborhoods help rather than hurt. A rank-based collapse measure computed on the sketches should explain when this happens.
Core Claim
Our claim has two parts. First, in continuous-time graphs, over-smoothing shows up in the timing content of node summaries. It can be measured as falling effective rank of the matrix of propagated spectral sketches across hops. This drop in rank tracks the collapse of accuracy on unseen edges that TGB-Seq documents. Second, a scalable fix exists. Grid-free streaming sketches keep timing information without the interpolation artifacts that ASTGI warns about. A high-pass diversification channel then keeps neighborhood aggregation from erasing rhythm differences. With both in place, two- and three-hop temporal context becomes useful at the scale of the Temporal Graph Benchmark.
Why This Gap Is Real
Three lines of prior work each cover part of the problem.
The time-series work motivates the proposal. Um et al. show that jitter can mimic disease tremor. Yue et al. show that cropping induces false context. FrAug shows that operating in the frequency domain preserves periodic structure. However, FrAug is an augmentation method for regularly sampled series and relies on fixed grids. We take from it only the idea that frequency content is what must be protected. We do not use it as a component.
The over-smoothing work supplies the method. Complete the Missing Half splits the identity operator into a low-pass averaging part and a high-pass "diversification" part, $I = L_{LP} + L_{HP}$. Adding the high-pass channel rescues deep GCNII models and improves heterophilic benchmarks by roughly 10%. We reuse this decomposition. The difference is that we apply it to streaming timing summaries rather than to static node features. Are we measuring oversmoothing correctly? supplies our diagnostic. It shows that effective rank correlates with accuracy (average Pearson 0.91), while Dirichlet energy stays flat as accuracy crashes. It also warns that high rank is necessary but not sufficient. For that reason we never report rank without task accuracy.
The heavier anti-smoothing operators constrain the design. These are the wavelet channels of GSAN and the learned-potential Laplacian of μ-ChebNet. Both are static and costly on large, changing graphs. We therefore avoid any per-snapshot spectral decomposition of the graph itself.
The temporal-graph work sets the stage. GraphMixer pairs a fixed cosine time encoding with a one-layer mixer over 1-hop recent links. It beats deeper models, reaching 96.31% AP on LastFM against TGN's 82.23%. This is the strongest evidence that depth hurts. Our hypothesis is that depth hurts because averaging erases timing, and GraphMixer's retreat to one hop is a symptom of that. TGB and TGB-Seq show that neural models are slow. They also show that neural models can lose to moving-average heuristics, and that they collapse by 4x to 8x on unseen edges. Any method we propose must therefore be cheap and must be judged on unseen edges.
ASTGI is the closest bridge between timing and message passing. It handles irregular timestamps through learned coordinates, but its own sensitivity analysis shows degradation with depth. Its per-point nearest-neighbor graph construction also scales poorly. We differ on both counts: our summaries are fixed-size and incremental, and we explicitly counter homogenization.
The Mechanism
We fix $K$ frequencies $\omega_1,\dots,\omega_K$, spaced on a log scale from minutes to weeks, and a decay rate $\lambda$. For node $v$ with past events at times $t_i$, the sketch at time $t$ is
$$S_v^{(0)}(\omega_k, t) = \sum_{t_i < t} e^{-\lambda (t - t_i)}\, e^{\mathrm{i}\,\omega_k t_i}.$$
When a new event arrives at time $t'$, the old value is multiplied by $e^{-\lambda(t'-t)}$ and one term is added. The update therefore costs $O(K)$ per event and $O(NK)$ memory overall, where $N$ is the number of nodes. The sketch is a decayed non-uniform Fourier transform. It works on raw timestamps, so there is no interpolation, and it can be extended with edge-feature-weighted versions.
Propagation to hop $h$ uses each node's most recent $M$ neighbors, denoted $\mathcal{N}_M(v)$. For each hop we keep two channels: the neighborhood average $\bar S_v^{(h)} = \frac{1}{M}\sum_{u \in \mathcal{N}_M(v)} S_u^{(h-1)}$, and the diversification term
$$D_v^{(h)} = S_v^{(h-1)} - \bar S_v^{(h)}.$$
The diversification term measures how node $v$'s rhythm departs from its local crowd. It is the high-pass half of the filterbank decomposition, applied in the frequency domain of time. Both channels are computed lazily, only for the query endpoints, from stored neighbor sketches. A two-hop query costs $O(M^2 K)$, independent of graph size.
The magnitudes and phase differences of these channels, together with the node's raw features, feed a GraphMixer-style one-layer mixer. Learnable per-hop scalars set the balance between the averaging and difference channels, following the filterbank model. Depth enters only through fixed propagation of the sketches, not through stacked trainable layers. This choice also sidesteps the gradient collapse that Backward Oversmoothing proves for deep trainable message passing.
Research Program
The work has three stages.
The first stage is diagnostic. On TGB and TGB-Seq datasets, we compute the effective rank of the matrix whose rows are hop-$h$ averaged sketches, for $h=0,1,2,3$. We compare it against the same quantity for GraphMixer's pooled hidden features and TGN's memory states. We then correlate these rank curves with MRR, split by seen and unseen test edges. If timing collapse is real, the averaged-channel rank should fall with $h$, and the fall should predict the unseen-edge gap.
The second stage is a controlled synthetic study. We plant node classes that differ only in event periodicity, on graphs where neighbors mostly belong to a different rhythm class, which amounts to timing heterophily. We check that plain averaging erases the class signal within two hops while the difference channel keeps it.
The third stage builds the full model and runs it on TGB-scale streams. Wall-clock time and peak memory are reported alongside accuracy.
Baselines
The naive reference point is the set of non-learning heuristics reported by TGB: EdgeBank for link prediction and the moving average for node affinity. On tgbn-reddit, the moving average reaches NDCG@10 of 0.559, against 0.315 for TGN (TGB). We run these with TGB's official evaluator and negative samples. A method that does not beat them is not worth its cost.
The strongest existing method on our question is GraphMixer. It is cheap, it avoids over-smoothing by staying at one hop, and it reports 96.31% AP on LastFM. On tgbl-wiki, the file's strongest reported number is NAT's MRR of 0.749 (TGB). For TGB-Seq, we found no reported per-dataset result on Lacuna, so we will rerun GraphMixer and DyGFormer ourselves with the benchmark's code. Every baseline receives the same recent-neighbor budget $M$ and the same hyperparameter search budget, measured in trials and GPU-hours, on the same single GPU. Beating GraphMixer means higher MRR on unseen TGB-Seq edges at matched or lower wall-clock time, with the improvement exceeding seed variance on at least three of the five TGB-Seq datasets.
We also include TGN and DyGFormer as representatives of deeper, heavier models, and report runs that do not finish within the time limit as failures.
Two ablations isolate the key ingredient. The first gives GraphMixer the hop-0 sketch only, which tests whether grid-free timing features alone explain any gain. The second keeps multi-hop sketches but removes the difference channel, which tests whether diversification, rather than reach, explains the gain.
Why not just…?
Why not just use GraphMixer's one hop and its cosine time encoding? The encoding represents individual time gaps, not a node's rhythm over many events. Staying at one hop also gives up the higher-order context that TGB-Seq suggests is needed to separate distinct trajectories. The unseen-edge comparison against GraphMixer is the direct test. If GraphMixer matches us on unseen edges, the multi-hop claim fails.
Why not just add the sketch at one hop and stop there? This is the real threat. Grid-free timing features might account for most of any gain, which would make the over-smoothing story unnecessary. The first ablation above answers this directly. If hop-0 sketches plus GraphMixer capture more than roughly 80% of the full model's unseen-edge gain, we will reframe the contribution as streaming spectral features. We would drop the claim about temporal over-smoothing.
Why not just add residual connections or normalization to a deeper temporal GNN? Are we measuring oversmoothing correctly? finds that effective rank keeps falling under BatchNorm and LayerNorm even when energy looks healthy. Backward Oversmoothing shows that deep trainable propagation also stalls optimization. We still include a residual-and-normalized multi-hop mixer as a baseline, so this answer rests on measurement and not on assertion.
Why not just use heuristics or a Transformer? Heuristics depend on repetition, and TGB-Seq removes repetition by design. DyGFormer-style attention fails to finish on large TGB-Seq datasets within the benchmark's limits. Both are run as baselines rather than dismissed.
Why not interpolate onto a grid and apply FFT augmentation? ASTGI reports that alignment and interpolation distort irregular dynamics. Its improvement from avoiding them was a 6.04% MSE gain. A binned-FFT variant of our sketch will be included to test this in the graph setting.
Decisive Checks
The idea stands or falls on three results. First, the averaged-channel sketch rank must fall with hop count and must correlate with the unseen-edge gap across TGB-Seq datasets. Second, adding hops must hurt without the difference channel and help with it on unseen edges. Third, the full model must stay within a small constant factor of GraphMixer's throughput on tgbl-comment and tgbn-token. If the second result fails, temporal over-smoothing is not the operative mechanism, and we will report that finding as the paper's contribution.
References
- TGB-Seq Benchmark: Challenging Temporal GNNs with Complex Sequential Dynamics
- ASTGI: Adaptive Spatio-Temporal Graph Interactions for Irregular Multivariate Time Series Forecasting
- Data augmentation of wearable sensor data for parkinson's disease monitoring using convolutional neural networks
- TS2Vec: Towards Universal Representation of Time Series
- FrAug: Frequency Domain Augmentation for Time Series Forecasting
- Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks
- Are we measuring oversmoothing in graph neural networks correctly?
- Geometric Scattering Attention Networks
- Advection-Diffusion on Graphs: A Bakry-Emery Laplacian for Spectral Graph Neural Networks
- Do We Really Need Complicated Model Architectures For Temporal Networks?
- Temporal Graph Benchmark for Machine Learning on Temporal Graphs
- Backward Oversmoothing: why is it hard to train deep Graph Neural Networks?