基于Motif的图模式感知采样

doi:10.6040/j.issn.1672-3961.0.2025.252

摘要/Abstract

摘要： 针对在图数据快速增长背景下,现有图采样方法难以获取支持下游任务的高质量采样图的问题,提出一种基于Motif的图模式感知采样(Motif-based graph pattern-aware sampling, MGPA)方法。设计基于Motif信息的加权采样(Motif-informed weighted sampling, MIWS)策略,通过节点权重引导游走过程优先访问高价值区域,实现对富含频繁模式区域的针对性采样;构建基于邻域匹配的节点权重预测模型EchoModel,联合学习节点属性、局部结构与外部Motif模式集合,为每个节点输出引导游走权重,准确反映节点重要性;设计邻域匹配引导下的节点特征生成算法DomainMatching,通过量化节点邻域与预定义Motif模式集合的匹配程度,为每个节点生成富含邻域信息的目标向量,向EchoModel提供可靠的训练监督信息。由MIWS依据节点权重进行带偏好的随机游走,优先探索富含频繁模式的区域。试验结果表明,在多种评价指标下,MGPA均展现出优异性能,在采样率仅为20%的条件下,top-k(k=100)频繁模式的挖掘准确率最高可达96%。

关键词: 图采样, 频繁模式挖掘, 图卷积网络, Motif, 图稀疏化

Abstract: To address the problem that existing graph sampling methods were unable to obtain high-quality sampled graphs supporting downstream tasks under the rapid growth of graph data, a Motif-based graph pattern-aware sampling(MGPA)method was proposed. A Motif-informed weighted sampling(MIWS)strategy was designed, in which the walking process was guided by node weights so that high-value regions were preferentially visited, achieving targeted sampling of regions rich in frequent patterns. A neighborhood-matching-based node weight prediction model(EchoModel)was constructed to jointly learn node attributes, local structures, and an external Motif pattern set, and output the weight of the guiding walk for each node to accurately reflect node importance. A neighborhood-matching-guided node feature generation algorithm(DomainMatching)was designed. By quantifying the matching degree between each node's neighborhood and a predefined Motif pattern set, a target vector enriched with neighborhood information was produced for every node by the algorithm, and reliable supervisory information was thereby provided for the training of EchoModel. Biased random walks were performed by MIWS according to the node weights, and regions rich in frequent patterns were preferentially explored. Experimental results showed that superior performance was achieved by MGPA across multiple evaluation metrics, and a mining accuracy of up to 96% was attained for the top-k(k=100)frequent patterns under a sampling rate of only 20%.

Key words: graph sampling, frequent pattern mining, graph convolutional network, Motif, graph sparsification

中图分类号:

TP311

胡滨,王欣,谢文波,张翀,晏思思,肖峻峰. 基于Motif的图模式感知采样[J]. 山东大学学报 (工学版), 2026, 56(5): 79-91.

Hu Bin, Wang Xin, Xie Wenbo, Zhang Chong, Yan Sisi, Xiao Junfeng. Motif-based graph pattern-aware sampling[J]. Journal of Shandong University(Engineering Science), 2026, 56(5): 79-91.

参考文献

[1] Daud N N, Ab Hamid S H, Saadoon M, et al. Applications of link prediction in social networks: areview[J]. Journal of Network and Computer Appli-cations, 2020, 166: 102716.
[2] Qian Y J, Guo J, Tu Z K, et al. MolScribe: robust molecular structure recognition with image-to-graph generation[J]. Journal of Chemical Information and Modeling, 2023, 63(7): 1925-1934.
[3] Nguyen L B Q, Zelinka I, Snasel V, et al. Subgraph mining in a large graph: a review[J]. WIREs Data Mining and Knowledge Discovery, 2022, 12(4): e1454.
[4] Stumpf M P H, Wiuf C, May R M. Subnets of scale-free networks are not scale-free: sampling properties of networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2005, 102(12): 4221-4224.
[5] Nakajima K, Shudo K. Social graph restoration via random walk sampling[C] //2022 IEEE 38th Interna-tional Conference on Data Engineering(ICDE). Kuala Lumpur, Malaysia: IEEE, 2022: 806-819.
[6] Yousuf M I, KIM S. List sampling for large graphs[J]. Intelligent Data Analysis, 2018, 22(2): 261-295.
[7] Ahmed N K, Neville J, Kompella R. Network sampling: from static to streaming graphs[J]. ACM Transactions on Knowledge Discovery from Data, 2014, 8(2): 7.
[8] Zhou Z G, Shi C, Shen X L, et al. Context-aware sampling of large networks via graph representation learning[J]. IEEE Transactions on Visualization and Computer Graphics, 2021, 27(2): 1709-1719.
[9] Zhang X, Ni Y N, Li S Y, et al. A survey of large graph sampling techniques[J]. Journal of Computer-Aided Design & Computer Graphics, 2022, 34(12): 1805-1814.
[10] Ricaud B, Aspert N, Miz V. Spikyball sampling: exploring large networks via an inhomogeneous filtered diffusion[J]. Algorithms, 2020, 13(11): 275.
[11] Li Y K, Wu Z Y, Lin S, et al. Walking with perception: efficient random walk sampling via common neighbor awareness[C] //2019 IEEE 35th International Conference on Data Engineering(ICDE). Macao, China: IEEE, 2019: 962-973.
[12] 王鑫隆, 胡睿, 郭亚梁, 等. 面向节点分类任务的节点级自适应图卷积神经网络[J]. 模式识别与人工智能,2024, 37(4): 287-298. Wang Xinlong, Hu Rui, Guo Yaliang, et al. Node-level adaptive graph convolutional neural network for node classification tasks[J]. Pattern Recognition and Artificial Intelligence, 2024, 37(4): 287-298.
[13] Zhang L L, Jiang H, Wang F, et al. DRaWS: a dual random-walk based sampling method to efficiently estimate distributions of degree and clique size over social networks[J]. Knowledge-Based Systems, 2020, 198: 105891.
[14] Xie H, Yi P, Li Y K, et al. Optimizing random walk based statistical estimation over graphs via bootstrapping[J]. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(3): 2916-2929.
[15] Ali S, Ahmad M, Beg M A, et al. SsAG: summari-zation and sparsification of attributed graphs[J]. ACM Transactions on Knowledge Discovery from Data, 2024, 18(6): 141.
[16] Lee K, Jo H, Ko J, et al. SSumM: sparse summari-zation of massive graphs[C] //Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York, USA: ACM, 2020: 144-154.
[17] Milo R, Shen-Orr S, Itzkovitz S, et al. Network Motifs: simple building blocks of complex networks[J]. Science, 2002, 298(5594): 824-827.
[18] Seufert M, Lange S, Hoßfeld T, et al. More than topology:joint topology and attribute sampling and generation of social network graphs[J]. Computer Communications, 2016, 73: 176-187.
[19] Wagner C, Singer P, Karimi F, et al. Sampling from social networks with attributes[C] //Proceedings of the 26th International Conference on World Wide Web. Perth, Australia: ACM, 2017: 1181-1190.
[20] Lin M K, Li W Z, Lu S L. Balanced influence maximization in attributed social network based on sampling[C] //Proceedings of the 13th International Conference on Web Search and Data Mining. Houston, USA: ACM, 2020: 375-383.
[21] Kumar S, Sundaram H. Attribute-guided network sampling mechanisms[J]. ACM Transactions on Knowledge Discovery from Data, 2021, 15(4): 69.
[22] 石俊豪, 王欣, 邹杰军, 等. 基于Motif的图采样算法[J]. 南京大学学报(自然科学), 2024, 60(4): 552-565. Shi Junhao, Wang Xin, Zou Jiejun, et al. Motif-based graph sampling algorithm[J]. Journal of Nanjing University(Natural Science), 2024, 60(4): 552-565.
[23] Gao X Y, Yu J L, Chen T, et al. Graph condensation: a survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2025, 37(4): 1819-1837.
[24] Wang X, Lan Z, He Y A, et al. A cost-effective approach for mining near-optimal top-k patterns[J]. Expert Systems with Applications, 2022, 202: 117262.
[25] 邹杰军, 王欣, 石俊豪, 等. 面向大图的Top-Rank-K频繁模式挖掘算法[J]. 南京大学学报(自然科学), 2024, 60(1): 38-52. Zou Jiejun, Wang Xin, Shi Junhao, et al. Top-Rank-K frequent pattern mining algorithm for large graphs[J]. Journal of Nanjing University(Natural Science), 2024, 60(1): 38-52.
[26] Wang X, Shi J H, Zou J J, et al. Supports estimation via graph sampling[J]. Expert Systems with Appli-cations, 2024, 240: 122554.
[27] Ribeiro P, Paredes P, Silva M E P, et al. A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets[J]. ACM Computing Surveys, 2021, 54(2): 28.
[28] Elseidy M, Abdelhamid E, Skiadopoulos S, et al. GraMi:frequent subgraph and pattern mining in a single large graph[J]. Proceedings of the VLDB Endowment, 2014, 7(7): 517-528.
[29] Yang J, Leskovec J. Defining and evaluating network communities based on ground-truth[J]. Knowledge and Information Systems, 2015, 42(1): 181-213.
[30] Rozemberczki B, Allen C, Sarkar R. Multi-scale attributed node embedding[J]. Journal of Complex Networks, 2021, 9(2): cnab014.
[31] Cheng X, Dale C, Liu J C. Statistics and social network of YouTube videos[C] //2008 16th International Work-shop on Quality of Service. Enschede, Netherlands: IEEE, 2008: 229-238.
[32] Yousuf M I, Anwer I, Anwar R. Empirical characteri-zation of graph sampling algorithms[J]. Social Network Analysis and Mining, 2023, 13(1): 66.
[33] Ribeiro B, Towsley D. Estimating and sampling graphs with multidimensional random walks[C] //Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement. Melbourne, Australia: ACM, 2010: 390-403.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed