Correlation-Based Graph Smoothness Measures In Graph Signal Processing

Graph smoothness is an important prior used for designing sampling strategies for graph signals as well as for regularizing the problem of graph learning. Additionally, smoothness is an appropriate assumption for graph signal processing (GSP) tasks such as filtering or signal recovery from samples. The most popular measure of smoothness is the quadratic form of the Laplacian, which naturally follows from the factor analysis approach. This paper presents a novel smoothness measure based on the graph correlation. The proposed measure enhances the applicability of graph smoothness measures across a variety of GSP tasks, by facilitating interoperability and generalizing across shift operators.

I. Introduction

Graph signal processing (GSP) is an area of signal processing and data analysis that deals with structured data represented on graphs [1]–[3]. The application areas in which signals represented on graphs need to be processed are broad and include sensor networks, brain networks, gene regulatory networks, and social networks, to name a few [4]–[7]. By encoding the interaction between samples of data, graphs provide natural representations of data in irregular domains. This helps to improve the accuracy of data analysis. The structure of real-world data graphs varies and can take different forms, such as adjacency matrices, Laplacian matrices, or their normalized equivalents. Regardless of the above differences, specific signal processing tasks are addressed by algorithms of a unified nature. Therefore, in order to implement data-specific algorithms, an accurate understanding of how data structures are physically represented by graphs is critical.