TGTOD: A Global Temporal Graph Transformer for Outlier Detection at Scale
Kay Liu, Jiahao Ding, MohamadAli Torkamani, Philip S. Yu · 2024
Read TGTOD: A Global Temporal Graph Transformer for Outlier Detection at Scale by Kay Liu, Jiahao Ding, MohamadAli Torkamani, Philip S. Yu (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-00984.txt.
Introduction
Networks that change over time, from money flows to social ties, hide outliers that can signal fraud or failure. Kay Liu and co-authors present TGTOD in this 2024 paper, a transformer model built to spot such outliers in time-stamped graphs at scale. Older graph transformers saw only small neighborhoods, paid heavily for subgraph extraction, and generalized poorly.
TGTOD attends across the whole graph and chops big graphs into space-time patches, handled by a three-level transformer stack. On three public datasets it beat a wide field of rivals, lifting one key score by sixty-one percent on a financial dataset. It also trained forty-four times faster than earlier graph transformers. The authors share their code for others to reproduce the work.
Catalog record
| CREATOR | Kay Liu, Jiahao Ding, MohamadAli Torkamani, Philip S. Yu |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-00984
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
TGTOD: A Global Temporal Graph Transformer for Outlier Detection at Scale Kay Liu, Jiahao Ding, MohamadAli Torkamani, Philip S. Yu Abstract While Transformers have revolutionized machine learning on various data, existing Transformers for temporal graphs face limitations in (1) restricted receptive fields, (2) overhead of subgraph extraction, and (3) suboptimal generalization capability beyond link prediction. In this paper, we rethink temporal graph Transformers and propose TGTOD, a novel end-to-end Temporal Graph Transformer for Outlier Detection. TGTOD employs global attention to model both structural and temporal dependencies within temporal graphs. To tackle scalability, our approach divides large temporal graphs into spatiotemporal patches, which are then processed by a hierarchical Transformer architecture comprising Patch Transformer, Cluster Transformer, and Temporal Transformer. We evaluate TGTOD on three public datasets under two settings, comparing with a wide range of baselines. Our experimental results demonstrate the effectiveness of TGTOD, achieving AP improvement of 61% on Elliptic. Furthermore, our efficiency evaluation shows that TGTOD reduces training time by 44 × \times compared to existing Transformers for temporal graphs. To foster reproducibility, we make our implementation publicly available at https://github.com/kayzliu/tgtod . 1 Introduction Graph outlier detection focuses on identifying anomalous substructures within graphs. Traditionally, graph outlier detection methods have primarily focused on static graphs, where the structure and attributes remain constant over time. However, real-world graphs are often dynamic, evolving over time and providing rich temporal information that can be crucial for detecting outliers. Current static graph methods fall short when applied to temporal graphs, as they fail to capture the important temporal aspects necessary for effective outlier detection. Recently, Transformers have revolutionized machine learning on language [ 31 , 11 ] and vision [ 6 ] with their powerful ability to model complex dependencies in data through self-attention mechanisms. Unlike traditional recurrent neural network architectures that rely heavily on sequential processing, Transformers utilize attention mechanisms to weigh the importance of different parts of the input data, allowing them to capture long-range dependencies effectively. This self-attention mechanism in Transformers offers a promising direction by integrating temporal dynamics into graph representation learning. Although some recent efforts have adapted Transformers to temporal graphs, challenges remain. DyGFormer extracts one-hop interactions and feeds their neighbor, link, time, and co-occurrence encoding into a Transformer to capture temporal edges between nodes [ 43 ] . Similarly, SimpleDyG also models temporal neighbors as a sequence and introduces a temporal alignment technique to capture temporal evolution patterns [ 39 ] . Despite their potential, existing methods using Transformers on temporal graphs face significant limitations. • Limited receptive field : Current methods typically extract only one-hop neighboring subgraphs, restricting Transformers’ receptive field and overlooking long-range spatiotemporal dependencies. • Training inefficiency : These approaches often rely on subgraphs extraction for each edge during training [ 9 ] , leading to significant computational overhead and limiting the training efficiency. • Task misalignment : Existing Transformers are pretrained on link prediction , which may cause suboptimal generalization capability to node-level outlier detection due to a mismatch of objectives. To address these limitations, we propose TGTOD, a novel paradigm to apply Transformers on temporal graphs. ( Novelty 1 ) We explore adopting global spatiotemporal attention on the entire temporal graph for node-level outlier detection. It allows TGTOD to capture not only the local spatiotemporal dependencies between temporal neighbors but also the global spatiotemporal dependencies across the entire graph and multiple timestamps. However, due to the quadratic complexity of query-key multiplication in the attention mechanism, direct global spatiotemporal attention is computationally infeasible for large-scale temporal graphs. ( Novelty 2 ) Inspired by visual patching method used in video model [ 1 ] , we divide the large temporal graph into spatiotemporal patches to alleviate the challenge of scalability. For the spatial aspect, we use a graph clustering algorithm to partition the large graph into relatively small clusters. For the temporal aspect, we aggregate the interactions within each cluster into a snapshot with a specific time interval. These patches are then fed into a hierarchical Transformer, which includes Patch Transformer, Cluster Transformer, and Temporal Transformer. Through this approach, TGTOD significantly reduces the complexity of attention mechanisms while preserving global spatiotemporal receptive fields. ( Novelty 3 ) Furthermore, unlike existing Transformers on temporal graphs pretrained on link prediction task, TGTOD is trained end-to-end on node-level outlier detection, ensuring better alignment with the downstream task and thus providing stronger generalization capability. Our contributions in this work are summarized as follows: • Global attention : We propose TGTOD, making the first attempt to leverage global spatiotemporal attention for Transformers on temporal graphs for end-to-end node-level outlier detection. • Spatiotemporal patching : We introduce a spatiotemporal patching method, which significantly improves the scalability of TGTOD and enables outlier detection on large-scale temporal graphs. • Evaluation : Our comprehensive analysis and experiments demonstrate both the effectiveness and the efficiency of TGTOD. 2 Related Work Graph Transformers have emerged as a powerful approach for learning on graph data. NodeFormer [ 37 ] enables efficient computation via kernelized Gumbel-Softmax, reducing the algorithmic complexity to linear. DIFFormer [ 38 ] proposes a graph Transformer with energy-constrained diffusion. SGFormer [ 36 ] further improves the scalability of graph Transformers to handle large graphs more efficiently. CoBFormer [ 40 ] adopts bi-level architecture for graph Transformers to alleviate the over-globalization problem and improve efficiency. These methods lay a solid foundation for our work. On temporal graphs, SimpleDyG [ 39 ] and DyGFormer [ 43 ] model one-hop temporal neighbors as a sequence for Transformers. While these methods have shown promising results in temporal link prediction tasks, their application to node-level outlier detection remains limited. In this paper, we rethink the use of Transformers on temporal graphs and conduct global spatiotemporal attention on the entire temporal graph. For more related work, please refer to Appendix 0.A . 3 Methodology (a) Spatiotemporal patching method. (b) Hierarchical architecture of TGTOD conducting global attention. Figure 1 : An overview of TGTOD for end-to-end outlier detection. Figure 1 provides an overview of the proposed TGTOD for end-to-end node-level outlier detection on temporal graphs. In TGTOD, we aim to conduct global spatiotemporal attention across the entire temporal graph. However, due to the quadratic complexity of attention mechanism, direct global spatiotemporal attention is computationally infeasible for large-scale temporal graphs. We thus propose to divide large-scale temporal graphs into relatively manageable spatiotemporal patches to alleviate the challenge of scalability. Figure 1(a) shows a toy example of spatiotemporal patching . The obtained patches are then fed into a hierarchical Transformer architecture, as shown in Figure 1(b) , which includes Patch Transformer (PFormer), Cluster Transformer (CFormer), and Temporal Transformer (TFormer). In this section, we start with the problem definition in Section 3.1 and introduce our spatiotemporal patching method in Section 3.2 . Next, we define the hierarchical architecture of the proposed TGTOD in Section 3.3 , followed by a detailed design of Patch Transformer, which further reduces computational complexity, in Section 3.4 . We summarize the end-to-end training procedure of TGTOD in Section 3.5 and analyze the reduction in complexity achieved in TGTOD in Section 3.6 . The notations used are summarized in Table 5 in Appendix 0.B . 3.1 Problem Definition Consider a temporal graph \mathcal{G} consisting of a sequence of graph