模式感知采样算法研究  

Research on pattern aware sampling algorithm

作　　者：沈玲珍 王欣 石俊豪 王璐[1] SHEN Lingzhen;WANG Xin;SHI Junhao;WANG Lu(School of Computer Science and Software Engineering,Southwest Petroleum University,Chengdu 610500,China)

机构地区：[1]西南石油大学计算机与软件学院,四川成都610500

出　　处：《计算机工程与科学》2025年第4期740-750,共11页Computer Engineering & Science

基　　金：国家自然科学基金(62172102);四川省科技创新人才基金(2022JDRC009)。

摘　　要：图数据规模的迅速膨胀,传统分析技术难以应对,尤其在频繁模式挖掘任务中,传统算法往往面临计算资源崩溃的风险。图采样技术能够有效减小数据体量,并进而降低计算开销,已成为图数据分析任务重要的研究方向。然而,现有的图采样算法对频繁模式挖掘任务的支持存在局限,其原因是这些算法未能充分将图数据的关键属性融入结构特征,从而导致采样质量较低。为此,提出了兼顾图的高频结构与关键属性的模式感知采样PAS算法。PAS依托邻域(局部特征)和高频单边模式(全局特征)对图中节点和边进行加权,随后通过在加权图上的有偏游走,完成采样任务。实验表明,PAS在多项指标上优于基线算法,并且能在采样图上挖掘出与原图高度一致的前B个频繁模式,在采样率仅为0.20的设定下,准确率最高达到94%。With the rapid expansion of graph data scale,traditional analysis techniques struggle to cope with,particularly in frequent pattern mining tasks where traditional algorithms are at risk of computational resource collapse.Graph sampling technology effectively reduces data volume and calculation cost,making it a crucial research direction in graph data analysis.However,existing graph sampling algorithms have limitations in supporting frequent pattern mining tasks.The reason is that these algorithms fail to fully incorporate the key attributes of graph data into structural features,resulting in lower sampling quality.Therefore,this paper proposes a pattern aware sampling(PAS)algorithm that considers the high frequency structure and key attributes of the graph.PAS utilizes neighborhoods(local features)and high frequency single-edge patterns(global features)to weight nodes and edges in the graph,and then completes the biased walk on the weighted graph for sampling tasks.Experiments demonstrate that compared with other baseline algorithms,PAS achieves superior performance on multiple indicators and can mine top B frequent patterns highly consistent with those in original graph.Under a sampling ratio of merely 0.20,the accuracy reaches up to 94%.

关 键 词：图采样 频繁模式挖掘 聚合 图属性 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]