Heuristic approaches for non-exhaustive pattern-based change detection in dynamic networks
Pages 1455 - 1492
Abstract
Dynamic networks are ubiquitous in many domains for modelling evolving graph-structured data and detecting changes allows us to understand the dynamic of the domain represented. A category of computational solutions is represented by the pattern-based change detectors (PBCDs), which are non-parametric unsupervised change detection methods based on observed changes in sets of frequent patterns over time. Patterns have the ability to depict the structural information of the sub-graphs, becoming a useful tool in the interpretation of the changes. Existing PBCDs often rely on exhaustive mining, which corresponds to the worst-case exponential time complexity, making this category of algorithms inefficient in practice. In fact, in such a case, the pattern mining process is even more time-consuming and inefficient due to the combinatorial explosion of the sub-graph pattern space caused by the inherent complexity of the graph structure. Non-exhaustive search strategies can represent a possible approach to this problem, also because not all the possible frequent patterns contribute to changes in the time-evolving data. In this paper, we investigate the viability of different heuristic approaches which prevent the complete exploration of the search space, by returning a concise set of sub-graph patterns (compared to the exhaustive case). The heuristics differ on the criterion used to select representative patterns. The results obtained on real-world and synthetic dynamic networks show that these solutions are effective, when mining patterns, and even more accurate when detecting changes.
References
[1]
Akoglu L, Tong H, and Koutra D Graph based anomaly detection and description: a survey Data Min Knowledge Discovery 2015 29 3 626-688
[2]
Bailey, J. (2013). Statistical measures for contrast patterns. In: Contrast Data Mining: Concepts, Algorithms, and Applications, CRC Press, (pp. 13–20)
[3]
Barik M, Hafidi I, and Rochd Y Review of heuristic algorithms for frequent itemsets mining problem Computing and Informatics 2023 42 6 1360-1377
[4]
Bell, S., McDiarmid, A., Irvine, J. (2011). Nodobo: Mobile phone as a software sensor for social network research. In: Proceedings of the 73rd IEEE Vehicular Technology Conference, VTC Spring 2011, 15-18 May 2011, Budapest, Hungary, (pp. 1–5)
[5]
Bifet, A., Holmes, G., Pfahringer, B., Gavaldà, R. (2011). Mining frequent closed graphs on evolving data streams. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, August 21-24, 2011, (pp. 591–599),
[6]
Brandes U and Lerner J Visualization of conflict networks Nato Security Through Science Series - E: Human and Societal Dynamics 2008 36 169
[7]
Calders, T., Rigotti, C., Boulicaut, J. (2004). A survey on condensed representations for frequent sets. In: Constraint-Based Mining and Inductive Databases, European Workshop on Inductive Databases and Constraint Based Mining, Hinterzarten, Germany, March 11-13, 2004, Revised Selected Papers, (pp. 64–80),
[8]
Chaturvedi A, Tiwari A, and Spyratos N minstab: Stable network evolution rule mining for system changeability analysis IEEE Transaction on Emerging Topics in Computational Intelligence 2021 5 2 274-283
[9]
Chavary, E.A., Erfani, S.M., Leckie, C. (2017). Summarizing significant changes in network traffic using contrast pattern mining. In: E. Lim, M. Winslett, M. Sanderson, A.W. Fu, J. Sun, J.S. Culpepper, E. Lo, J.C. Ho, D. Donato, R. Agrawal, Y. Zheng, C. Castillo, A. Sun, V.S. Tseng, C. Li (eds.), Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM 2017, Singapore, November 06 - 10, 2017, ACM, (pp. 2015–2018),
[10]
Chen J, Zhang J, Xu X, Fu C, Zhang D, Zhang Q, and Xuan Q E-LSTM-D: A deep learning framework for dynamic network link prediction IEEE Transaction on System Man, and Cybernetics System 2021 51 6 3699-3712
[11]
Djenouri, Y., Drias, H., Chemchem, A. (2013). A hybrid bees swarm optimization and tabu search algorithm for association rule mining. In: Fifth World Congress on Nature and Biologically Inspired Computing, NaBIC 2013, Fargo, ND, USA, August 12-14, 2013, (pp. 120–125),
[12]
Djenouri, Y., Drias, H., Habbas, Z., Mosteghanemi, H. (2012). Bees swarm optimization for web association rule mining. In: 2012 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology, Macau, China, December 4-7, 2012, (pp. 142–146),
[13]
Dong, G., Li, J. (1999). Efficient mining of emerging patterns: Discovering trends and differences. In: Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, August 15-18, 1999, (pp. 43–52),
[14]
Dong G, Han J, Lam JMW, Pei J, Wang K, and Zou W Mining constrained gradients in large databases IEEE Transactions on Knowledge and Data Engineering 2004 16 8 922-938
[15]
Dzyuba V, van Leeuwen M, and Raedt LD Flexible constrained sampling with guarantees for pattern mining Data Mining and Knowledge Discovery 2017 31 5 1266-1293
[16]
Ferreira, C.H.G., Ferreira, F.M., de Sousa Matos, B., de Almeida, J.M. (2019). Modeling dynamic ideological behavior in political networks. The Journal of Web Science7
[17]
Flouvat F, Selmaoui-Folcher N, Sanhes J, Mu C, Pasquier C, and Boulicaut J Mining evolutions of complex spatial objects using a single-attributed directed acyclic graph Knowledge and Information System 2020 62 10 3931-3971
[18]
Fukushima S and Yamanishi K Detecting metachanges in data streams from the viewpoint of the MDL principle Entropy 2019 21 12 1134
[19]
Galbrun E The minimum description length principle for pattern mining: a survey Data Mining and Knowledge Discovery 2022 36 5 1679-1727
[20]
Geerts, F., Goethals, B., Mielikäinen, T. (2004). Tiling databases. In: E. Suzuki, S. Arikawa, (eds.), Discovery Science, 7th International Conference, DS 2004, Padova, Italy, October 2-5, 2004, Proceedings, Springer, Lecture Notes in Computer Science, (vol 3245, pp. 278–289),
[21]
Giacometti, A., Soulet, A. (2016). Frequent pattern outlier detection without exhaustive mining. In: Advances in Knowledge Discovery and Data Mining - 20th Pacific-Asia Conference, PAKDD 2016, Auckland, New Zealand, April 19-22, 2016, Proceedings, Part II, (pp. 196–207),
[22]
Goyal, P., Kamra, N., He, X., Liu, Y. (2018). Dyngem: Deep embedding method for dynamic graphs. arXiv:1805.11273
[23]
Goyal, P., Chhetri, S. R., & Canedo, A. (2020). dyngraph2vec: Capturing network dynamics using dynamic graph representation learning. Knowledge-Based System,187,.
[24]
Grattarola D, Zambon D, Livi L, and Alippi C Change detection in graph streams by learning graph embeddings on constant-curvature manifolds IEEE Transaction on Neural Networks and Learning System 2020 31 6 1856-1869
[25]
Haghir Chehreghani M, Abdessalem T, Bifet A, and Bouzbila M Sampling informative patterns from large single networks Future Generation Computer Systems 2020 106 653-658
[26]
Hasan MA and Zaki MJ Output space sampling for graph patterns PVLDB 2009 2 1 730-741
[27]
Hewapathirana IU, Lee D, Moltchanova E, and McLeod JC Change detection in noisy dynamic networks: a spectral embedding approach Social Network Analysis and Mining 2020 10 1 14
[28]
Impedovo, A., Ceci, M., Calders, T. (2019). Efficient and accurate non-exhaustive pattern-based change detection in dynamic networks. In: Discovery Science - 22nd International Conference, DS 2019, Split, Croatia, October 28-30, 2019, Proceedings, (pp. 396–411),
[29]
Impedovo A, Loglisci C, Ceci M, and Malerba D jkarma: A highly-modular framework for pattern-based change detection on evolving data Knowledge-Based System 2020 192 105303
[30]
Kalnay E, Kanamitsu M, Kistler R, Collins W, Deaven D, Gandin L, Iredell M, Saha S, White G, Woollen J, et al. The ncep/ncar 40-year reanalysis project Bulletin of the American Meteorological Society 1996 77 3 437-472
[31]
Koufakou A, Secretan J, and Georgiopoulos M Non-derivable itemsets for fast outlier detection in large high-dimensional categorical data Knowledge and Information System 2011 29 3 697-725
[32]
Li, J., Dani, H., Hu, X., Tang, J., Chang, Y., Liu, H. (2017). Attributed network embedding for learning in a dynamic environment. In: E. Lim, M. Winslett, M. Sanderson, A.W. Fu, J. Sun, J.S. Culpepper, E. Lo, J.C. Ho, D. Donato, R. Agrawal, Y. Zheng, C. Castillo, A. Sun, V.S. Tseng, C. Li, (eds.), Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM 2017, Singapore, November 06 - 10, 2017, ACM, (pp. 387–396),
[33]
Lim AH, Lee C, and Raman M Hybrid genetic algorithm and association rules for mining workflow best practices Expert System and Application 2012 39 12 10544-10551
[34]
Loglisci C, Ceci M, Impedovo A, and Malerba D Mining microscopic and macroscopic changes in network data streams Knowledge-Based System 2018 161 294-312
[35]
Luo R and Krishnamurthy V Fréchet-statistics-based change point detection in dynamic social networks IEEE Transaction on Computing Social System 2024 11 2 2863-2871
[36]
Ma, Y., Guo, Z., Ren, Z., Tang, J., Yin, D. (2020). Streaming graph neural networks. In: J.X. Huang, Y. Chang, X. Cheng, J. Kamps, V. Murdock, J. Wen, Y. Liu. (eds.), Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020, ACM, (pp. 719–728),
[37]
Micevska S, Awad A, and Sakr S SDDM: an interpretable statistical concept drift detection method for data streams Journal of Intelligence Information System 2021 56 3 459-484
[38]
Mitrovic, S., De Weerdt, J. (2019). Dyn2vec: Exploiting dynamic behaviour using difference networks-based node embeddings for classification. In: Proceedings of the International Conference on Data Science, CSREA Press, (pp. 194–200)
[39]
Paudel R and Eberle W An approach for concept drift detection in a graph stream using discriminative subgraphs ACM Transaction on Knowledge Discovery Data 2020 14 6 70:1-70:25
[40]
Preti G, Morales GDF, and Riondato M Maniacs: Approximate mining of frequent subgraph patterns through sampling ACM Transaction Intelligence Systems and Technology 2023 14 3 54:1-54:29
[41]
Rymon, R. (1992). Search through systematic set enumeration. In: Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR’92). Cambridge, MA, October 25-29, 1992., (pp. 539–550)
[42]
Scharwächter, E., Müller, E., Donges, J.F., Hassani, M., Seidl, T. (2016). Detecting change processes in dynamic networks by frequent graph evolution rule mining. In: IEEE 16th International Conference on Data Mining, ICDM 2016, December 12-15, 2016, Barcelona, Spain, (pp. 1191–1196),
[43]
Schrodt PA, Davis SG, and Weddle JL Political science: Keds’a program for the machine coding of event data Social Science Computer Review 1994 12 4 561-587
[44]
Sulem D, Kenlay H, Cucuringu M, and Dong X Graph similarity learning for change-point detection in dynamic networks Machine Learning 2024 113 1 1-44
[45]
Taheri, A., Gimpel, K., Berger-Wolf, T.Y. (2019). Learning to represent the evolution of dynamic graphs with recurrent models. In: S. Amer-Yahia, M. Mahdian, A. Goel, G. Houben, K. Lerman, J.J. McAuley, R. Baeza-Yates, L. Zia, (eds.), Companion of The 2019 World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019, ACM, (pp. 301–307),
[46]
van Leeuwen M, Bie TD, Spyropoulou E, and Mesnage C Subjective interestingness of subgraph patterns Machine Learning 2016 105 1 41-75
[47]
van Leeuwen M, Siebes A (2008) Streamkrimp: Detecting change in data streams. In: W. Daelemans, B. Goethals, K. Morik, (eds.), Machine Learning and Knowledge Discovery in Databases, European Conference, ECML/PKDD 2008, Antwerp, Belgium, September 15-19, 2008, Proceedings, Part I, Springer, Lecture Notes in Computer Science, (vol. 5211, pp. 672–687),
[48]
Ventura, S., & Luna, J. M. (2016). Pattern Mining with Evolutionary Algorithms. Springer.
[49]
Wang, T., Yang, Y., Gao, H., Hu, Q. (2023). MRSCN: A gnn-based model for mining relationship strength changes between nodes in dynamic networks. In: X. Wang, M.L. Sapino, W. Han, A.E. Abbadi, G. Dobbie, Z. Feng, Y. Shao, H. Yin, (eds.), Database Systems for Advanced Applications - 28th International Conference, DASFAA 2023, Tianjin, China, April 17-20, 2023, Proceedings, Part III, Springer, Lecture Notes in Computer Science, (vol. 13945, pp. 172–182),
[50]
Xiong, Y., Zhang, Y., Fu, H., Wang, W., Zhu, Y., Yu, P.S. (2019). Dyngraphgan: Dynamic graph embedding via generative adversarial networks. In: G. Li, J. Yang, J. Gama, J. Natwichai, Y. Tong, (eds.), Database Systems for Advanced Applications - 24th International Conference, DASFAA 2019, Chiang Mai, Thailand, April 22-25, 2019, Proceedings, Part I, Springer, Lecture Notes in Computer Science, (vol. 11446, pp. 536–552),
[51]
Yamanishi, K. (2023). MDL Change Detection, Springer Nature Singapore, Singapore, (pp. 209–263).
[52]
Yamanishi, K., Miyaguchi, K. (2016). Detecting gradual changes from data stream using mdl-change statistics. In: 2016 IEEE International Conference on Big Data, BigData 2016, Washington DC, USA, December 5-8, 2016, (pp 156–163),
[53]
Zhang T, Wei Q, and Lu L NFE-PCN: A node feature enhanced embedding framework for pattern change in dynamic network IEEE Access 2023 11 54569-54576
Index Terms
- Heuristic approaches for non-exhaustive pattern-based change detection in dynamic networks
Index terms have been assigned to the content through auto-classification.
Recommendations
Efficient and Accurate Non-exhaustive Pattern-Based Change Detection in Dynamic Networks
Discovery ScienceAbstractPattern-based change detectors (PBCDs) are non-parametric unsupervised change detection methods that are based on observed changes in sets of frequent patterns over time. In this paper we study PBCDs for dynamic networks; that is, graphs that ...
A pattern language for creating pattern languages: 364 patterns for pattern mining, writing, and symbolizing
PLoP '16: Proceedings of the 23rd Conference on Pattern Languages of ProgramsIn this paper, we present the purpose, creating process, and overview of a pattern language for creating pattern languages, consisting 364 patterns for pattern mining, pattern writing, and pattern symbolizing. For the past 10 years, we, Iba Lab, have ...
Hyperclique pattern discovery
Existing algorithms for mining association patterns often rely on the support-based pruning strategy to prune a combinatorial search space. However, this strategy is not effective for discovering potentially interesting patterns at low levels of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s) 2024.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 02 July 2024
Accepted: 20 June 2024
Revision received: 18 June 2024
Received: 06 March 2024
Author Tags
Qualifiers
- Research-article
Funding Sources
- Università degli Studi di Bari Aldo Moro
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Nov 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in