Modeling Dynamic and Temporal Graphs

While many systems can be represented as static graphs, numerous phenomena are inherently dynamic. Social networks evolve as friendships form and dissolve, communication networks see fluctuating traffic, financial transaction graphs grow with each exchange, and biological interaction networks change over time. Modeling these systems requires Graph Neural Networks that can capture not only the complex relationships within a graph snapshot but also the evolution of these relationships and node attributes over time. Methods for adapting GNNs to handle dynamic and temporal graphs are presented.

Understanding Dynamic Graphs

A dynamic graph is a graph whose structure (nodes and edges) or features (node or edge attributes) change over time. We can broadly categorize representations and corresponding modeling approaches based on how time is treated:

1. Discrete-Time Dynamic Graphs (Snapshots): The evolving graph is represented as a sequence of static graph snapshots taken at discrete time intervals: $G_1, G_2, ..., G_T$. Each snapshot $G_t = (V_t, E_t, X_t)$ captures the graph's state at time $t$. This is a common representation, particularly when data is collected periodically. However, it can miss fine-grained changes occurring between snapshots and assumes a fixed, sometimes arbitrary, time granularity.
2. Continuous-Time Dynamic Graphs (Event Streams): The graph's evolution is represented as a continuous stream of timed events, such as node additions/deletions, edge formations/removals, or feature updates. Each event is associated with a precise timestamp. This representation captures the full temporal resolution of the graph dynamics but introduces challenges related to processing irregularly timed events and potentially large event volumes.

The choice of representation often depends on the data availability and the specific task. Modeling approaches differ significantly based on whether they operate on sequences of snapshots or continuous event streams.

Discrete-Time Approaches: Combining GNNs and Sequence Models

When dealing with graph snapshots, a natural approach is to combine the spatial processing power of GNNs with the temporal modeling capabilities of sequence models, primarily Recurrent Neural Networks (RNNs) like LSTMs or GRUs.

The general idea is to first use a GNN at each time step $t$ to compute node embeddings that capture the graph structure and features within that snapshot:

$$H_t = GNN(A_t, X_t)$$

Here, $A_t$ and $X_t$ are the adjacency matrix and node feature matrix at time $t$, respectively, and $H_t$ is the matrix of node embeddings.

These sequences of node embeddings (or graph-level embeddings, if applicable) are then fed into an RNN to model the temporal dependencies:

$$S_{t+1}, O_{t+1} = RNN(H_t, S_t)$$

where $S_t$ is the hidden state of the RNN at time $t$, and $O_{t+1}$ might be a prediction for the next time step (e.g., future node labels, predicted links).

Diagram of a discrete-time dynamic GNN model using a Recurrent Neural Network (RNN) component to process sequences of graph embeddings generated by a GNN at each time step.

Example Models:

• GCN-LSTM: A straightforward implementation using GCN for spatial aggregation and LSTM for temporal modeling.
• EvolveGCN: Addresses the limitation that the GNN parameters are static across time in simple GNN-RNN combinations. EvolveGCN proposes using an RNN (like GRU) to dynamically update the parameters of the GCN layer itself at each time step, allowing the GNN model to adapt its behavior based on the evolving graph dynamics.

These discrete-time models are effective when clear snapshots are available and inter-snapshot dynamics are less critical. However, they can be computationally expensive as they require running a GNN for each snapshot.

Continuous-Time Approaches: Event-Based Modeling

Continuous-time models aim to capture graph dynamics with finer granularity by directly processing a stream of timestamped events. These models often avoid the discretization into snapshots and can, in principle, handle interactions occurring at any point in time.

A prominent category involves memory-based approaches, exemplified by the Temporal Graph Network (TGN) framework. TGNs maintain a memory vector (or state) for each node, representing its history. When an interaction (event) involving certain nodes occurs at time $t$:

1. The current memory states of the interacting nodes are retrieved.
2. These memory states, along with event features and time information, are processed (often using attention mechanisms and MLP layers) to compute messages.
3. These messages are used to update the memory states of the involved nodes.
4. The interaction information and updated memories can then be used to compute temporal embeddings for downstream tasks like link prediction or node classification.

Components often found in continuous-time models like TGN:

• Memory Module: Stores and updates node states over time.
• Embedding Module: Computes temporal embeddings for nodes based on their memory and recent interactions.
• Temporal Encoding: Techniques to represent the continuous time of events, often involving mapping time differences ($\Delta t$) to feature vectors (e.g., using radial basis functions or learned time embeddings).
• Interaction Processing: Modules (often neural networks) that process events using node memories and temporal information.

Continuous-time models offer higher temporal precision but can be more complex to implement and train. They need efficient ways to manage memory and process asynchronous event streams.

Technical Aspects for Dynamic GNNs

Regardless of the approach, several technical aspects are important when modeling dynamic graphs:

• Temporal Information Encoding: Effectively representing time is significant. This can involve encoding absolute timestamps, time differences between events, or using positional encodings adapted for the temporal dimension. The choice impacts how the model perceives recency and duration.
• Temporal Attention: Attention mechanisms can be adapted to weigh the influence of past interactions or snapshots based on their temporal proximity or relevance, allowing the model to focus on pertinent history.
• Handling Structural Changes: Models must accommodate nodes and edges appearing or disappearing. This might involve strategies for initializing new node memories/embeddings, handling message passing for nodes with changing neighborhoods, or explicitly modeling node/edge existence probabilities.
• Computational Scalability: The temporal dimension adds significant computational overhead. Processing long sequences of snapshots or massive event streams requires efficient implementations, potentially involving sampling techniques adapted for the temporal domain (e.g., temporal neighborhood sampling) or approximations.
• Evaluation: Evaluating dynamic GNNs requires careful consideration of time-splitting strategies (e.g., training on $t_0$ to $t_k$, validating on $t_{k+1}$ to $t_m$, testing on $t_{m+1}$ to $T$) to prevent information leakage from the future. Tasks like future link prediction are common benchmarks.

Applications

Dynamic and temporal GNNs are applied to various problems where evolution over time is a defining characteristic:

• Link Prediction: Predicting future interactions in social networks, collaboration networks, or transaction graphs.
• Node Classification/Regression: Classifying nodes (e.g., detecting anomalous users/transactions) or predicting node attributes where behavior evolves over time.
• Event Time Prediction: Predicting when the next interaction involving a node might occur.
• Recommendation Systems: Modeling the temporal evolution of user preferences and item interactions.
• Epidemic Forecasting: Modeling disease spread over contact networks that change over time.

Modeling dynamic graphs adds a layer of complexity compared to static graph analysis, but it unlocks the ability to understand and predict systems that are constantly in flux. Choosing between discrete-time and continuous-time approaches depends heavily on the nature of the data and the specific requirements of the task. As research progresses, hybrid methods and more sophisticated techniques for capturing spatio-temporal dependencies continue to emerge.