图概要技术研究进展

Progress and Challenges of Graph Summarization Techniques

图的概要化,简称图概要,旨在寻找一组简洁的超图或稀疏图,阐明原始图的主要结构信息或变化趋势.当前图概要的研究大多结合原始图的应用领域和背景,使用不同的概要技术构建一个特定的概要图,解决目前大图面临的信息过载、查询优化、空间压缩、影响分析、社交网络可视化等问题.对现有的图概要技术进行了汇总,以概要主要目的作为分类标准划分为基于空间压缩的图概要、基于查询优化的图概要、基于模式可视化的图概要和基于影响分析的图概要四大类,针对部分属性图和无属性图概要算法在真实数据集上进行了相关实验,并从压缩率、信息保持率、信息熵和时间进行对比分析.点明图概要的发展趋势,并指出图概要面临的挑战和可深入探索的研究方向,结合热门的深度学习技术提出了部分有价值的的宏观想法用以解决当前挑战.

Graph summarization aims to search a group of simple hypergraphs or sparse graphs,which illustrate the main structural information or change trend of the original graph.Based on the application field and background of original graph,different graph summarization techniques are used to construct a specific summary graph,which can solve the problems of information overload,query optimization,spatial compression,impact analysis,social network visualization and so on.According to the classification criteria of the main purpose of the summary,the existing graph summarization techniques are divided into four categories:the graph summarization based on spatial compression,the graph summarization based on query optimization,the graph summarization based on pattern visualization and the graph summarization based on impact analysis.The partial graph summarization algorithms of non-attribute graphs and attribute graphs are tested on real data sets to analyze the indexes of information retention rate,compression rate,information entropy and running time experimentally.At last,not only the development trends of the graph summarization are highlighted,but also the challenges and the future research directions that can be explored in depth are pointed out.Combining with the popular deep learning technology,some valuable and potential Macro coutermeasures are put forward to solve these challenges.