Spectral Anomaly Detection in Large Graphs Using a Complex Moment-Based Eigenvalue Solver
Publication: ASCE-ASME Journal of Risk and Uncertainty in Engineering Systems, Part A: Civil Engineering
Volume 6, Issue 2
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.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
Some or all data, models, or code generated or used during the study are available from the corresponding author by request. Available items: matrix data files and program codes for numerical experiments.
Acknowledgments
The present study is supported in part by the Japan Science and Technology Agency (JST), ACT-I (No. JPMJPR16U6), the New Energy and Industrial Technology Development Organization (NEDO), and the Japan Society for the Promotion of Science (JSPS), Grants-in-Aid for Scientific Research (Nos. 17K12690, 18H03250, and 19K20280).
References
Avron, H., and S. Toledo. 2011. “Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix.” J. ACM 58 (2): 1–34. https://doi.org/10.1145/1944345.1944349.
Birk, S., and A. Frommer. 2013. “A deflated conjugate gradient method for multiple right hand sides and multiple shifts.” Numer. Algorithms 67 (3): 507–529. https://doi.org/10.1007/s11075-013-9805-9.
Di Napoli, E., E. Polizzi, and Y. Saad. 2016. “Efficient estimation of eigenvalue counts in an interval.” Numer. Linear Algebra Appl. 23 (4): 674–692. https://doi.org/10.1002/nla.2048.
Fan, C., and A. Mostafavi. 2019. “A graph-based method for social sensing of infrastructure disruptions in disasters.” Comput.-Aided Civ. Infrastruct. Eng. 34 (12): 1055. https://doi.org/10.1111/mice.12457.
Frias-Martinez, V., and E. Frias-Martinez. 2014. “Spectral clustering for sensing urban land use using twitter activity.” Eng. Appl. Artif. Intell. 35 (Oct): 237–245. https://doi.org/10.1016/j.engappai.2014.06.019.
Fu, G., S. Wilkinson, and R. J. Dawson. 2016. “A spatial network model for civil infrastructure system development.” Comput.-Aided Civ. Infrastruct. Eng. 31 (9): 661–680. https://doi.org/10.1111/mice.12204.
Futamura, Y., T. Sakurai, S. Furuya, and J.-I. Iwata. 2013. “Efficient algorithm for linear systems arising in solutions of eigenproblems and its application to electronic-structure calculations.” In Vol. 7851 of High performance computing for computational science—VECPAR 2012: Lecture notes in computer science, edited by M. Daydé, O. Marques, and K. Nakajima, 226–235. Berlin: Springer.
Futamura, Y., H. Tadano, and T. Sakurai. 2010. “Parallel stochastic estimation method of eigenvalue distribution.” JSIAM Lett. 2: 127–130. https://doi.org/10.14495/jsiaml.2.127.
Hutchinson, M. 1990. “A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines.” Commun. Stat. Simul. Comput. 19 (2): 433–450. https://doi.org/10.1080/03610919008812866.
Idé, T., and H. Kashima. 2004. “Eigenspace-based anomaly detection in computer systems.” In Proc., 10th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, KDD ’04, 440–449. New York: ACM.
Ikegami, T., and T. Sakurai. 2010. “Contour integral eigensolver for non-Hermitian systems: A Rayleigh-Ritz-type approach.” Taiwanese J. Math. 14 (3A): 825–837. https://doi.org/10.11650/twjm/1500405869.
Ikegami, T., T. Sakurai, and U. Nagashima. 2010. “A filter diagonalization for generalized eigenvalue problems based on the Sakurai-Sugiura projection method.” J. Comput. Appl. Math. 233 (8): 1927–1936. https://doi.org/10.1016/j.cam.2009.09.029.
Leman, A., H. Tong, and D. Koutra. 2015. “Graph based anomaly detection and description: A survey.” Data Min. Knowl. Discovery 29 (3): 626–688. https://doi.org/10.1007/s10618-014-0365-y.
Miller, B., N. Bliss, and P. J. Wolfe. 2010. “Subgraph detection using eigenvector L1 norms.” In Advances in neural information processing systems 23, edited by J. D. Lafferty, C. K. I. Williams, J. Shawe-Taylor, R. S. Zemel, and A. Culotta, 1633–1641. Red Hook, NY: Curran Associates.
Miller, B. A., M. S. Beard, P. J. Wolfe, and N. T. Bliss. 2015. “A spectral framework for anomalous subgraph detection.” IEEE Trans. Signal Process. 63 (16): 4191–4206. https://doi.org/10.1109/TSP.2015.2437841.
Sakurai, T., and H. Sugiura. 2003. “A projection method for generalized eigenvalue problems using numerical integration.” J. Comput. Appl. Math. 159 (1): 119–128. https://doi.org/10.1016/S0377-0427(03)00565-X.
Sakurai, T., and H. Tadano. 2007. “CIRR: A Rayleigh-Ritz type method with contour integral for generalized eigenvalue problems.” Hokkaido Math. J. 36 (4): 745–757. https://doi.org/10.14492/hokmj/1272848031.
Tadano, H., S. Shusaku, and A. Imakura. 2017. “Efficient algorithm for linear systems arising in solutions of eigenproblems and its application to electronic-structure calculations.” In Vol. 117 of Eigenvalue problems: Algorithms, software and applications in petascale computing: EPASA 2015: Lecture notes in computational science and engineering, edited by T. Sakurai, S.-L. Zhang, T. Imamura, Y. Yusaku, Y. Kuramashi, and T. Hoshi, 171–185. Cham, Switzerland: Springer.
Wu, L., X. Wu, A. Lu, and Z.-H. Zhou. 2013. “A spectral approach to detecting subtle anomalies in graphs.” J. Intell. Inf. Syst. 41 (2): 313–337. https://doi.org/10.1007/s10844-013-0246-7.
Information & Authors
Information
Published In
ASCE-ASME Journal of Risk and Uncertainty in Engineering Systems, Part A: Civil Engineering
Volume 6 • Issue 2 • June 2020
Copyright
©2020 American Society of Civil Engineers.
History
Received: Jul 3, 2019
Accepted: Oct 28, 2019
Published online: Feb 8, 2020
Published in print: Jun 1, 2020
Discussion open until: Jul 8, 2020
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.