Spectral Anomaly Detection in Large Graphs Using a Complex Moment-Based Eigenvalue Solver

Abstract

Detecting anomalies is an important and challenging task for many applications. In recent years, spectral methods have been proposed to detect anomalous subgraphs embedded into a background graph using eigenvectors corresponding to some of the largest positive eigenvalues of the graph’s modularity matrix. The spectral methods use the standard Lanczos-type eigenvalue solver to compute these exterior eigenpairs. However, eigenvectors with interior eigenvalues could also indicate the existence of anomalous subgraphs. In this study, we propose an efficient method using a complex moment-based eigenvalue solver, which can efficiently search anomalous subgraphs related to eigenvectors with both exterior and interior eigenvalues. Experimental results show the potential of the proposed method.