  Counterfactual explanations have been argued to be one of the most intuitive
forms of explanation. They are typically defined as a minimal set of edits on a
given data sample that, when applied, changes the output of a model on that
sample. However, a minimal set of edits is not always clear and understandable
to an end-user, as it could, for instance, constitute an adversarial example
(which is indistinguishable from the original data sample to an end-user).
Instead, there are recent ideas that the notion of minimality in the context of
counterfactuals should refer to the semantics of the data sample, and not to
the feature space. In this work, we build on these ideas, and propose a
framework that provides counterfactual explanations in terms of knowledge
graphs. We provide an algorithm for computing such explanations (given some
assumptions about the underlying knowledge), and quantitatively evaluate the
framework with a user study.
