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

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. (C) 2020 American Society of Civil Engineers.