Message passing on directed graphs

[Newiz430]

I've read issue #1845 but there's something confusing to me.

Assume a directed graph like 1 <- 0 -> 2 with self loops. Then the adjacency matrix is like
A = [[1, 1, 1], [0, 1, 0], [0, 0, 1]] (dense) or A = [[0, 0, 0, 1, 2], [0, 1, 2, 1, 2]] (sparse)
Assume every node has a scalar feature, i.e. X = [a, b, c]^T where a is the feature of node 0 etc.
The expected behavior of aggregation is that node 1 and 2 receives the information of 0, i.e. Z = agg(X, A) = [a, b+a, c+a]^T
But as the aggregation is like Z = AX, torch.matmul(A, X) yields Z = [a+b+c, b, c]^T (and I observe the same process in GCNConv where torch_sparse.spmm(adj_t, x) exactly does the matrix multiplication above)
This is exactly the opposite of what I expected in #1845 (messages are passed along outgoing edges and are aggregated by incoming nodes), which are instead aggregated by outgoing node 0.

Where did I go wrong?

[rusty1s]

That's exactly the reason why we are referring to adj_t, meaning the transposed adjacency matrix.

[Newiz430]

Thank you for the timely reply!

So the actual message passing acts as Z = A^TX I guess, but I seldom see the transposed adjacency matrix in the literature. Why the difference between the formulation and implementation?

[rusty1s]

I think most papers drop this because they are operating on undirected graphs or do not really care about whether message passing is performed from source to destination or vice versa. IMO, this is an implementation detail.

[Newiz430]

@rusty1s Got it, thank you so much!