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 .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

SPGRF: A Structure-Preserving Graph Reduction Framework

  • Xin Wang,
  • Haiyang Pan,
  • Zhenhao Tong,
  • Ji Zhang,
  • Bin Hu,
  • Wenbo Xie

摘要

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 .