APAN: Asynchronous Propagate Attention Network for Real-time Temporal Graph Embedding

Xuhong Wang, Ding Lyu, Mengjian Li, Yang Xia, Qi Yang, Xinwen Wang, Xinguang Wang, Ping Cui, Yupu Yang, Bowen Sun, Zhenyu Guo

TL;DR

This paper introduces APAN, a novel asynchronous graph neural network architecture designed for real-time temporal graph embedding. By decoupling graph querying from model inference, APAN significantly accelerates inference speed, making it suitable for time-sensitive applications like financial fraud detection, while maintaining competitive performance.

What Problem Does This Paper Address?

Many real-world networks are dynamic, with nodes and edges constantly changing over time. Graph Neural Networks (GNNs) are powerful tools for learning representations from these networks, but traditional GNNs often struggle with the high computational cost of querying a large number of neighbors (k-hop neighbors) in dynamic graphs. This latency makes it difficult to deploy these models for real-time applications, where millisecond-level inference is crucial. For instance, in financial fraud detection, a delayed response can allow fraudsters to escape before being flagged. The paper aims to bridge this gap by enabling GNNs to perform real-time inference on dynamic graphs without being bottlenecked by graph querying.

Methods

APAN introduces an "asynchronous" approach to temporal graph embedding. The core innovation lies in decoupling the synchronous inference phase from an asynchronous propagation phase.

  • Synchronous Inference: When an interaction occurs, APAN's attention-based encoder and MLP decoder perform inference without querying the graph database for neighbors. Instead, they leverage pre-computed information stored in a "mailbox" associated with each node. This allows for very fast inference.
  • Asynchronous Propagation: After inference, a "mail propagator" module generates a "mail" summarizing the interaction. This mail is then asynchronously sent to the k-hop neighbors' mailboxes. This process happens in the background and does not impact the real-time inference speed.

Key components include:

  • Attention Encoder: Uses multi-head attention to incorporate information from the node's last updated embedding and its mailbox.
  • Mailbox Mechanism: Stores historical interaction information from neighbors, allowing nodes to access relevant context without direct graph queries during inference.
  • Mail Propagator: Handles the asynchronous delivery of interaction summaries (mails) to neighbors' mailboxes.

Datasets

The paper evaluates APAN on three real-world temporal graph datasets:

  • Wikipedia: A bipartite temporal graph with user-page interactions, used for link prediction and node classification. It includes unseen nodes, testing inductive capabilities.
  • Reddit: Another bipartite temporal graph representing user-subreddit interactions, also used for link prediction and node classification.
  • Alipay: A large-scale industrial financial transaction dataset, used to evaluate APAN's performance in a real-world fraud detection scenario.

Key Insights and Ideas

  • Decoupling for Speed: The fundamental insight is that separating graph computation (neighbor querying and aggregation) from model inference is key to achieving millisecond-level latency in dynamic graph settings.
  • Mailbox as a Cache: The mailbox acts as an efficient, asynchronous cache for relevant neighbor information, eliminating the need for real-time graph traversals during inference.
  • Robustness to Batch Size: APAN's asynchronous nature makes it significantly less sensitive to the size of interaction batches, a critical advantage for real-world platforms that handle thousands of events concurrently. This is because it doesn't rely on the "latest" interaction in a batch, but rather on historical information in the mailbox.
  • Interpretability Potential: The mailbox mechanism, by storing detailed interaction information, offers potential for better interpretability, as attention weights can reveal which past interactions influenced a node's current embedding.

Key Results

  • Inference Speed: APAN achieves a significant inference speedup, being 8.7 times faster than TGN on the Wikipedia dataset for link prediction.
  • Competitive Performance: Despite the speed improvement, APAN maintains competitive performance, often outperforming static graph methods and matching or exceeding other dynamic graph methods in accuracy and AP scores across various tasks and datasets. For example, on the Reddit dataset for link prediction, APAN achieves the highest average AP (99.22%).
  • Robustness: APAN demonstrates strong robustness to hyperparameter choices, particularly batch size, sampled neighbors, and mailbox slots, with results fluctuating minimally.

Limitations and Future Work

  • Module Improvement: The authors acknowledge that the current modules (encoder, propagator) are relatively simple and that more sophisticated designs could further enhance the asynchronous CTDG framework.
  • Interpretability Exploration: While the mailbox mechanism offers potential for interpretability, further research is needed to fully leverage this.
  • Timestamp Ordering: While the mailbox mechanism helps mitigate issues with out-of-order events in streaming systems, the paper notes that in a real system, ensuring strict timestamp ordering is still a consideration.
  • Future Work: The authors plan to explore more advanced modules and extensions for the asynchronous CTDG framework, aiming to further improve performance and applicability. They also encourage the research community to propose better asynchronous CTDG models.

Summary updated

Abstract

Limited by the time complexity of querying k-hop neighbors in a graph database, most graph algorithms cannot be deployed online and execute millisecond-level inference. This problem dramatically limits the potential of applying graph algorithms in certain areas, such as financial fraud detection. Therefore, we propose Asynchronous Propagation Attention Network, an asynchronous continuous time dynamic graph algorithm for real-time temporal graph embedding. Traditional graph models usually execute two serial operations: first graph computation and then model inference. We decouple model inference and graph computation step so that the heavy graph query operations will not damage the speed of model inference. Extensive experiments demonstrate that the proposed method can achieve competitive performance and 8.7 times inference speed improvement in the meantime.
BibTeX
@inproceedings{wang2021apan,
  author = {Xuhong Wang and Ding Lyu and Mengjian Li and Yang Xia and Qi Yang and Xinwen Wang and Xinguang Wang and Ping Cui and Yupu Yang and Bowen Sun and Zhenyu Guo},
  title = {{APAN: Asynchronous Propagate Attention Network for Real-time Temporal Graph Embedding}},
  booktitle = {SIGMOD},
  year = {2021},
  url = {https://openreview.net/forum?id=cOIuWf1h99U},
}
Figure