Continuous-time dynamic graph learning based on spatio-temporal random walks

The application of dynamic graph representation learning in the processing of dynamic systems, such as social networks and transportation networks, has increased in recent times due to its ability to efficiently integrate topological and temporal information into a compact representation. Continuous-time dynamic graphs (CTDGs) have received considerable attention due to their capacity to retain precise temporal information. Existing methods based on random walk techniques often use time-biased sampling to extract dynamic graph patterns, neglecting the topological properties of the graph. Additionally, previous anonymous walks do not share node identifiers, failing to fully leverage the correlations between network patterns, which play a crucial role in predicting future interactions. Consequently, this study focuses on methods related to CTDGs. This paper presents a novel continuous-time dynamic graph learning method based on spatio-temporal random walks, which makes three main contributions: (i) By considering temporal constraints and topological structures, our method extracts diverse expressive patterns from CTDGs; (ii) It introduces the hitting counts of the nodes at a certain position as the node's relative identity. This approach fully leverages the correlation of network patterns, ensuring that the pattern structure remains consistent even after removing node identities; (iii) An attention mechanism is employed to aggregate walk encodings, allowing the importance of different walks to be distinguished. This facilitates a more precise delineation of the relationships and structural attributes between nodes, thereby enhancing the precision and expressive power of node representations. The proposed method demonstrates superior performance compared to the average strongest baseline, achieving gains of 2.72% and 2.46% in all transductive and inductive link prediction tasks, respectively. Additionally, it attains up to an 8.7% improvement on specific datasets. Furthermore, it exhibits the second best overall performance in dynamic node classification tasks.