计算机科学与探索2025，Vol.19Issue(11)：2967-2980,14.DOI:10.3778/j.issn.1673-9418.2502013
IMLS:用于大规模属性图的迭代有损图摘要方法
IMLS:Iterative Lossy Graph Summarization for Large-Scale Attributed Graphs
摘要
Abstract
With the advancement of computing resources,an increasing amount of real-world data is stored in the form of graphs.However,the time and resource costs required to process large-scale graphs continue to rise.Lossy graph summa-rization techniques refine and reduce the size of the graph while preserving its overall structure and key attributes,generating a compact representation that approximates the input graph.This approach helps to achieve lower storage requirements and higher computational efficiency.However,existing methods often face a trade-off between computational efficiency and summary quality,or fail to incorporate node attributes.To address these issues,this paper proposes an iterative MinHash-LSH(MinHash locality-sensitive hashing)lossy graph summarization method IMLS.The method introduces a scoring function that combines attribute weights to evaluate the benefit of node merging.By iteratively merging node pairs,it generates a summary graph with a restricted number of nodes.The method aims to minimize reconstruction error and storage size while maximizing node homogeneity.Experimental results show that,with similar compression ratios,IMLS is 51.3 times faster than comparable methods and produces summary graphs with 91.87%lower reconstruction error.Additionally,IMLS exhibits linear scalability,making it suitable for large-scale graphs.By controlling the attribute weight parameter,it ensures that the generated summary graphs maintain controllable node homogeneity.关键词
图计算/图摘要/图压缩/图简化Key words
graph computation/graph summarization/graph compression/graph simplification分类
计算机与自动化引用本文复制引用
赵丹枫,马健,贺琪,郑小罗,李明刚..IMLS:用于大规模属性图的迭代有损图摘要方法[J].计算机科学与探索,2025,19(11):2967-2980,14.基金项目
国家自然科学基金(42376194) （42376194）
国家自然科学基金青年项目(42106190). This work was supported by the National Natural Science Foundation of China(42376194),and the Youth Fund of the National Natural Science Foundation of China(42106190). （42106190）
