A spectral approach to detecting subtle anomalies in graphs

摘要

In this paper we investigate the problem of detecting small and subtle subgraphs embedded into a large graph with a common structure. We call the embedded small and subtle subgraphs as signals or anomalies and the large graph as background. Those small and subtle signals, which are structurally dissimilar to the background, are often hidden within graph communities and cannot be revealed in the graph’s global structure. We explore the minor eigenvectors of the graph’s adjacency matrix to detect subtle anomalies from a background graph. We demonstrate that when there are such subtle anomalies, there exist some minor eigenvectors with extreme values on some entries corresponding to the anomalies. Under the assumption of the Erdos–Renyi random graph model, we derive the formula that show how eigenvector entries are changed and give detectability conditions. We then extend our theoretical study to the general case where multiple anomalies are embedded in a background graph with community structure. We develop an algorithm that uses the eigenvector kurtosis to filter out the eigenvectors that capture the signals. Our theoretical analysis and empirical evaluations on both synthetic data and real social networks show effectiveness of our approach to detecting subtle signals.