google-deepmind/jraph

Doubt about the implementation of GraphConvolution

Closed this issue · 5 comments

llan-ml commented

I found that the output of the GCN implementation in this repo is different from that of the original matrix multiplication based implementation, when the input graph is not symmetric.

I did some tests in this colab notebook.

@jg8610 Could you take a look at this?

jg8610 commented

Thanks, I am taking a look.

jg8610 commented

Hi llan-ml,

I believe the matrix multiple version you are talking about assumes an undirected graph (i.e. a symmetric adjacency matrix), at least according the original paper. Could you point me to the paper with the directed version?

Jonathan

llan-ml commented

Hi,

Indeed, the matrix based version assumes that the graph is undirected. For directed graphs, the author suggests to do normalization with $D^{-1}A$ instead of the symmetric normalization (here and here).

In addition, even for undirected graphs, I still do not know why we perform pre-normalization by sqrt sender_degree to implement $D^{-1/2}AD^{-1/2}X$, though sender_degree and receiver_degree are the same and the final results are not influenced. Could you please clarify this a bit more?

jg8610 commented

Hey,

I agree that we could make this clearer. It seems there are a few situations:

  • we have an undirected graph, in which case what we implement is correct but a little confusing because we have senders and receivers. I can add some comments for this.
  • we have a directed graph, in which case if you pass 'symmetric normalization' we do something a little different that hasn't been reported in the literature.
  • we don't make explicit that using mean aggregation (D^{-1}) is a useful option instead of segment_sum if you have an undirected graph

My preference would be to add more documentation - what do you think?

  • 👍2
llan-ml commented

I think it is a good idea to document this more clearly. BTW, thanks for making this repo!