Undirected Bipartite Graph with Edge Weight

[liujxing]

Hi,

First of all, thanks for writing this library! This makes graph neural network much more accessible to people like me!

I have a use case that is quite different from all the examples given in the documents, so I have many questions on how to make things work. I have an undirected bipartite graph, with N type A nodes and M type B nodes. In addition, the edge is undirected but weighted, with weight being in range (0, 1).

1. How do I represent an undirected graph using edge_index? My understanding the edge_index[0] is the source nodes and is indexed in type A nodes, and edge_index[1] is the destination nodes and is indexed in type B nodes, so how do we represent an edge from type B nodes to type A nodes? I don't think we need such edges since this graph is bipartite, but it really depends on how the convolution layers are implemented.
2. Now the graph has a weight on each edge, I'm looking for layers that also take into x as tuple of tensors and also edge_weight in its forward method, but there does not seem to be any. Do you know if any of the existing layers work in my case?
3. I did a little experiment using GATConv by discarding the weight of the edges. I have num_nodes_type_A = 653, num_nodes_type_B = 3827, num_features_type_A = 4, num_feature_type_B = 3, and I construct the layer as conv_layer = GATConv(in_channels=(num_features_type_A, num_features_type_B), out_channels=2, heads=5, concat=False) then I call the forward method by conv_layer(x=(x_A, x_B), edge_index, size=((num_features_type_A, num_features_type_B)) The output has shape (num_nodes_type_B, out_channels). I'm pretty confused by what I see here: Is the output the generated embedding for type B nodes? Shouldn't we get a tuple, with the first element being the output for type A nodes with shape (num_nodes_type_A, out_channels) and the second element being the output I see? And what does the size variable mean in here? I tried running it without size and it seems to give me the same result but I don't know if that's the right thing to do.

[liujxing]

One thought I about weighted edge: I can simply replace the sparse adjacency matrix containing 0/1 with the adjacency matrix with weight as its element. Do you think that will work? I think it depends on the implementation of layers here.

[liujxing]

I just tried it out myself, using the edge_index as 1. tensor with shape (2, num_edges), 2. sparse tensor with shape (num_type_A_nodes, num_type_B_nodes) and value of 1 for all positions, 3. sparse tensor with shape (num_type_A_nodes, num_type_B_nodes) and value of edge weight for all positions. The results of the first 2 cases are the same, which is not a surprise. However, the 3rd way also generates the same output, so somewhere along the forward() function, the value of sparse tensor edge_index is discarded. Do you know if I can change the code somewhere to avoid this behavior?

[rusty1s]

Message passing in bipartite graphs will send messages from source nodes to target nodes, and as such, will only give a new representation for the target nodes. All your code looks correct, besides that you also want to do message passing in reverse direction using the transposed adjacency matrix:

conv1 = GATConv(in_channels=(num_features_type_A, num_features_type_B, out_channels=...)
conv2 = GATConv(in_channels=(num_features_type_B, num_features_type_A, out_channels=...)

out1 = conv1(x=(x_A, x_B), edge_index)
out2 = conv2(x=(x_B, x_A), edge_index[torch.tensor([1, 0]).as_tensor(edge_index))

Note that GATConv does not support edge weights, as it will compute an edge weight/attention score on the fly. Operators that support edge weights in a bipartite fashion are, e.g., GraphConv or TransformerConv.

[michalisfrangos]

Hi rusty1s, thank you for the response above.

I have a related question/discussion with the implementation of a directed bipartite graph, as described in the figure below, where nodes of type A can send AND/OR receive messages from nodes of type E, and we are interested is classification on nodes E. If I understood the implementation above, I have the impression that a single message pass from each group of nodes as you describe keeps the 2 conv layers independent (am I right?). If we want nodes E to be updated based on the information they send AND receive, don't we need to link the two layers together as you have done similarly HERE )?

I share my approach below. I would appreciate any comments or if you have in mind of another example in PyG for directed bipartite (from both directions) I could have a look at. Thank you in advance.

self.conv1_A_to_E = GATConv(in_channels = (num_features_type_A, num_features_type_E),
                                out_channels = hidden_channels,
                                heads = heads, concat=True)

self.conv1_E_to_A = GATConv(in_channels = (num_features_type_E, num_features_type_A),
                              out_channels = hidden_channels,
                              heads = heads, 
                              concat=True)

self.conv2_A_to_E = GATConv(in_channels = (hidden_channels*heads, hidden_channels*heads),
                              out_channels = hidden_channels, heads = 1)

self.linear = Linear(hidden_channels, num_classes)

  def forward(self, x_A, x_E, edge_index_AE, edge_index_EA):
      h_A = F.dropout(x_A, p=0.5, training=self.training)
      h_E = F.dropout(x_E, p=0.5, training=self.training)
      h_E1 = self.conv1_A_to_E((h_A, h_E), edge_index=edge_index_AE) #, edge_attr=edge_attr)
      h_E1 = F.elu(h_E1)
      h_A1 = self.conv1_E_to_A((h_E, h_A), edge_index=edge_index_EA) #, edge_attr=edge_attr)
      h_A1 = F.elu(h_A1)
      h_A1 = F.dropout(h_A1, p=0.5, training=self.training)
      h_E1 = F.dropout(h_E1, p=0.5, training=self.training)
      h_E2 = self.conv2_A_to_E((h_A1, h_E1), edge_index=edge_index_AE)
      h_E2 = F.elu(h_E2)
   
      out = self.linear(h_E2)
      return h_E2, out

[rusty1s]

I think your example looks correct, although I'm not sure what you mean with "keeping the 2 conv layers indepedent". Otherwise, you may also want to look into how PyG 2.0 handles these heterogeneous graphs by now and simplifies the computation. See here for a quick tutorial.

[michalisfrangos]

Thank you rusty1s for the hint in the heterogenous graphs , I'll have a look!

Regarding the comment on the two layers being independent, I'm referring to the layers in your comment :

'

conv1 = GATConv(in_channels=(num_features_type_A, num_features_type_B, out_channels=...)
conv2 = GATConv(in_channels=(num_features_type_B, num_features_type_A, out_channels=...)

'

I don't see how the weights of one layer have an influence on the weights of the other (via the hidden state, or the outputs of each other), and their weights are not shared either, unless we introduce a third layer to link the two layers together

[rusty1s]

That is correct, you do only achieve that when stacking these bipartite message passing layers as part of a deep GNN. You can think of conv1 and conv2 as one round of message passing/one GNN layer.

[michalisfrangos]

great thanks rusty1s!