Reconsidering Faithfulness in Regular, Self-Explainable and Domain Invariant GNNs

As Graph Neural Networks (GNNs) become more pervasive, it becomes paramount to build reliable tools for explaining their predictions. A core desideratum is that explanations are $\mathit{\text{faithful}}$, \ie that they portray an accurate picture of the GNN’s reasoning process. However, a number of different faithfulness metrics exist, begging the question of what is faithfulness exactly and how to achieve it. We make three key contributions. We begin by showing that $\mathit{\text{existing}}\mathit{\text{metrics}}\mathit{\text{are}}\mathit{\text{not}}\mathit{\text{interchangeable}}$ – \ie explanations attaining high faithfulness according to one metric may be unfaithful according to others – and can systematically ignore important properties of explanations. We proceed to show that, surprisingly, $\mathit{\text{optimizing}}\mathit{\text{for}}\mathit{\text{faithfulness}}\mathit{\text{is}}\mathit{\text{not}}\mathit{\text{always}}\mathit{\text{a}}\mathit{\text{sensible}}\mathit{\text{design}}\mathit{\text{goal}}$. Specifically, we prove that for injective regular GNN architectures, perfectly faithful explanations are completely uninformative. This does not apply to modular GNNs, such as self-explainable and domain-invariant architectures, prompting us to study the relationship between architectural choices and faithfulness. Finally, we show that $\mathit{\text{faithfulness}}\mathit{\text{is}}\mathit{\text{tightly}}\mathit{\text{linked}}\mathit{\text{to}}\mathit{\text{out-of-distribution}}\mathit{\text{generalization}}$, in that simply ensuring that a GNN can correctly recognize the domain-invariant subgraph, as prescribed by the literature, does not guarantee that it is invariant unless this subgraph is also faithful.The code is publicly available on GitHub