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 neighborhood 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.
