More Web Proxy on the site http://driver.im/

research-article

Public Access

Discovering Graph Temporal Association Rules

Authors:

Mohammad Hossein Namaki,

Tingjian GeAuthors Info & Claims

CIKM '17: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management

Pages 1697 - 1706

https://doi.org/10.1145/3132847.3133014

Published: 06 November 2017 Publication History

Abstract

Detecting regularities between complex events in temporal graphs is critical for emerging applications. This paper proposes graph temporal association rules (GTAR). A GTAR extends traditional association rules to discover temporal associations for complex events captured by a class of temporal pattern queries. We introduce notions of support and confidence for GTARS and formalize the discovery problem for GTARS. We show that despite the enhanced expressive power, GTARS discovery is feasible over large temporal graphs. We develop an effective rule discovery algorithm, which integrates event mining and rule discovery as a single process, and reduces the redundant computation by leveraging their interaction. Using real-life and synthetic data, we experimentally verify the effectiveness and scalability of the algorithms. Our case study also verifies that GTARS demonstrate highly interpretable associations in real-world networks.

References

[1]

sl http://memeburn.com/2015/10/ddos-attacks-increasingly-used-as-smokescreen-for-other-security-threats/.

[2]

Z. Abedjan, C. G. Akcora, M. Ouzzani, P. Papotti, and M. Stonebraker. Temporal rules discovery for web data cleaning. VLDB, pages 336--347, 2015.

Digital Library

[3]

C. C. Aggarwal, Y. Li, P. S. Yu, and R. Jin. On dense pattern mining in graph streams. VLDB, pages 975--984, 2010.

Digital Library

[4]

R. Agrawal, T. Imieli'nski, and A. Swami. Mining association rules between sets of items in large databases. SIGMOD Record, 22(2):207--216, 1993.

Digital Library

[5]

J. M. Ale and G. H. Rossi. An approach to discovering temporal association rules. In SIGAPP, pages 294--300, 2000.

Digital Library

[6]

X. Ao, P. Luo, C. Li, F. Zhuang, and Q. He. Online frequent episode mining. In ICDE, pages 891--902, 2015.

[7]

B. Arai, G. Das, D. Gunopulos, and N. Koudas. Anytime measures for top-k algorithms. In VLDB, pages 914--925, 2007.

Digital Library

[8]

M. Berlingerio, F. Bonchi, B. Bringmann, and A. Gionis. Mining graph evolution rules. In ECML PKDD, pages 115--130. 2009.

[9]

P. Bogdanov, M. Mongiovi, and A. K. Singh. Mining heavy subgraphs in time-evolving networks. In ICDM, pages 81--90, 2011.

Digital Library

[10]

K. M. Borgwardt, H.-P. Kriegel, and P. Wackersreuther. Pattern mining in frequent dynamic subgraphs. In ICDM, 2006.

Digital Library

[11]

X. Chen and I. Petrounias. Mining temporal features in association rules. In PKDD, pages 295--300. 1999.

Digital Library

[12]

W. Fan. Graph pattern matching revised for social network analysis. In ICDT, 2012.

Digital Library

[13]

W. Fan, X. Wang, Y. Wu, and J. Xu. Association rules with graph patterns. VLDB, pages 1502--1513, 2015.

Digital Library

[14]

W. Fan, Y. Wu, and J. Xu. Functional dependencies for graphs. In SIGMOD, 2016.

Digital Library

[15]

M. Fellendorf and P. Vortisch. Microscopic traffic flow simulator vissim. In Fundamentals of traffic simulation, pages 63--93. 2010.

[16]

J. Gao, C. Zhou, and J. X. Yu. Toward continuous pattern detection over evolving large graph with snapshot isolation. VLDB, pages 1--22, 2015.

Digital Library

[17]

X. Gao and M. P. Singh. Mining contracts for business events and temporal constraints in service engagements. TSC, pages 427--439, 2014.

[18]

L. Geng and H. J. Hamilton. Interestingness measures for data mining: A survey. CSUR, page 9, 2006.

Digital Library

[19]

S. Gurukar, S. Ranu, and B. Ravindran. Commit: A scalable approach to mining communication motifs from dynamic networks. In SIGMOD, 2015.

Digital Library

[20]

M. R. Henzinger, T. A. Henzinger, and P. W. Kopke. Computing simulations on finite and infinite graphs. In FOCS, 1995.

Digital Library

[21]

H.-P. Hsieh and C.-T. Li. Mining temporal subgraph patterns in heterogeneous information networks. In SocialCom, pages 282--287, 2010.

Digital Library

[22]

P.-s. Kam and A. Fu. Discovering temporal patterns for interval-based events. DaWaK, pages 317--326, 2000.

Digital Library

[23]

B. Liu, Y. Ma, and R. Lee. Analyzing the interestingness of association rules from the temporal dimension. In ICDM, pages 377--384, 2001.

Digital Library

[24]

D. Lo and S.-C. Khoo. Mining patterns and rules for software specification discovery. VLDB, pages 1609--1616, 2008.

Digital Library

[25]

S. Ma, Y. Cao, W. Fan, J. Huai, and T. Wo. Capturing topology in graph pattern matching. VLDB, pages 310--321, 2011.

Digital Library

[26]

S. Mansfield-Devine. The growth and evolution of ddos. Network Security, pages 13--20, 2015.

Digital Library

[27]

M. H. Namaki, K. Sasani, Y. Wu, and T. Ge. Beams: Bounded event detection in graph streams. In ICDE, pages 1387--1388, 2017.

[28]

B. Özden, S. Ramaswamy, and A. Silberschatz. Cyclic association rules. In ICDE, pages 412--421, 1998.

Digital Library

[29]

A. Paranjape, A. R. Benson, and J. Leskovec. Motifs in temporal networks. In WSDM, pages 601--610, 2017.

Digital Library

[30]

F. Pennerath and A. Napoli. The model of most informative patterns and its application. In MLKDD, pages 205--220. 2009.

[31]

C. Rainsford and J. Roddick. Adding temporal semantics to association rules. PKDD, pages 504--509, 1999.

Digital Library

[32]

K. Semertzidis and E. Pitoura. Durable graph pattern queries on historical graphs. In ICDE, 2016.

[33]

B. Shaparenko, R. Caruana, J. Gehrke, and T. Joachims. Identifying temporal patterns and key players in document collections. In TDM, 2005.

[34]

A. Silva, W. Meira Jr, and M. J. Zaki. Mining attribute-structure correlated patterns in large attributed graphs. VLDB, pages 466--477, 2012.

Digital Library

[35]

C. Song, T. Ge, C. Chen, and J. Wang. Event pattern matching over graph streams. VLDB, pages 413--424, 2014.

Digital Library

[36]

V. Srinivasan, S. Moghaddam, A. Mukherji, K. K. Rachuri, C. Xu, and E. M. Tapia. Mobileminer: Mining your frequent patterns on your phone. In UbiComp, pages 389--400, 2014.

Digital Library

[37]

Q. Yuan, G. Cong, and A. Sun. Graph-based point-of-interest recommendation with geographical and temporal influences. In CIKM, 2014.

Digital Library

[38]

Y. Zhang, Q. Ji, and H. Lu. Event detection in complex scenes using interval temporal constraints. In ICCV, pages 3184--3191, 2013.

Digital Library

Cited By

Gionis AOettershagen LSarpe IChua TNgo CKumar RLauw HKa-Wei Lee R(2024)Mining Temporal NetworksCompanion Proceedings of the ACM Web Conference 202410.1145/3589335.3641245(1260-1263)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589335.3641245
Xin HChen L(2024)KartGPS: Knowledge Base Update with Temporal Graph Pattern-based Semantic Rules2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00105(5075-5087)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00105
Liu DKwashie SZhang YZhou GBewong MWu XGuo XHe KFeng Z(2024)An efficient approach for discovering Graph Entity Dependencies (GEDs)Information Systems10.1016/j.is.2024.102421125(102421)Online publication date: Nov-2024
https://doi.org/10.1016/j.is.2024.102421
Show More Cited By

Index Terms

Discovering Graph Temporal Association Rules

Recommendations

Discovering Temporal Association Rules: Algorithms, Language and System
ICDE '00: Proceedings of the 16th International Conference on Data Engineering

Due to a wide variety of application potentials of association rules, the problem of association rule discovery has been studied for several years. Most previous work overlooks time components, which are usually attached to transactions in databases. ...
ARMADA - An algorithm for discovering richer relative temporal association rules from interval-based data

Temporal association rule mining promises the ability to discover time-dependent correlations or patterns between events in large volumes of data. To date, most temporal data mining research has focused on events existing at a point in time rather than ...
Incremental sequential patterns for multivariate temporal association rules mining
Abstract
Most temporal association rule mining algorithms can mine the temporal relationship between items, but the sequential relations between successive items remain unknown, while sequential pattern mining algorithms can discover the ...
Highlights
- PrefixSpan is extended to mine fuzzy sequential pattern from multivariate time series.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '17: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management

November 2017

2604 pages

ISBN:9781450349185

DOI:10.1145/3132847

General Chairs:
Ee-Peng Lim
Singapore Management University, Singapore
,
Marianne Winslett
University of Illinois at Urbana-Champaign, USA, and Advanced Digital Sciences Center, Singapore
,
Program Chairs:
Mark Sanderson
RMIT, Australia
,
Ada Fu
Chinese University of Hong Kong, Hong Kong
,
Jimeng Sun
Georgia Tech, USA
,
Shane Culpepper
RMIT, Australia
,
Eric Lo
Chinese University of Hong Kong, Hong Kong
,
Joyce Ho
Emory University, USA
,
Debora Donato
Mix Tech, Inc., USA
,
Rakesh Agrawal
Data Insights Laboratories, USA
,
Yu Zheng
Microsoft Research Asia, China
,
Carlos Castillo
Qatar Computing Research Institute, Qatar
,
Aixin Sun
Nanyang Technological University, Singapore
,
Vincent S. Tseng
National Cheng Kung University, Taiwan
,
Chenliang Li
Wuhan University, China

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Google Faculty Research Award.
National Science Foundation

Conference

CIKM '17

Sponsor:

CIKM '17: ACM Conference on Information and Knowledge Management

November 6 - 10, 2017

Singapore, Singapore

Acceptance Rates

CIKM '17 Paper Acceptance Rate 171 of 855 submissions, 20%;

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
865
Total Downloads

Downloads (Last 12 months)93
Downloads (Last 6 weeks)11

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gionis AOettershagen LSarpe IChua TNgo CKumar RLauw HKa-Wei Lee R(2024)Mining Temporal NetworksCompanion Proceedings of the ACM Web Conference 202410.1145/3589335.3641245(1260-1263)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589335.3641245
Xin HChen L(2024)KartGPS: Knowledge Base Update with Temporal Graph Pattern-based Semantic Rules2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00105(5075-5087)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00105
Liu DKwashie SZhang YZhou GBewong MWu XGuo XHe KFeng Z(2024)An efficient approach for discovering Graph Entity Dependencies (GEDs)Information Systems10.1016/j.is.2024.102421125(102421)Online publication date: Nov-2024
https://doi.org/10.1016/j.is.2024.102421
Gao CZhou ZShi LOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Noether embeddingProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668213(48185-48202)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668213
Huang CZhang QGuo DZhao XWang X(2023)Discovering Association Rules with Graph Patterns in Temporal NetworksTsinghua Science and Technology10.26599/TST.2021.901009028:2(344-359)Online publication date: Apr-2023
https://doi.org/10.26599/TST.2021.9010090
Alipourlangouri MMansfield AChiang FWu Y(2023)Inconsistency Detection with Temporal Graph Functional Dependencies2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00042(464-476)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00042
Huynh BNguyen LNguyen DNguyen NNguyen HPham TPham TNguyen LNguyen TVo B(2023)Mining Association Rules from a Single Large GraphCybernetics and Systems10.1080/01969722.2022.216274055:3(693-707)Online publication date: 18-Jan-2023
https://doi.org/10.1080/01969722.2022.2162740
Xue BZou L(2022)Knowledge Graph Quality Management: a Comprehensive SurveyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.3150080(1-1)Online publication date: 2022
https://doi.org/10.1109/TKDE.2022.3150080
Song QNamaki MLin PWu Y(2022)Answering Why-Questions for Subgraph QueriesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.304643634:10(4636-4649)Online publication date: 1-Oct-2022
https://doi.org/10.1109/TKDE.2020.3046436
Chaturvedi ATiwari ASpyratos N(2022)System Network Analytics: Evolution and Stable Rules of a State Series2022 IEEE 9th International Conference on Data Science and Advanced Analytics (DSAA)10.1109/DSAA54385.2022.10032382(1-10)Online publication date: 13-Oct-2022
https://doi.org/10.1109/DSAA54385.2022.10032382
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents