# EvoFormer: Learning Dynamic Graph-Level Representations with Structural and Temporal Bias Correction

arXiv: https://arxiv.org/abs/2508.15378 · HTML: https://mlsanity.com/paper/2508.15378/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 57 references that are in the map.
- First posted on arXiv 21 Aug 2025.

## Builds on (most cited first, 26 of 26)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [graph2vec: Learning Distributed Representations of Graphs](https://mlsanity.com/paper/1707.05005/) (2017)
- [Diachronic Word Embeddings Reveal Statistical Laws of Semantic Change](https://mlsanity.com/paper/1605.09096/) (2016)
- [Graph-Bert: Only Attention is Needed for Learning Graph Representations](https://mlsanity.com/paper/2001.05140/) (2020)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [DynGEM: Deep Embedding Method for Dynamic Graphs](https://mlsanity.com/paper/1805.11273/) (2018)
- [dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation Learning](https://mlsanity.com/paper/1809.02657/) (2018)
- [Graph Transformer for Graph-to-Sequence Learning](https://mlsanity.com/paper/1911.07470/) (2019)
- [A Survey on Embedding Dynamic Graphs](https://mlsanity.com/paper/2101.01229/) (2021)
- [Node Embedding over Temporal Graphs](https://mlsanity.com/paper/1903.08889/) (2019)
- [Dynamic Graph Representation Learning via Self-Attention Networks](https://mlsanity.com/paper/1812.09430/) (2018)
- [A survey of dynamic graph neural networks](https://mlsanity.com/paper/2404.18211/) (2024)
- [Anomaly detection in online social networks](https://mlsanity.com/paper/1608.00301/) (2016)
- [Graph Embedding via Diffusion-Wavelets-Based Node Feature Distribution Characterization](https://mlsanity.com/paper/2109.07016/) (2021)

## Abstract (arXiv)

Dynamic graph-level embedding aims to capture structural evolution in networks, which is essential for modeling real-world scenarios. However, existing methods face two critical yet under-explored issues: Structural Visit Bias, where random walk sampling disproportionately emphasizes high-degree nodes, leading to redundant and noisy structural representations; and Abrupt Evolution Blindness, the failure to effectively detect sudden structural changes due to rigid or overly simplistic temporal modeling strategies, resulting in inconsistent temporal embeddings. To overcome these challenges, we propose EvoFormer, an evolution-aware Transformer framework tailored for dynamic graph-level representation learning. To mitigate Structural Visit Bias, EvoFormer introduces a Structure-Aware Transformer Module that incorporates positional encoding based on node structural roles, allowing the model to globally differentiate and accurately represent node structures. To overcome Abrupt Evolution Blindness, EvoFormer employs an Evolution-Sensitive Temporal Module, which explicitly models temporal evolution through a sequential three-step strategy: (I) Random Walk Timestamp Classification, generating initial timestamp-aware graph-level embeddings; (II) Graph-Level Temporal Segmentation, partitioning the graph stream into segments reflecting structurally coherent periods; and (III) Segment-Aware Temporal Self-Attention combined with an Edge Evolution Prediction task, enabling the model to precisely capture segment boundaries and perceive structural evolution trends, effectively adapting to rapid temporal shifts. Extensive evaluations on five benchmark datasets confirm that EvoFormer achieves state-of-the-art performance in graph similarity ranking, temporal anomaly detection, and temporal segmentation tasks, validating its effectiveness in correcting structural and temporal biases.