Loopy belief propagation

[BarclayII]

The loopy belief propagation updates messages on a directed edge e = (u, v) by looking at the messages on all edges pointing to u, except the one that comes from v. An example from Junction-Tree VAE looks like this:

where m's are messages, x are input features and W are weights (the latter two should be fine).
The readout would be something like

and the output vector being the average of all h_u's.

I can't think of a direct way to do loopy belief propagation like this within the current framework.

A possible workaround for this particular phase I can think of is to divide the process into two stages, maintaining a field called msg_sum, containing the sum of incoming message for each node :

• Send phase: compute m_uv like this:
  
  As you can see, this require us to query the message on the reverse edge, which I wonder if is possible. AFAIK the message function does not allow you to look at edges other than the ones to be updated.
• Recv phase: compute s_u as the sum of all incoming m_uv.
• [EDIT] Final readout phase: we can directly use s_u to compute the h's.

Any ideas?

[jermainewang]

I remember this paper (https://arxiv.org/pdf/1705.08415.pdf) mentioned this problem and propose to do GNN on line graph. On line graph, m_{uv} and m_{wu} are connected nodes. The idea is to maintain two GNNs. On the line graph GNN, it computes the summation of m_{uv}. On the normal graph, it computes the summation of x. The two GNNs need to cooperate by state sharing (currently just manually set/get reprs).

[BarclayII]

Just a side note: the official implementation simply builds for each edge a list of indices of all the incoming edges, stored in an integer Tensor. The indices start from 1, with 0 for a "dummy" edge whose message is always a zero vector. The update phase then simply involves an embedding lookup in message tensor with the index tensor, followed by a sum.

@jermainewang For this reason, I don't think a line graph is necessary for most cases involving such kind of loopy belief propagation (though I'm not sure if line graph could be a more general solution). Also, the line graph deduced from the bidirectional graph would still include a connection for every (u, v)-(v, u) which is to be excluded.

[jermainewang]

For the official implementation, does that means the edge features are variable length vector depending on the number of in-coming edges? If so, it might be troublesome for us to batch them in a tensor.

For the line graph, the author proposes the construction as follows:

[BarclayII]

Re official implementation: I'm not sure what you meant by saying "edge features are variable length vector". All the message vectors have the same number of elements. While each edge does have a variable number of incoming messages, they solve the problem by padding with a dummy edge whose message is always a zero vector, so that the number of incoming messages become the same. This idea only works for reducing with sum() or alike.

Re line graph: I see. A small caveat is that such a construction differs from networkx.line_graph().

[BarclayII]

For now, I guess I'll stick to the line graph approach. But it seems to me that this will introduce a non-negligible overhead, particularly due to the construction of another DGLGraph object with node attributes duplicated onto the new edge nodes.

A more elegant approach would be to define some other primitives that support edge-to-edge (or message-to-message) updates, but I'm not sure how to do that, and I'm reluctant to have other primitive(s) added solely for loopy BP. I wonder if there is any other solution...

[zzhang-cn]

Would it suffice by putting a filter on message reduction?

[BarclayII]

We decided that doing message passing on line graph (specifically, the line graph without feedback from itself; see Joan's paper above) is a more general solution.