Pattern detection in large temporal graphs using algebraic fingerprints
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Authors
Date
2020
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
9
Series
Proceedings of the 2020 SIAM International Conference on Data Mining, SDM 2020, pp. 37-45
Abstract
In this paper, we study a family of pattern-detection problems in vertex-colored temporal graphs. In particular, given a vertex-colored temporal graph and a multi-set of colors as a query, we search for temporal paths in the graph that contain the colors specified in the query. These types of problems have several interesting applications, for example, recommending tours for tourists, or searching for abnormal behavior in a network of financial transactions. For the family of pattern-detection problems we define, we establish complexity results and design an algebraic-algorithmic framework based on constrained multilinear sieving. We demonstrate that our solution can scale to massive graphs with up to hundred million edges, despite the problems being NP-hard. Our implementation, which is publicly available, exhibits practical edge-linear scalability and highly optimized. For example, in a real-world graph dataset with more than six million edges and a multi-set query with ten colors, we can extract an optimal solution in less than eight minutes on a haswell desktop with four cores.Description
| openaire: EC/H2020/871042/EU//SoBigData-PlusPlus
Keywords
Other note
Citation
Thejaswi, S & Gionis, A 2020, Pattern detection in large temporal graphs using algebraic fingerprints . in C Demeniconi & N Chawla (eds), Proceedings of the 2020 SIAM International Conference on Data Mining, SDM 2020 . Proceedings of the 2020 SIAM International Conference on Data Mining, SDM 2020, Society for Industrial and Applied Mathematics, pp. 37-45, SIAM International Conference on Data Mining, Cincinnati, Ohio, United States, 07/05/2020 . https://doi.org/10.1137/1.9781611976236.5