lingfanyu
commented
5 years ago For RGCN, I think the weight W should not be in the message signature, and message function should directly reference it (for example, using closure).
Here is what the code might look like:
class MessageFunc(nn.Module):
def __init__(self):
self.w = torch.Tensor(num_relations, in_feat, out_feat)
def forward(self, src, edge):
return torch.bmm(src['h'], self.w[edge['type']])Then the propagation looks like: g.update_all(msg_func, fn.sum(), update_func)
And we need to lower the spmv executor from update_all, send_and_recv api to recv api so that all builtin reduce can be done as a spmv from edge space to node space. And if message func is also builtin, we can provide a shortcut to rewrite as a spmv from node space to node space. This is related to executor redesign @jermainewang and I previously discussed.
zheng-da
BarclayII
jermainewang
Had a discussion with @ylfdq1118 today. Here is the conclusion we have reached:
Storage
In our current codebase, we store the graph as adjacency lists (node to node). We propose to directly change the storage in C++ backend to incidence lists, more specifically, an incidence list for inbound edges and another for outbound ones. This implies that we are no longer handling simple graphs and multi-graphs separately like in NetworkX. This will affect the implementation of the following backend methods:
predandsucc: Essentially, we will have to find the inbound/outbound edges of the given vertices first, then look up the source/target vertex of those edges (we can also have a predecessor/successor list in parallel to the inbound/outbound edges, but this is essentially duplicating the edge list and I'm not sure whether we would like it). These methods should support a boolean argumentuniqueto dictate whether we expect a unique list of vertices (useful for graph traversal) or not (useful for deciding source/target nodes formessageandapply_edgefunctions).vertex_subgraph: Similar topred/succ, we need to do two-step queries.get_eid,: Now it would return a list of edge IDs instead of one.in_edges,out_edgesget_eids,batch_in_edges,batch_out_edges: We haven't go through the semantics of this method yet. I would suggest returning a list of lists if possible, following the same practice asigraph.Graph.neighborhood(). Returning a padded array (along with the lengths) can also do the job if we wish to enable padding (which is a separate functionality we wish to consider I assume).(source, target, edge ID)tuples.EDIT4: after all, the changes in C++ interface only involves changing the returning type of
get_eidtoIdArrayandbatch_get_eidtoEdgeArray.User Interface
Right now, the following user interfaces assumes that no multi-edge exist:
set_e_reprget_e_reprapply_edgessend(and consequentlysend_and_recv,pull,push, andupdate_all)pull,pushandupdate_allonly assumes that in the implementation due to usage ofsend; the interface itself is fine.update_edgeSince the interfaces expects to take in and return tensors, we think that having multi-edges will complicate the semantics significantly for
get_e_reprandset_e_reprin particular: the users often have to track of how many edges are between two given vertices (e.g. Given a multi-graph ((0, 1), (0, 1), (1, 2)),set_edge_repr([0, 1], [1, 2])will actually require a tensor with 3 rows, quite unnatural).EDIT2: Our suggestion is to
get_e_reprandset_e_repr, simply raise an error if multi-edge exists between any of the given source/target pairs. We can have nicer semantics later.apply_edges,send,send_and_recv, andupdate_edge(e.g.sendon) as well (set_e_reprandget_e_repralready have their edge ID counterparts), to allow sending/applying on individual edges.We concluded that switching to incidence matrices in the backend should not break compatibility on the current user interfaces.
Side note: Filtering vertices/edges
Since RGCN already involves edges with different "types", which are represented by integers, we can expect that later on we will have models requiring to perform graph operations on a "type" of node/edge at a time. To be even more general, the users can do stuff on a subset of nodes/edges satisfying a certain predicate. We think it will be nice to have a filtering function which returns a subset of given nodes/edges that satisfies a given predicate. For example:
Of course, the signature does not have to be exactly like this.
gSPMV Optimization
One thing we have noticed is that, if we use incidence matrices in our storage, then builtin reduce functions can be always represented by a gSPMV between the inbound incidence matrix and the message tensors.
However, if the message function is also a builtin, we don't want to actually broadcast the messages onto edges since it will potentially take up much more space. So
EDIT: gSPMV on adjacency matrix with multi-edges is more subtle. Since multi-edges are analogous to duplicate entries in COO sparse matrix, depending on the message and reduce function form the actual implementation can be different:
copy_src/src_mul_edgeand reduce functionsum, on PyTorch we can still stick with existing SPMM multiplications by directly constructing the (weighted) adjacency matrix from edge lists; PyTorch will automatically coalesce duplicated entries by summing them up. I don't know if this is the case for MXNet and Tensorflow.max, the coalescing operation is no longer a sum but something like max pooling, so direct sparse tensor construction in PyTorch no longer works.RGCN example
Under the proposed changes, we expect that the RGCN code can be greatly simplified, and our behavior could match the official implementations. Namely, the message function is simply a batched dot product between the source tensor and the weight matrices corresponding to the edge types, while the reduce function is just a sum (@ylfdq1118 correct me if I'm wrong):
Comments and questions are welcome.