  We propose a nonparametric approach to link prediction in large-scale dynamic
networks. Our model uses graph-based features of pairs of nodes as well as
those of their local neighborhoods to predict whether those nodes will be
linked at each time step. The model allows for different types of evolution in
different parts of the graph (e.g, growing or shrinking communities). We focus
on large-scale graphs and present an implementation of our model that makes use
of locality-sensitive hashing to allow it to be scaled to large problems.
Experiments with simulated data as well as five real-world dynamic graphs show
that we outperform the state of the art, especially when sharp fluctuations or
nonlinearities are present. We also establish theoretical properties of our
estimator, in particular consistency and weak convergence, the latter making
use of an elaboration of Stein's method for dependency graphs.
