Fast Algorithm for Approximate Motif Counting in Temporal Graph Streams

Wang Jingjing; Wang Yanhao; Jiang Wenjun; Zeng Yifu; Zhu Tuanfei

doi:10.7544/issn1000-1239.202330788

Journal of Computer Research and Development > 2025 > 62(3): 709-719. > DOI: 10.7544/issn1000-1239.202330788 CSTR: 32373.14.issn1000-1239.202330788

Wang Jingjing, Wang Yanhao, Jiang Wenjun, Zeng Yifu, Zhu Tuanfei. Fast Algorithm for Approximate Motif Counting in Temporal Graph Streams[J]. Journal of Computer Research and Development, 2025, 62(3): 709-719. DOI: 10.7544/issn1000-1239.202330788

Citation:

PDF (1755 KB)

Fast Algorithm for Approximate Motif Counting in Temporal Graph Streams

1.
College of Computer Science and Engineering, Changsha University, Changsha 410022
2.
School of Data Science and Engineering, East China Normal University, Shanghai 200062
3.
College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082

Funds: This work was supported by the National Key Research and Development Program of China (2022ZD0118302 ), the National Natural Science Foundation of China (62202169, 62006030, 62302061, 62302062, 62172149, 62172372, 62372067), the Natural Science Foundation of Hunan Province (2023JJ40080，2023JJ40081), the Scientific Research Foundation of Hunan Provincial Education Department (24B0789), and Changsha Natural Science Foundation (kq2502339).

More Information

Author Bio:
Wang Jingjing: born in 1991. PhD, lecturer. Member of CCF. Her main research interests include graph data mining and social network analysis

Wang Yanhao: born in 1990. PhD, associate professor, PhD supervisor. Member of CCF. His main research interests include algorithm design and analysis, graph data mining, and responsible data management. (yhwang@dase.ecnu.edu.cn)

Jiang Wenjun: born in 1982. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include social network analysis and recommendation system, smart education, and learning optimization

Zeng Yifu: born in 1990. PhD, master supervisor. Member of CCF. His main research interests include data management, network of data center

Zhu Tuanfei: born in 1987. PhD, associate professor, master supervisor. Member of CCF. His main research interests include ensemble learning and imbalanced data learning
Received Date: October 09, 2023
Revised Date: February 05, 2024
Available Online: October 29, 2024

Graphical Abstract

Abstract

Abstract

Graphs often have rich temporal information and evolve dynamically over time, which can be modeled as temporal graph streams. A temporal graph stream consists of a set of vertices and a series of timestamped and directed edges, where new vertices and edges arrive continuously over time. Temporal motifs are generalizations of subgraph patterns in static graphs which take into account edge orderings and durations in addition to topologies. Counting the number of occurrences of temporal motifs is a fundamental problem for temporal graph analysis. However, traditional streaming subgraph counting methods cannot support temporal matching, and are only suitable for simple graphs that do not contain temporal information. In addition, existing temporal motifs counting methods suffer from poor performance in temporal graph streams. We thus study approximate temporal motif counting via random sampling in temporal graph streams. We propose a generic streaming edge sampling (SES) algorithm to estimate the number of instances of any temporal motif in a given temporal graph stream. We then provide comprehensive analyses of the theoretical bounds and time complexities of SES. Finally, we perform extensive experimental evaluations for SES on four real world datasets. The results show that SES achieves up to three orders of magnitude speedups over the state-of-the-art sampling methods while having comparable estimation errors for temporal motif counting in the streaming setting.
- temporal motif,
- motif counting,
- temporal graph streams,
- random sampling,
- graph algorithm

FullText(HTML)

References (26)

References

[1]	Holme P, Saramäki J. Temporal networks[J]. Physics Reports, 2012, 519(3): 97−125 doi: 10.1016/j.physrep.2012.03.001
[2]	Gurukar S, Ranu S, Ravindran B. Commit: A scalable approach to mining communication motifs from dynamic networks[C]// Proc of the 36th ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2015: 475−489
[3]	张天明,赵杰,金露,等. 时态图顶点介数中心度计算方法[J]. 计算机研究与发展,2023,60(10):2383−2393 doi: 10.7544/issn1000-1239.202220650 Zhang Tianming, Zhao Jie, Jin Lu, et al. Vertex betweenness centrality computation method over temporal graphs[J]. Journal of Computer Research and Development, 2023, 60(10): 2383−2393 (in Chinese) doi: 10.7544/issn1000-1239.202220650
[4]	张天明,徐一恒,蔡鑫伟,等. 时态图最短路径查询方法[J]. 计算机研究与发展,2022,59(2):362−375 doi: 10.7544/issn1000-1239.20210893 Zhang Tianming, Xu Yiheng, Cai Xinwei, et al. A shortest path query method over temporal graphs[J]. Journal of Computer Research and Development, 2022, 59(2): 362−375 (in Chinese) doi: 10.7544/issn1000-1239.20210893
[5]	Paranjape A, Benson A R, Leskovec J. Motifs in temporal networks[C]//Proc of the 10th ACM Int Conf on Web Search and Data Mining (WSDM). New York: ACM, 2017: 601−610
[6]	Li Ronghua, Su Jiao, Qin Lu, et al. Persistent community search in temporal networks[C]//Proc of the 34th IEEE Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2018: 797−808
[7]	Hameed K, Johnston R, Younce B, et al. Motif-based exploratory data analysis for state-backed platform manipulation on Twitter[C]//Proc of the 17th Int AAAI Conf on Web and Social Media. Palo Alto, CA: AAAI, 2023: 315−326
[8]	Liu P, Benson A R, Charikar M. Sampling methods for counting temporal motifs[C]//Proc of the 12th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2019: 294−302
[9]	Kumar R, Calders T. 2SCENT: An efficient algorithm to enumerate all simple temporal cycles[J]. Proceedings of the VLDB Endowment, 2018, 11(11): 1441−1453 doi: 10.14778/3236187.3236197
[10]	Kosyfaki C, Mamoulis N, Pitoura E, et al. Flow motifs in interaction networks[D]. Ioannina, Greece: University of Ioannina, 2019
[11]	Kovanen L, Karsai M, Kaski K, et al. Temporal motifs in time dependent networks[J]. Journal of Statal Mechanics Theory and Experiment, 2011, 11(11): 1−18
[12]	Mackey P, Porterfield K, Fitzhenry E, et al. A chronological edge-driven approach to temporal subgraph isomorphism[C]//Proc of the 2018 IEEE Int Conf on Big Data. Piscataway, NJ: IEEE, 2018: 3972−3979
[13]	Wang Jingjing, Wang Yanhao, Jiang Wenjun, et al. Efficient sampling algorithms for approximate temporal motif counting[C]//Proc of the 29th ACM Int Conf on Information and Knowledge Management. New York: ACM, 2020: 1505−1514
[14]	Viard J, Latapy M, Magnien C. Revealing contact patterns among high-school students using maximal cliques in link streams[C]//Proc of the 2015 IEEE/ACM Int Conf on Advances in Social Networks Analysis and Mining. Piscataway, NJ: IEEE, 2015: 1517−1522
[15]	Viard T, Latapy M, Magnien C. Computing maximal cliques in link streams[J]. Theoretical Computer Science, 2016, 609(1): 245−252
[16]	Himmel A S, Molter H, Niedermeier R, et al. Enumerating maximal cliques in temporal graphs[C]//Proc of the 2016 IEEE/ACM Int Conf on Advances in Social Networks Analysis and Mining. Piscataway, NJ: IEEE, 2016: 337−344
[17]	Oettershagen L, Kriege N M, Jordan C, et al. A temporal graphlet kernel for classifying dissemination in evolving networks[C]// Proc of the 23rd SIAM Int Conf on Data Mining (SDM). Philadelphia, PA: SIAM, 2023: 19−27
[18]	Cai Xinwei, Ke Xiangyu, Wang Kai, et al. Efficient temporal butterfly counting and enumeration on temporal bipartite graphs[J]. arXiv preprint, arXiv: 2306.00893, 2023
[19]	潘敏佳,李荣华,赵宇海,等. 面向时序图数据的快速环枚举算法[J]. 软件学报,2020,31(12):3823−3835 Pan Minjia, Li Ronghua, Zhao Yuhai, et al. Fast temporal cycle enumeration algorithm on temporal graphs[J]. Journal of Software, 2020, 31(12): 3823−3835 (in Chinese)
[20]	Lim Y, Kang U. Mascot: Memory-efficient and accurate sampling for counting local triangles in graph streams[C]//Proc of the 21st ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2015: 685−694
[21]	McGregor A, Vorotnikova S, Vu H T. Better algorithms for counting triangles in data streams[C]//Proc of the 35th ACM SIGMOD-SIGACT-SIGAI Symp on Principles of Database Systems. New York: ACM, 2016: 401−411
[22]	Hassan Z R, Ali S, Khan I, et al. Computing graph descriptors on edge streams[J]. ACM Transactions on Knowledge Discovery from Data, 2023, 17(8): 1−25
[23]	Wang Kaixin, Long Cheng, Yan Da, et al. Reinforcement learning enhanced weighted sampling for accurate subgraph counting on fully dynamic graph streams[C]//Proc of the 39th IEEE Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2023: 1084−1097
[24]	Li Rundong, Wang Pinghui, Jia Peng, et al. Approximately counting butterflies in large bipartite graph streams[J]. IEEE Transactions on Knowledge and Data Engineering, 2021, 34(12): 5621−5635
[25]	Xuan Wei, Cao Huawei, Yan Mingyu, et al. BSR-TC: Adaptively sampling for accurate triangle counting over evolving graph streams[J]. International Journal of Software Engineering and Knowledge Engineering, 2021, 31(11/12): 1561−1581
[26]	Leskovec J, Sosic R. SNAP: A general-purpose network analysis and graph-mining library[J]. ACM Transactions on Intelligent Systems, 2016, 8(1): 1−20

Cited By

Cited by

Periodical cited type(6)

1.	王博，万良，叶金贤，刘明盛，孙菡迪. 融合稀疏注意力机制在DDoS攻击检测中的应用. 计算机工程与设计. 2024(05): 1312-1320 .
2.	刘泽坤，宫鑫，刘秀，安龙，吕延滨，刘欣. 基于电力数据中台的行为审计工具建设. 电力大数据. 2024(02): 62-68 .
3.	崔峻玮，翟亚红. 近邻成分分析下的DDoS攻击检测. 湖北汽车工业学院学报. 2023(02): 36-41 .
4.	冯景瑜，张静，时翌飞. 物联网中具备终端匿名的加密流量双层过滤方法. 西安邮电大学学报. 2023(02): 72-81 .
5.	王冲，魏子令，陈曙晖. 基于自注意力机制的无边界应用动作识别方法. 计算机研究与发展. 2022(05): 1092-1104 . 本站查看
6.	邹福泰，俞汤达，许文亮. 基于隐马尔可夫模型的加密恶意流量检测. 软件学报. 2022(07): 2683-2698 .