import marimo as mo
Higher-Order Models for Time-Respecting Paths in Temporal Graphs¶
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.
# 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 the tutorial on paths and higher-order models, we have seen how we can use higher-order models to model paths in complex networks. In this example, paths were directly given in terms of sequences of nodes traversed by some process (like a random walk). We have further seen that higher-order De Bruijn graph models can be used to capture patterns that influence the causal topology of a complex network, i.e. which nodes can possibly influence each other via paths. The same is true for time-respecting paths in a temporal graph. Due to the fact that time-stamped edges need to occur in the correct temporal ordering (and within a given time interval based on the maximum time difference $\delta$), the causal topology given by time-respecting paths can be very different from what we would expect from the (static) topology of links.
In the following, we will show how we can easily and efficiently construct higher-order models for time-respecting paths in a temporal graph. To illustrate this, we use the same toy example as in Time-Respecting Paths, Centralities and Communities:
import pathpyG as pp
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)
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 Time-Respecting Paths, Centralities and Communities, we have used a directed acyclic event graph to enumerate all time-respecting paths in this temporal graph. For $\delta=1$, there are six different time-respecting paths of length one (i.e. the six edges), six different time-respecting paths of length two (where $a \rightarrow b \rightarrow a$ occurs twice), four time-respecting paths of length three, and two time-respecting paths of length four.
As you can see, these time-respecting paths are actually very similar to the paths data that we have previously represented using the PathData object. In fact, we could - in theory - first extract all time-respecting paths of all lengths, add them to a PathData object and then use the MultiOrderModel class to generate higher-order De Bruijn graph models of all orders. In the example above, since we have paths of length one to four, we could create higher-order models with orders from one to four.
However, this approach would not be efficient for large temporal graphs, as it is computationally expensive to calculate all possible time-respecting paths as well as subpaths of length $k$, especially for larger values of $\delta$. To avoid this bottleneck, pathpyG uses a smarter, GPU-based algorithm to calculate time-respecting paths of length $k$ that are needed for a given order $k$, starting from the event graph introduced in Event Graphs.
For the example above, we can generate all higher-order models up to order four as follows:
m = pp.MultiOrderModel.from_temporal_graph(t, delta=1, max_order=4)
print(m.layers[3])
print(m.layers[4])
0%| | 0/6 [00:00<?, ?it/s] 100%|██████████| 6/6 [00:00<00:00, 2592.81it/s]
Higher-order graph of order 3 with 6 nodes and 4 edges
(over 4 first-order nodes)
{ 'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([4])"},
'Graph Attributes': {'inverse_idx': "<class 'torch.Tensor'> -> torch.Size([7])", 'num_nodes': "<class 'int'>"},
'Node Attributes': {}}
Higher-order graph of order 4 with 4 nodes and 2 edges
(over 4 first-order nodes)
{'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([2])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
Each layer m.layers[k] is a HigherOrderGraph, which we have introduced in Working with Higher-Order De Bruijn Graphs. This is why printing a layer shows its order as well as the number of first-order nodes from which its higher-order nodes are built. Remember that in a $k$-th order model nodes capture paths of length $k-1$, while edges capture paths of length $k$.
This implies that the first-order model has four nodes and six edges, which simply corresponds to the time-aggregated weighted graph for our example temporal network.
print(m.layers[1])
pp.plot(m.layers[1]);
Higher-order graph of order 1 with 4 nodes and 6 edges
(over 4 first-order nodes)
{'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([6])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
For the second-order model, we have six nodes, which map to the six different edges (each edge trivially being a time-respecting path of length one) of the temporal graph. The six edges in the second-order model represent the six different time-respecting paths of length two (see above). Since the time-respecting path $a \rightarrow b \rightarrow a$ occurs twice at different times, we have one edge with weight two.
print(m.layers[2])
print(m.layers[2].data.edge_weight)
pp.plot(m.layers[2]);
Higher-order graph of order 2 with 6 nodes and 6 edges
(over 4 first-order nodes)
{ 'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([6])"},
'Graph Attributes': {'inverse_idx': "<class 'torch.Tensor'> -> torch.Size([10])", 'num_nodes': "<class 'int'>"},
'Node Attributes': {}}
tensor([2., 1., 1., 1., 1., 1.])
For the third-oder mode, we have four edges representing the four different time-respecting paths of length three in the temporal graph above:
print(m.layers[3])
pp.plot(m.layers[3]);
Higher-order graph of order 3 with 6 nodes and 4 edges
(over 4 first-order nodes)
{ 'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([4])"},
'Graph Attributes': {'inverse_idx': "<class 'torch.Tensor'> -> torch.Size([7])", 'num_nodes': "<class 'int'>"},
'Node Attributes': {}}
And finally, for the model with order $k=4$ we only have two edges, representing the two time-respecting paths $a \rightarrow b \rightarrow a \rightarrow b \rightarrow a$ and $a \rightarrow b \rightarrow c \rightarrow b \rightarrow a$:
print(m.layers[4])
pp.plot(m.layers[4]);
Higher-order graph of order 4 with 4 nodes and 2 edges
(over 4 first-order nodes)
{'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([2])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
Intuitively, since in our example there are no time-respecting paths longer than four, if we were to generate a multi-order model with De Bruijn graphs with orders larger than four, those graphs cannot contain any edges. We see this in the following example. The first-order graph is simply the time-aggregated weighted graph, i.e. the number of nodes is equal to the number of nodes in the temporal graph and the number of edges is equal to the number of different time-stamped edges. In each graph of order $k>1$, the number of nodes corresponds to the number of edges in the graph with order $k-1$, since each of those nodes corresponds to a time-respecting path of length $k-1$, which are represented by edges in a $k-1$-th order graph. This implies that the graph with order five has two nodes, which are the two time-respecting paths of length four. Those nodes are not connected since there is no time-respecting path with length five.
m_1 = pp.MultiOrderModel.from_temporal_graph(t, delta=1, max_order=5)
print(m_1.layers[4])
print(m_1.layers[5])
pp.plot(m_1.layers[5]);
0%| | 0/6 [00:00<?, ?it/s] 100%|██████████| 6/6 [00:00<00:00, 8224.13it/s]
Higher-order graph of order 4 with 4 nodes and 2 edges
(over 4 first-order nodes)
{'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([2])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
Higher-order graph of order 5 with 2 nodes and 0 edges
(over 4 first-order nodes)
{'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([0])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
If we only need a single order $k$, we can directly create the corresponding HigherOrderGraph using the class method HigherOrderGraph.from_temporal_graph. Note that each call constructs all lower orders internally, so if we need several orders, it is more efficient to create a MultiOrderModel once and access its layers. For the third-order model of our example, we obtain the six different time-respecting paths of length two as nodes and the four time-respecting paths of length three as edges:
g3 = pp.HigherOrderGraph.from_temporal_graph(t, order=3, delta=1)
print(g3)
print(g3.nodes)
0%| | 0/6 [00:00<?, ?it/s] 100%|██████████| 6/6 [00:00<00:00, 8402.61it/s]
Higher-order graph of order 3 with 6 nodes and 4 edges
(over 4 first-order nodes)
{ 'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([4])"},
'Graph Attributes': {'inverse_idx': "<class 'torch.Tensor'> -> torch.Size([7])", 'num_nodes': "<class 'int'>"},
'Node Attributes': {}}
[('a', 'b', 'a'), ('a', 'b', 'c'), ('b', 'a', 'b'), ('b', 'c', 'b'), ('c', 'b', 'a'), ('d', 'c', 'd')]
Constructing Higher-Order De Bruijn Graph Models for Empirical Temporal Networks¶
Let us now use pathpyG to construct higher-order De Bruijn graph models for time-respecting paths in empirical temporal networks. For this, we first read a number of temporal graphs using pp.io.read_csv_temporal_graph. In the following, we use the following three publicly available data sets:
- Antenna interactions between ants in a colony (Blonder and Dornhaus, 2011)
- E-Mail exchanges in a manufacturing company (Nurek and Michalski, 2020)
- Face-to-face interactions in a highschool (Mastrandrea, Fournet, Barrat, 2015)
t_ants = pp.io.read_csv_temporal_graph(pp.io.example_data('ants_1_1.tedges'), header=False)
print(t_ants)
Temporal Graph with 89 nodes, 947 unique edges and 1911 events in [0, 1438]
{ 'Edge Attributes': {'edge_attr_1': "<class 'torch.Tensor'> -> torch.Size([1911])", 'edge_attr_2': "<class 'torch.Tensor'> -> torch.Size([1911])"},
'Graph Attributes': {'num_nodes': "<class 'int'>"},
'Node Attributes': {}}
t_email = pp.io.read_csv_temporal_graph(pp.io.example_data('manufacturing_email.tedges'), header=False)
print(t_email)
Temporal Graph with 167 nodes, 5784 unique edges and 82614 events in [0, 23430482000000]
{'Edge Attributes': {}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
t_sp = pp.io.read_csv_temporal_graph(pp.io.example_data('sociopatterns_highschool_2013.tedges'), header=False)
print(t_sp)
Temporal Graph with 327 nodes, 5818 unique edges and 188508 events in [1385982020, 1386345580]
{ 'Edge Attributes': {'edge_attr_1': "<class 'numpy.ndarray'>", 'edge_attr_2': "<class 'numpy.ndarray'>"},
'Graph Attributes': {'num_nodes': "<class 'int'>"},
'Node Attributes': {}}
To generate a MultiOrderModel consisting of multiple layers of higher-order De Bruijn graph models, we can use the MultiOrderModel.from_temporal_graph method. We can further specify the maximum order of the highest-order layer, as well as the maximum time difference $\delta$ for time-respecting paths.
For the ants, we consider time-respecting paths with a maximum time difference of 30 seconds up to length four. Since we want to compare this to a smaller maximum time difference of 20 seconds below, we first construct an EventGraph (see Event Graphs), from which we can create a MultiOrderModel using MultiOrderModel.from_event_graph:
# Hide the progress output
with mo.capture_stdout(), mo.capture_stderr():
eg_ants = pp.EventGraph.from_temporal_graph(t_ants, delta=30)
m_2 = pp.MultiOrderModel.from_event_graph(eg_ants, max_order=4)
print(m_2.layers[1])
print(m_2.layers[2])
print(m_2.layers[3])
print(m_2.layers[4])
Higher-order graph of order 1 with 89 nodes and 947 edges
(over 89 first-order nodes)
{'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([947])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
Higher-order graph of order 2 with 947 nodes and 1780 edges
(over 89 first-order nodes)
{ 'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([1780])"},
'Graph Attributes': {'inverse_idx': "<class 'torch.Tensor'> -> torch.Size([1911])", 'num_nodes': "<class 'int'>"},
'Node Attributes': {}}
Higher-order graph of order 3 with 1780 nodes and 2410 edges
(over 89 first-order nodes)
{ 'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([2410])"},
'Graph Attributes': {'inverse_idx': "<class 'torch.Tensor'> -> torch.Size([2518])", 'num_nodes': "<class 'int'>"},
'Node Attributes': {}}
Higher-order graph of order 4 with 2410 nodes and 3292 edges
(over 89 first-order nodes)
{ 'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([3292])"},
'Graph Attributes': {'inverse_idx': "<class 'torch.Tensor'> -> torch.Size([3572])", 'num_nodes': "<class 'int'>"},
'Node Attributes': {}}
Rather than constructing the time-respecting paths for a maximum time difference of 20 seconds from scratch, we can reduce the maximum time difference of the existing event graph. The resulting higher-order models have fewer edges, since fewer pairs of interactions are close enough in time to form a time-respecting path:
m_2_20 = pp.MultiOrderModel.from_event_graph(eg_ants.reduce_delta(10), max_order=4)
print(m_2_20.layers[2])
print(m_2_20.layers[4])
Higher-order graph of order 2 with 947 nodes and 1372 edges
(over 89 first-order nodes)
{ 'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([1372])"},
'Graph Attributes': {'inverse_idx': "<class 'torch.Tensor'> -> torch.Size([1911])", 'num_nodes': "<class 'int'>"},
'Node Attributes': {}}
Higher-order graph of order 4 with 1410 nodes and 1434 edges
(over 89 first-order nodes)
{ 'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([1434])"},
'Graph Attributes': {'inverse_idx': "<class 'torch.Tensor'> -> torch.Size([1849])", 'num_nodes': "<class 'int'>"},
'Node Attributes': {}}
For the E-Mail communication network, we use time-respecting paths up to length four with a maximum time difference of one hour. Note that the timestamps in this data set are given in microseconds rather than seconds, so we scale $\delta$ accordingly.
m_3 = pp.MultiOrderModel.from_temporal_graph(t_email, delta=3600 * 1000000, max_order=4)
print(m_3.layers[1])
print(m_3.layers[2])
print(m_3.layers[3])
print(m_3.layers[4])
0%| | 0/57842 [00:00<?, ?it/s] 0%| | 212/57842 [00:00<00:27, 2119.64it/s] 1%| | 593/57842 [00:00<00:18, 3113.10it/s] 2%|▏ | 905/57842 [00:00<00:20, 2727.85it/s] 2%|▏ | 1261/57842 [00:00<00:18, 3028.33it/s] 3%|▎ | 1763/57842 [00:00<00:15, 3706.40it/s] 4%|▍ | 2226/57842 [00:00<00:13, 4006.98it/s] 5%|▍ | 2708/57842 [00:00<00:12, 4265.47it/s] 5%|▌ | 3167/57842 [00:00<00:12, 4365.92it/s] 6%|▋ | 3673/57842 [00:00<00:11, 4577.72it/s] 7%|▋ | 4191/57842 [00:01<00:11, 4759.68it/s] 8%|▊ | 4669/57842 [00:01<00:11, 4486.21it/s] 9%|▉ | 5122/57842 [00:01<00:12, 4370.94it/s] 10%|▉ | 5563/57842 [00:01<00:12, 4308.65it/s] 10%|█ | 5997/57842 [00:01<00:12, 4283.21it/s] 11%|█ | 6427/57842 [00:01<00:12, 4260.27it/s] 12%|█▏ | 6854/57842 [00:01<00:12, 4075.14it/s] 13%|█▎ | 7264/57842 [00:01<00:15, 3254.14it/s] 13%|█▎ | 7618/57842 [00:01<00:15, 3323.95it/s] 14%|█▍ | 7971/57842 [00:02<00:17, 2921.55it/s] 14%|█▍ | 8386/57842 [00:02<00:15, 3218.42it/s] 15%|█▌ | 8812/57842 [00:02<00:14, 3485.87it/s] 16%|█▌ | 9180/57842 [00:02<00:13, 3533.01it/s] 17%|█▋ | 9548/57842 [00:02<00:16, 3014.74it/s] 17%|█▋ | 9872/57842 [00:02<00:17, 2748.94it/s] 18%|█▊ | 10169/57842 [00:02<00:17, 2801.05it/s] 18%|█▊ | 10591/57842 [00:02<00:14, 3164.51it/s] 19%|█▉ | 11014/57842 [00:03<00:13, 3450.31it/s] 20%|█▉ | 11442/57842 [00:03<00:12, 3680.16it/s] 21%|██ | 11873/57842 [00:03<00:11, 3858.40it/s] 21%|██ | 12269/57842 [00:03<00:12, 3788.73it/s] 22%|██▏ | 12655/57842 [00:03<00:12, 3608.55it/s] 23%|██▎ | 13055/57842 [00:03<00:12, 3715.57it/s] 23%|██▎ | 13467/57842 [00:03<00:11, 3829.13it/s] 24%|██▍ | 13879/57842 [00:03<00:11, 3910.63it/s] 25%|██▍ | 14274/57842 [00:03<00:11, 3918.23it/s] 25%|██▌ | 14669/57842 [00:03<00:11, 3880.15it/s] 26%|██▌ | 15059/57842 [00:04<00:11, 3829.27it/s] 27%|██▋ | 15491/57842 [00:04<00:10, 3971.76it/s] 27%|██▋ | 15905/57842 [00:04<00:10, 4020.69it/s] 28%|██▊ | 16324/57842 [00:04<00:10, 4068.85it/s] 29%|██▉ | 16751/57842 [00:04<00:09, 4125.75it/s] 30%|██▉ | 17184/57842 [00:04<00:09, 4184.54it/s] 30%|███ | 17608/57842 [00:04<00:09, 4198.66it/s] 31%|███ | 18034/57842 [00:04<00:09, 4216.86it/s] 32%|███▏ | 18463/57842 [00:04<00:09, 4236.70it/s] 33%|███▎ | 18892/57842 [00:04<00:09, 4251.41it/s] 33%|███▎ | 19319/57842 [00:05<00:09, 4254.51it/s] 34%|███▍ | 19745/57842 [00:05<00:08, 4243.74it/s] 35%|███▍ | 20176/57842 [00:05<00:08, 4262.14it/s] 36%|███▌ | 20603/57842 [00:05<00:08, 4256.03it/s] 36%|███▋ | 21029/57842 [00:05<00:08, 4235.68it/s] 37%|███▋ | 21456/57842 [00:05<00:08, 4243.32it/s] 38%|███▊ | 21881/57842 [00:05<00:08, 4231.94it/s] 39%|███▊ | 22305/57842 [00:05<00:08, 4162.82it/s] 39%|███▉ | 22722/57842 [00:05<00:08, 4097.73it/s] 40%|███▉ | 23133/57842 [00:06<00:08, 4025.22it/s] 41%|████ | 23536/57842 [00:06<00:08, 3992.25it/s] 41%|████▏ | 23936/57842 [00:06<00:08, 3979.99it/s] 42%|████▏ | 24335/57842 [00:06<00:08, 3965.29it/s] 43%|████▎ | 24740/57842 [00:06<00:08, 3987.96it/s] 43%|████▎ | 25139/57842 [00:06<00:08, 3829.41it/s] 44%|████▍ | 25524/57842 [00:06<00:08, 3711.89it/s] 45%|████▍ | 25897/57842 [00:06<00:08, 3606.23it/s] 45%|████▌ | 26260/57842 [00:06<00:08, 3612.36it/s] 46%|████▌ | 26623/57842 [00:06<00:08, 3532.52it/s] 47%|████▋ | 26977/57842 [00:07<00:09, 3411.52it/s] 47%|████▋ | 27320/57842 [00:07<00:08, 3404.72it/s] 48%|████▊ | 27662/57842 [00:07<00:09, 3023.02it/s] 48%|████▊ | 27972/57842 [00:07<00:10, 2909.05it/s] 49%|████▉ | 28269/57842 [00:07<00:12, 2438.26it/s] 49%|████▉ | 28536/57842 [00:07<00:11, 2492.28it/s] 50%|████▉ | 28810/57842 [00:07<00:11, 2555.10it/s] 50%|█████ | 29117/57842 [00:07<00:10, 2691.47it/s] 51%|█████ | 29395/57842 [00:08<00:10, 2666.02it/s] 51%|█████▏ | 29723/57842 [00:08<00:09, 2835.74it/s] 52%|█████▏ | 30034/57842 [00:08<00:09, 2912.07it/s] 53%|█████▎ | 30422/57842 [00:08<00:08, 3191.00it/s] 53%|█████▎ | 30770/57842 [00:08<00:08, 3275.37it/s] 54%|█████▍ | 31153/57842 [00:08<00:07, 3438.53it/s] 55%|█████▍ | 31545/57842 [00:08<00:07, 3579.64it/s] 55%|█████▌ | 31917/57842 [00:08<00:07, 3621.19it/s] 56%|█████▌ | 32281/57842 [00:08<00:07, 3331.30it/s] 56%|█████▋ | 32620/57842 [00:08<00:08, 3078.44it/s] 57%|█████▋ | 33004/57842 [00:09<00:07, 3283.73it/s] 58%|█████▊ | 33402/57842 [00:09<00:07, 3476.94it/s] 58%|█████▊ | 33757/57842 [00:09<00:06, 3465.42it/s] 59%|█████▉ | 34133/57842 [00:09<00:06, 3548.68it/s] 60%|█████▉ | 34512/57842 [00:09<00:06, 3616.40it/s] 60%|██████ | 34887/57842 [00:09<00:06, 3654.00it/s] 61%|██████ | 35255/57842 [00:09<00:07, 3055.57it/s] 62%|██████▏ | 35579/57842 [00:09<00:08, 2722.15it/s] 62%|██████▏ | 35869/57842 [00:10<00:08, 2548.21it/s] 62%|██████▏ | 36137/57842 [00:10<00:08, 2438.61it/s] 63%|██████▎ | 36389/57842 [00:10<00:09, 2330.74it/s] 63%|██████▎ | 36628/57842 [00:10<00:09, 2280.65it/s] 64%|██████▍ | 36949/57842 [00:10<00:08, 2519.90it/s] 64%|██████▍ | 37247/57842 [00:10<00:07, 2642.20it/s] 65%|██████▌ | 37638/57842 [00:10<00:06, 2994.56it/s] 66%|██████▌ | 38029/57842 [00:10<00:06, 3252.93it/s] 66%|██████▋ | 38361/57842 [00:10<00:06, 3184.06it/s] 67%|██████▋ | 38684/57842 [00:11<00:06, 3035.36it/s] 68%|██████▊ | 39058/57842 [00:11<00:05, 3231.51it/s] 68%|██████▊ | 39440/57842 [00:11<00:05, 3396.78it/s] 69%|██████▉ | 39809/57842 [00:11<00:05, 3480.31it/s] 70%|██████▉ | 40204/57842 [00:11<00:04, 3615.01it/s] 70%|███████ | 40601/57842 [00:11<00:04, 3717.94it/s] 71%|███████ | 40975/57842 [00:11<00:04, 3699.14it/s] 71%|███████▏ | 41347/57842 [00:11<00:04, 3614.89it/s] 72%|███████▏ | 41710/57842 [00:11<00:04, 3580.81it/s] 73%|███████▎ | 42069/57842 [00:12<00:05, 3011.84it/s] 73%|███████▎ | 42386/57842 [00:12<00:05, 2730.35it/s] 74%|███████▍ | 42772/57842 [00:12<00:05, 3010.00it/s] 75%|███████▍ | 43156/57842 [00:12<00:04, 3227.18it/s] 75%|███████▌ | 43493/57842 [00:12<00:04, 3143.16it/s] 76%|███████▌ | 43881/57842 [00:12<00:04, 3343.51it/s] 77%|███████▋ | 44279/57842 [00:12<00:03, 3520.37it/s] 77%|███████▋ | 44673/57842 [00:12<00:03, 3640.13it/s] 78%|███████▊ | 45043/57842 [00:12<00:03, 3437.44it/s] 78%|███████▊ | 45393/57842 [00:12<00:03, 3447.03it/s] 79%|███████▉ | 45801/57842 [00:13<00:03, 3627.64it/s] 80%|███████▉ | 46168/57842 [00:13<00:03, 2975.20it/s] 80%|████████ | 46487/57842 [00:13<00:04, 2746.20it/s] 81%|████████ | 46884/57842 [00:13<00:03, 3046.93it/s] 82%|████████▏ | 47268/57842 [00:13<00:03, 3253.14it/s] 82%|████████▏ | 47611/57842 [00:13<00:03, 3299.80it/s] 83%|████████▎ | 48011/57842 [00:13<00:02, 3492.87it/s] 84%|████████▎ | 48420/57842 [00:13<00:02, 3662.38it/s] 84%|████████▍ | 48803/57842 [00:14<00:02, 3708.44it/s] 85%|████████▌ | 49180/57842 [00:14<00:02, 3610.83it/s] 86%|████████▌ | 49546/57842 [00:14<00:02, 3556.28it/s] 86%|████████▋ | 49945/57842 [00:14<00:02, 3679.27it/s] 87%|████████▋ | 50328/57842 [00:14<00:02, 3719.71it/s] 88%|████████▊ | 50725/57842 [00:14<00:01, 3791.27it/s] 88%|████████▊ | 51111/57842 [00:14<00:01, 3808.22it/s] 89%|████████▉ | 51527/57842 [00:14<00:01, 3911.97it/s] 90%|████████▉ | 51920/57842 [00:14<00:01, 3831.74it/s] 90%|█████████ | 52341/57842 [00:14<00:01, 3942.44it/s] 91%|█████████ | 52761/57842 [00:15<00:01, 4016.48it/s] 92%|█████████▏| 53179/57842 [00:15<00:01, 4062.43it/s] 93%|█████████▎| 53597/57842 [00:15<00:01, 4095.08it/s] 93%|█████████▎| 54007/57842 [00:15<00:01, 3818.30it/s] 94%|█████████▍| 54393/57842 [00:15<00:00, 3451.66it/s] 95%|█████████▍| 54747/57842 [00:15<00:00, 3301.91it/s] 95%|█████████▌| 55147/57842 [00:15<00:00, 3487.52it/s] 96%|█████████▌| 55503/57842 [00:15<00:00, 3350.26it/s] 97%|█████████▋| 55876/57842 [00:15<00:00, 3453.33it/s] 97%|█████████▋| 56226/57842 [00:16<00:00, 3229.26it/s] 98%|█████████▊| 56555/57842 [00:16<00:00, 2767.76it/s] 98%|█████████▊| 56846/57842 [00:16<00:00, 2483.63it/s] 99%|█████████▊| 57107/57842 [00:16<00:00, 2311.90it/s] 99%|█████████▉| 57347/57842 [00:16<00:00, 2214.64it/s] 100%|█████████▉| 57574/57842 [00:16<00:00, 2151.40it/s] 100%|██████████| 57842/57842 [00:16<00:00, 3435.03it/s]
Higher-order graph of order 1 with 167 nodes and 5784 edges
(over 167 first-order nodes)
{'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([5784])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
Higher-order graph of order 2 with 5784 nodes and 26080 edges
(over 167 first-order nodes)
{ 'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([26080])"},
'Graph Attributes': {'inverse_idx': "<class 'torch.Tensor'> -> torch.Size([82614])", 'num_nodes': "<class 'int'>"},
'Node Attributes': {}}
Higher-order graph of order 3 with 26080 nodes and 50861 edges
(over 167 first-order nodes)
{ 'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([50861])"},
'Graph Attributes': {'inverse_idx': "<class 'torch.Tensor'> -> torch.Size([115555])", 'num_nodes': "<class 'int'>"},
'Node Attributes': {}}
Higher-order graph of order 4 with 50861 nodes and 77916 edges
(over 167 first-order nodes)
{ 'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([77916])"},
'Graph Attributes': {'inverse_idx': "<class 'torch.Tensor'> -> torch.Size([246097])", 'num_nodes': "<class 'int'>"},
'Node Attributes': {}}
And finally, for the largest data set from the Sociopatterns collaboration, we use a maximum time difference of 15 minutes. As you can see below, we can efficiently generate a 5-th order model despite using a temporal graph with more than 188,000 time-stamped edges and considering all time-respecting paths up to length five with a large maximum time difference. Thanks to the use of GPU-accelerated operations, creating such a model takes less than 12 seconds on an (old) RTX 2080 GPU.
m_4 = pp.MultiOrderModel.from_temporal_graph(t_sp, delta=900, max_order=5)
print(m_4.layers[1])
print(m_4.layers[5])
0%| | 0/7375 [00:00<?, ?it/s] 2%|▏ | 176/7375 [00:00<00:04, 1753.85it/s] 5%|▌ | 383/7375 [00:00<00:03, 1933.66it/s] 8%|▊ | 577/7375 [00:00<00:03, 1901.85it/s] 10%|█ | 773/7375 [00:00<00:03, 1924.41it/s] 13%|█▎ | 987/7375 [00:00<00:03, 1998.77it/s] 16%|█▌ | 1187/7375 [00:00<00:03, 1876.75it/s] 19%|█▊ | 1376/7375 [00:00<00:03, 1755.34it/s] 21%|██▏ | 1581/7375 [00:00<00:03, 1839.67it/s] 24%|██▍ | 1800/7375 [00:00<00:02, 1943.00it/s] 27%|██▋ | 1997/7375 [00:01<00:02, 1807.54it/s] 30%|██▉ | 2181/7375 [00:01<00:03, 1662.98it/s] 32%|███▏ | 2351/7375 [00:01<00:03, 1572.90it/s] 34%|███▍ | 2512/7375 [00:01<00:03, 1477.10it/s] 37%|███▋ | 2696/7375 [00:01<00:02, 1569.70it/s] 40%|███▉ | 2914/7375 [00:01<00:02, 1734.59it/s] 42%|████▏ | 3106/7375 [00:01<00:02, 1783.39it/s] 45%|████▌ | 3319/7375 [00:01<00:02, 1881.36it/s] 48%|████▊ | 3559/7375 [00:01<00:01, 2030.61it/s] 51%|█████▏ | 3786/7375 [00:02<00:01, 2100.15it/s] 55%|█████▍ | 4030/7375 [00:02<00:01, 2196.43it/s] 58%|█████▊ | 4252/7375 [00:02<00:01, 1603.24it/s] 60%|██████ | 4437/7375 [00:02<00:01, 1658.73it/s] 63%|██████▎ | 4622/7375 [00:02<00:01, 1682.78it/s] 65%|██████▌ | 4804/7375 [00:02<00:01, 1599.99it/s] 67%|██████▋ | 4974/7375 [00:02<00:01, 1576.18it/s] 70%|██████▉ | 5145/7375 [00:02<00:01, 1610.87it/s] 73%|███████▎ | 5372/7375 [00:03<00:01, 1790.65it/s] 76%|███████▌ | 5603/7375 [00:03<00:00, 1933.63it/s] 79%|███████▊ | 5801/7375 [00:03<00:00, 1861.68it/s] 81%|████████ | 5991/7375 [00:03<00:00, 1839.36it/s] 84%|████████▍ | 6178/7375 [00:03<00:00, 1645.68it/s] 87%|████████▋ | 6381/7375 [00:03<00:00, 1745.16it/s] 90%|████████▉ | 6607/7375 [00:03<00:00, 1885.18it/s] 92%|█████████▏| 6810/7375 [00:03<00:00, 1924.17it/s] 96%|█████████▌| 7083/7375 [00:03<00:00, 2154.81it/s] 100%|█████████▉| 7360/7375 [00:04<00:00, 2331.30it/s] 100%|██████████| 7375/7375 [00:04<00:00, 1839.44it/s]
Higher-order graph of order 1 with 327 nodes and 5818 edges
(over 327 first-order nodes)
{'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([5818])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
Higher-order graph of order 5 with 24550 nodes and 17433 edges
(over 327 first-order nodes)
{ 'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([17433])"},
'Graph Attributes': {'inverse_idx': "<class 'torch.Tensor'> -> torch.Size([12314285])", 'num_nodes': "<class 'int'>"},
'Node Attributes': {}}
How can we use such higher-order graph models for graph learning tasks? We will demonstrate this in the tutorials on causality-aware temporal graph learning, e.g. De Bruijn Graph Neural Networks.