More Web Proxy on the site http://driver.im/

research-article

Anomaly Detection in Dynamic Graphs via Transformer

Authors:

Vincent CS LeeAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 35, Issue 12

Pages 12081 - 12094

https://doi.org/10.1109/TKDE.2021.3124061

Published: 02 November 2021 Publication History

Abstract

Detecting anomalies for dynamic graphs has drawn increasing attention due to their wide applications in social networks, e-commerce, and cybersecurity. Recent deep learning-based approaches have shown promising results over shallow methods. However, they fail to address two core challenges of anomaly detection in dynamic graphs: the lack of informative encoding for unattributed nodes and the difficulty of learning discriminate knowledge from coupled spatial-temporal dynamic graphs. To overcome these challenges, in this paper, we present a novel <underline><bold>T</bold></underline>ransformer-based <underline><bold>A</bold></underline>nomaly <underline><bold>D</bold></underline>etection framework for <underline><bold>DY</bold></underline>namic graphs (<bold>TADDY</bold>). Our framework constructs a comprehensive node encoding strategy to better represent each node’s structural and temporal roles in an evolving graphs stream. Meanwhile, TADDY captures informative representation from dynamic graphs with coupled spatial-temporal patterns via a dynamic graph transformer model. The extensive experimental results demonstrate that our proposed TADDY framework outperforms the state-of-the-art methods by a large margin on six real-world datasets.

References

[1]

L. Wang, Z. Yu, F. Xiong, D. Yang, S. Pan, and Z. Yan, “Influence spread in GEO-social networks: A multiobjective optimization perspective,” IEEE Trans. Cybern., vol. 51, no. 5, pp. 2663–2675, May 2021.

[2]

S. Ji, S. Pan, E. Cambria, P. Marttinen, and P. S. Yu, “A survey on knowledge graphs: Representation, acquisition, and applications,” IEEE Trans. Neural Netw. Learn. Syst., early access, Apr. 26, 2021.

[3]

Y. Zheng et al., “Clustering social audiences in business information networks,” Pattern Recognit., vol. 100, 2020, Art. no.

Digital Library

[4]

Y. Gao, X. Li, H. Peng, B. Fang, and P. Yu, “HinCTI: A cyber threat intelligence modeling and identification system based on heterogeneous information network,” IEEE Trans. Knowl. Data Eng., early access, Apr. 20, 2020.

Digital Library

[5]

D. Jin et al., “A survey of community detection approaches: From statistical modeling to deep learning,” IEEE Trans. Knowl. Data Eng., early access, Aug. 11, 2021.

[6]

F. Xia et al., “Graph learning: A survey,” IEEE Trans. Artif. Intell., vol. 2, no. 2, pp. 109–127, Apr. 2021.

[7]

H. Peng et al., “LIME: Low-cost incremental learning for dynamic heterogeneous information networks,” IEEE Trans. Comput., early access, Feb. 11, 2021.

Digital Library

[8]

P. Jiao et al., “Temporal network embedding for link prediction via VAE joint attention mechanism,” IEEE Trans. Neural Netw. Learn. Syst., early access, Jun. 9, 2021.

[9]

W. Yu, W. Cheng, C. C. Aggarwal, K. Zhang, H. Chen, and W. Wang, “NetWalk: A flexible deep embedding approach for anomaly detection in dynamic networks,” in Proc. 24th ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining, 2018, pp. 2672–2681.

[10]

L. Zheng, Z. Li, J. Li, Z. Li, and J. Gao, “AddGraph: Anomaly detection in dynamic graph using attention-based temporal GCN,” in Proc. 28th Int. Joint Conf. Artif. Intell., 2019, pp. 4419–4425.

[11]

C. C. Aggarwal, Y. Zhao, and S. Y. Philip, “Outlier detection in graph streams,” in Proc. IEEE 27th Int. Conf. Data Eng., 2011, pp. 399–409.

[12]

S. Ranshous, S. Harenberg, K. Sharma, and N. F. Samatova, “A scalable approach for outlier detection in edge streams using sketch-based approximations,” in Proc. SIAM Int. Conf. Data Mining., 2016, pp. 189–197.

[13]

L. Cai et al., “Structural temporal graph neural networks for anomaly detection in dynamic graphs,” 2020,.

[14]

C. Yang, L. Zhou, H. Wen, Z. Zhou, and Y. Wu, “H-VGRAE: A hierarchical stochastic spatial-temporal embedding method for robust anomaly detection in dynamic networks,” 2020,.

[15]

H. Peng et al., “Streaming social event detection and evolution discovery in heterogeneous information networks,” ACM Trans. Knowl. Discov. Data, vol. 15, no. 5, pp 1–33, 2021.

Digital Library

[16]

K. Sricharan and K. Das, “Localizing anomalous changes in time-evolving graphs,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2014, pp. 1347–1358.

[17]

E. Manzoor, S. M. Milajerdi, and L. Akoglu, “Fast memory-efficient anomaly detection in streaming heterogeneous graphs,” in Proc. 22nd ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining, 2016, pp. 1035–1044.

[18]

D. Eswaran, C. Faloutsos, S. Guha, and N. Mishra, “SpotLight: Detecting anomalies in streaming graphs,” in Proc. 24th ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining, 2018, pp. 1378–1386.

[19]

T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in Proc. Int. Conf. Learn. Representations, 2017, pp. 1–14.

[20]

A. Vaswani et al., “Attention is all you need,” in Proc. 31st Int. Conf. Neural Inf. Process. Syst., 2017, pp. 6000–6010.

[21]

J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “BERT: Pre-training of deep bidirectional transformers for language understanding,” in Proc. Conf. North Amer. Chapter Assoc. Comput. Linguistics, Hum. Lang. Technol., 2019, pp. 4171–4186.

[22]

Z. Lan, M. Chen, S. Goodman, K. Gimpel, P. Sharma, and R. Soricut, “ALBERT: A lite bert for self-supervised learning of language representations,” in Proc. Int. Conf. Learn. Representations, 2019, pp. 1–17.

[23]

Y. Liu et al., “RoBERTa: A robustly optimized bert pretraining approach,” 2019,.

[24]

Z. Yang, Z. Dai, Y. Yang, J. Carbonell, R. R. Salakhutdinov, and Q. V. Le, “XLNet: Generalized autoregressive pretraining for language understanding,” in Proc. 33rd Int. Conf. Neural Inf. Process. Syst., 2019, pp. 5753–5763.

[25]

L. Liu, W. L. Hamilton, G. Long, J. Jiang, and H. Larochelle, “A universal representation transformer layer for few-shot image classification,” in Proc. Int. Conf. Learn. Representations, 2021, pp. 1–12.

[26]

N. Carion, F. Massa, G. Synnaeve, N. Usunier, A. Kirillov, and S. Zagoruyko, “End-to-end object detection with transformers,” in Proc. Eur. Conf. Comput. Vis., 2020, pp. 213–229.

[27]

A. Dosovitskiy et al., “An image is worth 16x16 words: Transformers for image recognition at scale,” in Proc. Int. Conf. Learn. Representations, 2021, pp. 1–21.

[28]

S. Zheng et al., “Rethinking semantic segmentation from a sequence-to-sequence perspective with transformers,” in Proc. IEEE/CVF Conf. Comput. Vis. Pattern Recognit., 2021, pp. 6881–6890.

[29]

K. Han et al., “A survey on visual transformer,” 2020,.

[30]

Y. Tay, M. Dehghani, D. Bahri, and D. Metzler, “Efficient transformers: A survey,” 2020,.

[31]

S. Yun, M. Jeong, R. Kim, J. Kang, and H. J. Kim, “Graph transformer networks,” in Proc. 33rd Int. Conf. Neural Inf. Process. Syst., 2019, pp. 11 983–11 993.

[32]

Z. Hu, Y. Dong, K. Wang, and Y. Sun, “Heterogeneous graph transformer,” in Proc. Web Conf., 2020, pp. 2704–2710.

Digital Library

[33]

Y. Rong et al., “Self-supervised graph transformer on large-scale molecular data,” in Proc. Int. Conf. Neural Inf. Process. Syst., 2020, pp. 12559–12571.

[34]

J. Zhang, H. Zhang, C. Xia, and L. Sun, “Graph-Bert: Only attention is needed for learning graph representations,” 2020,.

[35]

Y. Liu, S. Pan, M. Jin, C. Zhou, F. Xia, and P. S. Yu, “Graph self-supervised learning: A survey,” 2020,.

[36]

Y. Liu, Z. Li, S. Pan, C. Gong, C. Zhou, and G. Karypis, “Anomaly detection on attributed networks via contrastive self-supervised learning,” IEEE Trans. Neural Netw. Learn. Syst., early access, Apr. 05, 2021.

[37]

J. Klicpera, S. Weißenberger, and S. Günnemann, “Diffusion improves graph learning,” in Proc. Int. Conf. Neural Inf. Process. Syst., 2019, pp. 13 333–13 345.

[38]

K. Hassani and A. H. Khasahmadi, “Contrastive multi-view representation learning on graphs,” in Proc. Int. Conf. Mach. Learn., 2020, pp. 3451–3461.

[39]

L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation ranking: Bringing order to the web,” Stanford InfoLab, Stanford, CA, USA: Tech. Rep.1999–66, 1999.

[40]

R. I. Kondor and J. Lafferty, “Diffusion kernels on graphs and other discrete structures,” in Proc. Int. Conf. Mach. Learn., 2002, pp. 315–322.

[41]

J. Gehring, M. Auli, D. Grangier, D. Yarats, and Y. N. Dauphin, “Convolutional sequence to sequence learning,” in Proc. 34th Int. Conf. Mach. Learn., 2017, pp. 1243–1252.

[42]

T. Opsahl and P. Panzarasa, “Clustering in weighted networks,” Social Netw., vol. 31, no. 2, pp. 155–163, 2009.

[43]

M. De Choudhury, H. Sundaram, A. John, and D. D. Seligmann, “Social synchrony: Predicting mimicry of user actions in online social media,” in Proc. Int. Conf. Comput. Sci. Eng., 2009, pp. 151–158.

[44]

R. A. Rossi and N. K. Ahmed, “The network data repository with interactive graph analytics and visualization,” in Proc. 29th AAAI Conf. Artif. Intell., 2015, pp. 4292–4293. [Online]. Available: http://networkrepository.com

[45]

S. Kumar, F. Spezzano, V. Subrahmanian, and C. Faloutsos, “Edge weight prediction in weighted signed networks,” in Proc. IEEE 16th Int. Conf. Data Mining., 2016, pp. 221–230.

[46]

S. Kumar, B. Hooi, D. Makhija, M. Kumar, C. Faloutsos, and V. Subrahmanian, “REV2: Fraudulent user prediction in rating platforms,” in Proc. 11th ACM Int. Conf. Web Search Data Mining., 2018, pp. 333–341.

[47]

B. Zhang, R. Liu, D. Massey, and L. Zhang, “Collecting the internet AS-level topology,” ACM SIGCOMM Comput. Commun. Rev., vol. 35, no. 1, pp. 53–61, 2005.

Digital Library

[48]

B. Perozzi, R. Al-Rfou, and S. Skiena, “DeepWalk: Online learning of social representations,” in Proc. 20th ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining, 2014, pp. 701–710.

[49]

A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in Proc. 22nd ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining, 2016, pp. 855–864.

[50]

U. Von Luxburg, “A tutorial on spectral clustering,” Statist. Comput., vol. 17, no. 4, pp. 395–416, 2007.

Digital Library

[51]

A. Paszke et al., “PyTorch: An imperative style, high-performance deep learning library,” in Proc. Int. Conf. Neural Inf. Process. Syst., 2019, pp. 8026–8037.

Cited By

Zhang JYing RShao J(2024)Online Detection of Anomalies in Temporal Knowledge Graphs with InterpretabilityProceedings of the ACM on Management of Data10.1145/36988232:6(1-26)Online publication date: 20-Dec-2024
https://dl.acm.org/doi/10.1145/3698823
Pazho ANoghre GPurkayastha AVempati JMartin OTabkhi H(2024)A Survey of Graph-Based Deep Learning for Anomaly Detection in Distributed SystemsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.328289836:1(1-20)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TKDE.2023.3282898
Messai MSeba H(2023)IoT Network Attack Detection: Leveraging Graph Learning for Enhanced SecurityProceedings of the 18th International Conference on Availability, Reliability and Security10.1145/3600160.3605053(1-7)Online publication date: 29-Aug-2023
https://dl.acm.org/doi/10.1145/3600160.3605053
Show More Cited By

Index Terms

Anomaly Detection in Dynamic Graphs via Transformer

Index terms have been assigned to the content through auto-classification.

Recommendations

Anomaly Detection, Clustering, and Visualization on Dynamic Graphs
Scalable anomaly detection in graphs

The advantage of graph-based anomaly detection is that the relationships between elements can be analyzed for structural oddities that could represent activities such as fraud, network intrusions, or suspicious associations in a social network. ...
Two-stage anomaly detection algorithm via dynamic community evolution in temporal graph
Abstract
Detecting anomalies from a massive amount of user behavioral data is often liken to finding a needle in a haystack. While tremendous efforts have been devoted to anomaly detection from temporal graphs, existing studies rarely consider community ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 35, Issue 12

Dec. 2023

1114 pages

ISSN:1041-4347

Issue’s Table of Contents

1041-4347 © 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 02 November 2021

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang JYing RShao J(2024)Online Detection of Anomalies in Temporal Knowledge Graphs with InterpretabilityProceedings of the ACM on Management of Data10.1145/36988232:6(1-26)Online publication date: 20-Dec-2024
https://dl.acm.org/doi/10.1145/3698823
Pazho ANoghre GPurkayastha AVempati JMartin OTabkhi H(2024)A Survey of Graph-Based Deep Learning for Anomaly Detection in Distributed SystemsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.328289836:1(1-20)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TKDE.2023.3282898
Messai MSeba H(2023)IoT Network Attack Detection: Leveraging Graph Learning for Enhanced SecurityProceedings of the 18th International Conference on Availability, Reliability and Security10.1145/3600160.3605053(1-7)Online publication date: 29-Aug-2023
https://dl.acm.org/doi/10.1145/3600160.3605053
Ren JXia FLee INoori Hoshyar AAggarwal C(2023)Graph Learning for Anomaly Analytics: Algorithms, Applications, and ChallengesACM Transactions on Intelligent Systems and Technology10.1145/357090614:2(1-29)Online publication date: 16-Feb-2023
https://dl.acm.org/doi/10.1145/3570906
Hu YZhang YWang YWork D(2023)Detecting Socially Abnormal Highway Driving Behaviors via Recurrent Graph Attention NetworksProceedings of the ACM Web Conference 202310.1145/3543507.3583452(3086-3097)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583452
Wang YZhang JHuang ZLi WFeng SMa ZSun YYu DDong FJin JWang BLuo J(2023)Label Information Enhanced Fraud Detection against Low Homophily in GraphsProceedings of the ACM Web Conference 202310.1145/3543507.3583373(406-416)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583373
Guo JTang SLi JPan KWu L(2023)RustGraph: Robust Anomaly Detection in Dynamic Graphs by Jointly Learning Structural-Temporal DependencyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.332864536:7(3472-3485)Online publication date: 30-Oct-2023
https://dl.acm.org/doi/10.1109/TKDE.2023.3328645
Yuan ZShao MYan Q(2023)Motif-Level Anomaly Detection in Dynamic GraphsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.327273118(2870-2882)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TIFS.2023.3272731
Ma MHan LZhou C(2023)BTADAdvanced Engineering Informatics10.1016/j.aei.2023.10194956:COnline publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.aei.2023.101949

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents