  Recently, graph neural networks (GNNs) have been widely used to develop
successful recommender systems. Although powerful, it is very difficult for a
GNN-based recommender system to attach tangible explanations of why a specific
item ends up in the list of suggestions for a given user. Indeed, explaining
GNN-based recommendations is unique, and existing GNN explanation methods are
inappropriate for two reasons. First, traditional GNN explanation methods are
designed for node, edge, or graph classification tasks rather than ranking, as
in recommender systems. Second, standard machine learning explanations are
usually intended to support skilled decision-makers. Instead, recommendations
are designed for any end-user, and thus their explanations should be provided
in user-understandable ways. In this work, we propose GREASE, a novel method
for explaining the suggestions provided by any black-box GNN-based recommender
system. Specifically, GREASE first trains a surrogate model on a target
user-item pair and its $l$-hop neighborhood. Then, it generates both factual
and counterfactual explanations by finding optimal adjacency matrix
perturbations to capture the sufficient and necessary conditions for an item to
be recommended, respectively. Experimental results conducted on real-world
datasets demonstrate that GREASE can generate concise and effective
explanations for popular GNN-based recommender models.
