SPGRF: A Structure-Preserving Graph Reduction Framework
摘要
Large-scale graphs are prevalent. Their vast scale poses formidable challenges for analytical tasks. Graph reduction techniques, which can significantly shrink graph size while preserving key information, have thus become one of the key technologies for large graph analysis. However, existing methods mostly focus on low-order graph properties or task-specific objectives, omitting the high-order structures of a graph. The reduced graphs thus do not meet the expectation on downstream tasks. To address this, we propose the Structure-Preserving Graph Reduction Framework (SPGRF) to retain crucial structure of a large graph. Firstly, a local-to-global edge importance assessment method is developed to guide the construction of an initial graph skeleton. Secondly, a neighborhood-based enhancement mechanism is designed to compensate for the structural loss, producing a reduced graph \(G_s\) , that is better suited for downstream tasks. Extensive experiments on real graphs demonstrate that SPGRF excels across multiple metrics. The reduced graphs effectively preserve the original backbone structure and provide strong support for various downstream tasks, e.g., when the reduction ratio is only 10%, the accuracy on the top-k (k=800) frequent patterns can even reach 96%. The source code is available at https://github.com/oceanphy/SPGRF .