Subgraph Signal Processing

Abstract

Graph signal processing, like the graph Fourier transform, requires the full graph signal at every vertex of the graph. However, in practice, only signals at a subset of vertices may be available. We propose a subgraph signal processing framework that relates a graph shift operator or filter on a subgraph with a filter on the ambient graph through an operator loss. It allows us to define shift operators for the subgraph signal, which has a meaningful interpretation and relation to mixtures of shift invariant filters restricted to different subgraphs of the ambient graph (which we call semi shift invariant). This leads to a notion of frequency domain for the subgraph signal consistent in some sense with that of the full graph signal. We apply the subgraph signal processing machinery to several applications and demonstrate the utility of this framework in cases where only partial graph signals are observed.

References in corpus (11)

• Community structure in social and biological networks
• Semi-Supervised Classification with Graph Convolutional Networks
• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Discrete Signal Processing on Graphs
• Discrete Signal Processing on Graphs: Sampling Theory
• Signals on Graphs: Uncertainty Principle and Sampling
• Identifying Infection Sources and Regions in Large Networks
• A Spectral Graph Uncertainty Principle
• Irregularity-Aware Graph Fourier Transforms
• A Hilbert Space Theory of Generalized Graph Signal Processing
• Active Semi-Supervised Learning Using Sampling Theory for Graph Signals