Exploring graph-based clustering and outlier detection algorithms

Li, J. (2025)

Doctoral Thesis

In the era of big data, extracting insights from complex datasets is a key challenge. This thesis demonstrates the superiority of graph-based methods over traditional clustering (e.g., k-means, DBSCAN) and outlier detection for analyzing high-dimensional and noisy data. We show that Minimum Spanning Tree (MST) and spectral techniques excel at identifying irregularly shaped clusters and hierarchical structures missed by other approaches.

For outlier detection, we introduce novel methods like Spectral Analysis Outlier Detection (SAOD) and Adaptive Mini-MST Outlier Detection (MMOD). These leverage graph structures and local density scaling to effectively identify contextual anomalies without prior assumptions, proving highly effective in domains like healthcare and cybersecurity. Collectively, this research establishes graph-based analysis as a flexible and powerful framework, bridging theoretical innovation with practical application for modern data challenges.

• Graph-based clustering
• Cluster-based outlier detection

• All authors: Li, J.
• Supervisor: Verbeek, F.J.
• Co-supervisor: Wang, C.
• Committee: Bonsangue, M.M.; Batenburg, K.J.; Plaat, A.; Nurami Ruchjana, B.; Guo, Y.; Pucci, R.
• Qualification: Doctor (dr.)
• Awarding Institution: Leiden Institute of Advanced Computer Science (LIACS), Faculty of Science, Leiden University
• Date: 2025-11-12
• DOI: doi:10.60602/1887/4282945