In [ ]:

import marimo as mo

import marimo as mo

Temporal Graph Analysis¶

Prerequisites¶

First, we need to set up our Python environment that has PyTorch, PyTorch Geometric and PathpyG installed. Depending on where you are executing this notebook, this might already be (partially) done. E.g. Google Colab has PyTorch installed by default so we only need to install the remaining dependencies. The DevContainer that is part of our GitHub Repository on the other hand already has all of the necessary dependencies installed.

In the following, we install the packages for usage in Google Colab using Jupyter magic commands. For other environments comment in or out the commands as necessary. For more details on how to install pathpyG especially if you want to install it with GPU-support, we refer to our documentation. Note that %%capture discards the full output of the cell to not clutter this tutorial with unnecessary installation details. If you want to print the output, you can comment %%capture out.

In [ ]:

# magic command not supported in marimo; please file an issue to add support
# %%capture
# # !pip install torch
# # !pip install torch_geometric
# # !pip install git+https://github.com/pathpy/pathpyG.git

# magic command not supported in marimo; please file an issue to add support # %%capture # # !pip install torch # # !pip install torch_geometric # # !pip install git+https://github.com/pathpy/pathpyG.git

Motivation and Learning Objectives¶

In this tutorial we will introduce the representation of temporal graph data using the TemporalGraph class. We show how we can create temporal graphs, restrict them to time windows, aggregate them to static graphs, and read and write temporal graph data.

In [ ]:

import os
import tempfile

import pandas as pd
import torch
from torch_geometric.data import Data

import pathpyG as pp

import os import tempfile import pandas as pd import torch from torch_geometric.data import Data import pathpyG as pp

We can create a temporal graph object from a list of time-stamped edges. Since TemporalGraph is a subclass of the Graph class, the internal structures are very similar:

In [ ]:

_tedges = [('a', 'b', 1), ('a', 'b', 2), ('b', 'a', 3), ('b', 'c', 3), ('d', 'c', 4), ('a', 'b', 4), ('c', 'b', 4), ('c', 'd', 5), ('b', 'a', 5), ('c', 'b', 6)]
t = pp.TemporalGraph.from_edge_list(_tedges)
print(t.mapping)
print(t.n)
print(t.m)

_tedges = [('a', 'b', 1), ('a', 'b', 2), ('b', 'a', 3), ('b', 'c', 3), ('d', 'c', 4), ('a', 'b', 4), ('c', 'b', 4), ('c', 'd', 5), ('b', 'a', 5), ('c', 'b', 6)] t = pp.TemporalGraph.from_edge_list(_tedges) print(t.mapping) print(t.n) print(t.m)

a -> 0
b -> 1
c -> 2
d -> 3

4
10

By default, all temporal graphs are directed. We can create an undirected version a temporal graph as follows:

In [ ]:

x = t.to_undirected()
print(x.mapping)
print(x.n)
print(x.m)

x = t.to_undirected() print(x.mapping) print(x.n) print(x.m)

a -> 0
b -> 1
c -> 2
d -> 3

4
20

We can also directly create a temporal graph from a pyG Data object that has an edge_index and a time tensor

In [ ]:

td = Data(edge_index=torch.Tensor([[0, 1, 2, 0], [1, 2, 3, 1]]).long(), time=torch.Tensor([0, 1, 2, 3]), num_nodes=4)
print(td)
t2 = pp.TemporalGraph(td)
print(t2)

td = Data(edge_index=torch.Tensor([[0, 1, 2, 0], [1, 2, 3, 1]]).long(), time=torch.Tensor([0, 1, 2, 3]), num_nodes=4) print(td) t2 = pp.TemporalGraph(td) print(t2)

Data(edge_index=[2, 4], time=[4], num_nodes=4)
Temporal Graph with 4 nodes, 3 unique edges and 4 events in [0.0, 3.0]
{'Edge Attributes': {}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}

We can restrict a temporal graph to a time window, which returns a temporal graph that only contains time-stamped edges in the given time interval.

In [ ]:

_t1 = t.get_window(0, 4)
print(_t1)
print(_t1.m)
print(_t1.start_time)
print(_t1.end_time)

_t1 = t.get_window(0, 4) print(_t1) print(_t1.m) print(_t1.start_time) print(_t1.end_time)

Temporal Graph with 4 nodes, 3 unique edges and 4 events in [1, 3]
{'Edge Attributes': {}, 'Graph Attributes': {}, 'Node Attributes': {}}
4
1
3

We can also extract a TemporalGraph object for a batch of temporal edges, which is defined by the start and end index of the edges defining the batch.

In [ ]:

_t1 = t.get_batch(1, 6)
print(_t1)
print(_t1.m)
print(_t1.start_time)
print(_t1.end_time)

_t1 = t.get_batch(1, 6) print(_t1) print(_t1.m) print(_t1.start_time) print(_t1.end_time)

Temporal Graph with 4 nodes, 4 unique edges and 5 events in [2, 4]
{'Edge Attributes': {}, 'Graph Attributes': {}, 'Node Attributes': {}}
5
2
4

We can easily convert a temporal graph into a weighted time-aggregated static graph, where edge weights count the number of occurrences of an edge across all timestamps.

In [ ]:

_g = t.to_static_graph(weighted=True)
print(_g)

_g = t.to_static_graph(weighted=True) print(_g)

Directed graph with 4 nodes and 6 edges
{'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([6])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}

We can also aggregate a temporal graph within a certain time window:

In [ ]:

_g = t.to_static_graph(time_window=(1, 3), weighted=True)
print(_g)

_g = t.to_static_graph(time_window=(1, 3), weighted=True) print(_g)

Directed graph with 2 nodes and 1 edges
{'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([1])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}

Finally, we can use the class RollingTimeWindow to perform a rolling window analysis. The class returns an iterable object, where each iteration yields a time-aggregated weighted graph object as well as the corresponding time window.

In [ ]:

r = pp.algorithms.RollingTimeWindow(t, window_size=3, step_size=1, return_window=True)
for _g, _w in r:
    print('Time window ', _w)
    print(_g)
    print(_g.data.edge_index)
    print('---')

r = pp.algorithms.RollingTimeWindow(t, window_size=3, step_size=1, return_window=True) for _g, _w in r: print('Time window ', _w) print(_g) print(_g.data.edge_index) print('---')

Time window  (1, 4)
Directed graph with 3 nodes and 3 edges
{'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([3])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
EdgeIndex([[0, 1, 1],
           [1, 0, 2]], sparse_size=(3, 3), nnz=3, sort_order=row)
---
Time window  (2, 5)
Directed graph with 4 nodes and 5 edges
{'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([5])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
EdgeIndex([[0, 1, 1, 2, 3],
           [1, 0, 2, 1, 2]], sparse_size=(4, 4), nnz=5, sort_order=row)
---
Time window  (3, 6)
Directed graph with 4 nodes and 6 edges
{'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([6])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
EdgeIndex([[0, 1, 1, 2, 2, 3],
           [1, 0, 2, 1, 3, 2]], sparse_size=(4, 4), nnz=6, sort_order=row)
---
Time window  (4, 7)
Directed graph with 4 nodes and 5 edges
{'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([5])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
EdgeIndex([[0, 1, 2, 2, 3],
           [1, 0, 1, 3, 2]], sparse_size=(4, 4), nnz=5, sort_order=row)
---
Time window  (5, 8)
Directed graph with 4 nodes and 3 edges
{'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([3])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
EdgeIndex([[1, 2, 2],
           [0, 1, 3]], sparse_size=(4, 4), nnz=3, sort_order=row)
---
Time window  (6, 9)
Directed graph with 3 nodes and 1 edges
{'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([1])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
EdgeIndex([[2],
           [1]], sparse_size=(3, 3), nnz=1, sort_order=row)
---

We can visualize temporal graphs using the plot function just like static graphs:

In [ ]:

pp.plot(t);

pp.plot(t);

The source nodes, destination nodes and timestamps of time-stamped edges are stored in a pyG Data object with an edge_index and a time tensor, which we can access in the following way.

In [ ]:

t.data

t.data

Data(edge_index=[2, 10], time=[10], num_nodes=4)

In [ ]:

print(t.data.edge_index)

print(t.data.edge_index)

EdgeIndex([[0, 0, 1, 1, 3, 0, 2, 2, 1, 2],
           [1, 1, 0, 2, 2, 1, 1, 3, 0, 1]], sparse_size=(4, 4), nnz=10)

In [ ]:

print(t.data.time)

print(t.data.time)

tensor([1, 2, 3, 3, 4, 4, 4, 5, 5, 6])

With the generator functions edges and temporal_edges we can iterate through the time-ordered (temporal) multi-edges of a temporal graph.

In [ ]:

for _v, _w in t.edges:
    print(_v, _w)

for _v, _w in t.edges: print(_v, _w)

a b
a b
b a
b c
d c
a b
c b
c d
b a
c b

In [ ]:

for _v, _w, time in t.temporal_edges:
    print(_v, _w, time)

for _v, _w, time in t.temporal_edges: print(_v, _w, time)

a b 1
a b 2
b a 3
b c 3
d c 4
a b 4
c b 4
c d 5
b a 5
c b 6

Reading and writing temporal graph data¶

Similar to simple graphs, we can read and write temporal graph data into various common formats. For example, we can easily convert our temporal graph to a Pandas DataFrame using the temporal_graph_to_df function and create a temporal graph from a DataFrame using the df_to_temporal_graph function:

In [ ]:

_tedges = [('a', 'b', 1), ('a', 'b', 2), ('b', 'a', 3), ('b', 'c', 3), ('d', 'c', 4), ('a', 'b', 4), ('c', 'b', 4), ('c', 'd', 5), ('b', 'a', 5), ('c', 'b', 6)]
t_1 = pp.TemporalGraph.from_edge_list(_tedges)
df = pp.io.temporal_graph_to_df(t_1)
print(df)

_tedges = [('a', 'b', 1), ('a', 'b', 2), ('b', 'a', 3), ('b', 'c', 3), ('d', 'c', 4), ('a', 'b', 4), ('c', 'b', 4), ('c', 'd', 5), ('b', 'a', 5), ('c', 'b', 6)] t_1 = pp.TemporalGraph.from_edge_list(_tedges) df = pp.io.temporal_graph_to_df(t_1) print(df)

   v  w  t
0  a  b  1
1  a  b  2
2  b  a  3
3  b  c  3
4  d  c  4
5  a  b  4
6  c  b  4
7  c  d  5
8  b  a  5
9  c  b  6

In [ ]:

t_2 = pp.io.df_to_temporal_graph(df)
print(t_2)

t_2 = pp.io.df_to_temporal_graph(df) print(t_2)

Temporal Graph with 4 nodes, 6 unique edges and 10 events in [1, 6]
{'Edge Attributes': {}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}

In [ ]:

with tempfile.TemporaryDirectory() as tmpdirname:
    print('created temporary directory', tmpdirname)
    tmp_file = os.path.join(tmpdirname, 'test_graph.csv')
    pp.io.write_csv(t_2, path_or_buf=tmp_file)
    csv_t = pp.io.read_csv_temporal_graph(filename=tmp_file)
pp.plot(csv_t);

with tempfile.TemporaryDirectory() as tmpdirname: print('created temporary directory', tmpdirname) tmp_file = os.path.join(tmpdirname, 'test_graph.csv') pp.io.write_csv(t_2, path_or_buf=tmp_file) csv_t = pp.io.read_csv_temporal_graph(filename=tmp_file) pp.plot(csv_t);

created temporary directory /tmp/tmpsidj3c8f

If the columns of a DataFrame are not named, df_to_temporal_graph assumes that the first three columns contain the source node, target node, and timestamp of each time-stamped edge:

In [ ]:

df_1 = pd.DataFrame([['a', 'b', 1], ['b', 'c', 2], ['a', 'c', 3]])
print(df_1)
t_3 = pp.io.df_to_temporal_graph(df_1)
print(t_3)

df_1 = pd.DataFrame([['a', 'b', 1], ['b', 'c', 2], ['a', 'c', 3]]) print(df_1) t_3 = pp.io.df_to_temporal_graph(df_1) print(t_3)

   0  1  2
0  a  b  1
1  b  c  2
2  a  c  3
Temporal Graph with 3 nodes, 3 unique edges and 3 events in [1, 3]
{'Edge Attributes': {}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}

The real power of temporal graphs comes into play when we consider time-respecting paths, i.e. paths that follow the temporal ordering of time-stamped edges. We introduce time-respecting paths, as well as temporal centralities and communities that build on them, in the tutorial Time-Respecting Paths, Centralities and Communities.