Temporal graph patterns by timed automata

Amir Aghasadeghi, Jan Van den Bussche, Julia Stoyanovich

    Research output: Contribution to journalArticlepeer-review

    Abstract

    Temporal graphs represent graph evolution over time, and have been receiving considerable research attention. Work on expressing temporal graph patterns or discovering temporal motifs typically assumes relatively simple temporal constraints, such as journeys or, more generally, existential constraints, possibly with finite delays. In this paper we propose to use timed automata to express temporal constraints, leading to a general and powerful notion of temporal basic graph pattern (BGP). The new difficulty is the evaluation of the temporal constraint on a large set of matchings. An important benefit of timed automata is that they support an iterative state assignment, which can be useful for early detection of matches and pruning of non-matches. We introduce algorithms to retrieve all instances of a temporal BGP match in a graph, and present results of an extensive experimental evaluation, demonstrating interesting performance trade-offs. We show that an on-demand algorithm that processes total matchings incrementally over time is preferable when dealing with cyclic patterns on sparse graphs. On acyclic patterns or dense graphs, and when connectivity of partial matchings can be guaranteed, the best performance is achieved by maintaining partial matchings over time and allowing automaton evaluation to be fully incremental. The code and datasets used in our analysis are available at http://github.com/amirpouya/TABGP .

    Original languageEnglish (US)
    Pages (from-to)25-47
    Number of pages23
    JournalVLDB Journal
    Volume33
    Issue number1
    DOIs
    StatePublished - Jan 2024

    Keywords

    • Graph query languages
    • Property graphs
    • Temporal graphs
    • Timed automata
    • dataflow systems

    ASJC Scopus subject areas

    • Information Systems
    • Hardware and Architecture

    Fingerprint

    Dive into the research topics of 'Temporal graph patterns by timed automata'. Together they form a unique fingerprint.

    Cite this