Loopy belief propagation

[dmlc]

Loopy belief propagation

[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.