Spectral graph features for the classification of graphs and graph sequences

In this paper, the classification power of the eigenvalues of six graph-associated matrices is investigated. Each matrix contains a certain type of geometric/ spatial information, which may be important for the classification process. The performances of the different feature types is evaluated on two data sets: first a benchmark data set for optical character recognition, where the extracted eigenvalues were utilized as feature vectors for multi-class classification using support vector machines. Classification results are presented for all six feature types, as well as for classifier combinations at decision level. For the decision level combination, probabilistic output support vector machines have been applied, with a performance up to 92.4 %. To investigate the power of the spectra for time dependent tasks, too, a second data set was investigated, consisting of human activities in video streams. To model the time dependency, hidden Markov models were utilized and the classification rate reached 98.3 %. Copyright Springer-Verlag Berlin Heidelberg 2014