  Knowledge graph embedding (KGE) models are an effective and popular approach
to represent and reason with multi-relational data. Prior studies have shown
that KGE models are sensitive to hyperparameter settings, however, and that
suitable choices are dataset-dependent. In this paper, we explore
hyperparameter optimization (HPO) for very large knowledge graphs, where the
cost of evaluating individual hyperparameter configurations is excessive. Prior
studies often avoided this cost by using various heuristics; e.g., by training
on a subgraph or by using fewer epochs. We systematically discuss and evaluate
the quality and cost savings of such heuristics and other low-cost
approximation techniques. Based on our findings, we introduce GraSH, an
efficient multi-fidelity HPO algorithm for large-scale KGEs that combines both
graph and epoch reduction techniques and runs in multiple rounds of increasing
fidelities. We conducted an experimental study and found that GraSH obtains
state-of-the-art results on large graphs at a low cost (three complete training
runs in total).
