Generating graph for autoregressive model (path prediction)

[GianlucaDeStefano]

Hi all!

I am here because I don't know how to handle whole path prediction where each edge is a component of an entire path between two nodes.

My problem is the following:

I have a graph that contains multiple types of edges, my objective is to predict if a path between two nodes exists.
In practice, this consists of taking a set of successive predictions (each one depending on the previouses) to predict whether all the edges in this path are present.

This is an autoregressive process, so supposing that I am trying to predict the presence of the i_th edge, I want to include in the subgraph all the i_th -1 edges already predicted while excluding all successive future edges that come after in the path (and that will be predicted later on).

How can I generate this subgraph?
Is there any easy way of handling this?
The only way I see is to modify the LinkNeighborLoader
to sample different types of edges depending on the 'side' of the target edge. However, I am not sure if there is already something built in or if there is a better way to handle this problem.
Do you have any tips or advice?

Thank you in advance

To clarify further: To solve this it would be sufficient to not include the specific type of edge subject to the prediction in the neighbourhood graph generated starting from the destination node of the current target edge.
Is this possible?

[rusty1s]

Do you desperately need graph-sampling (e.g., LinkNeighborLoader) for this? Otherwise, I guess this is straightforward to implement. You have a GNN operating on the existing graph, and train against finding the next best node pair/edge. Afterwards, you simply concatenate this pair to edge_index and repeat. The usage of LinkNeighborLoader makes this a bit harder to solve since it does not support modification to the underlying graph that easily (it operates on CSC sparse matrix format).

[rusty1s]

Why do you need to collate them together in the first place? How about you create small subgraphs from your data first to split your giant graphs into multiple ones (containing all node/edge types up to a certain number of hops)?

Also, why is it necessary to customize the sampler here? Can you clarify? LinkNeighborLoader already supports sampling from both end points of an edge under consideration.

[GianlucaDeStefano]

Hi, thank you for the response.

1. "Why do you need to collate them together in the first place?":
   Well, because I don't see how else to do the training. I am trying to train a model to predict a particular type of edge between two nodes. Furthermore, I want to include training examples from multiple graphs as each is constructed differently and may offer a specific contribution to the training.
   To do this, I collate all graphs into a single giant one from which I sample examples randomly using the LinkNeighborLoader class.
   Doing this allows me to sample examples from multiple graphs simultaneously and does not require any pre-training pruning of the graph.

2. "How about you create small subgraphs from your data first to split your giant graphs into multiple ones (containing all node/edge types up to a certain number of hops)" :
   If I understand correctly, you are proposing to create a set of small graphs before the training, each representing the 'neighborhood' of an edge. So that, at training time, it would not be necessary to use the LinkNeighborLoader, right? This is feasible but would require rebuilding the dataset if I change the number of hops to use. Do you have any examples that do this already by any chance?

3. "Also, why is it necessary to customize the sampler here? Can you clarify? LinkNeighborLoader already supports sampling from both end points of an edge under consideration."
   Well, supposing to stick to the method I am currently using (collating all graphs together). Modifying the sampler would be necessary to sample edges differently depending on the edge's node under consideration.
   Suppose I have the following graph.
   I want to train a model to recognize the presence of all the red edges that compose the path between A and D.
   I have to proceed step by step, predicting the presence of the first edge, the second, and so on.
   Suppose I am training the model and randomly sampled the edge B -> C to be used as a training example.
   I use LinkNeighbourLoader to get a subgraph of the total graph containing the relevant neighbors.
   My problem is that in this case, I would like this subgraph to include the red edge A -> B as it represents valuable information from the past, while I would like to exclude the red edge C -> D as it represents a future prediction and is a possible source of bias.
   In the end, to predict the presence of B -> C, I would like to sample a graph such as this where the information that can generate a bias (presence of future edges) is excluded.

[rusty1s]

1. Okay, got it. I think this makes sense.
2. Yeah, that is true - it would need re-building when changing the number of hops. The advantages are that you can iterate faster and train on smaller data to validate your claims. I guess this is a trade-off.

I think there are some optimizations we can make here. It looks like your data is inherently temporal, and we already support temporal sampling as part of neighborhood sampling - that is, we support to only sample nodes past the time of a given seed timestamp for the edge under consideration. Sadly, we only support timestamps at the node-level right now. Is that something that would still be applicable? We can think about bringing temporal sampling support to edges as well.

[GianlucaDeStefano]

Thanks again for your feedback!

I am inclined to adopt your proposed approach (pre-splitting the data); how would you approach this?
At the moment, I have the following architecture in mind:
Before training:

1. Foreach edge to predict, generate and save its neighborhood graph in an ad hoc Data object. (Saving in a specific tensor also the edge_index of the edge that is the target of the example).

At training time:
1)Sample randomly examples to load
2) Load the subgraphs of these examples
3) Collate them together and train the network as before

Is this what you had in mind?
Is there already any logic implemented by pyg to split graphs and create n-subgraphs suitable for this approach?

Unfortunately, I don't think that using node-based temporal methods is feasible in my case, as the nodes are fixed and not conditioned on the presence of the edge I am trying to predict.

[rusty1s]

Yeah, this is what I had in mind. You create a List[Data] from the k-hop neighborhood around each edge and simply feed them into the model via DataLoader(dataset, shuffle=False). This is very similar to the SEAL method, see examples/seal_link_pred.py. For the most efficient solution, I think you can utilize LinkNeighborLoader to generate these data objects, but instead of feeding them into the model, you just save them.