A Structural Information Guided Hierarchical Reconstruction for Graph Anomaly Detection
Pages 4318 - 4323
Abstract
Anomalies in graphs involve attributes and structures and may occur at different levels (e.g., node or community). Existing GNN-based detection methods often merely focus on anomalies of single nodes or neighborhoods, making it hard to cope with complex and organized networks. Towards this, we propose SI-HGAD, a novel Graph Anomaly Detection (GAD) approach that utilizes hierarchical information to detect anomalies. Powered by structural information, SI-HGAD can mine an optimal graph abstraction while enabling hierarchical substructural modeling. Also, we design a Graph Transformer to mine multi-range structural and attribute patterns for nodes. The decoders reconstruct both the node attributes and the multi-level subgraphs in a bottom-up manner. Extensive experiments demonstrate the superiority of SI-HGAD.
References
[1]
Leman Akoglu, Hanghang Tong, and Danai Koutra. 2015. Graph based anomaly detection and description: a survey. Data mining and knowledge discovery, Vol. 29 (2015), 626--688.
[2]
Sambaran Bandyopadhyay, Lokesh N, Saley Vishal Vivek, and M. N. Murty. 2020. Outlier Resistant Unsupervised Deep Architectures for Attributed Network Embedding. In Proceedings of the 13th International Conference on Web Search and Data Mining (WSDM '20). Association for Computing Machinery, New York, NY, USA, 25--33. https://doi.org/10.1145/3336191.3371788
[3]
Adam Breuer, Roee Eilat, and Udi Weinsberg. 2020. Friend or Faux: Graph-Based Early Detection of Fake Accounts on Social Networks. In Proceedings of The Web Conference 2020 (WWW '20). Association for Computing Machinery, New York, NY, USA, 1287--1297. https://doi.org/10.1145/3366423.3380204
[4]
Yuwei Cao, Hao Peng, Zhengtao Yu, and Philip S. Yu. 2024. Hierarchical and Incremental Structural Entropy Minimization for Unsupervised Social Event Detection. Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38, 8 (March 2024), 8255--8264. https://doi.org/10.1609/aaai.v38i8.28666
[5]
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. 2020. Simple and deep graph convolutional networks. In International conference on machine learning. PMLR, 1725--1735.
[6]
Kaize Ding, Jundong Li, Rohit Bhanushali, and Huan Liu. 2019. Deep Anomaly Detection on Attributed Networks. In Proceedings of the 2019 SIAM International Conference on Data Mining (SDM) (Proceedings). Society for Industrial and Applied Mathematics, 594--602. https://doi.org/10.1137/1.9781611975673.67
[7]
Yingtong Dou, Zhiwei Liu, Li Sun, Yutong Deng, Hao Peng, and Philip S. Yu. 2020. Enhancing Graph Neural Network-based Fraud Detectors against Camouflaged Fraudsters. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management. ACM, Virtual Event Ireland, 315--324. https://doi.org/10.1145/3340531.3411903
[8]
Jingcan Duan, Siwei Wang, Pei Zhang, En Zhu, Jingtao Hu, Hu Jin, Yue Liu, and Zhibin Dong. 2023. Graph Anomaly Detection via Multi-Scale Contrastive Learning Networks with Augmented View. Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37, 6 (June 2023), 7459--7467. https://doi.org/10.1609/aaai.v37i6.25907
[9]
Haoyi Fan, Fengbin Zhang, and Zuoyong Li. 2020. Anomalydae: Dual Autoencoder for Anomaly Detection on Attributed Networks. In ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). 5685--5689. https://doi.org/10.1109/ICASSP40776.2020.9053387
[10]
Shangbin Feng, Zhaoxuan Tan, Rui Li, and Minnan Luo. 2022. Heterogeneity-Aware Twitter Bot Detection with Relational Graph Transformers. Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 36, 4 (June 2022), 3977--3985. https://doi.org/10.1609/aaai.v36i4.20314
[11]
Yuan Gao, Xiang Wang, Xiangnan He, Zhenguang Liu, Huamin Feng, and Yongdong Zhang. 2023. Alleviating Structural Distribution Shift in Graph Anomaly Detection. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining (WSDM '23). Association for Computing Machinery, New York, NY, USA, 357--365. https://doi.org/10.1145/3539597.3570377
[12]
Leonardo Gutiérrez-Gómez, Alexandre Bovet, and Jean-Charles Delvenne. 2020. Multi-Scale Anomaly Detection on Attributed Networks. Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34, 01 (April 2020), 678--685. https://doi.org/10.1609/aaai.v34i01.5409
[13]
Junwei He, Qianqian Xu, Yangbangyan Jiang, Zitai Wang, and Qingming Huang. 2024. ADA-GAD: Anomaly-Denoised Autoencoders for Graph Anomaly Detection. Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38, 8, 8481--8489. https://doi.org/10.1609/aaai.v38i8.28691
[14]
Ming Jin, Yixin Liu, Yu Zheng, Lianhua Chi, Yuan-Fang Li, and Shirui Pan. 2021. ANEMONE: Graph Anomaly Detection with Multi-Scale Contrastive Learning. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management (CIKM '21). Association for Computing Machinery, New York, NY, USA, 3122--3126. https://doi.org/10.1145/3459637.3482057
[15]
Thomas N Kipf and Max Welling. 2016. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308 (2016).
[16]
Clement Lee and Darren J Wilkinson. 2019. A review of stochastic block models and extensions for graph clustering. Applied Network Science, Vol. 4, 1 (2019), 1--50.
[17]
Angsheng Li and Yicheng Pan. 2016. Structural information and dynamical complexity of networks. IEEE Transactions on Information Theory, Vol. 62, 6 (2016), 3290--3339.
[18]
Angsheng Li, Xianchen Yin, Bingxiang Xu, Danyang Wang, Jimin Han, Yi Wei, Yun Deng, Ying Xiong, and Zhihua Zhang. 2018. Decoding topologically associating domains with ultra-low resolution Hi-C data by graph structural entropy. Nature communications, Vol. 9, 1 (2018), 1--12.
[19]
Jundong Li, Harsh Dani, Xia Hu, and Huan Liu. 2017. Radar: Residual analysis for anomaly detection in attributed networks. In IJCAI, Vol. 17. 2152--2158.
[20]
Fanzhen Liu, Xiaoxiao Ma, Jia Wu, Jian Yang, Shan Xue, Amin Beheshti, Chuan Zhou, Hao Peng, Quan Z. Sheng, and Charu C. Aggarwal. 2022 d. DAGAD: Data Augmentation for Graph Anomaly Detection. In 2022 IEEE International Conference on Data Mining (ICDM). 259--268. https://doi.org/10.1109/ICDM54844.2022.00036
[21]
Kay Liu, Yingtong Dou, Yue Zhao, Xueying Ding, Xiyang Hu, Ruitong Zhang, Kaize Ding, Canyu Chen, Hao Peng, Kai Shu, George H. Chen, Zhihao Jia, and Philip S. Yu. 2022. PyGOD: A Python Library for Graph Outlier Detection. arXiv preprint arXiv:2204.12095 (2022).
[22]
Kay Liu, Yingtong Dou, Yue Zhao, Xueying Ding, Xiyang Hu, Ruitong Zhang, Kaize Ding, Canyu Chen, Hao Peng, Kai Shu, Lichao Sun, Jundong Li, George H. Chen, Zhihao Jia, and Philip S. Yu. 2022. BOND: Benchmarking Unsupervised Outlier Node Detection on Static Attributed Graphs. Advances in Neural Information Processing Systems, Vol. 35 (Dec. 2022), 27021--27035.
[23]
Yang Liu, Xiang Ao, Zidi Qin, Jianfeng Chi, Jinghua Feng, Hao Yang, and Qing He. 2021. Pick and Choose: A GNN-based Imbalanced Learning Approach for Fraud Detection. In Proceedings of the Web Conference 2021 (WWW '21). Association for Computing Machinery, New York, NY, USA, 3168--3177. https://doi.org/10.1145/3442381.3449989
[24]
Yixin Liu, Zhao Li, Shirui Pan, Chen Gong, Chuan Zhou, and George Karypis. 2022. Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning. IEEE Transactions on Neural Networks and Learning Systems, Vol. 33, 6 (June 2022), 2378--2392. https://doi.org/10.1109/TNNLS.2021.3068344
[25]
Andreas Loukas. 2019. What Graph Neural Networks Cannot Learn: Depth vs Width. In International Conference on Learning Representations.
[26]
Xuexiong Luo, Jia Wu, Amin Beheshti, Jian Yang, Xiankun Zhang, Yuan Wang, and Shan Xue. 2022. ComGA: Community-Aware Attributed Graph Anomaly Detection. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining. ACM, Virtual Event AZ USA, 657--665. https://doi.org/10.1145/3488560.3498389
[27]
Xiaoxiao Ma, Jia Wu, Shan Xue, Jian Yang, Chuan Zhou, Quan Z. Sheng, Hui Xiong, and Leman Akoglu. 2023. A Comprehensive Survey on Graph Anomaly Detection With Deep Learning. IEEE Transactions on Knowledge and Data Engineering, Vol. 35, 12 (Dec. 2023), 12012--12038. https://doi.org/10.1109/TKDE.2021.3118815
[28]
Emmanuel Müller, Patricia Iglesias Sánchez, Yvonne Mülle, and Klemens Böhm. 2013. Ranking outlier nodes in subspaces of attributed graphs. In 2013 IEEE 29th international conference on data engineering workshops (ICDEW). IEEE, 216--222.
[29]
Junjun Pan, Yixin Liu, Yizhen Zheng, and Shirui Pan. 2023. PREM: A Simple Yet Effective Approach for Node-Level Graph Anomaly Detection. In 2023 IEEE International Conference on Data Mining (ICDM). 1253--1258. https://doi.org/10.1109/ICDM58522.2023.00157
[30]
Yulong Pei, Tianjin Huang, Werner Van Ipenburg, and Mykola Pechenizkiy. 2022. ResGCN: Attention-Based Deep Residual Modeling for Anomaly Detection on Attributed Networks. Machine Learning, Vol. 111, 2 (Feb. 2022), 519--541. https://doi.org/10.1007/s10994-021-06044-0
[31]
Hao Peng, Jingyun Zhang, Xiang Huang, Zhifeng Hao, Angsheng Li, Zhengtao Yu, and Philip S Yu. 2024. Unsupervised Social Bot Detection via Structural Information Theory. arXiv preprint arXiv:2404.13595 (2024).
[32]
Zhen Peng, Minnan Luo, Jundong Li, Huan Liu, and Qinghua Zheng. 2018. ANOMALOUS: A Joint Modeling Approach for Anomaly Detection on Attributed Networks. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, Stockholm, Sweden, 3513--3519. https://doi.org/10.24963/ijcai.2018/488
[33]
Amit Roy, Juan Shu, Jia Li, Carl Yang, Olivier Elshocht, Jeroen Smeets, and Pan Li. 2024. GAD-NR: Graph Anomaly Detection via Neighborhood Reconstruction. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining (WSDM '24). Association for Computing Machinery, New York, NY, USA, 576--585. https://doi.org/10.1145/3616855.3635767
[34]
Patricia Iglesias Sánchez, Emmanuel Müller, Fabian Laforet, Fabian Keller, and Klemens Böhm. 2013. Statistical selection of congruent subspaces for mining attributed graphs. In 2013 IEEE 13th international conference on data mining. IEEE, 647--656.
[35]
Mingyue Tang, Pan Li, and Carl Yang. 2021. Graph Auto-Encoder via Neighborhood Wasserstein Reconstruction. In International Conference on Learning Representations.
[36]
Max Welling and Thomas N Kipf. 2016. Semi-supervised classification with graph convolutional networks. In Proceedings of the International Conference on Learning Representations.
[37]
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. 2020. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, Vol. 32, 1 (2020), 4--24.
[38]
Zhiming Xu, Xiao Huang, Yue Zhao, Yushun Dong, and Jundong Li. 2022. Contrastive attributed network anomaly detection with data augmentation. In Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, 444--457.
[39]
Yingguang Yang, Renyu Yang, Hao Peng, Yangyang Li, Tong Li, Yong Liao, and Pengyuan Zhou. 2023. FedACK: Federated Adversarial Contrastive Knowledge Distillation for Cross-Lingual and Cross-Model Social Bot Detection. In Proceedings of the ACM Web Conference 2023 (WWW '23). Association for Computing Machinery, New York, NY, USA, 1314--1323. https://doi.org/10.1145/3543507.3583500
[40]
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. 2018. Hierarchical graph representation learning with differentiable pooling. Advances in neural information processing systems, Vol. 31 (2018).
[41]
Xianghua Zeng, Hao Peng, Angsheng Li, Chunyang Liu, Lifang He, and Philip S Yu. 2023. Hierarchical State Abstraction based on Structural Information Principles. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence.
[42]
Ge Zhang, Jia Wu, Jian Yang, Amin Beheshti, Shan Xue, Chuan Zhou, and Quan Z. Sheng. 2021. FRAUDRE: Fraud Detection Dual-Resistant to Graph Inconsistency and Imbalance. In 2021 IEEE International Conference on Data Mining (ICDM). 867--876. https://doi.org/10.1109/ICDM51629.2021.00098
[43]
Yu Zheng, Ming Jin, Yixin Liu, Lianhua Chi, Khoa T. Phan, Shirui Pan, and Yi-Ping Phoebe Chen. 2022. From Unsupervised to Few-shot Graph Anomaly Detection: A Multi-scale Contrastive Learning Approach. https://doi.org/10.48550/arXiv.2202.05525 arxiv: 2202.05525 [cs]
[44]
Xiaokang Zhou, Wei Liang, Weimin Li, Ke Yan, Shohei Shimizu, I Kevin, and Kai Wang. 2021. Hierarchical adversarial attacks against graph-neural-network-based IoT network intrusion detection system. IEEE Internet of Things Journal, Vol. 9, 12 (2021), 9310--9319.
Index Terms
- A Structural Information Guided Hierarchical Reconstruction for Graph Anomaly Detection
Recommendations
GAD-NR: Graph Anomaly Detection via Neighborhood Reconstruction
WSDM '24: Proceedings of the 17th ACM International Conference on Web Search and Data MiningGraph Anomaly Detection (GAD) is a technique used to identify abnormal nodes within graphs, finding applications in network security, fraud detection, social media spam detection, and various other domains. A common method for GAD is Graph Auto-Encoders (...
EGNN-AD: An Effective Graph Neural Network-Based Approach for Anomaly Detection on Edge-Attributed Graphs
Database Systems for Advanced ApplicationsAbstractThe emergence of Graph Neural Networks (GNNs) has led to the development of several GNN-based anomaly detection models that detect anomalies in attributed graphs using graph structural and attribute information. However, most existing solutions ...
One-class graph neural networks for anomaly detection in attributed networks
AbstractNowadays, graph-structured data are increasingly used to model complex systems. Meanwhile, detecting anomalies from graph has become a vital research problem of pressing societal concerns. Anomaly detection is an unsupervised learning task of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2024
5705 pages
Copyright © 2024 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 October 2024
Check for updates
Author Tags
Qualifiers
- Short-paper
Funding Sources
- National Nature Science Foundation of China
- CCF-DiDi GAIA Collaborative Research Funds
- Shijiazhuang Science and Technology Plan Project
- National Key R&D Program of China
- Guangdong Basic and Applied Basic Research Foundation
Conference
CIKM '24
Sponsor:
CIKM '24: The 33rd ACM International Conference on Information and Knowledge Management
October 21 - 25, 2024
ID, Boise, USA
Acceptance Rates
Overall Acceptance Rate 1,861 of 8,427 submissions, 22%
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 132Total Downloads
- Downloads (Last 12 months)132
- Downloads (Last 6 weeks)121
Reflects downloads up to 10 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in