Source-linked AI summary
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
Real-time temporal graph systems struggle because k-hop neighbor queries make CTDG inference too slow for online use, limiting applications such as financial fraud detection. APAN decouples inference from graph computation through synchronous mailbox reads and asynchronous propagation, achieving competitive performance with an author-reported 8× inference-speed improvement.
Problem
CTDG models serially query temporal k-hop neighbors before inference, making millisecond-level online deployment difficult for real-time applications such as financial fraud detection.
Method
APAN uses a synchronous inference link that reads node mailboxes and an asynchronous propagation link that delivers interaction information to k-hop neighbors.
Results
8× inference speed improvement was achieved with competitive performance in extensive experiments across three real-world temporal graph datasets.
Takeaways & Limitations
APAN provides an asynchronous CTDG framework designed to adapt temporal graph embedding to online deployment and real-time inference.
Takeaways & Limitations
Related extensions were tested only on experimented datasets and were not deployed in an actual environment, so they were left for future work.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Dynamic graph methods must preserve evolving temporal structure while delivering millisecond-level online inference. APAN addresses CTDG latency by decoupling inference from graph querying and computation through asynchronous propagation, achieving competitive performance and faster inference.
- Motivation: Most prior graph-learning methods assume static, time-invariant graphs, whereas real-life networks evolve as nodes, edges, and attributes change.Static representations cannot capture evolutionary topology patterns or the influence of historical and upcoming events.
- Dynamic graph learning: DTDG methods partition continuous interactions into time-window snapshots, losing within-window information and becoming sensitive to window size.CTDG methods instead process timestamped interactions sequentially, but typically require temporal k-hop neighbor queries before inference.
- Online inference challenge: CTDG algorithms serialize graph querying and model inference, creating latency that conflicts with millisecond-level online deployment.This limitation is especially consequential for fraud detection, where delayed response may allow illicit withdrawals and financial or reputation losses.
- APAN framework: APAN decouples model inference from graph querying and computation by placing heavy operations in asynchronous links.Its synchronous inference link reads node mailboxes, while its asynchronous propagation link sends interaction information to k-hop neighbors.
- Evaluation: APAN was tested on three real-world temporal graph datasets and achieved competitive performance with significant inference-speed improvements.The experiments include two public datasets and an industrial online-payment dataset collected from Alipay.
2 RELATED WORK
Related work spans static network embedding, graph neural networks, and temporal graph representation learning. Existing temporal approaches use snapshots, temporal processes, recurrent memory, or attention, with some methods not explicitly modeling multi-hop topology.
- 2.1 Network Embedding: Static network-embedding methods learn low-dimensional representations but often serialize graph structure into linear sequences and may be transductive.Random-walk methods such as DeepWalk and Node2Vec transform neighborhoods into sequences, while matrix-factorization methods use node-similarity matrices.
- 2.2 Graph Neural Networks: GNNs directly process graph structure through message passing, with architectures including convolutional aggregation, inductive neighborhood learning, and attention-based neighbor weighting.Encoder-decoder variants can extract embeddings from graph structure and node attributes.
- 2.3 Discrete-Time Dynamic Graph Learning: Most temporal-network representation methods use snapshots because network evolution and dynamics complicate learning.Examples preserve temporal information through triadic closure, high-order subgraph dependencies, periodic and non-periodic channels, or recurrent historical memory.
- 2.3 Discrete-Time Dynamic Graph Learning: Continuous-time methods model timestamped events using temporal random walks, Hawkes processes, or event-triggered node updates.These approaches aim to represent topology evolution and node activity without relying solely on discrete snapshots.
- 2.3 Discrete-Time Dynamic Graph Learning: JODIE and TigeCMN update related-node memory and read it with attention, but they do not explicitly visit two-hop neighbors.Their updates are limited to the two nodes incident to an edge, restricting direct multi-hop topology modeling.
3 METHOD
APAN embeds continuous-time graph interactions through an attention encoder, MLP decoder, and asynchronous mail propagator. Its design separates real-time inference from neighbor propagation while retaining historical neighbor information in mailboxes.
- APAN is an asynchronous CTDG algorithm comprising an attention-based encoder, an MLP decoder, and an asynchronous mail propagator.
- Synchronous Part: The encoder updates node embeddings from event details, historical embeddings, and mailbox data, while the decoder uses the updated embeddings for downstream prediction.
- Asynchronous Part: The propagator creates interaction mails and asynchronously sends them along temporal edges to k-hop neighbors’ mailboxes, allowing later embedding updates to read historical neighbor information.
- Attention Based Encoder: The encoder combines positional encoding, multi-head attention, and layer normalization to aggregate temporal-neighbor information into node embeddings.
- Asynchronous CTDG framework: APAN’s asynchronous framework separates model inference from graph querying so heavy neighbor operations do not damage millisecond-level inference speed.
4 EXPERIMENTS
APAN is evaluated on three temporal datasets across link prediction, node classification, and edge classification. It delivers competitive performance alongside faster inference, robustness to key hyperparameters, and suitability for online deployment.
- Experimental Setup: Experiments cover link prediction, node classification, and edge classification on two benchmark datasets and one industrial Alipay dataset.The datasets include Wikipedia, Reddit, and Alipay; splits follow interaction timestamps, with zero node features assigned where features are absent.
- Downstream Results: APAN achieves competitive performance against eleven SOTA baselines in link prediction, with especially strong performance on Reddit.Dynamic graph methods generally outperform static graph methods, while unsupervised embeddings perform poorly because their representations are task agnostic.
- Downstream Results: Higher asynchronous node-update frequency gives APAN stronger dynamic graph embedding capability, with similar conclusions reported for node and edge classification.Asynchronous propagation updates mailboxes when neighboring nodes interact, unlike synchronous methods that update only interacting nodes.
- Efficiency: 8.7× faster inference than TGN is achieved with almost the same testing result.APAN’s inference speed does not change with network depth because mail propagation is asynchronous, whereas deeper TGN and TGAT models become slower.
- Robustness: APAN remains robust to batch size, sampled-neighbor count, and mailbox-slot count, with the best and worst hyperparameter results differing by only 0.6%.Small mailboxes can suffice for link prediction, while too many sampled neighbors may blur representations and too few may omit important neighbors.
- Robustness: The mailbox mechanism is not a memory bottleneck because its memory usage depends on node count, while historical edge storage can grow with interactions.The authors state that the architecture and hyperparameters are sufficient for their applications but can still be improved, and that the design suits online Internet deployment.
5 CONCLUSION
APAN is proposed as an asynchronous CTDG framework for real-time temporal graph embedding and online deployment. Extensive experiments show competitive performance with an 8× inference speed improvement.
- APAN is an asynchronous CTDG algorithm framework designed for real-time temporal graph embedding and online deployment.
- 8× inference speed improvement is achieved alongside competitive performance in extensive experiments.
6 BROADER IMPACT
APAN is presented as a dynamic graph neural network approach for super-fast inference, with potential applications across online distributed graph systems and several industries.
- APAN is presented as a dynamic graph neural network approach for super-fast inference.
- The approach could support millisecond-level and large-scale inference in online distributed graph databases.
- Potential application areas include recommender systems, financial systems, and social networks.