  Graph neural networks (GNNs) have shown great potential in learning on
graphs, but they are known to perform sub-optimally on link prediction tasks.
Existing GNNs are primarily designed to learn node-wise representations and
usually fail to capture pairwise relations between target nodes, which proves
to be crucial for link prediction. Recent works resort to learning more
expressive edge-wise representations by enhancing vanilla GNNs with structural
features such as labeling tricks and link prediction heuristics, but they
suffer from high computational overhead and limited scalability. To tackle this
issue, we propose to learn structural link representations by augmenting the
message-passing framework of GNNs with Bloom signatures. Bloom signatures are
hashing-based compact encodings of node neighborhoods, which can be efficiently
merged to recover various types of edge-wise structural features. We further
show that any type of neighborhood overlap-based heuristic can be estimated by
a neural network that takes Bloom signatures as input. GNNs with Bloom
signatures are provably more expressive than vanilla GNNs and also more
scalable than existing edge-wise models. Experimental results on five standard
link prediction benchmarks show that our proposed model achieves comparable or
better performance than existing edge-wise GNN models while being 3-200
$\times$ faster and more memory-efficient for online inference.
