Efficient Heterogeneous Graph Learning via Random Projection
Jun Hu Bryan Hooi Bingsheng He
Heterogeneous Graph Neural Networks (HGNNs) are powerful tools for deep
learning on heterogeneous graphs. Typical HGNNs require repetitive message
passing during training, limiting efficiency for large-scale real-world graphs.
Recent pre-computation-based HGNNs use one-time message passing to transform a
heterogeneous graph into regular-shaped tensors, enabling efficient mini-batch
training. Existing pre-computation-based HGNNs can be mainly categorized into
two styles, which differ in how much information loss is allowed and
efficiency. We propose a hybrid pre-computation-based HGNN, named Random
Projection Heterogeneous Graph Neural Network (RpHGNN), which combines the
benefits of one style's efficiency with the low information loss of the other
style. To achieve efficiency, the main framework of RpHGNN consists of
propagate-then-update iterations, where we introduce a Random Projection
Squashing step to ensure that complexity increases only linearly. To achieve
low information loss, we introduce a Relation-wise Neighbor Collection
component with an Even-odd Propagation Scheme, which aims to collect
information from neighbors in a finer-grained way. Experimental results
indicate that our approach achieves state-of-the-art results on seven small and
large benchmark datasets while also being 230% faster compared to the most
effective baseline. Surprisingly, our approach not only surpasses
pre-processing-based baselines but also outperforms end-to-end methods.