Abstract
Graph Neural Networks (GNNs) have revolutionized learning on graph-structured data, yet their performance on dynamic graphs remains limited by the lack of effective augmentation strategies. Most existing graph augmentation methods are designed for static graphs and fail to account for the temporal locality inherent in evolving systems. This paper introduces TIARA (Time-aware Random Walk Diffusion), a model-agnostic augmentation framework that extends random walk diffusion to the temporal dimension. By incorporating a "time travel" mechanism into random walks, TIARA generates enhanced adjacency matrices that capture both local spatial structures and temporal decay. Experimental results across seven diverse datasets demonstrate that TIARA consistently improves the performance of various dynamic GNN architectures in link prediction and node classification tasks.
Introduction
Dynamic graphs, such as social networks, financial transaction logs, and co-authorship networks, are characterized by their evolution over time. Learning effective representations for these graphs requires capturing both spatial relationships and temporal dependencies. While graph augmentation—techniques like edge dropping or diffusion—has proven successful in boosting the robustness of static GNNs, applying these methods to dynamic graphs is non-trivial.
Static augmentation methods typically treat each time-step in isolation, ignoring the "arrow of time." In real-world dynamic systems, recent interactions are often more significant than distant ones—a property known as temporal locality. Naively applying static diffusion fails to capture how information flows across time-steps, leaving dynamic GNNs under-optimized. TIARA addresses this gap by proposing a diffusion process that is inherently time-aware.
Methodology
The core of the TIARA framework is the Time-aware Random Walk with Restart (TRWR). Unlike standard random walks that only navigate spatial neighbors, TRWR introduces a temporal dimension to the surfer's movement.
As illustrated in the figure above, a "surfer" navigating the graph snapshots has three possible actions at any given node:
- Spatial Move: The surfer moves to a neighboring node within the current time-step, capturing local structural information.
- Restart: The surfer jumps back to the original "seed" node, ensuring the diffusion maintains a focus on the local neighborhood.
- Time Travel: The surfer moves to the same node in the subsequent time-step, allowing information to flow forward through time.
By calculating the stationary distribution of this surfer, TIARA derives a diffusion matrix that serves as an augmented adjacency matrix. This matrix effectively combines a spatial augmenter (strengthening local connectivity) and a temporal augmenter (carrying over relevant historical information). To ensure scalability, the authors utilize power iteration for approximation and sparsification to remove low-weight, noisy edges, which also serves as a form of denoising.
Key Insights and Results
TIARA's mathematical formulation naturally incorporates temporal decay, ensuring that information from the distant past has a diminishing influence compared to recent events. This alignment with real-world temporal locality is a key driver of its success. Furthermore, TIARA is model-agnostic; it functions as a preprocessing step that can be plugged into various base models such as GCN, GCRN, and EvolveGCN.
The sensitivity analysis of the temporal decay ratio ($\gamma$) highlights the importance of the time-aware component. As shown in the figure above, performance on datasets like BitcoinAlpha and WikiElec peaks when the temporal component is appropriately weighted, whereas setting the temporal influence to zero (effectively reverting to static diffusion) results in lower accuracy.
In empirical evaluations, TIARA delivered substantial gains:
- Link Prediction: On the BitcoinAlpha trust network, TIARA improved a standard GCN's AUC from 57.3% to 76.0%.
- Node Classification: On the Brain dataset, TIARA boosted Macro F1 scores from 44.7% to 68.7%, representing a nearly 50% relative improvement.
Conclusion
TIARA represents a significant step forward in dynamic graph learning by bridging the gap between static diffusion and temporal modeling. By treating time as a traversable dimension in a random walk, it provides a robust, model-agnostic way to enhance the input data for dynamic GNNs. While the current method is highly effective, future work may explore its application to continuous-time dynamic graphs (CTDGs) and automated parameter tuning to further optimize performance on billion-scale datasets.
Summary updated