图结构聚类是理解和分析大规模图数据的关键技术，而图数据的质量问题以及聚类参数的设定不合理问题，导致得到的聚类结果并不能够满足用户的真实需求。为聚类结果提供溯源解释能够有效的提高图数据库的质量和可用性，也是对现有图结构聚类系统的一个有效补充。课题从图结构数据的索引结构构建、面向数据敏感的溯源解释、面向参数敏感的溯源解释等三个方面，对面向图结构聚类溯源解释的关键技术进行研究。研究图结构聚类算法，提出面向图结构聚类溯源解释的索引结构；研究数据敏感对聚类结果的影响，实现面向数据敏感的图结构聚类的溯源解释技术；研究参数敏感对聚类结果的影响，实现基于用户实例的聚类参数估计技术和面向参数敏感的图结构聚类的溯源解释技术。课题最终实现一个面向图结构聚类的溯源解释原型系统，研究成果将在理论和实践两个层面，为图结构聚类提供良好的溯源解释支持，具有十分重要的理论价值和研究意义。

Structural graph clustering is a key technique for understanding and analyzing large-scale graph data. Due to the quality of graph data and the unreasonable setting of clustering parameters, clustering results do not satisfy the users' real requirements. Providing provenance explanations for the clustering results can effectively improve the quality and availability of the graph database, which is also an effective supplement to the existing structural graph clustering system. This research proposal proposes studying on structural graph clustering oriented key techniques of provenance explanation from the aspects of index structure construction of structural graph data, data sensitive oriented provenance explanation, and parameter sensitive oriented provenance explanation. We study the structural graph clustering algorithms, which builds an index structure for provenance explanation of structural graph clustering. We analyze that how the data affect the clustering results, and propose a provenance explanation technique based on data sensitivity. We also analyze the effect of parameters on the clustering results, and explore a technique to estimate the clustering parameters based on the user instances, and propose a provenance explanation technique in terms of parameter sensitivity. We plan to implement a structural graph clustering oriented prototype system of provenance explanation. Our research results would provide theoretical and practical supports for provenance explanations of structural graph clustering, which has very important theoretical value and research significance.