Finding Path Motifs in Large Temporal Graphs Using Algebraic Fingerprints
No Thumbnail Available
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in 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)
Other link related to publication (opens in new window)
Date
2020-10-01
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
28
Series
Big Data, Volume 8, issue 5, pp. 335-362
Abstract
We study a family of pattern-detection problems in vertex-colored temporal graphs. In particular, given a vertex-colored temporal graph and a multiset 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 applications, for example, in recommending tours for tourists or detecting abnormal behavior in a network of financial transactions. For the family of pattern-detection problems we consider, we establish complexity results and design an algebraic-algorithmic framework based on constrained multilinear sieving. We demonstrate that our solution scales to massive graphs with up to a billion edges for a multiset query with 5 colors and up to 100 million edges for a multiset query with 10 colors, despite the problems being non-deterministic polynomial time-hard. Our implementation, which is publicly available, exhibits practical edge-linear scalability and is highly optimized. For instance, in a real-world graph dataset with >6 million edges and a multiset query with 10 colors, we can extract an optimal solution in <8 minutes on a Haswell desktop with four cores.Description
| openaire: EC/H2020/871042/EU//SoBigData-PlusPlus
Keywords
algebraic algorithms, constrained multilinear sieving, pattern detection, temporal paths, temporal patterns
Other note
Citation
Thejaswi, S, Gionis, A & Lauri, J 2020, ' Finding Path Motifs in Large Temporal Graphs Using Algebraic Fingerprints ', Big Data, vol. 8, no. 5, pp. 335-362 . https://doi.org/10.1089/big.2020.0078