Finding Path Motifs in Large Temporal Graphs Using Algebraic Fingerprints

Research output: Contribution to journalArticleScientificpeer-review

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.

Original languageEnglish
Pages (from-to)335-362
Number of pages28
JournalBig Data
Volume8
Issue number5
DOIs
Publication statusPublished - 1 Oct 2020
MoE publication typeA1 Journal article-refereed

Keywords

  • algebraic algorithms
  • constrained multilinear sieving
  • pattern detection
  • temporal paths
  • temporal patterns

Fingerprint Dive into the research topics of 'Finding Path Motifs in Large Temporal Graphs Using Algebraic Fingerprints'. Together they form a unique fingerprint.

Cite this