  To deduce new facts on a knowledge graph (KG), a link predictor learns from
the graph structure and collects local evidence to find the answer to a given
query. However, existing methods suffer from a severe scalability problem due
to the utilization of the whole KG for prediction, which hinders their promise
on large scale KGs and cannot be directly addressed by vanilla sampling
methods. In this work, we propose the one-shot-subgraph link prediction to
achieve efficient and adaptive prediction. The design principle is that,
instead of directly acting on the whole KG, the prediction procedure is
decoupled into two steps, i.e., (i) extracting only one subgraph according to
the query and (ii) predicting on this single, query dependent subgraph. We
reveal that the non-parametric and computation-efficient heuristics
Personalized PageRank (PPR) can effectively identify the potential answers and
supporting evidence. With efficient subgraph-based prediction, we further
introduce the automated searching of the optimal configurations in both data
and model spaces. Empirically, we achieve promoted efficiency and leading
performances on five large-scale benchmarks. The code is publicly available at:
https://github.com/tmlr-group/one-shot-subgraph.
