  Explaining the predictions of neural black-box models is an important
problem, especially when such models are used in applications where user trust
is crucial. Estimating the influence of training examples on a learned neural
model's behavior allows us to identify training examples most responsible for a
given prediction and, therefore, to faithfully explain the output of a
black-box model. The most generally applicable existing method is based on
influence functions, which scale poorly for larger sample sizes and models.
  We propose gradient rollback, a general approach for influence estimation,
applicable to neural models where each parameter update step during gradient
descent touches a smaller number of parameters, even if the overall number of
parameters is large. Neural matrix factorization models trained with gradient
descent are part of this model class. These models are popular and have found a
wide range of applications in industry. Especially knowledge graph embedding
methods, which belong to this class, are used extensively. We show that
gradient rollback is highly efficient at both training and test time. Moreover,
we show theoretically that the difference between gradient rollback's influence
approximation and the true influence on a model's behavior is smaller than
known bounds on the stability of stochastic gradient descent. This establishes
that gradient rollback is robustly estimating example influence. We also
conduct experiments which show that gradient rollback provides faithful
explanations for knowledge base completion and recommender datasets.
