面向图结构聚类溯源解释的关键技术研究

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.

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

图结构聚类作为理解和分析大规模图数据的关键技术，具有重要的应用价值。然而，当图数据出现质量问题或聚类参数出现设置不合理问题时，得到的聚类结果可能无法满足用户的真实需求，降低了图结构聚类的质量和图数据的可用性。针对该问题，本项目对面向图结构聚类溯源解释的关键技术展开研究。主要包括：（1）支持图数据查询的索引策略；（2）基于数据敏感的溯源解释技术；（3）基于参数敏感的溯源解释技术。主要成果如下：.（1）支持图数据查询的索引构建：项目组基于网格索引研究了路网图中的路径规划、最近邻查询以及同出发点拼车等查询优化问题，查询效率提升了2~3倍，为基于结点密度和聚类特征构建支持图结构聚类溯源解释的双层索引技术奠定了理论基础。.（2）基于数据敏感的溯源解释：项目组首先研究了基于数据敏感的图结构聚类溯源解释算法，能够为不同的期望数据提供有效的数据修改策略。随后项目组研究了支持数据敏感溯源解释的隐私保护技术，信息损失降低了82.53%，数据可用率提升了10%左右。为研究支持保护隐私的溯源解释技术提供了技术支撑。 .（3）基于参数敏感的溯源解释：项目组首先研究了基于参数敏感的图结构聚类溯源解释算法，为不同的非期望数据提供了有效的参数精炼策略，随后项目组对算法进行了优化，解释效率提升了一个数量级。第二，项目组研究了基于参数敏感的top-k查询溯源解释算法，在保护隐私的同时对top-k查询中的期望数据进行了有效的解释。然后，项目组研究了流数据环境下内存受限的近似连续top-k查询优化算法，查询效率提升了数倍，为提升top-k查询溯源解释的效率提供了技术支撑。第三，项目组研究了基于参数变化的图结构聚类增量计算算法，聚类效率提升了至少10倍，为提高基于参数敏感的图结构聚类溯源解释的效率提供了理论保证。第四，项目组基于机器学习研究了图数据中结点的文本属性分类算法以及基于用户实例簇的图结构聚类参数计算算法，为提高图结构聚类溯源解释的效率提供了技术支撑。