Reconstructing the Surprise: Masked Pretraining for Evolving Graphs That Does Not Teach Smoothing

Masked pretraining is a common way to learn from unlabeled graphs whose connections change over time: hide some node attributes and train a network to fill them back in from the visible neighbors. This note argues that the objective itself pushes the model toward over-smoothing, where node representations blur into their neighborhood average and lose what makes each node distinct. That push exists however shallow or well-regularized the network is. Under a squared-error loss, the best guess for a hidden node is roughly the average of its recent past and its current neighbors. The pretrained representations therefore learn to encode the predictable, smooth part of the signal. The part that matters most on evolving graphs is exactly what that average cannot predict: a sudden new interaction, an extreme rainfall at one station, an anomalous transaction. Evolving-graph evaluations suggest this is a real problem. On the Temporal Graph Benchmark, a moving-average heuristic beats a deep temporal network on node-affinity forecasting, which means much of the learned models' capacity is spent rediscovering the average.

We propose to change what the model reconstructs. First, a fixed, cheap predictor built from a temporal moving average and a neighbor average over visible nodes produces a "smooth guess" for each masked node. The decoder is then trained to reconstruct the innovation: the difference between the true attribute and that smooth guess. The heuristic that wins the benchmark becomes the floor the model is asked to improve on, and the pretraining signal is concentrated on the high-frequency, surprising component that low-pass message passing throws away. The central empirical question is whether this changes which information survives in the representation. We measure that with rank-based collapse diagnostics, and we test it on the nodes and time steps where surprise is highest.

Core Claim

Masked attribute reconstruction on dynamic graphs acts as a smoothing pressure on the encoder. Replacing the raw-attribute target with an innovation target yields representations whose effective rank, measured on the component not explained by the smooth guess, stays high. It also yields better downstream forecasts on high-surprise events, without hurting low-surprise ones. Precisely, for node $i$ at time $t$ we set

$$\hat{x}_i^t = \alpha\,\frac{1}{k}\sum_{s=1}^{k} x_i^{t-s} + (1-\alpha)\,\frac{1}{|\mathcal{V}_t(i)|}\sum_{j\in\mathcal{V}_t(i)} x_j^t,\qquad r_i^t = x_i^t - \hat{x}_i^t .$$

Here $x_i^t$ is the node's attribute vector, $k$ is a history window, $\mathcal{V}_t(i)$ is the set of visible (unmasked) neighbors of $i$ at time $t$, and $\alpha\in[0,1]$ trades temporal against spatial smoothing. The pretraining loss is the squared error between the decoder output for masked nodes and $r_i^t$, each dimension normalized by the running variance of $r$ so that the loss does not collapse to predicting zero. Nodes that have just appeared have no history, so for them $\alpha=0$. This lets the method handle a changing node set, which DynaSTy's fixed-node design does not.

The claim is new because of where the anti-smoothing mechanism sits. Existing anti-smoothing work changes the propagation operator. Existing dynamic masked autoencoders reconstruct raw quantities. Nobody in this literature has asked whether the reconstruction target is itself the source of collapse.

Relation to Prior Work

Four systems combine masked reconstruction with evolving graphs, and they supply our setting. DyGMAE masks edges at multiple scales per snapshot, aligns the masked views contrastively, and reconstructs links. DynaSTy pretrains an edge-biased transformer with BERT-style masking of raw node attributes, then forecasts with a recurrent decoder. HGAurban jointly masks features and edges on multi-view urban graphs and credits reconstruction with denoising. UDGSL learns time-varying brain connectivity by reconstructing raw BOLD signals through a GCN. All four reconstruct raw values, and none measures representation collapse. We keep their encoders and masking and change only the target.

DiffLiG motivates the proposal. It shows that spatial averaging on station networks erases extreme precipitation, and it repairs this after the fact with a diffusion-based ensemble in a purely supervised pipeline. We move the correction upstream, into what unlabeled pretraining rewards. ASTGI reports over-smoothing when stacking propagation layers on irregular time-series graphs and simply stays shallow. This constrains us: any claim of benefit must hold at shallow depth, not only for deep encoders.

On measurement we build on Are we measuring oversmoothing in graph neural networks correctly?. It shows Dirichlet energy misses collapse in trained networks, while effective rank (the exponential of the entropy of normalized singular values) correlates with accuracy at an average Pearson 0.91 on static node classification. The same paper warns that high rank is not sufficient, since noise has maximal rank. That warning drives our design: we measure rank on the innovation-explaining subspace rather than on raw embeddings, and we treat a direct rank penalty as a competitor rather than a solution. Operator-level remedies are orthogonal to our change: Complete the Missing Half adds a high-pass channel, Residual connections provably mitigate oversmoothing bounds similarity decay with skips, and the Bakry-Émery Laplacian controls the spectral gap with a learned potential. Our innovation target is roughly the objective-space analogue of the high-pass channel in Complete the Missing Half. We use the [MASK]-token replacement from Rethinking Tokenizer and Decoder in Masked Graph Modeling for Molecules throughout, so that information leakage cannot explain any result. GSTBench finds that generative masked pretraining transfers better than contrastive pretraining, which is our reason to stay generative rather than add contrastive terms as DyGMAE does.

Research Program

The first component is a short analysis of why raw-target masking smooths. In a linear-Gaussian model of node attributes on a graph with homophilous covariance, the optimal masked predictor is a weighted neighbor average, a low-pass filter. An encoder trained to support that predictor therefore needs only the low-frequency subspace. We will state this as a small proposition. We will then check empirically whether it survives nonlinearity by tracking, during pretraining, the effective rank of encoder outputs projected orthogonally to the span of the smooth guesses $\hat{x}$.

The second component is the method: the innovation target above, with $\alpha$ and $k$ chosen on validation reconstruction error. We will also test a learned smooth predictor. That variant is riskier because it can absorb the innovation itself, so its gradient into the encoder is stopped.

The third component is a surprise-stratified evaluation protocol. Test events are bucketed by $\|r_i^t\|$ under a predictor fit only on training data, following the spirit of TGB's surprise index. Results are reported per bucket, not only on average.

Baselines

The naive reference points are the non-learned predictors. On TGB node-affinity tasks this is the Moving Average heuristic, which the benchmark paper reports at NDCG@10 of 0.559 on tgbn-reddit against 0.315 for TGN. On forecasting datasets it is the same smooth guess $\hat{x}$ used as a direct forecast. Because our target is defined relative to this predictor, beating it on the high-surprise bucket is the minimum bar. Matching it on the low-surprise bucket is required so that the model cannot trade one regime for the other.

The strongest existing method on node-attribute forecasting over evolving graphs is DynaSTy. Its paper reports RMSE 17.61 on ABIDE brain dynamics, against 21.9 for MTGNN, and MAE 1.15 on Bitcoin Alpha, against 1.53 for PDFormer. We will rerun DynaSTy from its released configuration on the same splits. We will then swap only its pretraining target to the innovation, holding encoder, recurrent decoder, masking rate, pretraining epochs, and tuning budget fixed; the tuning budget is the same number of trials over learning rate and mask rate for both. Beating it means lower RMSE and MAE on the top-surprise decile with no worse average error. If our rerun does not reproduce the reported 17.61 and 1.15, we report both numbers. For link-level evolving graphs we compare against DyGMAE on Enron, Facebook, and AS733 using AUC and AP. The file gives only DyGMAE's relative gain on Facebook (3.88% AUC, 4.41% AP over the second-best method), so no absolute baseline number was found on Lacuna. There, innovations are defined on node-level degree and interaction-count features.

Two ablations isolate the key ingredient. The first reconstructs the raw target while feeding $\hat{x}$ as an extra input, which separates "knowing the smooth guess" from "being trained on the residual." The second keeps the raw target but adds a high-pass diversification channel to the encoder in the style of Complete the Missing Half, which tests whether the operator fix alone is enough.

Why not just…?

Why not just add an effective-rank penalty to the standard masked objective? This is the most direct reading of the gap left by the rank-metrics paper, and it is a real threat. That same paper notes that rank can be inflated by noise, so a penalty can raise rank without adding information about surprises. We will run this penalty with a tuned weight. Our claim fails if it matches the innovation target on the high-surprise bucket. We also report the rank of each model's representation projected away from $\hat{x}$, to show whether the rank that a penalty buys is useful rank.

Why not just use residual connections or a two-layer encoder? Both address depth-driven smoothing. The residual-connection theory rests on linear, i.i.d.-weight assumptions, and Backward Oversmoothing shows that gradient collapse persists in practice. More to the point, our argument is that the target smooths regardless of depth. We will sweep encoder depth from 2 to 8, with and without residuals, under both targets. If raw-target collapse and the surprise-bucket gap vanish at depth 2 with residuals, the objective-level claim is wrong and we will say so.

Why not just reweight the supervised loss toward extreme values? For extreme-event domains, this is the obvious practitioner fix. It needs labels and a threshold, whereas our method acts during unlabeled pretraining. We include heavy-tail-weighted fine-tuning of the raw-pretrained model as a baseline, and we also combine it with our pretraining. If reweighting alone closes the gap, the pretraining contribution is small.

Why not just use the moving-average heuristic, given that it already wins? On tgbn-reddit it does beat TGN, but heuristics cannot represent unseen transitions, and TGB shows memorization falters on high-surprise data such as tgbl-review. Our design uses the heuristic as a component rather than competing with it. The surprise-stratified results show directly whether learning adds anything beyond it.

Proposed Experiments

We pretrain and fine-tune on ABIDE brain dynamics and Bitcoin Alpha/OTC, using DynaSTy's setting and MAE/RMSE. We evaluate node affinity on tgbn-reddit, tgbn-trade, and tgbn-genre with NDCG@10, using a scalable message-passing encoder since quadratic attention is infeasible there. We add HCP S1200 reconstruction and forecasting in UDGSL's setting, where UDGSL reports 24–32% lower reconstruction MSE than non-graph baselines. If the CMA station data used by DiffLiG is obtainable, we will test threat scores at 20mm and 100mm, for which no reported number was found on Lacuna.

The decisive check is the surprise-stratified comparison between raw and innovation targets under an otherwise identical pipeline. The predicted signature has three parts: near-equal error on the lowest-surprise buckets, a widening advantage for the innovation target toward the top decile, and a matching gap in projected effective rank that appears during pretraining, before any labels are seen. A second check tests whether the gain survives transfer. We pretrain on one Bitcoin network and fine-tune on the other, and pretrain on one brain cohort and fine-tune on another, mirroring GSTBench's finding that reconstruction quality predicts transfer. If the rank penalty, the depth sweep, or loss reweighting reproduces this signature, the proposal reduces to a known remedy and we will report that outcome.