Graph neural networks often struggle when the data they are trained on is older than the data they are asked to classify. In chronologically split graphs, connectivity patterns shift over time, and models trained on historical nodes tend to degrade when applied to recent ones. The authors of a new arXiv paper propose a simple fix: instead of aggregating messages from neighbors indiscriminately, they balance the messages by timestamp so that no single time period dominates the representation.

The resulting operator, called Symmetric Temporal Averaging Message Passing (STAMP), enforces first-moment invariance across temporal domains. That means the average feature distribution seen by the model stays consistent over time, which directly addresses the distribution shift caused by temporal dependencies. The method is designed to be scalable and easy to implement, and it comes with theoretical support rather than relying on assumptions that are difficult to verify in practice.

In experiments, STAMP and its variant STAMP-mag improved accuracy across all evaluated temporal graph benchmarks. STAMP reached state-of-the-art performance on ogbn-arxiv, while STAMP-mag did the same on ogbn-mag. For the temporal-split Pokec dataset, where no established benchmark existed, applying STAMP to the current best model consistently improved results under the authors' chronological split. The work suggests that timestamp-balanced propagation is a practical and effective way to mitigate temporal distribution shift in graph learning.