Analysis of vertex-varying spectral content of signals on graphs challenges the assumption of vertex invariance and requires the introduction of vertex-frequency representations as a new tool for graph signal analysis. Local smoothness, an important parameter of vertex-varying graph signals, is introduced and defined in this paper. Basic properties of this parameter are given. By using the local smoothness, an ideal vertex-frequency distribution is introduced. The local smoothness estimation is performed based on several forms of the vertex-frequency distributions, including the graph spectrogram, the graph Rihaczek distribution, and a vertex-frequency distribution with reduced interferences. The presented theory is illustrated through numerical examples.

Graph signal processing deals with signals whose domain, defined by a graph, is irregular. An overview of basic graph forms and definitions is presented first. Spectral analysis of graphs is discussed next. Some simple forms of processing signal on graphs, like filtering in the vertex and spectral domain, subsampling and interpolation, are given. Graph topologies are reviewed and analyzed as well. Theory is illustrated through examples, including few applications at the end of the chapter.

A vertex-varying spectral content on graphs challenges the assumption of vertex invariance and requires vertex-frequency representations for an adequate analysis. In this letter, we introduce a class of vertex-frequency energy distributions inspired by traditional time-frequency energy distributions. These newly introduced distributions do not use localization windows. Their efficiency in energy concentration is illustrated through examples.

The analysis of signals defined over a graph is relevant in many applications, such as social and economic networks, big data or biological networks, and so on. A key tool for analyzing these signals is the so-called graph Fourier transform (GFT). Alternative definitions of GFT have been suggested in the literature, based on the eigen-decomposition of either the graph Laplacian or adjacency matrix. In this paper, we address the general case of directed graphs and we propose an alternative approa...

This paper considers the definition of the graph Fourier transform (GFT) and of the spectral decomposition of graph signals. Current literature does not address the lack of unicity of the GFT. The GFT is the mapping from the signal set into its representation by a direct sum of irreducible shift invariant subspaces: 1) this decomposition may not be unique; and 2) there is freedom in the choice of basis for each component subspace. These issues are particularly relevant when the graph shift has r...

In design and manufacturing, mesh segmentation is required for FACE construction in boundary representation (B-Rep), which in turn is central for feature-based design, machining, parametric CAD and reverse engineering, among others. Although mesh segmentation is dictated by geometry and topology, this article focuses on the topological aspect (graph spectrum), as we consider that this tool has not been fully exploited. We pre-process the mesh to obtain a edge-length homogeneous triangle set and ...

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 a...

Abstract 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., s...

The windowed Fourier transform (short time Fourier transform) and the S-transform are widely used signal processing tools for extracting frequency information from non-stationary signals. Previously, the windowed Fourier transform had been adopted for signals on graphs and has been shown to be very useful for extracting vertex-frequency information from graphs. However, high computational complexity makes these algorithms impractical. We sought to develop a fast windowed graph Fourier transform ...

(MIT: Massachusetts Institute of Technology), Dorina Thanou9

Estimated H-index: 9

(EPFL: École Polytechnique Fédérale de Lausanne)+ -3 AuthorsPierre Vandergheynst48

Estimated H-index: 48

(EPFL: École Polytechnique Fédérale de Lausanne)

The construction of a meaningful graph plays a crucial role in the success of many graph-based representations and algorithms for handling structured data, especially in the emerging field of graph signal processing. However, a meaningful graph is not always readily available from the data, nor easy to define depending on the application domain. In particular, it is often desirable in graph signal processing applications that a graph is chosen such that the data admit certain regularity or smoot...

We propose a sampling theory for signals that are supported on either directed or undirected graphs. The theory follows the same paradigm as classical sampling theory. We show that perfect recovery is possible for graph signals bandlimited under the graph Fourier transform. The sampled signal coefficients form a new graph signal, whose corresponding graph structure preserves the first-order difference of the original graph signal. For general graphs, an optimal sampling operator based on experim...

Graph signal processing deals with signals which are observed on an irregular graph domain. While many approaches have been developed in classical graph theory to cluster vertices and segment large graphs in a signal independent way, signal localization based approaches to the analysis of data on graph represent a new research direction which is also a key to big data analytics on graphs. To this end, after an overview of the basic definitions in graphs and graph signals, we present and discuss ...

A vertex-varying spectral content on graphs challenges the assumption of vertex invariance and requires vertex-frequency representations for an adequate analysis. In this letter, we introduce a class of vertex-frequency energy distributions inspired by traditional time-frequency energy distributions. These newly introduced distributions do not use localization windows. Their efficiency in energy concentration is illustrated through examples.