Understanding Evolving Graph Structures for Large Discrete-Time Dynamic Graph Representation

Discrete-Time Dynamic Graphs (DTDGs) are commonly used to model and analyze systems evolving in discrete time steps (snapshots). For DTDG representation, existing approaches typically manage nodes' neighbors using an individual adjacency matrix for each snapshot, which provides neighbor information for structure learning based on neural networks. They either focus on the current snapshot, overlooking the evolution of temporal structures, or require preprocessing to access historical neighbors, resulting in significant computational overhead. In addition, the adjacency matrices for a DTDG consume O ( T | V | 2 ) memory, where T and | V | are the snapshot size and node size, respectively, restricting scalability on large DTDGs. To address these issues, in this paper, we propose a scalable and efficient framework (called UnderGS) with an efficient neighbor store, which can understand evolving graph structures for representation learning over DTDGs. Concretely, we first define a temporal influence score that helps identify influential temporal neighbors from current and previous snapshots. Upon it, we develop a temporal-cohesive neighbor store that maintains influential temporal neighbors for each node directly on the GPU, preserving evolving structural relationships across snapshots, which takes O (| V | K ) memory for a DTDG ( K is the neighbor size). Furthermore, our neighbor store enables seamless integration with message-passing graph neural networks and non-message-passing neural networks for temporal structure learning. Last, we introduce a lightweight training pipeline with a late-snapshot gradient aggregation mechanism, which enhances computational efficiency. Extensive experimental results on eight DTDGs show that UnderGS achieves up to 9× speed-up against the best competitors while achieving an average improvement of 31.36% in accuracy.