  Knowledge graphs (KGs) capture knowledge in the form of head--relation--tail
triples and are a crucial component in many AI systems. There are two important
reasoning tasks on KGs: (1) single-hop knowledge graph completion, which
involves predicting individual links in the KG; and (2), multi-hop reasoning,
where the goal is to predict which KG entities satisfy a given logical query.
Embedding-based methods solve both tasks by first computing an embedding for
each entity and relation, then using them to form predictions. However,
existing scalable KG embedding frameworks only support single-hop knowledge
graph completion and cannot be applied to the more challenging multi-hop
reasoning task. Here we present Scalable Multi-hOp REasoning (SMORE), the first
general framework for both single-hop and multi-hop reasoning in KGs. Using a
single machine SMORE can perform multi-hop reasoning in Freebase KG (86M
entities, 338M edges), which is 1,500x larger than previously considered KGs.
The key to SMORE's runtime performance is a novel bidirectional rejection
sampling that achieves a square root reduction of the complexity of online
training data generation. Furthermore, SMORE exploits asynchronous scheduling,
overlapping CPU-based data sampling, GPU-based embedding computation, and
frequent CPU--GPU IO. SMORE increases throughput (i.e., training speed) over
prior multi-hop KG frameworks by 2.2x with minimal GPU memory requirements (2GB
for training 400-dim embeddings on 86M-node Freebase) and achieves near linear
speed-up with the number of GPUs. Moreover, on the simpler single-hop knowledge
graph completion task SMORE achieves comparable or even better runtime
performance to state-of-the-art frameworks on both single GPU and multi-GPU
settings.
