Graph Signals Classification Using Total Variation and Graph Energy Informations

Abstract

In this work, we consider the problem of graph signals classification. We investigate the relevance of two attributes, namely the total variation (TV) and the graph energy (GE) for graph signals classification. The TV is a compact and informative attribute for efficient graph discrimination. The GE information is used to quantify the complexity of the graph structure which is a pertinent information. Based on these two attributes, three similarity measures are introduced. Key of these measures is their low complexity. The effectiveness of these similarity measures are illustrated on five data sets and the results compared to those of five kernel-based methods of the literature. We report results on computation runtime and classification accuracy on graph benchmark data sets. The obtained results confirm the effectiveness of the proposed methods in terms of CPU runtime and of classification accuracy. These findings also show the potential of TV and GE informations for graph signals classification.