Counterfactual Explanations for Graph Classification Through the Lenses
  of Density
Carlo Abrate Giulia Preti Francesco Bonchi
Counterfactual examples have emerged as an effective approach to produce
simple and understandable post-hoc explanations. In the context of graph
classification, previous work has focused on generating counterfactual
explanations by manipulating the most elementary units of a graph, i.e.,
removing an existing edge, or adding a non-existing one. In this paper, we
claim that such language of explanation might be too fine-grained, and turn our
attention to some of the main characterizing features of real-world complex
networks, such as the tendency to close triangles, the existence of recurring
motifs, and the organization into dense modules. We thus define a general
density-based counterfactual search framework to generate instance-level
counterfactual explanations for graph classifiers, which can be instantiated
with different notions of dense substructures. In particular, we show two
specific instantiations of this general framework: a method that searches for
counterfactual graphs by opening or closing triangles, and a method driven by
maximal cliques. We also discuss how the general method can be instantiated to
exploit any other notion of dense substructures, including, for instance, a
given taxonomy of nodes. We evaluate the effectiveness of our approaches in 7
brain network datasets and compare the counterfactual statements generated
according to several widely-used metrics. Results confirm that adopting a
semantic-relevant unit of change like density is essential to define versatile
and interpretable counterfactual explanation methods.