Explaining Graph Neural Networks for Node Similarity on Graphs

This research paper addresses the challenge of providing explanations for similarity search tasks within graph data applications, such as citation networks and knowledge graphs. While Graph Neural Networks (GNNs) are widely used for computing node similarities, the interpretability of these models has received limited attention. The authors investigate how GNN-based methods can be augmented with explanations by evaluating two prominent approaches: mutual information (MI) and gradient-based (GB) explanations. Through empirical validation across various popular graph benchmarks, the study compares the suitability and properties of these methods. The findings indicate that gradient-based explanations possess three distinct advantages over MI explanations. They are actionable, meaning input selection based on them leads to predictable changes in similarity scores. They are consistent, with minimal overlap between the effects of selecting versus discarding specific inputs. Finally, they allow for significant pruning to create sparse explanations that effectively retain their impact on similarity scores, offering a more robust framework for explainable AI in graph processing.