Towards Event Prediction in Temporal Graphs

Download PDF

Abstract

This paper proposes a class of temporal association rules, denoted by TACOs, for event prediction. As opposed to previous graph rules, TACOs monitor updates to graphs, and can be used to capture temporal interests in recommendation and catch frauds in response to behavior changes, among other things. TACOs are defined on temporal graphs in terms of change patterns and (temporal) conditions, and may carry machine learning (ML) predicates for temporal event prediction. We settle the complexity of reasoning about TACOs, including their satisfiability, implication and prediction problems.We develop a system, referred to as TASTE. TASTE discovers TACOs by iteratively training a rule creator based on generative ML models in a creator-critic framework. Moreover, it predicts events by applying the discovered TACOs.We also provide parallel algorithms underlying TASTE. Using real-life and synthetic datasets,we experimentally verify that TASTE is on average 38.2 times faster than conventional data mining method in TACO discovery, and it improves the accuracy of state-of-the-art event prediction models by 23.4%.