Plans for a true undirected graph? And temporary workardound?

Questions
#1

It seems that DGL doesn’t have a true undirected graph class. The suggestion is to add edges going both directions in a DiGraph as a workaround. This works well enough except regarding edge features, because the two edges do not share the same features, even though they are supposed to be the same entity. Of course, there are also efficiency problems with double recording each edge too.

  1. Are their plans implement a true undirected graph class?

  2. Is there a way, in the interim, to link the edge data between the two edges going opposite ways in a graph?

Thanks.

#2
  1. I don’t think we will support true undirected graph class in the future as the current directed graph class allows a general interface for dealing with directed and undirected graphs. In addition, message passing always comes with a direction.
  2. If your graphs are just molecular graphs, smiles_to_bigraph and mol_to_bigraph might help.
  3. You are probably aware of to_bidirected, which can be helpful for adding edges for both directions. Currently it does not handle edge features. One possibility is to allow users to pass a user-defined function, which takes the original graph topology and edge features as input and will be responsible for defining the edge features for graphs with both directions. Copy @minjie for visibility.
  4. For linking the edge data between the two edges going opposite ways in a graph, are you suggesting sharing the memory for features of edges with opposite directions?
1 Like
#3

Yes, that seems extremely important if a true UGD is not planned in the future.

#4

I wonder if a fairly thin wrapper around DiGraph could emulate a UGD. How hard is it to swap the direction of an edge? If that is easy in the API, there should be a way to create a UGD like interface that would store the transversal across the UGD as directionally on the edges.

This might make most sense to implement as a separate of functions that treat a digraph differently.

#5

We had a brief discussion on the topic among the team. The largest difficulty comes from that our kernels mostly assume a directed graph and to fully support un-directed graphs we need to make some non-trivial effort. If you just want to share edge features between opposite edges, you can use DGLHeteroGraph as follows:

edge_list = [(0, 1), (1, 2)] # Edge list for an un-directed graph
reverse_edge_list = [(j, i) for (i, j) in edge_list]
g = dgl.heterograph({
      ('node', 'edge', 'node'): edge_list, 
      ('node', 'reverse_edge', 'node'): reverse_edge_list
})
edge_feats = torch.randn(2, 2)
g.edges['edge'].data['h'] = edge_feats
g.edges['reverse_edge'].data['h'] = edge_feats

assert id(g.edges['edge'].data['h']) == id(g.edges['reverse_edge'].data['h'])

For message passing, we will need to separately perform message passing for both directions and combine them. For example,

import dgl.function as fn

g.multi_update_all(
    {'edge': (fn.copy_edge('h', 'm'), fn.sum('m', 'h'))}, 
     'reverse_edge': (fn.copy_edge('h', 'm'), fn.sum('m', 'h'))},
'sum')

The documentation can be found here.

2 Likes
#6

Is there an easy way to reverse the direction of an edge in a graph, preserving it’s data?

#7

Does dgl.transform.reverse help?

1 Like
#8

Unfortunately no. I’d want a simple way of efficiently reversing a single edge or defined set of edges (if that is more efficient), while keeping its edge data etc. entirely intact and linked. If such a simple interface or pattern existed, I see an easy way build an efficient UDG layer on top of what you currently have, at least for a large class of use cases.