A Joint Spectral Similarity Measure for Graphs Classification

Abstract

In spite of the simple linear relationship between the adjacency A and the Laplacian L matrices, L=D-A where D is the degrees matrix, these matrices seem to reveal informations about the graph in different ways, where it appears that some details are detected only by one of them, as in the case of cospectral graphs. Based on this observation, a new graphs similarity measure, referred to as joint spectral similarity (JSS) incorporating both spectral information from A and L is introduced. A weighting parameter to control the relative influence of each matrix is used. Furthermore, to highlight the overlapping and the unequal contributions of these matrices for graph representation, they are compared in terms of the so called Von Neumann entropy (VN), connectivity and complexity measures. The graph is viewed as a quantum system and thus, the calculated VN entropy of its perturbed density matrix emphasizes the overlapping in terms of information quantity of A and L matrices. The impact of matrix representation is strongly illustrated by classification findings on real and conceptual graphs based on JSS measure. The obtained results show the effectiveness of the JSS measure in terms of graph classification accuracies and also highlight varying information overlapping rates of A and L, and point out their different ways in recovering structural information of the graph.