Top-k Outlier Detection in Graphs Using Graph Neural Networks: A novel approach for evaluating GNN algorithms

Anomaly detection in complex networks has emerged as a critical task due to the variety of its applications, which includes domains such as fraud prevention, cybersecurity, review systems and even healthcare. Traditional graph anomaly detection techniques often evaluate performance using global classification metrics, which do not align with real-world investigative practices where only a limited number of suspicious entities can be examined. This dissertation addresses this gap by introducing a top-k evaluation framework for anomaly detection in graphs using Graph Neural Networks (GNNs). We investigate and compare the performance of four GNN architectures—Graph Convolutional Network (GCN), Graph Attention Network (GAT), GraphSAGE and Bandwidth Graph Neural Network (BWGNN). The first three are considered as baseline or more traditional methods compared to the most recent BWGNN. A custom sigmoid output layer was introduced across all models to generate anomaly probabilities, enabling ranking-based evaluation. Furthermore, the node feature sets were enriched with structural descriptors, providing additional context for anomaly detection. This enrichment however, didn't provide any statistically significant improvement on the evaluation results. Experimental results demonstrate that the most recent method (BWGNN) achieves near-perfect performance in detecting anomalies at small values of k, seconded by GraphSAGE, while the other baseline methods fall behind. Analysis of each method seperately shows that for very small k, variance increases considerably due to limited anomalous nodes, but the overall trends remain robust. Experiments were performed on two major and annotated datasets, frequently used as benchmark datasets for AD tasks, FraudAmazon and FraudYelp from the Deep Graph Library. Overall, this dissertation's main contribution is the design and development of a novel ranking-based evaluation method for graph anomaly detection. Future directions include extending the framework with rank-based metrics, evaluating the framework across more datasets and models in pursuit of a benchmarking review, and developing a plug-in solution for seamless incorporation into existing and future GNN algorithms.