Dynamic Graph

Unlike static graphs, dynamic graphs undergo continuous structural changes as edges and nodes are added, removed, or rewired over discrete or continuous time steps. This evolution reflects real-world processes such as supplier onboarding, logistics rerouting, or transaction flows.

• Edge arrival and deletion: New relationships form while obsolete connections dissolve
• Node addition and removal: Entities enter and exit the network over time
• Community drift: Clusters of tightly connected nodes shift their composition
• Temporal motifs: Recurring subgraph patterns that appear at specific time intervals

Node and edge attributes in dynamic graphs evolve independently of structural changes. A supplier's risk score, a warehouse's inventory level, or a shipment's temperature reading may fluctuate while the graph topology remains constant.

• Node feature streams: Time-varying attributes such as capacity, demand, or compliance status
• Edge weight dynamics: Relationship strength or transaction volume that changes over time
• Concept drift: The statistical properties of features shift, requiring models to adapt
• Stateful representations: Node embeddings must encode both current and historical feature values

Dynamic graphs are modeled using two fundamental paradigms. Discrete-time dynamic graphs (DTDG) capture snapshots at fixed intervals, while continuous-time dynamic graphs (CTDG) represent events as they occur on a real-valued timeline.

• Snapshot-based (DTDG): Graph is observed at regular timestamps G₁, G₂, ..., Gₜ
• Event-based (CTDG): Each interaction is timestamped as a quadruple (source, target, time, features)
• Temporal point processes: Hawkes processes and neural ODEs model event arrival rates
• Trade-off: Snapshots simplify batching but lose fine-grained temporal resolution

Capturing long-range temporal dependencies requires integrating recurrent neural networks (RNNs) or self-attention mechanisms with graph convolutions. These architectures maintain a hidden state that summarizes the graph's evolutionary history.

• EvolveGCN: Uses an RNN to update GCN weight matrices over time, decoupling parameter evolution from node dynamics
• TGN (Temporal Graph Network): Maintains a compressed memory module for each node updated via message functions
• DySAT: Applies self-attention across both structural neighbors and historical representations
• GRU-GCN: Embeds a Gated Recurrent Unit within the message-passing framework to propagate temporal states

Efficient training on large-scale dynamic graphs requires temporal-aware sampling strategies that respect causality. Unlike static graph sampling, temporal neighbors must be restricted to interactions occurring before the target event.

• Temporal random walks: Biased walks that respect chronological ordering of edges
• Causal neighborhood: Only historical interactions are valid for predicting future events
• Temporal GraphSAGE: Extends inductive sampling to include time-weighted aggregation
• Memory staleness: Sampled historical states may become outdated, requiring refresh mechanisms

Dynamic link prediction extends beyond binary existence to forecast when a connection will form, how long it will persist, and when it will dissolve. This is critical for supply chain applications like predicting supplier relationship duration.

• Survival analysis: Models the probability a link survives beyond time t using hazard functions
• Recurrent event modeling: Captures repeated interactions between the same node pairs
• Temporal knowledge graph completion: Predicts missing facts at specific timestamps (subject, relation, object, time)
• Cold-start links: Forecasting connections for nodes with no prior interaction history

The primary architecture for processing dynamic graphs. ST-GNNs simultaneously capture spatial dependencies (relationships between nodes at a given time) via graph convolutions and temporal dependencies (how those relationships evolve) via recurrent units like LSTMs or temporal convolutions.

• Mechanism: A GCN extracts spatial features at time t, which are then fed into an RNN to model the transition to time t+1.
• Use Case: Predicting traffic speed across a sensor network where the road topology (spatial) and congestion levels (temporal) change continuously.

A generic framework for deep learning on continuous-time dynamic graphs. Unlike discrete-time snapshots, TGNs process events (edge additions/deletions) as they occur in real-time.

• Core Component: A memory module that maintains a compressed, time-aware state vector for each node, updated whenever the node is involved in an interaction.
• Advantage: Avoids the information loss inherent in batching events into static snapshot windows, making it ideal for high-frequency streaming data like financial transactions.

A technique often coupled with dynamic graphs when the underlying topology is unknown, noisy, or incomplete. Instead of relying on a fixed adjacency matrix, the model jointly learns the optimal graph structure and node representations.

• Dynamic Relevance: In supply chains, formal BOM connections may miss informal dependencies. Structure learning infers latent connections from correlated inventory fluctuations.
• Approach: Often uses a metric learning module to calculate pairwise node similarity and construct a learned adjacency matrix for downstream GNN processing.

A spatial GNN that employs self-attention to assign different importance weights to neighboring nodes during feature aggregation. In a dynamic context, attention coefficients naturally adapt to shifting relationship strengths over time.

• Dynamic Benefit: A supplier's influence on a manufacturer can increase during a shortage. GATs automatically learn to weight that connection higher without explicit reprogramming.
• Mechanism: Computes attention scores e_{ij} for node j's features relative to node i, allowing the model to focus on the most relevant temporal interactions.

A fundamental task for evaluating dynamic graph models. The goal is to predict the probability of a future connection between two nodes based on historical snapshots.

• Temporal Variant: Given a sequence of graph snapshots G_1 to G_T, predict the adjacency matrix at G_{T+1}.
• Supply Chain Application: Forecasting new supplier-manufacturer relationships that should exist to mitigate risk, or predicting the dissolution of a critical logistics partnership before it fails.

A process that propagates information across a graph using a diffusion kernel, often modeled via Personalized PageRank. This captures long-range dependencies that standard message passing might miss due to over-smoothing.

• Dynamic Context: In a temporal graph, diffusion can model the propagation delay of a disruption—how a factory shutdown's impact ripples through the supply chain over days or weeks.
• Key Concept: Moves beyond immediate 1-hop neighbors to aggregate information from a wider, relevance-weighted neighborhood defined by the diffusion process.