Transforming temporal-dynamic graphs into time-series data for solving event detection problems

Taşcı, Kutay; AKAL, FUAT

doi:10.55730/1300-0632.4023

Transforming temporal-dynamic graphs into time-series data for solving event detection problems

Kutay TAŞCI, (Bilkent Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Ankara, Türkiye)

Fuat AKAL (Hacettepe Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, Ankara, Türkiye)

Turkish Journal of Electrical Engineering and Computer Sciences

3 0

Yıl: 2023 Cilt: 31 Sayı: 5 Sayfa Aralığı: 876 - 891 Metin Dili: İngilizce DOI: 10.55730/1300-0632.4023 İndeks Tarihi: 22-11-2023

Transforming temporal-dynamic graphs into time-series data for solving event detection problems

Öz:

Event detection on temporal-dynamic graphs aims at detecting significant events based on deviations from the normal behavior of the graphs. With the widespread use of social media, many real-world events manifest as social media interactions, making them suitable for modeling as temporal-dynamic graphs. This paper presents a workflow for event detection on temporal-dynamic graphs using graph representation learning. Our workflow leverages generated embeddings of a temporal-dynamic graph to reframe the problem as an unsupervised time-series anomaly detection task. We evaluated our workflow on four distinct real-world social media datasets and compared our results with the related work. The results show that the performance depends on how anomalies deviate from normal. These include changes in both size and topology. Our results are similar to the related work for the graphs where the deviation from a normal state of the temporal-dynamic graph is apparent, e.g., Reddit. On the other hand, we achieved a 3-fold improvement in precision for the graphs where deviations exist on size and topology, e.g., Twitter. Also, our results are 20% to 5-fold better even if we introduced some delay factor. That is, we beat our competition while detecting events that occurred some time ago. As a result, our study proves that graph embeddings as time-series data can be used for event detection tasks.

Anahtar Kelime: Event detection graph representation learning anomaly detection Temporal-dynamic graphs

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

[1] Aggarwal C, Subbian K. Evolutionary network analysis: A survey. ACM Computing Surveys (CSUR) 2014; 47 (1): 1– 36. doi:10.1145/2601412
[2] Goyal P, Ferrara E. Graph embedding techniques, applications, and performance: A survey. Knowledge-Based Systems 2018; 151: 78-94. doi:10.1016/j.knosys.2018.03.022
[3] Rayana S, Akoglu L. Less is more: Building selective anomaly ensembles. ACM Transactions on Knowledge Discovery from Data (TKDD) 2016; 10 (4): 1-33. doi:10.1145/2890508
[4] Chandola V, Banerjee A, Kumar V. Anomaly detection: A survey. ACM Computing Surveys (CSUR) 2009; 41 (3): 1-58. doi:10.1145/1541880.1541882
[5] Hodge V, Austin J. A survey of outlier detection methodologies. Artificial Intelligence Review 2004; 22: 85-126. doi:10.1023/B:AIRE.0000045502.10941.a9
[6] Chen F, Wang YC, Wang B, Kuo CC. Graph representation learning: A survey. APSIPA Transactions on Signal and Information Processing 2020; 9: e15. doi:10.1017/ATSIP.2020.13
[7] Goyal P, Kamra N, He X, Liu Y. Dyngem: Deep embedding method for dynamic graphs. arXiv preprint 2018. doi:10.48550/arXiv.1805.11273
[8] Beladev M, Rokach L, Katz G, Guy I, Radinsky K. tdGraphEmbed: Temporal dynamic graph-level embedding. In: Proceedings of the ACM International Conference on Information & Knowledge Management; 2020. pp. 55-64. doi:10.1145/3340531.3411953
[9] Cordeiro M, Gama J. Online social networks event detection: A survey. Solving Large Scale Learning Tasks. Challenges and Algorithms: Essays Dedicated to Katharina Morik on the Occasion of Her 60th Birthday 2016; 1-41. doi:10.1007/978-3-319-41706-6_1
[10] Atefeh F, Khreich W. A survey of techniques for event detection in twitter. Computational Intelligence 2015; 31 (1): 132-64. doi:10.1111/coin.12017
[11] Hasan M, Orgun MA, Schwitter R. A survey on real-time event detection from the Twitter data stream. Journal of Information Science 2018; 44 (4): 443-63.
[12] Liu Y, Pan S, Wang YG, Xiong F, Wang L et al. Anomaly detection in dynamic graphs via transformer. IEEE Transactions on Knowledge and Data Engineering 2021. doi:10.1109/TKDE.2021.3124061
[13] Ding C, Sun S, Zhao J. MST-GAT: A multimodal spatial–temporal graph attention network for time series anomaly detection. Information Fusion 2023; 89: 527-36. doi:10.1016/j.inffus.2022.08.011
[14] Grover A, Leskovec J. node2vec: Scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; San Francisco, California, USA; 2016, pp. 855- 864. doi:10.1145/2939672.2939754
[15] Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; New York, USA; 2014, pp. 701-710. doi:10.1145/2623330.2623732
[16] Belkin M, Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances in Neural Information Processing Systems 2001; 14.
[17] Roweis ST, Saul LK. Nonlinear dimensionality reduction by locally linear embedding. Science 2000; 290 (5500): 2323-6. doi:10.1126/science.290.5500.232
[18] Cao S, Lu W, Xu Q. Deep neural networks for learning graph representations. In: Proceedings of the AAAI conference on artificial intelligence; 2016, Vol. 30: No. 1. https://doi.org/10.1609/aaai.v30i1.10179
[19] Wang D, Cui P, Zhu W. Structural deep network embedding. In: Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining; 2016, pp. 1225-1234. https://doi.org/10.1145/2939672.2939753
[20] Goyal P, Chhetri SR, Canedo A. dyngraph2vec: Capturing network dynamics using dynamic graph representation learning. Knowledge-Based Systems 2020; 187: 104816. doi:10.1016/j.knosys.2019.06.024
[21] Trivedi R, Farajtabar M, Biswal P, Zha H. Dyrep: Learning representations over dynamic graphs. In: International Conference on Learning Representations; New Orleans, USA; 2019. doi:10.48550/arXiv.1803.04051
[22] Zhou L, Yang Y, Ren X, Wu F, Zhuang Y. Dynamic network embedding by modeling triadic closure pro- cess. In: Proceedings of the AAAI Conference on Artificial Intelligence; New Orleans, USA; 2018. 32:1. doi:10.1609/aaai.v32i1.11257
[23] Narayanan A, Chandramohan M, Venkatesan R, Chen L, Liu Y et al. graph2vec: Learning distributed representa- tions of graphs. arXiv preprint 2017. doi:10.48550/arXiv.1707.0500
[24] Adhikari, B., Zhang, Y., Ramakrishnan, N., Prakash, B.A. Sub2Vec: Feature Learning for Subgraphs. In: 22nd Pacific-Asia Conference; Melbourne, VIC, Australia; 2018, pp. 170-182. doi:10.1007/978-3-319-93037-4_14
[25] ai Y, Ding H, Qiao Y, Marinovic A, Gu K et al. Unsupervised inductive graph-level representation learning via graph-graph proximity. arXiv preprint 2019. doi:10.48550/arXiv.1904.01098
[26] Goldstein M, Uchida S. A comparative evaluation of unsupervised anomaly detection algorithms for multivariate data. PloS one 2016; 11 (4): e0152173. doi:10.1371/journal.pone.0152173
[27] Habeeb RA, Nasaruddin F, Gani A, Hashem IA, Ahmed E et al. Real-time big data processing for anomaly detection: A survey. International Journal of Information Management 2019; 45:289-307. doi:10.1016/j.ijinfomgt.2018.08.006
[28] Geiger A, Liu D, Alnegheimish S, Cuesta-Infante A, Veeramachaneni K. Tadgan: Time series anomaly detection using generative adversarial networks. In: IEEE International Conference on Big Data; Virtual Conference; 2020, pp. 33-43. doi:10.1109/BigData50022.2020.9378139
[29] Pan R, Zhou Y, Cao B, Liu NN, Lukose R et al. One-class collaborative filtering. In: 8th IEEE International Conference on Data Mining; Pisa, Italy; 2008, pp. 502-511. doi:10.1109/ICDM.2008.16
[30] Angiulli F, Pizzuti C. Fast outlier detection in high dimensional spaces. In: 6th European Conference; Helsinki, Finland; 2002, pp. 15-27. doi:10.1007/3-540-45681-3_2
[31] Breunig MM, Kriegel HP, Ng RT, Sander J. LOF: identifying density-based local outliers. In: Proceedings of the ACM SIGMOD International Conference on Management of Data; Dallas, Texas, USA; 2000, pp. 93-104. doi:10.1145/342009.335388
[32] He Z, Xu X, Deng S. Discovering cluster-based local outliers. Pattern Recognition Letters 2003; 24 (9-10): 1641-50. doi:10.1016/S0167-8655(03)00003-5
[33] Pena EH, de Assis MV, Proença ML. Anomaly detection using forecasting methods arima and hwds. In: 32nd International Conference of the Chilean Computer Science Society; Temuco, Cautin, Chile; 2013, pp. 63-66. doi:10.1109/SCCC.2013.18
[34] Torres JM, Nieto PG, Alejano L, Reyes AN. Detection of outliers in gas emissions from urban areas using functional data analysis. Journal of Hazardous Materials 2011; 186 (1): 144-9. doi:10.1016/j.jhazmat.2010.10.091
[35] Ahmad S, Lavin A, Purdy S, Agha Z. Unsupervised real-time anomaly detection for streaming data. Neurocomputing 2017; 262: 134-47. doi:10.1016/j.neucom.2017.04.070
[36] Hundman K, Constantinou V, Laporte C, Colwell I, Soderstrom T. Detecting spacecraft anomalies using lstms and nonparametric dynamic thresholding. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining; New York, USA; 2018, pp. 387-395. doi:10.1145/3219819.3219845
[37] Ringberg H, Soule A, Rexford J, Diot C. Sensitivity of PCA for traﬀic anomaly detection. In: Proceedings of the 2007 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems; San Diego, California, USA; 2007, pp. 109-120. doi:10.1145/1254882.1254895
[38] An J, Cho S. Variational autoencoder based anomaly detection using reconstruction probability. Special lecture on IE 2015; 2 (1): 1-8.
[39] Malhotra P, Ramakrishnan A, Anand G, Vig L, Agarwal P et al. LSTM-based encoder-decoder for multi-sensor anomaly detection. arXiv preprint; 2016. doi:10.48550/arXiv.1607.00148
[40] Li D, Chen D, Jin B, Shi L, Goh J et al. MAD-GAN: Multivariate anomaly detection for time series data with generative adversarial networks. In: 28th International Conference on Artificial Neural Networks; Munich, Germany; 2019, pp. 703-716. doi:10.1007/978-3-030-30490-4_56
[41] Bhatnagar A, Kassianik P, Liu C, et al. Merlion: A machine learning library for time series. arXiv preprint; 2021. doi:10.48550/arXiv.2109.09265
[42] Schubert E, Zimek A, Kriegel HP. Local outlier detection reconsidered: a generalized view on locality with applications to spatial, video, and network outlier detection. Data Mining and Knowledge Discovery 2014; 28: 190-237. doi:10.1007/s10618-012-0300-z

APA	Taşcı K, AKAL F (2023). Transforming temporal-dynamic graphs into time-series data for solving event detection problems. , 876 - 891. 10.55730/1300-0632.4023
Chicago	Taşcı Kutay,AKAL FUAT Transforming temporal-dynamic graphs into time-series data for solving event detection problems. (2023): 876 - 891. 10.55730/1300-0632.4023
MLA	Taşcı Kutay,AKAL FUAT Transforming temporal-dynamic graphs into time-series data for solving event detection problems. , 2023, ss.876 - 891. 10.55730/1300-0632.4023
AMA	Taşcı K,AKAL F Transforming temporal-dynamic graphs into time-series data for solving event detection problems. . 2023; 876 - 891. 10.55730/1300-0632.4023
Vancouver	Taşcı K,AKAL F Transforming temporal-dynamic graphs into time-series data for solving event detection problems. . 2023; 876 - 891. 10.55730/1300-0632.4023
IEEE	Taşcı K,AKAL F "Transforming temporal-dynamic graphs into time-series data for solving event detection problems." , ss.876 - 891, 2023. 10.55730/1300-0632.4023
ISNAD	Taşcı, Kutay - AKAL, FUAT. "Transforming temporal-dynamic graphs into time-series data for solving event detection problems". (2023), 876-891. https://doi.org/10.55730/1300-0632.4023

APA	Taşcı K, AKAL F (2023). Transforming temporal-dynamic graphs into time-series data for solving event detection problems. Turkish Journal of Electrical Engineering and Computer Sciences, 31(5), 876 - 891. 10.55730/1300-0632.4023
Chicago	Taşcı Kutay,AKAL FUAT Transforming temporal-dynamic graphs into time-series data for solving event detection problems. Turkish Journal of Electrical Engineering and Computer Sciences 31, no.5 (2023): 876 - 891. 10.55730/1300-0632.4023
MLA	Taşcı Kutay,AKAL FUAT Transforming temporal-dynamic graphs into time-series data for solving event detection problems. Turkish Journal of Electrical Engineering and Computer Sciences, vol.31, no.5, 2023, ss.876 - 891. 10.55730/1300-0632.4023
AMA	Taşcı K,AKAL F Transforming temporal-dynamic graphs into time-series data for solving event detection problems. Turkish Journal of Electrical Engineering and Computer Sciences. 2023; 31(5): 876 - 891. 10.55730/1300-0632.4023
Vancouver	Taşcı K,AKAL F Transforming temporal-dynamic graphs into time-series data for solving event detection problems. Turkish Journal of Electrical Engineering and Computer Sciences. 2023; 31(5): 876 - 891. 10.55730/1300-0632.4023
IEEE	Taşcı K,AKAL F "Transforming temporal-dynamic graphs into time-series data for solving event detection problems." Turkish Journal of Electrical Engineering and Computer Sciences, 31, ss.876 - 891, 2023. 10.55730/1300-0632.4023
ISNAD	Taşcı, Kutay - AKAL, FUAT. "Transforming temporal-dynamic graphs into time-series data for solving event detection problems". Turkish Journal of Electrical Engineering and Computer Sciences 31/5 (2023), 876-891. https://doi.org/10.55730/1300-0632.4023