  Heterogeneous graph neural networks (HGNs) are prominent approaches to node
classification tasks on heterogeneous graphs. Despite the superior performance,
insights about the predictions made from HGNs are obscure to humans. Existing
explainability techniques are mainly proposed for GNNs on homogeneous graphs.
They focus on highlighting salient graph objects to the predictions whereas the
problem of how these objects affect the predictions remains unsolved. Given
heterogeneous graphs with complex structures and rich semantics, it is
imperative that salient objects can be accompanied with their influence paths
to the predictions, unveiling the reasoning process of HGNs. In this paper, we
develop xPath, a new framework that provides fine-grained explanations for
black-box HGNs specifying a cause node with its influence path to the target
node. In xPath, we differentiate the influence of a node on the prediction
w.r.t. every individual influence path, and measure the influence by perturbing
graph structure via a novel graph rewiring algorithm. Furthermore, we introduce
a greedy search algorithm to find the most influential fine-grained
explanations efficiently. Empirical results on various HGNs and heterogeneous
graphs show that xPath yields faithful explanations efficiently, outperforming
the adaptations of advanced GNN explanation approaches.
