Advice in dynamic predictions where new nodes are added at each time-step; one node can have multiple edges

[rperera12]

Hi,
It would be of tremendous help if you could advice me on the steps/networks/models to use in a specific more advanced case.
I have made my own in-house implementation for this problem, but I would really like to make use of the pytorch geometric library which you have created.
My problem involves predictions in time:

1. Given the current time-step graph, I have to predict a node feature for each n
   
   
   ode at the next time-step
2. For instance, at t0 my graph may have 750 nodes, and at t1 it increases to 1000 nodes.
3. Because the nodes are increasing, the edges are also increasing
4. One node can have multiple edges connecting to other nodes such that num_edges > num_nodes. The message passing network is giving me error messages <index 3088 is out of bounds for dimension 0 with size 747> since I have less nodes than edges at each graph
5. My prediction is one feature for each node from the next time-step, for instance, at t0 I have 747 nodes with 5 features as the input (x.shape = [747, 5]), however at the next time-step the num_nodes has increased so my target would be (y.shape = [1000, 1]).

Is there a specific approach you would advice me to take?
I would really appreciate your help with this problem and make use of pytorch geometric.

[rusty1s]

Interesting. In general, it might be best to look into PyTorch Geometric Temporal for this, which provides better support for these temporal problems.

In order to help you better, it would be important to find out how you update your graph across timestamps. In my opinion, you would have a graph for every timestamp. Within a single batch/sequence of these graphs, you would pad nodes with zeros such that all data has the same number of nodes (similar to how it is done in mini-batching of sentences).

[rusty1s]

Sorry for the delayed reply. I am not sure I understand your current implementation. It looks like you only take a single graph and predict the next time-step, right? In that case, you are not really making use of the temporal information of your graph, right?

I agree that having 37,249 nodes over a sequence of steps is computationally expensive. Is there any way to reduce the number of nodes here? In theory, you do not need to pad graphs with zeros (similar of how we don't need to do this when batching multiple graphs together). However, it helps when you actually want to pass node information from one timestep to another as the assignment of nodes over time is well-defined. How about still padding the number of nodes, but throwing away all edges pointing to invalid nodes?

[rperera12]

Matthias,
No worries at all! I understand it was the weekend :) I really appreciate your response and your help! It has been extremely helpful.
To answer each question and explain what my exact current implementation is, I will copy your questions/comments along with my response:

Question: It looks like you only take a single graph and predict the next time-step, right?
Answer: I am actually using the four previous time-steps to predict the future - Input = [T-3, T-2, T-1, T] ---> Target = [T+1]

Question: I agree that having 37,249 nodes over a sequence of steps is computationally expensive. Is there any way to reduce the number of nodes here?
Answer: On my first implementation I was not considering the inactive nodes as part of the input in order to reduce the number of nodes given to the input. The procedure I was following was to:

1. find the active nodes in the input sequence (Input = [T-3, T-2, T-1, T])
2. generate the edges for each time-step in the input sequence (only considering the active nodes). Note that since each time-step will have a different number of active nodes, the edge_index array will be of different shape at each time-step.
   ---> Now this is where I was getting stuck in terms of finding the correct network/model or just in terms of implementation. One challenge is that as time progresses, the number of active nodes is higher than at the previous time-steps (# nodes increases per time-step), thus the edge_index and num_nodes for T-2 will be different than T-3, the edge_index and num_nodes at T-1 will be different than at T....and so on. To overcome this challenge, on my first approach I took advantage of the fact that I do know what the # of active nodes is at T+1, so I set this size for all time-steps in the input sequence, and assign zeros to the added nodes (i.e., this way I can make the input sequence have the same size as the target).

Question: How about still padding the number of nodes, but throwing away all edges pointing to invalid nodes?
Answer: Also, on my first implement I applied the same methodology to the edge_index as I did to the nodes, making the edge_index at each time-step in the input sequence have the same size as the target. I used this approach because in order to use a time sequence in the input the edge_index.shape should be edge.shape = [batch_size, 2, num_edges, time-steps], and having different num_edges at each time-step did not allow me to do this. Another problem I was having with this method is that the training was not improving, I am thinking that by increasing the size of the nodes the model eventually gets confused as to which element in the input array corresponds to which node in the domain; since in one configuration an element in the input array will correspond to a completely different node in another configuration.

---> On your first response to this discussion you advised me to try instead and consider all the nodes in the domain (193193=37,249) as part of my input. This is the approach I am currently taking. I am following this example https://github.com/benedekrozemberczki/pytorch_geometric_temporal/blob/master/examples/recurrent/a3tgcn2_example.py where they use one of the models in geometric temporal. Now I am considering a static graph containing all the nodes 193193, and the edge_index is also the same. I will keep you updated on the results of this approach as I am currently waiting for the model to finalize training.

A couple quick questions:

1. On the example I am following https://github.com/benedekrozemberczki/pytorch_geometric_temporal/blob/master/examples/recurrent/a3tgcn2_example.py, their input is always the same size (input.shape = torch.Size([32, 207, 2, 2])), therefore they can easily use temporal information where two previous time-steps have the exact same size. Likewise, their edges are the same for each graph. If I wanted to go back to my initial approach where nodes keep increasing at each step, is there a model that can handle this? Or would you advise a different approach where I can do this?
2. On my in-house implementation I performed the message-passing network to both the edges and nodes for a number user-defined message-passing steps. In the PyTorch Geometric or PyTorch Geometric Temporal are these message-passing networks embedded into the model? Or should we implement those separately to the existing models. If they are embedded, how do we define the desired number of message-passing steps?

I'm sorry for the long discussion, I have been scratching my head with this problem for some time trying to find the correct implementation. The PyTorch Geometric library has become very helpful as it is much more optimized than my in-house implementation, and I am trying to find a network/model that can handle increasing graph sizes in the input sequence. Again thanks a lot for your time

[rusty1s]

1. Yes, this is the standard approach where graph structure does not change over time. It is the easiest one to implement :)
   If you consider a sequence of graphs with varying number of nodes, I would encode it as follows: Each graph is defined by a data object. You can "batch" them together via batch = Batch.from_data_list(data_inside_seq), where batch.batch now refers to the timestamp (you can rename it to batch.timestamp as well). Afterwards, you can apply a GNN on top of this batch object, and then exchange temporal information by converting it to a "dense batch" of shape [num_timestamps, num_nodes, num_features]: x, mask = to_dense_batch(x, batch.timestamp).
2. I'm not sure I understand this. Which model are you referring to? In general, a message passing layer computes new node embeddings by passing messages around local neighbors, and stacking them together will give you a full model. The number of message passing steps is a hyperparameter we can tune.

[rperera12]

Matthias,

Thank you so much for your response. This is very helpful advice!
I will implement the batching approach recommended.
The results when considering the entire domain were pretty accurate btw, thanks for your help with that as well.
But it would definitely be nice to improve computation speed with this new approach.

For the message passing approach, on my in-house code I used an approach very similar to the one on this paper https://arxiv.org/pdf/2002.09405.pdf
If I wanted to do this with PyTorch Geometric, basically I would need to use the instructions on (https://pytorch-geometric.readthedocs.io/en/latest/notes/create_gnn.html) and make this network separately right? And for controlling the number of message-passing steps we could simply use a loop?

[rusty1s]

You can either to edge embedding updating separately or as part of MessagePassing as well (simple return a tuple). We just added support for this via edge_updater. See here for an example. The number of steps can be indeed controlled using a loop.