Pattern detection in large temporal graphs using algebraic fingerprints

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

12 Lataukset (Pure)

Abstrakti

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.

AlkuperäiskieliEnglanti
OtsikkoProceedings of the 2020 SIAM International Conference on Data Mining, SDM 2020
ToimittajatCarlotta Demeniconi, Nitesh Chawla
KustantajaSociety for Industrial and Applied Mathematics Publications
Sivut37-45
Sivumäärä9
ISBN (elektroninen)9781611976236
DOI - pysyväislinkit
TilaJulkaistu - 2020
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaSIAM International Conference on Data Mining - Cincinnati, Yhdysvallat
Kesto: 7 toukokuuta 20209 toukokuuta 2020

Julkaisusarja

NimiProceedings of the 2020 SIAM International Conference on Data Mining, SDM 2020

Conference

ConferenceSIAM International Conference on Data Mining
LyhennettäSDM
MaaYhdysvallat
KaupunkiCincinnati
Ajanjakso07/05/202009/05/2020

Sormenjälki Sukella tutkimusaiheisiin 'Pattern detection in large temporal graphs using algebraic fingerprints'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

  • Projektit

    Adaptiivinen ja älykäs data

    Gionis, A., Muniyappa, S. & Ordozgoiti Rubio, B.

    01/01/201831/12/2021

    Projekti: Academy of Finland: Other research funding

    Siteeraa tätä

    Thejaswi, S., & Gionis, A. (2020). Pattern detection in large temporal graphs using algebraic fingerprints. teoksessa C. Demeniconi, & N. Chawla (Toimittajat), Proceedings of the 2020 SIAM International Conference on Data Mining, SDM 2020 (Sivut 37-45). (Proceedings of the 2020 SIAM International Conference on Data Mining, SDM 2020). Society for Industrial and Applied Mathematics Publications. https://doi.org/10.1137/1.9781611976236.5