Open AccessSignal processing on graphs: structure preserving maps
Author(s) -
Vaishnav Nileshkumar,
Tatu Aditya
Publication year - 2019
Publication title -
iet signal processing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.384
H-Index - 42
eISSN - 1751-9683
pISSN - 1751-9675
DOI - 10.1049/iet-spr.2018.5147
Subject(s) - graph isomorphism , graph homomorphism , homomorphism , adjacency matrix , algebraic graph theory , mathematics , isomorphism (crystallography) , adjacency list , discrete mathematics , graph property , subgraph isomorphism problem , spectral graph theory , computer science , combinatorics , graph , line graph , voltage graph , chemistry , crystal structure , crystallography
Signal processing on graphs using adjacency matrix (as opposed to more traditional graph Laplacian) results in an algebraic framework for graph signals and shift invariant filters. This can be seen as an example of the algebraic signal processing theory. In this study, the authors examine the concepts of homomorphism and isomorphism between two graphs from a signal processing point of view and refer to them as GSP isomorphism and GSP homomorphism, respectively. Collectively, they refer to these concepts as structure preserving maps (SPMs). The fact that linear combination of signals and linear transforms on signals are meaningful operations has implications on the GSP isomorphism and GSP homomorphism, which diverges from the topological interpretations of the same concepts (i.e. graph isomorphism and graph homomorphism). When SPMs exist between two graphs, signals and filters can be mapped between them while preserving spectral properties. They examine conditions on adjacency matrices for such maps to exist. They also show that isospectral graphs form a special case of GSP isomorphism and that GSP isomorphism and GSP homomorphism is intrinsic to resampling and downsampling process.