A fast algorithm for vertex-frequency representations of signals on graphs

From Time–Frequency to Vertex–Frequency and Back

The paper presents an analysis and overview of vertex–frequency analysis, an emerging area in graph signal processing. A strong formal link of this area to classical time–frequency analysis is provided. Vertex–frequency localization-based approaches to analyzing signals on the graph emerged as a response to challenges of analysis of big data on irregular domains. Graph signals are either localized in the vertex domain before the spectral analysis is performed or are localized in the spectral domain prior to the inverse graph Fourier transform is applied. The latter approach is the spectral form of the vertex–frequency analysis, and it will be considered in this paper since the spectral domain for signal localization is well ordered and thus simpler for application to the graph signals. The localized graph Fourier transform is defined based on its counterpart, the short-time Fourier transform, in classical signal analysis. We consider various spectral window forms based on which these transforms can tackle the localized signal behavior. Conditions for the signal reconstruction, known as the overlap-and-add (OLA) and weighted overlap-and-add (WOLA) methods, are also considered. Since the graphs can be very large, the realizations of vertex–frequency representations using polynomial form localization have a particular significance. These forms use only very localized vertex domains, and do not require either the graph Fourier transform or the inverse graph Fourier transform, are computationally efficient. These kinds of implementations are then applied to classical time–frequency analysis since their simplicity can be very attractive for the implementation in the case of large time-domain signals. Spectral varying forms of the localization functions are presented as well. These spectral varying forms are related to the wavelet transform. For completeness, the inversion and signal reconstruction are discussed as well. The presented theory is illustrated and demonstrated on numerical examples.

Differences in brain networks during consecutive swallows detected using an optimized vertex-frequency algorithm

Patients with dysphagia can have higher risks of aspiration after repetitive swallowing activity due to the "fatigue effect". However, it is still unknown how consecutive swallows affect brain activity. Therefore, we sought to investigate differences in swallowing brain networks formed during consecutive swallows using a signal processing on graph approach. Data were collected from 55 healthy people using electroencephalography (EEG) signals. Participants performed dry swallows (i.e., saliva swallows) and wet swallows (i.e., water, nectar-thick, and honey thick swallows). After standard pre-processing of the EEG time series, brain networks were formed using the time-frequency-based synchrony measure, while signals on graphs were formed as a line graph of the brain networks. For calculating the vertex frequency information from the signals on graphs, the proposed algorithm was based on the optimized window size for calculating the windowed graph Fourier transform and the graph S-transform. The proposed algorithms were tested using synthetic signals and showed improved energy concentration in comparison to the original algorithm. When applied to EEG swallowing data, the optimized windowed graph Fourier transform and the optimized graph S-transform showed that differences exist in brain activity between consecutive swallows. In addition, the results showed higher differences between consecutive swallows for thicker liquids.