Continuing on the discussion I had with @IngoScholtes today, where we were thinking about ways to speed up algorithms.temporal.temporal_graph_to_event_dag that creates a DAG from a temporal graph given a specific time window delta. Since I got this idea on the bike ride home today, I thought that I will write it down before I forget it again. We can discuss it in more detail in the upcoming sprint:
I know that we need the event DAG to construct the higher-order graphs for the temporal interactions. Do we need this anywhere else?
Because if not, then I may have an idea that would skip this step and directly construct the higher-order graph from the temporal graph. The procedure would be as follows:
Construct a graph where each timestamped edge corresponds to one edge in the graph where the time stamp is the edge weight. This might lead to duplicate edges but with different edge weights (time stamps).
Use the indexing-based lift order function inspired by PyG's Line Graph transformation (#132). This will create a 2nd order graph with all possible walks of length 2 without respecting the time. Note that since the edges now correspond to nodes, the edge weights now correspond to node features.
Subtract the node feature (edge timestamp) of the source node from the destination node in the higher-order edge index. This can be done either with message passing, but a simple diff = edge_weight[edge_index[1]] - edge_weight[edge_index[0]] should also do the trick.
Create a mask that filters the higher-order edges 0 < diff < delta and filter the higher-order edge index correspondingly. (Potentially remove isolated nodes.)
Benefits:
This will enable the use of continuous time stamps and does not require discretization.
Can be done on GPU
Potential Problems:
By using the time stamps as edge weights, we need to allow multiple edges between a pair of nodes. We need a sorted edge index (by source) for the line graph transformation to work. This might cause problems because coalesce in PyG removes all duplicate edges and aggregates the edge weights. I am not sure how or if there is sorting implemented for TemporalData but there might already be solutions there.
I am almost but not a 100% certain if this will work for any $k$ -> $k+1$. It should work because each node in the second-order graph corresponds to a time-stamped edge in the first-order graph. So we should only need to filter once from order $1$ -> $2$ and then all further transformations will respect the time automatically. But this leads to the next problem:
The higher-order representations will have multiple nodes for the same edge (at different time steps). Is this the higher-order representation that we need? I think it might be the same representation that we would get from the event DAG. If not, can we maybe map easily to the representation we need?
This might be very memory intensive since this will at first create a new graph with as many nodes as there are time-stamped edges and even more edges.
Continuing on the discussion I had with @IngoScholtes today, where we were thinking about ways to speed up
algorithms.temporal.temporal_graph_to_event_dagthat creates a DAG from a temporal graph given a specific time windowdelta. Since I got this idea on the bike ride home today, I thought that I will write it down before I forget it again. We can discuss it in more detail in the upcoming sprint:I know that we need the event DAG to construct the higher-order graphs for the temporal interactions. Do we need this anywhere else? Because if not, then I may have an idea that would skip this step and directly construct the higher-order graph from the temporal graph. The procedure would be as follows:
diff = edge_weight[edge_index[1]] - edge_weight[edge_index[0]]should also do the trick.0 < diff < deltaand filter the higher-order edge index correspondingly. (Potentially remove isolated nodes.)Benefits:
Potential Problems:
coalescein PyG removes all duplicate edges and aggregates the edge weights. I am not sure how or if there is sorting implemented forTemporalDatabut there might already be solutions there.