How to select nodes from bipartite graph & How to aggregate a node multiple times

[KIKOcaoyue]

@rusty1s Thanks you a lot! Thanks for your nice work!

I have two questions and wish you to help.

Now I have a graph G consisting of two ordinary graphs O1, O2 and a bipartite graph B, like this:

(Undirectional edges)
O1:
[[1,2]
[1,3]
[2,4]
[3,4]]

O2:
[[5,6]
[5,7]
[6,8]
[7,8]]

B:
[[2,5]
[2,6]
[2,7]
[2,8]
[1,7]
[2,7]
[3,7]
[4,7]]

and G is O1 + O2 + B

The message passing layer may be like this:
x_i = sigma (MLP(x_jo-x_i, x_jb-x_i))
where node x_jo in O1 or O2 and x_jb in B, as you can see from the graph above, there are multiple x_jo, but only one x_jb.

For example, for node 1:
x_1 = MLP(x_2-x_1,x_7-x_1) + MLP(x_3-x1, x_7-x_1)

The questions are:

1. I need to use one node from graph O and one node from graph B, how to do that?
2. The node from graph B may be used many times, how to do that?

Thank you very much!

[rusty1s]

I am not sure I totally understand. The given formula would only make sense if there is always a 1:1 relationship between O1, O2, B. In that case, you can simply order your edges accordingly so that you can access them efficiently. Let me know if I am missing something.

[KIKOcaoyue]

Thank you! @rusty1s
It's actually a story like this: I model the data into two graphs, and in order to exchange information in the two graphs, I need to connect the two graphs. So I choose one point in each of the two graphs, so that P1 is the point chosen in graph 1 and P2 is the point chosen in graph 2. P1 is connected to all the points in graph 2, and similarly, P1 is connected to all the points in graph 1.

Now, in the message passing layer, I need to update graph 1 and graph 2. When I update graph 1, I need to select the adjacent node from graph 1 and also select the connected node from graph 2. (Because one node P2 in graph 2 is connected to all nodes in graph 1). For graph 2, the same operation is performed.

So, when I select node P_i of graph 1 to update the information, (assuming that there are k nodes in graph 1 connected to P_i), then I need to use P2 in graph 2 k times. (Because P2 is connected to every node in graph 1 and P_i in graph 1 is only connected to P2 in graph 2). For graph 2, the same operation is performed.

I'm not sure if I've described the problem clearly, so if I haven't, please let me know, thanks!

[rusty1s]

Yes, this is now more clear to me, but it also means that you need to have some kind of aggregation, e.g.,

 x_i = sigma (sum_jo MLP(x_jo-x_i) + sum_jb MLP(x_jb-x_i))

Such a message passing module can be then implemented using bipartite message passing within PyG.

[KIKOcaoyue]

Thank you so much rusty1s, However, what I need to clarify is that the aggregating is like this:
x_i = sigma (MLP (x_jo-x_i || x_jb-x_i))
|| means concat. Yes, just like EdgeConv.

So where can I find the document about bipartite message passing?

Thanks!

[rusty1s]

You can also do

 x_i = sigma (sum_jo MLP(x_jo-x_i || x_jb-x_i))

but this requires that you have exactly one edge between jo and i for every edge between jb and i. Is that the case in your graph?

There is sadly no "real" documentation about bipartite message passing yet (sorry) but it is super similar to the general message passing case. However, instead of a single node feature matrix, you can also input a tuple of node feature matrices (corresponding to source and destination node features), and then have an edge_index that points from one set of nodes to the other one, e.g.:

    self.propagate(edge_index, x=(x_src, x_dst))

def message(self, x_j, x_i):
    # x_j corresponds to source node features
    # x_i corresponds to destination node features

[KIKOcaoyue]

Thanks a lot!
You answers are helpful.
And since jb is constant in every layer (because jb is the node in graph 2 and jb connects every node in graph 1), I coded it like this:

def __init__():
    self.x_jb = None

def forward(self, x, edge_index, x_jb):
    self.x_jb = x_jb
    self.propagate(edge_index, x=x) 

def message(self, x_i, x_j):
    tmp = torch.cat([x_j-x_i, self.x_jb-x_i])
    return self.mlp(tmp)

where x_j is what we call x_jo and self.x_jb is what we call x_jb.