Spectral recognition of graphs

Authors

  • Dragoš Cvetković Mathematical Institute SANU, Belgrade

DOI:

https://doi.org/10.2298/YJOR120925025C

Keywords:

Spectral graph theory, spectral recognition, computer science, internet, data mining

Abstract

At some time, in the childhood of spectral graph theory, it was conjectured that non-isomorphic graphs have different spectra, i.e. that graphs are characterized by their spectra. Very quickly this conjecture was refuted and numerous examples and families of non-isomorphic graphs with the same spectrum (cospectral graphs) were found. Still some graphs are characterized by their spectra and several mathematical papers are devoted to this topic. In applications to computer sciences, spectral graph theory is considered as very strong. The benefit of using graph spectra in treating graphs is that eigenvalues and eigenvectors of several graph matrices can be quickly computed. Spectral graph parameters contain a lot of information on the graph structure (both global and local) including some information on graph parameters that, in general, are computed by exponential algorithms. Moreover, in some applications in data mining, graph spectra are used to encode graphs themselves. The Euclidean distance between the eigenvalue sequences of two graphs on the same number of vertices is called the spectral distance of graphs. Some other spectral distances (also based on various graph matrices) have been considered as well. Two graphs are considered as similar if their spectral distance is small. If two graphs are at zero distance, they are cospectral. In this sense, cospectral graphs are similar. Other spectrally based measures of similarity between networks (not necessarily having the same number of vertices) have been used in Internet topology analysis, and in other areas. The notion of spectral distance enables the design of various meta-heuristic (e.g., tabu search, variable neighbourhood search) algorithms for constructing graphs with a given spectrum (spectral graph reconstruction). Several spectrally based pattern recognition problems appear in many areas (e.g., image segmentation in computer vision, alignment of protein-protein interaction networks in bio-informatics, recognizing hard instances for combinatorial optimization problems such as the travelling salesman problem). We give a survey of such and other graph spectral recognition techniques used in computer sciences.

References

Aouchiche M., and Hansen P., “A survey of automated conjectures in spectral graph theory”, Linear Algebra Appl., 432(2010) 2293-2322.

Arsić B., Cvetković D., Simić S.K., and Škarić M., “Graph spectral techniques in computer sciences”, Applicable Analysis and Discrete Mathematics, 6 (1)(2012) 1-30.

Blondel V.D., Gajardo A., Heymans M., Senellart P., and Van Doren P., “A measure of similarity between graph vertices: applications to synonym extraction and web searching“, SIAM Rev., 46(4)(2004) 647-666.

Brin S., and Page L., “The Anatomy of Large-Scale Hypertextual Web Search Engine”, Proc. 7th International WWW Conference, 1998.

Brouwer A.E., and Spence E., “Cospectral graphs on 12 vertices”, Electron. J. Combin., 16, 2009.

Caporossi G., Cvetković D., Gutman I., and Hansen P., “Variable neighborhood search for extremal graphs, 2. Finding graphs with extremal energy“, J. Chem. Inform. Comp. Sci., 39(1999) 984-996.

Comellas F., and Diaz-Lopez J., “Spectral reconstruction of complex networks“, Phys. A, 387(2008) 6436-6442.

Cook, S. A. , “The complexity of theorem-proving procedures“, Proc. 3rd ACM Symposium on Theory of Computing, 1971, 151-158.

Cvetković D., “Star partitions and the graph isomorphism problem“, Linear and Multilinear Algebra, 39(1-2)(1995) 109-132.

Cvetković D., “Characterizing properties of some graph invariants related to electron charges in the Hüuckel molecular orbital theory“, Proc. DIMACS Workshop on Discrete Mathematical Chemistry, DIMACS Ser. Discrete Math. Theoret. Comp, Sci., 51(2000) 79-84.

Cvetković D., “Complexity indices for the travelling salesman problem and data mining“, Transactions of Combinatorics, 1(1)(2012) 35-43.

Cvetković D., Doob M., and Sachs H., Spectra of Graphs, Theory and Application, 3rd edition, Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995.

Cvetković D., and Gutman I., (eds.), Applications of Graph Spectra, Zb. Rad. (Beogr.), 13(21) Mathematical Institute SANU, Belgrade, 2009.

Cvetković D., and Gutman I., (eds.), Selected Topics on Applications of Graph Spectra, Zb. Rad. (Beogr.), 14(22), Mathematical Institute SANU, Belgrade, 2011.

Cvetković D., Rowlinson P., and Simić S. K., Eigenspaces of Graphs, Cambridge University Press, Cambridge, 1997.

Cvetković D., Rowlinson P., and Simić S., “Eigenvalue bounds for the signless Laplacian“, Publ. Inst. Math. (Beograd) 81(95)(2007) 11-27.

Cvetković D., Rowlinson P., and Simić S. K., An Introduction to the Theory of Graph Spectra, Cambridge University Press, Cambridge, 2009.

Cvetković D., and Simić S.K., “Towards a spectral theory of graphs based on the signless Laplacian I“, Publ. Inst. Math. (Beograd) 85(99)(2009) 19-33.

Cvetković D., and Simić S.K., “Towards a spectral theory of graphs based on the signless Laplacian, II“, Linear Algebra Appl., 432(2010) 2257-2272.

Cvetković D., and Simić S.K., “Towards a spectral theory of graphs based on the signless Laplacian, III“, Appl. Anal. Discrete Math., 4(2010) 156-166.

Cvetković D., and Simić S.K., “Graph spectra in computer science“, Linear Algebra Appl., 434(2011) 1545-1562.

Dam E.R. van, and Haemers W., “Which graphs are determined by their spectrum? “, Linear Algebra Appl., 373(2003) 241-272.

Demirci M.F., Leuken R.H. van, and Veltkamp R.C., “Indexing through laplacian spectra“, Computer Vision and Image Understanding, 2008. doi: 10.1016/j.cviu.2007.09.012.

Fan Y., “On spectral integral variations of graphs“, Linear Multilinear Algebra 50 (2002) 133-142.

Fay D., Haddadi H., Thomason A., Mortier R., Jamakovic A., Uhlig S., and Rio M., “Weighted spectral distribution for internet topology analysis: theory and applications“, J. IEEE/ACM Trans. Networking (TON), 18(1)(2010) 164-176.

Fiedler M., “Algebraic connectivity of graphs“, Czechoslovak Math. J., 23(98)(1973) 298-305.

Fiedler M., “A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory“, Czechoslovak Math. J., 25(100)(1975) 619-633.

Golub G.H., and Van Loan C., Matrix Computations, Johns Hopkins University Press, 2006.

Haemers W., and Spence E., “Enumeration of cospectral graphs“, European J. Combin. 25 (2004) 199-211.

Heilbronner E., and Jones T.B., “Spectral differences between "isospectral" molecules“, J. Amer. Chem. Soc., 100(20)(1978) 6505-6507.

Jovanović I., and Stanić Z., “Spectral distances of graphs“, Linear Algebra Appl., 436(2012) 1425-1435.

Kirkland S., “A Characterization of Spectral Integral Variation in Two Places for Laplacian Matrices“, Linear Multilinear Algebra, 52 (2004) 79-98.

Kuchaiev O., Milenković T., Memišević V., Hayes W., and Pržulj N., “Topological network alignment uncovers biological function and phylogeny“, J. Roy. Soc. Interface, 7(2010) 1341-1354.

Liu D., Wang H., and Van Mieghem P., “Spectral perturbation and reconstructability of complex networks“, Phys. Rev. E, 81(2010) 016101, 1-9.

Papadimitriou, C.H., Raghavan P., Tamaki H., and Vempala S., “Spectral perturbation and reconstructability of complex networks“, J. Comput. System Sci., 61(2)(2000) 217-235.

Papadimitriou, C., and Steiglitz K., Combinatorial Optimization: algorithms and complexity, Dover, 1998.

Pinto, A., MIREX2007 - Graph spectral method, to appear.

Pržulj, N., Corneil, D.G., and Jurisica, I., “Efficient estimation of graphlet frequency distributions in protein-protein interaction networks“, Bioinformatics, 22(8)(2006) 974-980.

Shi, J., and Malik, J., “Normalized cuts and image segmentation“, Proc. IEEE Conf. Computer Vision and Pattern Recognition, 1997, 731-737; IEEE Trans. Pattern Analysis Machine Intell., 28(2000) 888-905.

Shokoufandeh, A., Dickinson, S. J., Siddiqi, K., and Zucker, S. W., “Indexing using a spectral encoding of topological structure“, IEEE Trans. Comput. Vision Pattern Recognition, 2 (1999) 491-497.

Singh, R., Xu J., and Berger B., “Pairwise global alignment of protein interaction networks by matching neighborhood topology”, Research in Computational Molecular Biology, Springer, 2007, 16-31.

Skilicorn, D.B., Understanding Complex Data Bases: Data Mining with Matrix Decompositions, Chapman & Hall/CRC, New York, 2007.

So, W., “Rank one perturbation and its application to the Laplacian spectrum of a graph“, Linear Multilinear Algebra, 46 (1999) 193-198.

Spielman, D. A., “Spectral graph theory and its applications“, 48th Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2007, 29-38.

Vukadinović, D., Huang, P., and Erlebach, T., “A spectral analysis of the Internet topology“, Technical Report 118, TIK Institute, ETH Zürich, 2001.

Vukadinović, D., Huang P., and Erlebach T., “On the spectrum and structure of the Internet topology graphs“, Proc. Second Internat. Workshop on Innovative Internet Computing Systems, IICS '02, 2346 (2002) 83-95.

Wei, T.H., “The algebraic foundations of ranking theory“, Thesis, Cambridge, 1952.

Weiss, Y., “Segmentation using eigenvectors: a unifying view“, Proc. Seventh IEEE Internat. Conf. Computer Vision, 2 (1999) 975-982.

Xuan, Q., Yu, L., Du F., and Wu, T.-J., “A review on node-matching between networks“, in: Y. Zhang, (ed.), New Frontiers in Graph Theory, Intex, Rijeka, 2012, 153-167.

Ying, X., and Wu, X., “Randomizing social networks: a spectrum preserving approach“, Proc. SIAM Internat. Conf. Data Mining, SDM2008, April 24-26, 2008, Atlanta, Georgia, USA, SIAM, 2008, 739-750.

Zou, L., Chen, L., Yu, J.X., and Lu, Y., “A novel spectral coding in a large graph database“, EDBT'08, March 25 - 30, 2008, Nantes, France.

Downloads

Published

2012-09-01

Issue

Section

Research Articles