Vertex-Frequency Analysis: A Way to Localize Graph Spectral Components [Lecture Notes]

Currently, brain and social networks are examples of new data types that are massively acquired and disseminated [1]. These networks typically consist of vertices (nodes) and edges (connections between nodes). Usually, information is conveyed through the strength of connection among nodes, but in recent years, it has been discovered that valuable information may also be conveyed in signals that occur on each vertex. However, traditional signal processing often does not offer reliable tools and algorithms to analyze such new data types. This is especially true for cases where networks (e.g., the strength of connections), or signals on vertices, have properties that change over the network. This lecture note presents a new method to analyze changes in signals on graphs. This method, called the vertex-frequency analysis, relies on Laplacian matrices to establish connections between vertex changes and spectral content [2]-[5]. Specifically, this lecture note aims to connect concepts from frequency and time-frequency analyses (e.g., [6] and [7]) to the spectral analysis of graph signals. Graph signal processing is a major research area, however, we still lack understanding of how to relate graph signal processing concepts to concepts from traditional signal processing.

Relevance

The vertex-frequency analysis presented here is a valuable tool that can be used to analyze vertex-varying changes in networks (graphs) such as brain networks (e.g., brain changes during consecutive swallows [8]), changes in social interactions in a large group of people, or to understand traffic patterns during rush hour in major metropolitan areas. Theoretically, it connects principles of the Fourier analysis and eigenvalue decomposition from undergraduate courses, to more advanced topics such as time-frequency representations typically taught at a graduate level.