Journal Home > Volume 28 , Issue 2
Tsinghua Science and Technology 2023, 28(2): 344-359 https://doi.org/10.26599/TST.2021.9010090
Open Access | Issue | Published: 29 September 2022

Discovering Association Rules with Graph Patterns in Temporal Networks

Show Author's Information Chu Huang1,  Qianzhen Zhang1,  Deke Guo1( ),  Xiang Zhao1,  Xi Wang1
Science and Technology on Information Systems Engineering Laboratory, College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
Keywords:
graph mining, temporal networks, graph association rule, subgraph pattern matching, big graphs
Cite this article:
Huang C, Zhang Q, Guo D, et al. Discovering Association Rules with Graph Patterns in Temporal Networks. Tsinghua Science and Technology, 2023, 28(2): 344-359. https://doi.org/10.26599/TST.2021.9010090
Download citation
EndNote(RIS)
BibTeX

565

Views

61

Downloads

Citations

3

Crossref

2

WoS

2

Scopus

1

CSCD

Abstract Full text About this article

Discovering regularities between entities in temporal graphs is vital for many real-world applications (e.g., social recommendation, emergency event detection, and cyberattack event detection). This paper proposes temporal graph association rules (TGARs) that extend traditional graph-pattern association rules in a static graph by incorporating the unique temporal information and constraints. We introduce quality measures (e.g., support, confidence, and diversification) to characterize meaningful TGARs that are useful and diversified. In addition, the proposed support metric is an upper bound for alternative metrics, allowing us to guarantee a superset of patterns. We extend conventional confidence measures in terms of maximal occurrences of TGARs. The diversification score strikes a balance between interestingness and diversity. Although the problem is NP-hard, we develop an effective discovery algorithm for TGARs that integrates TGARs generation and TGARs selection and shows that mining TGARs is feasible over a temporal graph. We propose pruning strategies to filter TGARs that have low support or cannot make top- k as early as possible. Moreover, we design an auxiliary data structure to prune the TGARs that do not meet the constraints during the TGARs generation process to avoid conducting repeated subgraph matching for each extension in the search space. We experimentally verify the effectiveness, efficiency, and scalability of our algorithms in discovering diversified top- k TGARs from temporal graphs in real-life applications.


menu
Abstract
Full text
Outline
About this article

Discovering Association Rules with Graph Patterns in Temporal Networks

Show Author's information Chu Huang1, Qianzhen Zhang1, Deke Guo1( ), Xiang Zhao1, Xi Wang1
Science and Technology on Information Systems Engineering Laboratory, College of Systems Engineering, National University of Defense Technology, Changsha 410073, China

Abstract

Discovering regularities between entities in temporal graphs is vital for many real-world applications (e.g., social recommendation, emergency event detection, and cyberattack event detection). This paper proposes temporal graph association rules (TGARs) that extend traditional graph-pattern association rules in a static graph by incorporating the unique temporal information and constraints. We introduce quality measures (e.g., support, confidence, and diversification) to characterize meaningful TGARs that are useful and diversified. In addition, the proposed support metric is an upper bound for alternative metrics, allowing us to guarantee a superset of patterns. We extend conventional confidence measures in terms of maximal occurrences of TGARs. The diversification score strikes a balance between interestingness and diversity. Although the problem is NP-hard, we develop an effective discovery algorithm for TGARs that integrates TGARs generation and TGARs selection and shows that mining TGARs is feasible over a temporal graph. We propose pruning strategies to filter TGARs that have low support or cannot make top- k as early as possible. Moreover, we design an auxiliary data structure to prune the TGARs that do not meet the constraints during the TGARs generation process to avoid conducting repeated subgraph matching for each extension in the search space. We experimentally verify the effectiveness, efficiency, and scalability of our algorithms in discovering diversified top- k TGARs from temporal graphs in real-life applications.

Keywords: graph mining, temporal networks, graph association rule, subgraph pattern matching, big graphs

References(33)

[1]
W. Fan, X. Wang, Y. Wu, and J. Xu, Association rules with graph patterns, Proceedings of the VLDB Endowment, vol. 8, no. 12, pp. 1502–1513, 2015.
DOI Google Scholar
[2]
X. Wang, Y. Xu, R. Zhao, J. Lin, and H. Zhan, Gparminer: A system to mine graph pattern association rules, in Proc. International Conference on Database Systems for Advanced Applications (DASFAA 2019), Chiang Mai, Thailand, 2019, pp. 547–552.
DOI Google Scholar
[3]
X. Wang, Y. Xu, and H. Zhan, Extending association rules with graph patterns, Expert Syst. Appl., vol. 141, no. 10, p. 112897, 2020.
DOI Google Scholar
[4]
P. Lin, Q. Song, and Y. Wu, Fact checking in knowledge graphs with ontological subgraph patterns, Data Sci. Eng., vol. 3, no. 4, pp. 341–358, 2018.
DOI Google Scholar
[5]
Y. Yang, D. Yan, H. Wu, J. Cheng, S. Zhou, and J. C. S. Lui, Diversified temporal subgraph pattern mining, in Proc. 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, 2016, pp. 1965–1974.
DOI Google Scholar
[6]
S. Ma, R. Hu, L. Wang, X. Lin, and J. Huai, Fast computation of dense temporal subgraphs, in Proc. 33rd IEEE International Conference on Data Engineering (ICDE 2017), San Diego, CA, USA, 2017, pp. 361–372.
DOI Google Scholar
[7]
R. Li, J. Su, L. Qin, J. X. Yu, and Q. Dai, Persistent community search in temporal networks, in Proc. 34th IEEE International Conference on Data Engineering (ICDE 2018), Paris, France, 2018, pp. 797–808.
DOI Google Scholar
[8]
D. Guo, B. Ren, and G. Cheng, Minimum-cost forest for uncertain multicast with delay constraints, Tsinghua Science and Technology, vol. 24, no. 2, pp. 147–159, 2019.
DOI Google Scholar
[9]
Y. Qin, D. Guo, X. Lu, and G. Cheng, Design and optimization of VLC enabled data center network, Tsinghua Science and Technology, vol. 25, no. 1, pp. 82–92, 2020.
DOI Google Scholar
[10]
Z. Hu, X. Teng, D. Guo, B. Ren, P. Lv, and Z. Liu, Comparing set reconciliation methods based on bloom filters and their variants, Tsinghua Science and Technology,vol. 21, no. 2, pp. 157–167, 2016.
DOI Google Scholar
[11]
Q. Yuan, G. Cong, and A. Sun, Graph-based point-of-interest recommendation with geographical and temporal influences, in Proc. 23rd ACM International Conference on Conference on Information and Knowledge Management (CIKM 2014), Shanghai, China, 2014, pp. 659–668.
DOI Google Scholar
[12]
S. Amer-Yahia, L. V. S. Lakshmanan, S. Vassilvitskii, and C. Yu, Battling predictability and overconcentration in recommender systems, IEEE Data Eng. Bull., vol. 32, no. 4, pp. 33–40, 2009.
Google Scholar
[13]
D. Xin, H. Cheng, X. Yan, and J. Han, Extracting redundancy-aware top-k patterns, in Proc. 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia, PA, USA, 2006, pp. 444–453.
DOI Google Scholar
[14]
M. H. Namaki, Y. Wu, Q. Song, P. Lin, and T. Ge, Discovering graph temporal association rules, in Proc. 2017 ACM on Conference on Information and Knowledge Management (CIKM 2017), Singapore, 2017, pp. 1697–1706.
DOI Google Scholar
[15]
S. Gollapudi and A. Sharma, An axiomatic approach for result diversification, in Proc. 18th International Conference on World Wide Web (WWW 2009), Madrid, Spain, 2009, pp. 381–390.
DOI Google Scholar
[16]
S. Gurukar, S. Ranu, and B. Ravindran, COMMIT: A scalable approach to mining communication motifs from dynamic networks, in Proc. 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Australia, 2015, pp. 475–489.
DOI Google Scholar
[17]
M. Fiedler and C. Borgelt, Subgraph support in a single large graph, in Proc. 7th IEEE International Conference on Data Mining (ICDM 2007), Omaha, NE, USA, 2007, pp. 399–404.
DOI Google Scholar
[18]
X. Yan and J. Han, GSpan: Graph-based substructure pattern mining, in Proc. 2002 IEEE International Conference on Data Mining (ICDM 2002), Maebashi City, Japan, 2002, pp. 721–724.
Google Scholar
[19]
Q. Zhang, D. Guo, X. Zhao, and A. Guo, On continuously matching of evolving graph patterns, in Proc. 28th ACM International Conference on Information and Knowledge Management (CIKM 2019), Beijing, China, 2019, pp. 2237–2240.
DOI Google Scholar
[20]
S. Huang, A. W. Fu, and R. Liu, Minimum spanning trees in temporal graphs, in Proc. 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Australia, 2015, pp. 419–430.
DOI Google Scholar
[21]
L. Chu, Y. Zhang, Y. Yang, L. Wang, and J. Pei, Online density bursting subgraph detection from temporal graphs, Proc. VLDB Endow., vol. 12, no. 13, pp. 2353–2365, 2019.
DOI Google Scholar
[22]
D. Wen, Y. Huang, Y. Zhang, L. Qin, W. Zhang, and X. Lin, Efficiently answering span-reachability queries in large temporal graphs, in Proc. 36th IEEE International Conference on Data Engineering (ICDE 2020), Dallas, TX, USA, 2020, pp. 1153–1164.
DOI Google Scholar
[23]
Y. Ma, Y. Yuan, M. Liu, G. Wang, and Y. Wang, Graph simulation on large scale temporal graphs, GeoInformatica, vol. 24, no. 1, pp. 199–220, 2020.
DOI Google Scholar
[24]
M. Berlingerio, F. Bonchi, B. Bringmann, and A. Gionis, Mining graph evolution rules, in Proc. 2009th European Conference on Machine Learning and Knowledge Discovery in Databases (ECMLPKDD 2009), Bled, Slovenia, 2009, pp. 115–130.
DOI Google Scholar
[25]
W. Fan, Y. Wu, and J. Xu, Functional dependencies for graphs, in Proc. 2016 International Conference on Management of Data, San Francisco, CA, USA, 2016, pp. 1843–1857.
DOI Google Scholar
[26]
H. Hsieh and C. Li, Mining temporal subgraph patterns in heterogeneous information networks, in Proc. 2010 IEEE Second International Conference on Social Computing, Minneapolis, MN, USA, 2010, pp. 282–287.
DOI Google Scholar
[27]
K. Semertzidis and E. Pitoura, Durable graph pattern queries on historical graphs, in Proc. 2016 IEEE 32nd International Conference on Data Engineering (ICDE 2016), Helsinki, Finland, 2016, pp. 541–552.
DOI Google Scholar
[28]
J. Gao, C. Zhou, and J. X. Yu, Toward continuous pattern detection over evolving large graph with snapshot isolation, VLDB J., vol. 25, no. 2, pp. 269–290, 2016.
DOI Google Scholar
[29]
A. Paranjape, A. R. Benson, and J. Leskovec, Motifs in temporal networks, in Proc. Tenth ACM International Conference on Web Search and Data Mining (WSDM 2017), Cambridge, UK, 2017, pp. 601–610.
DOI Google Scholar
[30]
M. Kuramochi and G. Karypis, Finding frequent patterns in a large sparse graph*, Data Min. Knowl. Discov., vol. 11, no. 3, pp. 243–271, 2005.
DOI Google Scholar
[31]
M. Elseidy, E. Abdelhamid, S. Skiadopoulos, and P. Kalnis, GraMi: Frequent subgraph and pattern mining in a single large graph, Proc. VLDB Endow., vol. 7, no. 7, pp. 517–528, 2014.
DOI Google Scholar
[32]
M. Kuramochi and G. Karypis, GREW—A scalable frequent subgraph discovery algorithm, in Proc. 4th IEEE International Conference on Data Mining (ICDM2004), Brighton, UK, 2004, pp. 439–442.
DOI Google Scholar
[33]
C. Chen, X. Yan, F. Zhu, and J. Han, GApprox: Mining frequent approximate patterns from a massive network, in Proc. 7th IEEE International Conference on Data Mining (ICDM 2007), Omaha, NE, USA, 2007, pp. 445–450.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 31 October 2021
Revised: 19 November 2021
Accepted: 22 November 2021
Published: 29 September 2022
Issue date: April 2023

Copyright

© The author(s) 2023.

Acknowledgements

This work was partially supported by the National Key Research and Development Program (No. 2018YFB1800203), National Natural Science Foundation of China (No. U19B2024), and Postgraduate Scientific Research Innovation Project of Hunan Province (No. CX20210038).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return