APAN: Asynchronous Propagation 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 (GNN) for real-time temporal graph embedding. By decoupling graph querying from model inference, APAN significantly speeds up processing, 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, such as social media or financial transaction systems, are dynamic, meaning nodes and edges change over time. Graph Neural Networks (GNNs) are powerful tools for learning representations (embeddings) of nodes in these networks. However, existing GNNs for dynamic graphs often struggle with real-time inference. This is because they typically perform two sequential, time-consuming operations: first, querying the graph to find relevant neighbors (often k-hops away), and second, using this information to update node embeddings. In large, dense temporal graphs, this neighbor querying step becomes a major bottleneck, preventing GNNs from being deployed in applications requiring millisecond-level responses, such as detecting fraudulent financial transactions before they can be completed.

Methods

The core innovation of APAN lies in its asynchronous propagation mechanism. Unlike traditional GNNs that perform graph querying and inference synchronously, APAN decouples these two steps.

  • Synchronous Link (Inference): When a new interaction occurs, APAN's attention-based encoder directly uses the node's historical embedding and information stored in its "mailbox" to generate a real-time embedding. This phase is fast because it doesn't require querying the graph database.
  • Asynchronous Link (Propagation): After inference, a "mail" summarizing the interaction is generated. This mail is then asynchronously propagated to the k-hop neighbors' mailboxes. This propagation happens in the background, without impacting the real-time inference speed.

This asynchronous approach allows APAN to handle a large number of interactions and neighbor information without incurring the latency associated with synchronous querying. The "mailbox" acts as a buffer, storing historical interaction information from neighbors, which the encoder can then efficiently access.

Datasets

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

  • Wikipedia: A bipartite temporal graph with user-wiki page interactions, used for link prediction and node classification. It includes a significant number of 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 the computationally intensive graph querying from the model inference is crucial for achieving real-time performance in dynamic graphs.
  • Mailbox as a Memory: The mailbox mechanism provides a novel way to store and access historical neighbor information asynchronously, enabling efficient real-time updates without direct graph traversal during inference.
  • Robustness to Batch Size: APAN's asynchronous nature makes it less sensitive to the size of interaction batches. This is a significant advantage over synchronous methods, which suffer performance degradation with larger batches as they miss recent interactions within the batch.
  • Interpretability Potential: The mailbox mechanism, by storing detailed interaction information, offers potential for improved interpretability, allowing analysis of which neighbor interactions most influenced a node's embedding.

Key Results

  • Inference Speed: APAN achieves a significant speedup, being 8.7x faster than TGN in inference on the Wikipedia dataset, while maintaining comparable performance.
  • Performance: APAN demonstrates competitive performance across link prediction, node classification, and edge classification tasks on all three datasets, often outperforming other dynamic graph embedding methods. For instance, on the Reddit dataset, APAN shows an amazing performance.
  • Robustness: APAN is shown to be robust to batch size, with performance degrading much less than TGAT and TGN as batch size increases. It also exhibits robustness to the number of sampled neighbors and mailbox slots.
  • Training Speed: In the training phase, APAN's speed is comparable to state-of-the-art methods like TGN.

Limitations and Future Work

  • Module Complexity: The authors acknowledge that the current APAN model uses relatively simple modules for its attention encoder and mail propagator. They suggest that more sophisticated modules could further enhance the asynchronous CTDG framework.
  • Interpretability Exploration: While the mailbox mechanism offers potential for interpretability, this aspect was not deeply explored in the current work and is a direction for future research.
  • Further Enhancements: Future work could involve exploring more advanced mailbox updating mechanisms (e.g., using key-value memory networks) and leveraging time embedding kernels for positional encoding. The authors also express a desire for the broader community to propose even better asynchronous CTDG models.

Summary updated

Abstract

To capture higher-order structural features, most GNN-based algorithms learn node representations incorporating k-hop neighbors' information. Due to the high time complexity of querying k-hop neighbors, most graph algorithms cannot be deployed in a giant dense temporal network to execute millisecond-level inference. This problem dramatically limits the potential of applying graph algorithms in certain areas, especially 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 querying and then model inference. Different from previous graph algorithms, we decouple model inference and graph computation to alleviate the damage of the heavy graph query operation to the speed of model inference. Extensive experiments demonstrate that the proposed method can achieve competitive performance while greatly improving the inference speed. The source code is published at a Github repository.
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 Propagation Attention Network for Real-time Temporal Graph Embedding}},
  booktitle = {SIGMOD},
  year = {2021},
  url = {https://openreview.net/forum?id=cOIuWf1h99U},
}
Figure