Community-Aware Graph Signal Processing

Abstract

The emerging field of graph signal processing (GSP) allows to transpose classical signal processing operations (e.g., filtering) to signals on graphs. The GSP framework is generally built upon the graph Laplacian, which plays a crucial role to study graph properties and measure graph signal smoothness. Here instead, we propose the graph modularity matrix as the centerpiece of GSP, in order to incorporate knowledge about graph community structure when processing signals on the graph, but without the need for community detection. We study this approach in several generic settings such as filtering, optimal sampling and reconstruction, surrogate data generation, and denoising. Feasibility is illustrated by a small-scale example and a transportation network dataset, as well as one application in human neuroimaging where community-aware GSP reveals relationships between behavior and brain features that are not shown by Laplacian-based GSP. This work demonstrates how concepts from network science can lead to new meaningful operations on graph signals.

21 pages, 4 figures, Accepted to Signal Processing Magazine: Special Issue on Graph Signal Processing: Foundations and Emerging Directions

References in corpus (17)

• Fast algorithm for detecting community structure in networks
• Assortative mixing in networks
• Finding community structure in networks using the eigenvectors of matrices
• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Functional cartography of complex metabolic networks
• Link communities reveal multiscale complexity in networks
• Community detection in networks: A user guide
• The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
• Discrete Signal Processing on Graphs
• Clustering and Community Detection in Directed Networks: A Survey
• Signals on Graphs: Uncertainty Principle and Sampling
• Stationary Graph Processes and Spectral Estimation
• A Review of Stochastic Block Models and Extensions for Graph Clustering
• Topological Signal Processing over Simplicial Complexes
• Identifying "communities" within energy landscapes
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• On the Graph Fourier Transform for Directed Graphs