  We propose a non-parametric link prediction algorithm for a sequence of graph
snapshots over time. The model predicts links based on the features of its
endpoints, as well as those of the local neighborhood around the endpoints.
This allows for different types of neighborhoods in a graph, each with its own
dynamics (e.g, growing or shrinking communities). We prove the consistency of
our estimator, and give a fast implementation based on locality-sensitive
hashing. Experiments with simulated as well as five real-world dynamic graphs
show that we outperform the state of the art, especially when sharp
fluctuations or non-linearities are present.
