Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

Static vs Dynamic Graphs: When Structure Changes Over Time

4 minute read

Published:

TL;DR: A static graph has fixed topology throughout learning. A dynamic graph changes over time: edges form and dissolve, nodes arrive and depart, features drift. Dynamic graphs come in two forms — discrete-time (snapshots) and continuous-time (event streams). Each requires different modelling assumptions.

Why Graphs Change Over Time

Real-world networks are never truly static:

  • Social networks: friendships form and fade, users join and leave
  • Financial networks: transactions occur at specific timestamps
  • Traffic networks: road states change with congestion, incidents
  • Citation networks: papers get cited over years; authors leave academia
  • Protein interactions: binding/unbinding events, cell-state-dependent interactions

A static GNN trained once on a snapshot cannot predict future edges or adapt to structural shifts. Dynamic graph learning is the framework for handling this.

Taxonomy of Dynamic Graphs

Discrete-Time Dynamic Graphs (DTDG)

The graph is observed as a sequence of snapshots:

G = {G_1, G_2, ..., G_T} where G_t = (V_t, E_t, X_t)

Each snapshot G_t is a full graph at time t. Between snapshots, changes are not tracked — only the state at each observation.

Modelling approach: run a GNN on each snapshot, then apply a temporal model (RNN/Transformer) across snapshots to capture evolution.

Examples:

  • Monthly snapshots of a social network
  • Daily transaction graphs in finance
  • Hourly traffic sensor graphs

Limitation: if events happen between snapshots, they are invisible. Finer snapshots increase resolution but increase computation.

Continuous-Time Dynamic Graphs (CTDG)

The graph is a stream of timestamped events:

E = {(u_i, v_i, t_i, f_i)}_{i=1}^{N}

Where each event is an edge (u_i, v_i) occurring at time t_i with optional features f_i. Nodes may also have state updates at specific times.

Modelling approach: maintain a memory state for each node, updated upon each interaction. Compute node embeddings on demand for any time t.

Examples:

  • Reddit posts (user posts to subreddit at timestamp)
  • Wikipedia edits (user edits page at timestamp)
  • E-commerce interactions (user clicks product at time)

Advantage over snapshots: exact timing information preserved; computation triggered by events (sparse updates).

Key Challenges

1. Evolving Structure

New edges and nodes arrive continuously. The model must incorporate new information without full retraining:

  • Transductive: all nodes known at training time
  • Inductive: new nodes appear at test time (requires generalising to unseen entities)

2. Temporal Dependencies

Events at time t may depend on events at t-k (historical context). Capturing long-range temporal dependencies while maintaining efficient updates is the core challenge.

3. Forgetting and Recency

Not all past events are equally relevant. A social interaction from 3 years ago matters less than one from last week. Models must balance memory capacity with relevance weighting.

The memory bottleneck: Naive CTDG models replay all past events to compute current node states — O(history) per query. TGN and similar architectures solve this with fixed-size memory modules that summarise history efficiently, analogous to how LSTMs summarise sequence history in a fixed hidden state.

DTDG vs CTDG: Practical Trade-offs

PropertyDTDG (Snapshots)CTDG (Event Stream)
Temporal resolutionCoarse (snapshot intervals)Fine (exact timestamps)
Modelling complexityGNN + sequence modelEvent-driven memory
ComputationPer snapshot (batched)Per event (online)
Handles new nodesRetrain or fine-tuneNaturally inductive
Memory of historyImplicit in sequence modelExplicit memory module
Use casesRegular-interval dataIrregular event data

Standard Benchmarks

CTDG benchmarks:

  • Wikipedia: 9227 nodes, 157474 interaction events
  • Reddit: 10984 nodes, 672447 interaction events
  • MOOC: student-course interactions with timestamps
  • LastFM: user-song interactions (music streaming)

DTDG benchmarks:

  • Bitcoin-OTC / Bitcoin-Alpha: trust ratings over time
  • DBLP co-authorship: yearly snapshots
  • Yelp reviews: monthly snapshots

Summary

ConceptDefinition
Static graphFixed (V, E, X) — standard GNN setting
Snapshot graphSeries G_1, …, G_T of static graphs
Event streamOrdered sequence of timestamped interactions
InductiveGeneralises to nodes not seen during training
Memory moduleFixed-size state capturing interaction history

Dynamic graph learning adds the temporal dimension to all GNN tasks: link prediction becomes “will u and v interact in the future?”, node classification becomes “what is v’s state now?”, and graph-level tasks must account for structural evolution. The field is rapidly developing, with TGN as the current dominant framework for CTDG.

References

You May Also Enjoy

Open Problems and Future Directions in Sheaf Neural Networks

5 minute read

Published:

Sheaf Neural Networks are a young field with many open research problems. This post surveys the most important unsolved questions: scalability to million-node graphs, stochastic sheaves for uncertainty quantification, sheaf autoencoders for generative models, connections to persistent homology, and unification with other topological deep learning frameworks.

Sheaf GNNs for Molecular Property Prediction

7 minute read

Published:

Molecular graphs are naturally heterophilic — atoms of different types bonded together — and have rich geometric structure (bond angles, torsion angles). Sheaf GNNs can encode this structure via restriction maps that represent the relational geometry between bonded atoms. This post explores how sheaf theory applies to molecular property prediction.

Sheaf GNNs for Heterophilic Node Classification: Benchmarks and Results

6 minute read

Published:

A systematic comparison of sheaf GNNs against baselines on standard heterophilic node classification benchmarks. Which datasets benefit most from sheaf structure? How does stalk dimension d affect performance? When do sheaves win — and when don’t they?

Sheaves Meet Attention: Transformer-Inspired Sheaf Models

6 minute read

Published:

Graph Transformers use global attention to capture long-range dependencies that local message passing misses. Sheaf Transformers combine sheaf-based local aggregation (with learnable relational geometry) with global attention (for long-range dependencies). This post surveys the design space of sheaf-augmented attention models.