南京大学学报（自然科学版）2026，Vol.62Issue(4)：629-646,18.DOI:10.13232/j.cnki.jnju.2026.04.009
结构保持式图约简框架
Structure-preserving graph reduction framework
摘要
Abstract
Large-scale graph data,such as knowledge graphs and social networks,are ubiquitous.The enormous size of these graphs poses significant challenges for analytical tasks like frequent pattern mining(FPM).Graph reduction techniques have emerged as a key enabler for large-scale graph analysis,as they can drastically reduce graph size while preserving critical information.However,existing graph reduction methods primarily focus on retaining specific attribute information or minimizing global information loss,often neglecting the preservation of local high-order structures.This limitation leads to suboptimal support for FPM tasks.To address this issue,we propose a Structure-Preserving Graph Reduction Framework(SPGRF)that retains a higher quantity of high-quality frequent patterns while reducing data scale.First,we introduce a local-to-global edge importance evaluation method that guides the construction of an initial reduction skeleton by precisely identifying key nodes and core edges.Second,to compensate for structural degradation caused by reduction,we design a neighborhood-based skeleton enhancement mechanism to improve the structural diversity and completeness of the reduced graph.Extensive experiments on real-world graphs demonstrate the superiority of our framework across multiple metrics.The generated reduced graphs effectively preserve the original"backbone"structure:when the graph is reduced to 10%of its original size(reduction rate=0.1),the accuracy of top-k(k=800)frequent patterns on the Wiki dataset reaches 96%.关键词
图约简/频繁模式挖掘/图卷积网络/约简骨架Key words
graph reduction/frequent pattern mining/graph convolutional networks/reduced skeleton分类
信息技术与安全科学引用本文复制引用
潘海洋,童贞豪,谢文波,王欣..结构保持式图约简框架[J].南京大学学报（自然科学版）,2026,62(4):629-646,18.基金项目
国家自然科学基金(62172102) （62172102）
