Effectively Explaining Missing Nodes on Structural Graph Clustering

摘要

To effectively manage and analyze graph data in many real-life graph applications, SCAN algorithm can efficiently help users to detect useful clusters, such as social networks, communication networks, gene networks, and so on. However, dirty data exist in graph data, for example, some edges are missing in graph data. In this case, the clustering results of SCAN over the dirty graph data cannot meet the users' requirements, such as, the missing nodes are not included in the desired clusters. To address this kind of problem, in this paper, we explore an effective explanation model to make the missing nodes be included in the desired clusters. The problem of explaining missing nodes in light of data modification is to explain why the missing nodes are not included in the desired clusters and how to make the missing nodes appear in the corresponding desired clusters by modifying the original graph dataset. To achieve this purpose, first, the clustering rational of SCAN algorithm is analyzed, and an unified explanation framework is proposed based on the analysis above. Moreover, based on the common explanation principle, the original clustering results should be maintained as much as possible in the new clustering results of SCAN, we design a penalty function to achieve this purpose. Then, we propose two explanation algorithms for making the missing nodes appear in the desired clusters by modifying the original graph dataset with minimum penalty value. Finally, comprehensive experiments are conducted, which demonstrate that the explored explanation model can efficiently explain the missing nodes on structural graph clustering.