Dynamic graph embedding

Overview

A dynamic graph embedding maps the nodes of a graph that changes over time to vectors, so that similar nodes stay close as the graph evolves 2204.01855 §2.1 §3.2. The input comes in one of two forms. A discrete-time graph is a sequence of snapshots, one graph per time step. A continuous-time graph is a stream of timed events, such as an edge that appears at a given moment 2204.01855 §3.2.

The two forms are not interchangeable. Converting a stream into snapshots, or the reverse, changes what a model can see 2204.01855 §3.2. A method should therefore be picked for the form the data already has.

Two surveys are the sources for this page. The dynamic-graph survey splits the field into traditional (non-GNN) methods and GNN-based methods, and each family into static and dynamic settings 2204.01855 §1. The variants below follow that split. The general graph-learning survey covers the topic only in passing, under random walks and spatial-temporal networks [arxiv:2105.00696 §2.3.4] §2.4.5. Neither survey gives experiments, so the variants are not ranked against each other here.

Variants

Aggregation over snapshots

Collapse the snapshots into one static graph, for example by summing or weighting their adjacency matrices, and embed that graph with a static method. Alternatively, embed each snapshot separately and combine the vectors over time, for example with a time-series model. Factorising a node-by-node-by-time tensor also belongs here 2204.01855 §3.2.1. The time order is lost in the first form and only partly kept in the second.

Temporal random walks

Walks are generated over the timed edges. CTDNE only follows edges whose timestamps do not decrease along the walk. EvoNRL updates its walks when edges change. DynNode2vec initialises node2vec from the snapshots [arxiv:2204.01855 §3.2.2] eq. 9. The walks are then fed to a skip-gram model, as in static random-walk embedding 2204.01855 §3.1.2. The general graph-learning survey also files time-varying network embedding under random-walk methods, but names no specific method there 2105.00696 §2.3.4.

Warm-started autoencoders (non-GNN deep learning)

Each snapshot's autoencoder starts from the weights of the previous snapshot, which the survey gives as the DynGEM approach 2204.01855 §3.2.3. Dyn-VGAE adds a penalty that keeps the latent variables of consecutive snapshots close 2204.01855 §3.2.3 eq. 10. dyngraph2vec instead encodes a window of past adjacency matrices 2204.01855 §3.2.3.

Temporal point processes

These model when new links form. HTNE uses a Hawkes process over a node's history of neighbours 2204.01855 §3.2.4 eq. 11 eq. 12. DyRep separates two kinds of event, communication and association, with two processes 2204.01855 §3.2.4. MTNE adds motif-based neighbourhoods 2204.01855 §3.2.4.

Triad closure (DynamicTriad)

DynamicTriad models how open triads close over time. It adds a homophily term and a temporal-smoothness term to its objective 2204.01855 §3.2.5.

Dynamic and spatio-temporal GNNs

Graph neural networks extended to time. Spatio-temporal models combine graph convolution with recurrent or temporal-convolution layers. They are applied to traffic, epidemic and sleep-stage forecasting 2204.01855 §4.3. Dynamic GNNs for event streams include TGAT, which adds a learned time encoding to graph attention, CAW-N, which scores links with causal anonymous walks, and MTSN, which combines motif encoding with a temporal shift [arxiv:2204.01855 §4.4]. Streaming GNNs train on changes as they arrive 2204.01855 §4.4. The general graph-learning survey lists spatial-temporal networks as one of its deep-learning families 2105.00696 §2.4.5. The general GNN basics this rests on are in 2204.01855 §4.1 and graph-neural-network.

When to use which

Pick by the form of the input and the output you need. The survey does not measure any of these trade-offs, so the rows state what each family can and cannot represent.

Implementation sketch

Two common patterns, both from the survey's taxonomy. The first is for timed events, the second for snapshots. The survey does not give the sampling rule for each walk method, so the choice step is marked open.

# Temporal random walk over timed edges  [§3.2.2]
# Input:  edges_by_node[u] = list of (v, t) sorted by t; walk length L
# Output: a walk whose edge times never decrease

def temporal_walk(start, edges_by_node, L):
    # 1. Start at the node of interest with no time bound yet  [§3.2.2]
    walk, t_last = [start], -inf
    for _ in range(L - 1):
        # 2. Keep only edges not earlier than the last one used  [§3.2.2]
        options = [(v, t) for (v, t) in edges_by_node[walk[-1]]
                   if t >= t_last]
        if not options:
            break
        # 3. Choose the next edge; the rule differs per method  [§3.2.2]
        v, t_last = choose(options)
        walk.append(v)
    return walk

# Warm-started embedding over snapshots  [§3.2.3]
# Input:  snapshots A_1..A_T (adjacency matrices); embedding dim d
# Output: one embedding matrix per snapshot

def embed_snapshots(snapshots, d):
    # 1. No model exists before the first snapshot  [§3.2.3]
    model, outputs = None, []
    for A_t in snapshots:
        # 2. Start from the previous snapshot's weights  [§3.2.3]
        model = fit_autoencoder(A_t, d, init=model)
        outputs.append(model.encode(A_t))
    return outputs

Contradictions

The two surveys do not disagree on any method. Within the general graph-learning survey, the open-issues section says dynamic graph learning has rarely been studied, while its random-walk section reviews time-varying network embedding. The card itself calls the wording loose 2105.00696 §4 §2.3.4. Within the dynamic-graph survey, the notation for the HTNE base rate and influence is unclear, and the factorization loss uses absolute rather than squared differences 2204.01855 §3.1.1 §3.2.4. Check the original method papers before implementing either.

Papers

• A Survey on Graph Representation Learning Methods: taxonomy of static and dynamic graph embedding, traditional and GNN-based, with nine GNN limitations and their proposed fixes.
• Graph Learning: A Survey: general map of graph learning in four families; touches time-varying embedding and spatial-temporal networks, with no experiments.