Specific implementation of Data and MessagePassing for undirected graphs?

[errhernandez]

I always find myself working with undirected graphs; having to define each edge twice (once for each direction) is a minor inconvenience and one that I can easily live with, but I often wonder if it wouldn't be worthwhile having a specific Data structure (e.g. UData) and a specific implementation UMessagePassing for undirected graphs, in which by construction always flow between both nodes linked by an edge. One reason why I think this may be worthwhile is this: imagine an application in which you want to propagate data from the line graph of a graph to the edges of the graph (e.g. because it is important to propagate information about what angles edges form among themselves). For this to work properly in an undirected graph, the line graph itself must be made undirected.

For example, consider the graph with the following edge_index array (8 nodes):
[[0, 0, 0, 0, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7],
[1, 2, 3, 4, 0, 5, 6, 7, 0, 0, 0, 1, 1, 1]]

This looks like an ethane molecule CH3-CH3. The graph has 14 edges to make it undirected. Those 14 edges turn to 14 nodes in the line graph; the undirected line graph would have 62 edges, but 12 angles. The situation gets worse if one needs to consider the line graph of the line graph: the line graph of the line graph would have 62 nodes, and 518 edges, when really there are only 9 distinct angles to consider (the angles formed by four nodes in a line). It sounds that this kind of problem could be treated much more directly, in a more memory-efficient way, if there was a specific implementation for undirected graphs. Any thoughts?

[rusty1s]

Thanks for this interesting issue. I personally always liked the generalization of MessagePassing to both undirected and directed graphs, and adding this now to the library seems like a huge effort that might not be worth it. It also gets a little bit more confusing if we think of heterogeneous graphs and how one would define the notion of undirected graphs there.

From a memory and computational perspective, there is also not much to gain here (besides saving half of memory for storing edge_index), since we still would need to compute and store the messages for each direction inside MessagePassing (while also losing the ability to parallelize this step properly).

If you desperately need this feature, we could think of adding support for this in MessagePassing, where we would need to compute messages for both directions, concatenate the results, and then apply a unified aggregation on top of this. WDYT?

[errhernandez]

Thank you for your rapid and thoughtful response. First, I do not desperately need this facility, I was just wondering if this would be difficult to implement. I confess that I have tried to make sense of the source of MessagePassing to try to figure this out myself, but at least on first sight the implementation details are a bit beyond me (I need a bigger effort there).

Nevertheless the question of whether this would be useful or not depends on what type of graph the community most often works with; if it is undirected graphs, then it might be worth considering. I do agree with you that memory savings are probably not large, except in the case in which edge_attr is used and is large (because in the current implementation this is duplicated for in and out edges), and also in the case I discussed earlier, using line graphs, which I would admit is probably not so common.

Thanks again, and if you want to have further discussion on this, I'll be only too glad. Cheers!

[rusty1s]

Thank you. You are right that the memory savings get better in case multi-dimensional edge features are involved. I am happy to talk further about a special implementation for this inside MessagePassing as well, but I need to admit that it is definitely of lower priority.

[errhernandez]

Hello again. What would you think if I tried implementing this as a dense convolution? I notice that the implementation of dense convolution models does not inherit from MessagePassing, but directly from torch.nn.Module. This may actually be ideal, as the graphs I tend to work with are not so large anyway. This would mean no need to either create UMessagePassing or modify MessagePassing, which I agree would be probably not worth it. Having this discussion has been really clarifying, so I thank you very much.

[rusty1s]

Sure, that works as well. This would require that you only store upper triangular matrices rather than the full matrix, right? How do you intent to store this in PyTorch?

[errhernandez]

You see, for me the point is not so much saving storage, particularly since my adjacency matrices are small, because most of the graphs I work with at present have only a few tens of nodes. So, to answer your question, I would store the full square symmetric adjacency matrix. The point is more easing the transfer of data that results from a convolution on the line graph nodes to the edges of the parent graph. It seems to me that this should be easier in the full matrix representation than it is in the sparse coo representation, because I can limit the number of nodes in the line graph to exactly the number of edges (counting an edge and its reverse as one).

If you go back to the example graph in my first question on this post, the line graph in this description would have only 7 nodes (one for each pair of edges of the graph) and there would be only 12 edges between those nodes in the line graph (or rather 24 to make it undirected). Working in the coo sparse representation would mean 62 edges in the full undirected line graph.

Anyway, I will try implementing this as a dense convolution and see first if I am able to make it work, and then whether it proves of any value ;-). Thank you for your time and help!