Deep models for graphs that change over time are expensive, and on realistic benchmarks they often lose to arithmetic. On the Temporal Graph Benchmark, a plain moving average of each node's past interactions beats a trained temporal graph network on three of four node-affinity tasks, and runs at least an order of magnitude faster at inference (Temporal Graph Benchmark for Machine Learning on Temporal Graphs). Video analysis ran into a similar tension years ago. Full 3D texture operators on a video volume produced huge, noisy codes. The fix that held up was LBP-TOP: cut the space-time block into three perpendicular 2D slices (one spatial, two space-by-time), compute a cheap fixed local binary pattern on each slice, and concatenate the histograms. A local binary pattern (LBP) is a bit code recording whether each neighbor is brighter than the center pixel. We propose the same move for temporal graphs. We treat the stream of timestamped edges as a sparse tensor indexed by source node, destination node and time. We slice it along its three orthogonal planes, compute fixed binary "shape of change" codes on each slice, and hand fixed-size histograms of these codes to a small tabular model. No gradients pass through the graph.
The claim is narrow and testable. Descriptors of this kind capture whether an interaction is rising, falling, bursting or fading, independent of its absolute volume. They can be maintained in constant memory per node under streaming edge insertions. A small ranker trained on them should beat the moving-average heuristic where learned temporal networks fail, and match learned models where those models do win. The whole pipeline should cost about as much as a heuristic. What is new is neither "fixed features for graphs" nor "slicing a tensor". It is the use of order-based binary codes on the node-by-time planes of an interaction tensor. The key experiment isolates that ingredient against raw windowed statistics.
Core Claim
Write the event stream, binned at resolution $\Delta$, as a sparse tensor $\mathcal{A}[u,v,t]$ giving the interaction weight from $u$ to $v$ in bin $t$. The three orthogonal planes play the roles of LBP-TOP's $XY$, $XT$ and $YT$ slices. The snapshot plane is $\mathcal{A}[\cdot,\cdot,t]$, the graph at one moment. The source-history plane is $\mathcal{A}[u,\cdot,\cdot]$, which records how $u$'s interactions with each partner evolve. The destination-history plane is $\mathcal{A}[\cdot,v,\cdot]$, which records how everyone's interactions with $v$ evolve.
LBP-TOP: A Tensor Unfolding Revisit formalizes LBP-TOP as mode unfoldings of a dense video tensor. We borrow that view directly and apply it to a sparse, irregular tensor, where the "rows" of a plane are graph neighbors rather than pixels.
On the source-history plane, the temporal code for a pair $(u,v)$ at time $t$ is
$$c_{uv}(t) = \sum_{k=1}^{P} 2^{k-1}\,\mathbb{1}\left[a_{uv}(t-k) \ge a_{uv}(t)\right] + 2^{P}\,\mathbb{1}\left[a_{uv}(t) \ge m_u(t)\right].$$
Here $a_{uv}(t)$ is the decayed interaction weight, $P$ is the number of past bins compared (the temporal radius), and $m_u(t)$ is the median weight across $u$'s currently active partners. The last bit plays the role of the spatial neighbor within the same plane.
The destination-history plane uses the same construction on $v$'s inbound series. The snapshot plane codes whether $u$'s current degree is at least that of each of its sampled neighbors.
Like image LBP under monotone brightness changes, every code is unchanged by any monotone rescaling of activity. That property matters for heavy-tailed, bursty interaction volumes. Per node we keep histograms of codes over its active partners, plus per-pair codes for candidate scoring. Each new edge updates a bounded number of counters, so memory does not grow with the number of hops or with the length of history.
Research Program
The first component is the descriptor and its streaming maintenance. We will use the non-uniform-pattern lesson of Improving Rotation Invariance of the Volume Local Binary Pattern Operator. That paper found that space-time volumes produce many non-uniform patterns, and that discarding them loses information. Grouping them by bit count instead gave a compact 26-bin code reaching 89.71% on DynTex. We therefore bin our codes by uniformity and bit density rather than keeping only uniform patterns. This choice constrains the design: we do not copy image-LBP practice blindly.
We also take the radius-sensitivity finding of CASME II seriously. There, accuracy depended strongly on the temporal radius. We will therefore compute codes at several bin widths $\Delta$ and concatenate them, which is cheap because each scale is just another counter set.
The second component is the predictor. For node-affinity and link-prediction queries, each candidate pair $(u,v)$ gets a feature vector with four parts: the pair's temporal codes at each scale, $u$'s and $v$'s plane histograms, the snapshot code, and the raw moving-average value itself. A gradient-boosted tree or small MLP then ranks candidates. Including the moving-average value is deliberate. The heuristic becomes a special case of the model, so any gain must come from the codes.
This follows the stance of Fixed Aggregation Features Can Rival GNNs. That paper precomputes fixed multi-hop mean, max and std reducers and trains only an MLP, matching standard GNNs on 12 of 14 static benchmarks. We extend its logic to time. We also differ from it in two ways. It aggregates raw values over hops on a static graph, and it reports a feature explosion beyond about four hops. We aggregate order codes over time within one hop, with a fixed histogram size.
The third component is analysis. We will measure which plane carries signal on which dataset. We will also test a specific hypothesis about new pairs. The destination-history plane gives nonzero, informative features for pairs never seen before, because it describes $v$'s trend and not the pair's history. It should therefore help most on the new-pair edges that make high-surprise datasets hard.
Baselines
The naive reference point is the moving-average heuristic from Temporal Graph Benchmark for Machine Learning on Temporal Graphs. It predicts each node's future affinity as its decayed past affinity. It is the strongest competitor on node affinity: the benchmark reports NDCG@10 of 0.559 on tgbn-reddit against 0.315 for TGN. We will run it through the official TGB evaluator with its decay rate tuned on the validation split. Beating it means higher test NDCG@10 on at least three of the four node-affinity datasets, averaged over five seeds, with non-overlapping standard errors. For link prediction, EdgeBank plays the same role and is run the same way.
The strongest learned method on the low-surprise link task is NAT (Neighborhood-aware Scalable Temporal Network Representation Learning). NAT keeps dictionary-style neighborhood caches on the GPU and reports an MRR of 0.749 on tgbl-wiki under TGB. We will run the released configuration on identical splits and hardware. On tgbl-review, TGB reports that GraphMixer and TGAT lead and that NAT drops. The file gives no numeric MRR for them (no reported result found on Lacuna for GraphMixer or TGAT on tgbl-review), so we will rerun both. Here "competitive" means within two MRR points of NAT on tgbl-wiki at a fraction of its training and inference time. On tgbl-review, we need to beat NAT and stay within two points of the best rerun model.
For scaling, the reference is the Decoupled Dynamic GNN of Decoupled Graph Neural Networks for Large Dynamic Graphs. It runs incremental graph propagation and then trains a separate sequence model, reporting 2 seconds per epoch on Wikipedia versus 12 for TGN and 147 for TGAT, and it scales to MAG. It is the fairest efficiency comparison, because it also removes graph operations from backpropagation. We will give it the same compute budget and the same number of tuning trials (a fixed random search of 30 configurations for every method). We will report end-to-end wall-clock time, peak memory and accuracy on the large TGB datasets.
Two ablations isolate the key ingredient. The first replaces every binary code with the raw windowed values it was computed from: the same lags, the same planes and the same reducers as in the FAF paper. This amounts to FAF extended over time. The second drops the planes one at a time. If the raw-value ablation matches the full model, the orthogonal-plane LBP idea adds nothing beyond temporal FAF, and we will say so.
Why not just…?
Why not just use the moving average or EdgeBank? On node affinity this is the method to beat, and it may well win on some datasets. The moving-average value sits inside our feature vector, so the only question is whether trend codes add ranking signal on top of it. The baseline comparison answers that directly. TGB's own results suggest headroom on link prediction: on tgbl-wiki a learned model (NAT, 0.749 MRR) beats persistence. So heuristics are not uniformly sufficient.
Why not just compute FAF-style windowed means, maxima and deviations over time and train an MLP? This is the most serious threat, because it shares our pipeline shape and differs only in using raw values instead of order codes. Our argument for codes is invariance to monotone rescaling, which should help when activity scales differ by orders of magnitude across nodes, as in token and trade graphs. The raw-value ablation decides the question. We expect the gap to be largest on the most heavy-tailed datasets. If no gap appears anywhere, the contribution collapses to "temporal FAF", and we will report it as such.
Why not just train a decoupled or memory-based temporal GNN such as the Decoupled DGNN or NAT? Both are effective, but they are trained sequence or cache models. TGB shows that NAT-style joint-neighborhood caches degrade on high-surprise data. The decoupled model still trains a neural sequence predictor over propagated features. Our pipeline has no trained graph component. That is only an advantage if accuracy holds, which the tgbl-wiki and tgbl-review comparisons test. We also expect the destination-plane codes to help specifically on the new-pair edges that hurt NAT.
Why not just condense the graph with SimGC or GCPA? These methods synthesize a small proxy graph (Simple Graph Condensation reaches 67.0% on ogbn-products at a 0.08% reduction rate; A Precompute-Then-Adapt Approach for Efficient Graph Condensation is 96 to 2,455 times faster than trajectory matching). Both are defined only for static node classification and have no notion of streaming edges. They do not apply to the tasks here without new research, so we do not treat them as baselines.
Proposed Experiments
The main evaluation uses the Temporal Graph Benchmark with its official streaming protocol and historical negatives. Node affinity is measured by NDCG@10 on tgbn-trade, tgbn-genre, tgbn-reddit and tgbn-token. Link prediction is measured by MRR on tgbl-wiki, tgbl-review, tgbl-coin, tgbl-comment and tgbl-flight.
The first decisive check is the comparison against moving average on the four node-affinity datasets, together with the raw-value ablation. Together these say whether order codes add anything beyond a heuristic and beyond temporal FAF.
The second decisive check splits tgbl-review and tgbl-wiki test edges into seen and unseen pairs. We will measure whether the destination-plane features close the gap on unseen pairs, where memory-based models fail.
The third check concerns scaling. We will run on tgbn-token (over 72 million edges) and tgbl-comment, plotting per-edge update time and resident memory against stream length. The prediction is flat memory per node and linear total time, compared with the Decoupled DGNN and NAT under matched hardware.
Finally, a sensitivity sweep over the bin width $\Delta$ and the number of lags $P$ will show whether combining several scales removes the radius sensitivity that CASME II reported for video. Axis-aligned slices may miss oblique space-time structure, a known limitation of LBP-TOP. If the plane ablation shows the snapshot plane contributes little, we will treat mixed codes that couple a node's trend to its neighbors' trends as a follow-up, not a claim of this work.
References
- Temporal Graph Benchmark for Machine Learning on Temporal Graphs
- LBP-TOP: A Tensor Unfolding Revisit
- Improving Rotation Invariance of the Volume Local Binary Pattern Operator
- CASME II: An Improved Spontaneous Micro-Expression Database and the Baseline Evaluation
- Fixed Aggregation Features Can Rival GNNs
- Neighborhood-aware Scalable Temporal Network Representation Learning
- Decoupled Graph Neural Networks for Large Dynamic Graphs
- Simple Graph Condensation
- A Precompute-Then-Adapt Approach for Efficient Graph Condensation