Journal of Shandong University(Engineering Science) ›› 2026, Vol. 56 ›› Issue (5): 79-91.doi: 10.6040/j.issn.1672-3961.0.2025.252

• Machine Learning & Data Mining • Previous Articles    

Motif-based graph pattern-aware sampling

Hu Bin, Wang Xin*, Xie Wenbo, Zhang Chong, Yan Sisi, Xiao Junfeng   

  1. Hu Bin, Wang Xin*, Xie Wenbo, Zhang Chong, Yan Sisi, Xiao Junfeng(School of Computer Science and Software Engineering, Southwest Petroleum University, Chengdu 610500, Sichuan, China
  • Published:2026-10-19

PDF (PC)

4

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

CLC Number: 

  • TP311
[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.
[1] ZHENG Zheming, KONG Lingling, HE Yin. Short-term wind power prediction model based on spatial-temporal graph convolutional network with dual-graph structure [J]. Journal of Shandong University(Engineering Science), 2026, 56(2): 130-138.
[2] HUANG Fang, WANG Xin, GAO Guohai, SHEN Lingzhen, FU Xun, FANG Yu. Mining Top-k frequent patterns for graphs based on subjective and objective metrics [J]. Journal of Shandong University(Engineering Science), 2025, 55(6): 1-12.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd