Anomaly Detection and Similarity Computation on Attributed Graphs
Jianheng Tang · 2025
Anomaly detection and similarity computation are two fundamental tasks in data mining, but when applied to graphs, their heterogeneous, relation-centric, and non-Euclidean nature presents unique challenges. This thesis explores novel approaches to both problems in the context of graph data and is divided into three parts: node-level anomaly detection, node-level similarity computation, and the combination of both in multi-graph scenarios. The first part investigates anomalous node detection in a static attributed graph through both theoretical and empirical perspectives. We analyze anomalies through the lens of graph spectrum, revealing a ""right-shift"" phenomenon where anomalous nodes redistribute spectral energy to higher frequencies. This insight drives our Beta Wavelet Graph Neural Network (BWGNN) with specialized spectral band-pass filters to better capture anomalous patterns. We further establish GADBench, a comprehensive benchmarking framework that evaluates 29 algorithms across diverse datasets, yielding surprising findings--traditional tree ensembles with simple neighborhood aggregation can outperform specialized GNNs in performance, robustness, and computational efficiency. The second part develops two frameworks addressing critical limitations in current node-level similarity computation approaches between attributed graphs. For unsupervised alignment with structural and feature inconsistencies, we propose a joint structural learning and optimal transport approach, SLOTAlign, which offers a provably robust and convergent solution for noisy, heterogeneous graphs. For knowledge graph entity alignment, we introduce FGWEA that fuses structural and semantic information via a specific optimal transport variant--the Fused Gromoy-Wasserstein (FGW) distance, improving cross-lingual and cross-source entity matching accuracy significantly. The third part unifies graph-level similarity computation and anomaly detection via FGWAlign, a fast computation method to compare graphs through approximating the Graph Edit Distance (GED). FGWAlign reformulates GED as a FGW optimization problem and incorporates three enhancements: random exploration, projection refinement, and multi-relational extensions. It achieves 80% error reduction and up to 15-60 times speedup over baselines. For anomaly detection, it simply uses GED-to-nearest-neighbor scores to represent the abnormality and employs a pivot-based heuristic to accelerate the comparison, outperforming eight specialized approaches on four multi-graph datasets. FGWAlign achieves a superior balance of efficiency and accuracy, enabling versatile graph-level analytics in bioinformatics and cybersecurity.