Signal processing on graphs: structure preserving maps

Abstract

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.