arXiv:2506.12558v2 Announce Type: replace-cross Abstract: Path reasoning graph neural networks have demonstrated state-of-the-art performance on knowledge graph completion tasks such as link prediction. However, interpreting their predictions remains a challenging open problem, as most GNN explainability methods target node-level or graph-level tasks. In this paper, we propose RAW-Explainer ($\underline{Ra}$ndom $\underline{W}$alk Explainer), a novel explainability method tailored to path reasoning GNNs that generates connected, concise, and interpretable subgraph explanations for link prediction in knowledge graphs. Our method uses heterogeneous information to identify factual explanations and encourages connectivity through a random walk objective, using a parameterized model for efficient collective explanation. Furthermore, RAW-Explainer overcomes the distribution shift issue when evaluating explanatory subgraphs that are orders of magnitude smaller than the full graph by proposing a robust evaluator that generalizes to the subgraph distribution. Extensive results on standard knowledge graph completion benchmarks demonstrate that our approach strikes a balance between explanation quality and computational efficiency. Code and data are available at: https://github.com/colab-nyuad/RAWExplainer