How can I implement the corresponding equivalent binary operations for the current g-SpMM and g-SDDMM?

Hello every one,

I wanted to extend the DGL with general binary operations for message function as well as reduce function, I have few questions?

  1. First question is it possible for all the message and reduce functions? (Note: i am studying corresponding equivalent operations in binary system for current message functions such as: Op: add/sub/mul/div/dot and similarly for reduce functions sum/max/min/mean/prod.
  2. If it is possible, then do i will need to implement it for both GPUs and CPUs myself or just a generic C APIs will do the work for both GPUs and CPUs.
  3. I assume it will significantly improve the GNNs speed and memory optimizations for both training and inference for large-scale graphs.

The resources currently i am studying are:
Bi-GCN: Binary Graph Convolutional Network
Binary Graph Neural Networks
Matrix Algebra in a Binary Finite Field

Hi @tariqaf

Sorry for the late reply.

  1. Yes, supporting message passing operations on boolean data is generally doable. The caveat will be the semantics of the reduce function. For example, suppose there is a node of three neighbors, and they send 2 messages in true while the other in false, what is the expected result for a sum reducer? How about others like mean? Once that is clear, then the implementation of such operation is no different than the current operators in DGL for float/double type.

  2. Yes, you need to implement some custom kernels. However, you can borrow many of DGL’s current spmm and sddmm kernel implementations.

  3. It actually depends. Although in theory working with 1-bit data is efficient, current hardware may not have good support for binary data especially when it comes to sparse operation. For example, in PyTorch, binary-type array is stored in uint8 which costs 8x more memory than the optimal.

-Minjie

1 Like

Hi @minjie,

Thank you so much for your reply. you are right i am also stuck at the reduce operations. currently i am researching ways to align reduce functions.However, i was not informed about the 3rd point you mentioned. i will study about these as well now.
About 2nd point i am not sure which spmm and sddmm kernel implementation i will need to borrow to support message passing operations on boolean data. but i have recently been able to debug python and c code for dgl and i am learning and will definitely know which code i would need to borrow from DGL spmm and sddmm kernels. Thanks for your time and reply.