A Joint Spectral Similarity Measure for Graphs Classification
Article dans une revue avec comité de lecture
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.
Files in this item
Showing items related by title, author, creator and subject.
Communication avec acteBAY-AHMED, Hadj-Ahmed; BOUDRAA, Abdel; DARE-EMZIVAT, Delphine; PREAUX, Yves (2017)La notion de mesure de similarité est très importante dans de nombreux domaines tels que l’apprentissage statistique, la fouille de données ou les sciences cognitives. Dans cet article, nous nous intéressons à la similarité ...
Communication avec acteBAY-AHMED, Hadj-Ahmed; DARE-EMZIVAT, Delphine; BOUDRAA, Abdel (2017)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 ...
Communication avec acteBAY-AHMED, Hadj-Ahmed; DARE-EMZIVAT, Delphine; BOUDRAA, Abdel-Ouahab (GRETSI, 2019-09)In this work, we present a new strategy for measuring the vulnerability of network connections, modeled by a graph, via the variations of the Von Neumann entropy of the density matrix associated to this graph, this one ...
Communication avec acteBAY-AHMED, Hadj-Ahmed; KOMATY, Ali; DARE, Delphine; BOUDRAA, Abdel-Ouahab (2015)In this work a new denoising scheme based on the empirical mode decomposition associated with a frequency analysis is introduced. Compared to classical approaches where the extracted modes are thresholded in time domain, ...
Communication avec acteCOLLIN, Steven; SZKOLNIK, Jean-Jacques; BOUDRAA, Abdel; DARE-EMZIVAT, Delphine; RAY, Cyril (2017)Cet article propose une approche pour détecter, de manière automatique, des anomalies de périodicité d’émission des messages AIS (Automatic Identification System) potentiellement révélatrices de comportements anormaux à ...