Timezone: »

BOND: Benchmarking Unsupervised Outlier Node Detection on Static Attributed Graphs
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 · Philip S Yu

Thu Dec 01 02:00 PM -- 04:00 PM (PST) @ Hall J #1030

Detecting which nodes in graphs are outliers is a relatively new machine learning task with numerous applications. Despite the proliferation of algorithms developed in recent years for this task, there has been no standard comprehensive setting for performance evaluation. Consequently, it has been difficult to understand which methods work well and when under a broad range of settings. To bridge this gap, we present—to the best of our knowledge—the first comprehensive benchmark for unsupervised outlier node detection on static attributed graphs called BOND, with the following highlights. (1) We benchmark the outlier detection performance of 14 methods ranging from classical matrix factorization to the latest graph neural networks. (2) Using nine real datasets, our benchmark assesses how the different detection methods respond to two major types of synthetic outliers and separately to “organic” (real non-synthetic) outliers. (3) Using an existing random graph generation technique, we produce a family of synthetically generated datasets of different graph sizes that enable us to compare the running time and memory usage of the different outlier detection algorithms. Based on our experimental results, we discuss the pros and cons of existing graph outlier detection algorithms, and we highlight opportunities for future research. Importantly, our code is freely available and meant to be easily extendable: https://github.com/pygod-team/pygod/tree/main/benchmark

Author Information

Kay Liu (University of Illinois Chicago)
Kay Liu

I am a second year Computer Science Ph.D. student in Big Data and Social Computing (BDSC) Lab at University of Illinois at Chicago. My advisor is Prof. Philip S. Yu. Before joining UIC, I received my bachelor degree from Beijing University of Posts and Telecommunications and Queen Mary University of London in 2021. I also interned in Walmart Global Tech in summer 2022, and AWS Shanghai AI Lab DGL team in summer 2021. My research interests are Graph Mining, Anomaly Detection, and Fraud Detection.

Yingtong Dou (Visa Research)
Yingtong Dou

I am a research scientist at Visa Research working on graph mining and its application in trust&safety domain. Before joining Visa, I obtained my Ph.D. degree in Computer Science at the University of Illinois Chicago in 2022.

Yue Zhao (Carnegie Mellon University)

I am pursuing a Ph.D. in Information Systems at Carnegie Mellon University, advised by Prof. Leman Akoglu. Different from most IS researchers, I focus on data mining algorithms, systems, and applications. Research Keywords: Outlier & Anomaly Detection; Ensemble Learning; Scalable Machine Learning; Machine Learning Systems.

Xueying Ding (Carnegie Mellon University)
Xiyang Hu (Carnegie Mellon University)
Ruitong Zhang
Kaize Ding (Arizona State University)
Canyu Chen (Illinois Institute of Technology)
Hao Peng (Beihang University)
Kai Shu (Illinois Institute of Technology)
Lichao Sun (Lehigh University)
Jundong Li (University of Virginia)
George H Chen (Carnegie Mellon University)

George Chen is an assistant professor of information systems at Carnegie Mellon University. He works on nonparametric prediction methods, applied to healthcare and sustainable development. He received his PhD from MIT in Electrical Engineering and Computer Science.

Zhihao Jia (Carnegie Mellon University)
Philip S Yu (UIC)

More from the Same Authors