IMLS：用于大规模属性图的迭代有损图摘要方法

doi:10.3778/j.issn.1673-9418.2502013

摘要/Abstract

摘要： 随着计算资源的进步，越来越多的现实世界数据以图的形式存储在计算机中。然而，直接处理大规模图所需的时间和资源成本不断攀升。有损图摘要技术在确保保留图的整体结构和主要属性的前提下，对图进行精炼和删减，从而生成一个近似输入图的紧凑表示，来获得较小存储需求和更高计算效率。然而，已有的工作通常面临计算效率与摘要质量的不平衡，或缺乏节点属性的纳入。为了解决这些问题，提出了一种基于迭代最小哈希局部敏感哈希（MinHash-LSH）的有损图摘要方法IMLS。方法通过引入结合属性权重的得分函数评估节点合并收益，迭代地合并节点对，生成一个限制节点数量的摘要图，旨在最大限度地减少重构误差与存储大小，同时最大限度地提高节点同质性。实验结果表明，IMLS在压缩比相似的情况下，运行时间比同类方法快约51.3倍，且能够生成较同类方法重构误差低约91.87%的摘要图。此外，IMLS方法具有线性可扩展性，适用于大规模图，并且通过控制属性权重参数，能够确保生成的摘要图具有可控的节点同质性。

关键词: 图计算, 图摘要, 图压缩, 图简化

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 summarization 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.

ZHAO Danfeng, MA Jian, HE Qi, ZHENG Xiaoluo, LI Minggang. IMLS: Iterative Lossy Graph Summarization for Large-Scale Attributed Graphs[J]. Journal of Frontiers of Computer Science and Technology, 2025, 19(11): 2967-2980.

参考文献

[1] BONCHI F, CASTILLO C, GIONIS A, et al. Social network analysis and mining for business applications[J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2(3): 1-37.
[2] ZHAO D F, LOU Y R, SONG W, et al. Stability analysis of reef fish communities based on symbiotic graph model[J]. Aquaculture and Fisheries, 2024, 9(6): 1007-1017.
[3] NAVLAKHA S, SCHATZ M C, KINGSFORD C. Revealing biological modules via graph summarization[J]. Journal of Computational Biology, 2009, 16(2): 253-264.
[4] ZHAO D F, YANG X S, SONG W, et al. Visibility graph analysis of the sea surface temperature irreversibility during El Ni?o events[J]. Nonlinear Dynamics, 2023, 111(18): 17393- 17409.
[5] KISTLER M, PERRONE M, PETRINI F. Cell multiprocessor communication network: built for speed[J]. IEEE Micro, 2006, 26(3): 10-23.
[6] NAGURNEY A. A multiclass, multicriteria traffic network equilibrium model[J]. Mathematical and Computer Modelling, 2000, 32(3/4): 393-411.
[7] LIU Y K, SAFAVI T, DIGHE A, et al. Graph summarization methods and applications: a survey[J]. ACM Computing Surveys, 2018, 51(3): 1-34.
[8] 孙伟, 张羽. 利用流挖掘和图挖掘的内网异常检测方法[J]. 计算机科学与探索, 2020, 14(7): 1154-1163.
SUN W, ZHANG Y. Intranet anomaly detection method using flow mining and graph mining[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(7): 1154-1163.
[9] YUAN Y, MA D L, WEN Z Y, et al. Efficient graph query processing over geo-distributed datacenters[C]//Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2020: 619-628.
[10] JAVED H T, KHAN K U, CHEEMA M F, et al. Instance-based lossless summarization of knowledge graph with optimized triples and corrections (IBA-OTC)[J]. IEEE Access, 2024, 12: 5584-5604.
[11] MISHRA P, KUMAR S, CHAUBE M K. Graph interpretation, summarization and visualization techniques: a review and open research issues[J]. Multimedia Tools and Applications, 2023, 82(6): 8729-8771.
[12] KOUTRA D, KANG U, VREEKEN J, et al. Summarizing and understanding large graphs[J]. Statistical Analysis and Data Mining, 2015, 8(3): 183-202.
[13] ALI S, SHAKEEL M H, KHAN I, et al. Predicting attributes of nodes using network structure[J]. ACM Transactions on Intelligent Systems and Technology, 2021, 12(2): 1-23.
[14] BERAHMAND K, LI Y F, XU Y. DAC-HPP: deep attributed clustering with high-order proximity preserve[J]. Neural Computing and Applications, 2023, 35(34): 24493-24511.
[15] LEE K, JO H, KO J, et al. SSumM: sparse summarization of massive graphs[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2020: 144-154.
[16] ALI S, AHMAD M, BEG M A, et al. SsAG: summarization and sparsification of attributed graphs[J]. ACM Transactions on Knowledge Discovery from Data, 2024, 18(6): 1-22.
[17] BRODER A. On the resemblance and containment of documents[C]//Proceedings of the Compression and Complexity of Sequences 1997. Piscataway: IEEE, 1997: 21-29.
[18] INDYK P, MOTWANI R. Approximate nearest neighbors: towards removing the curse of dimensionality[C]//Proceedings of the 30th Annual ACM Symposium on Theory of Computing. New York: ACM, 1998: 604-613.
[19] NAVLAKHA S, RASTOGI R, SHRIVASTAVA N. Graph summarization with bounded error[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2008: 419-432.
[20] KHAN K U, NAWAZ W, LEE Y K. Set-based approximate approach for lossless graph summarization[J]. Computing, 2015, 97(12): 1185-1207.
[21] SHIN K, GHOTING A, KIM M, et al. SWeG: lossless and lossy summarization of web-scale graphs[C]//Proceedings of the 2019 World Wide Web Conference. New York: ACM, 2019: 1679-1690.
[22] JACCARD P. The distribution of the flora in the alpine zone[J]. New Phytologist, 1912, 11(2): 37-50.
[23] YONG Q, HAJIABADI M, SRINIVASAN V, et al. Efficient graph summarization using weighted LSH at billion-scale[C]//Proceedings of the 2021 International Conference on Management of Data. New York: ACM, 2021: 2357-2365.
[24] LEE K, KO J, SHIN K. SLUGGER: lossless hierarchical summarization of massive graphs[C]//Proceedings of the 2022 IEEE 38th International Conference on Data Engineering. Piscataway: IEEE, 2022: 472-484.
[25] LEFEVRE K, TERZI E. GraSS: graph structure summarization[C]//Proceedings of the 2010 SIAM International Conference on Data Mining, 2010: 454-465.
[26] RIONDATO M, GARCíA-SORIANO D, BONCHI F. Graph summarization with quality guarantees[C]//Proceedings of the 2014 IEEE International Conference on Data Mining. Piscataway: IEEE, 2014: 947-952.
[27] BEG M A, AHMAD M, ZAMAN A, et al. Scalable approximation algorithm for graph summarization[C]//Advances in Knowledge Discovery and Data Mining: the 22nd Pacific-Asia Conference. Cham: Springer, 2018: 502-514.
[28] RISSANEN J. Modeling by shortest data description[J]. Automatica, 1978, 14(5): 465-471.
[29] SHANNON C E. A mathematical theory of communication[J]. Bell System Technical Journal, 1948, 27(3): 379-423.
[30] MCAULEY J, LESKOVEC J. Learning to discover social circles in ego networks[C]//Proceedings of the 26th International Conference on Neural Information Processing Systems, 2012: 539-547.
[31] DIESNER J, FRANTZ T L, CARLEY K M. Communication networks from the enron email corpus “it’s always about the people. Enron is no different”[J]. Computational & Mathematical Organization Theory, 2005, 11(3): 201-228.
[32] YANG J, LESKOVEC J. Defining and evaluating network communities based on ground-truth[C]//Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics. New York: ACM, 2012: 1-8.
[33] LESKOVEC J, ADAMIC L A, HUBERMAN B A. The dynamics of viral marketing[J]. ACM Transactions on the Web, 2007, 1(1): 5.
[34] LESKOVEC J, LANG K J, DASGUPTA A, et al. Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters[J]. Internet Mathematics, 2009, 6(1): 29-123.
[35] ADAMIC L A, GLANCE N. The political blogosphere and the 2004 U.S. election: divided they blog[C]//Proceedings of the 3rd International Workshop on Link Discovery. New York: ACM, 2005: 36-43.
[36] ROZEMBERCZKI B, ALLEN C, SARKAR R. Multi-scale attributed node embedding[J]. Journal of Complex Networks, 2021, 9(2).
[37] ROZEMBERCZKI B, DAVIES R, SARKAR R, et al. GEMSEC: graph embedding with self clustering[C]//Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Piscataway: IEEE, 2019: 65-72.
[38] CORMODE G, MUTHUKRISHNAN S. An improved data stream summary: the count-min sketch and its applications[J]. Journal of Algorithms, 2005, 55(1): 58-75.