Interpretable link prediction

Link prediction is a core data analysis issue in the field of network science and data mining. Previous link prediction methods mainly focus on how to accurately identify those potential links. In practice, it is also very critical to understand the decision-making process, i.e., explaining why there is a link between two nodes. Unfortunately, how to predict links in an explainable manner for general graphs still remains unaddressed. To fill this gap, we make an attempt towards this direction by introducing an interpretable link prediction method based on sparse decision tree. Our method first extracts explainable features that are highly relevant to the target link. Subsequently, it constructs a concise decision tree by either imposing depth constraint on classic algorithms or employing recent algorithms for constructing optimal sparse decision tree. Experimental results on real networks demonstrate that our method not only provides a transparent decision process for link prediction but also delivers performance comparable to many classic methods. The source codes of our method are publicly available at: https://github.com/Hailu-Tan/Interpretable-Link-Prediction.