Graph Signal Processing: Vertex Multiplication

A fundamental contribution from KocLab to Graph Signal Processing (GSP) has been recently published in IEEE Signal Processing Letters, where a new operation called Vertex Multiplication has been introduced.

On the Euclidean domains of classical signal processing, linking of signal samples to the underlying coordinate structure is straightforward. However, a major problem in graph signal processing is the lack of explicit association of vertices with an underlying coordinate structure since the vertices of a graph do not correspond to certain explicit quantitative values, apart from just indices of order.

Defined for graphs and can operate on graph signals, vertex multiplication (VM) has established this connection by using Fourier duality and generalized the coordinate multiplication operation in classical signal processing. VM is defined totally consistent with the theoretical structure of FT/DFT theory.

Such an explicit coordinate association can be helpful in the ongoing generalizations from classical signal processing to graph signal processing. It may also lead to new theoretical and computational endeavors, and deepen our theoretical understanding of the link between vertex and frequency domains with possible insights and applications to the notion of smoothness, distance metrics and localization in the vertex-domain, and transform designs for signals on graphs. Therefore, it can be considered as a natural and theoretically convenient way to embed the underlying irregular vertex domain to a quantitative coordinate structure for graphs and associated graph signals.

The paper can be accessed [here].

 

Abstract:

On the Euclidean domains of classical signal processing, linking of signal samples to underlying coordinate structures is straightforward. While graph adjacency matrices totally define the quantitative associations among the underlying graph vertices, a major problem in graph signal processing is the lack of explicit association of vertices with an underlying coordinate structure. To make this link, we propose an operation, called the vertex multiplication (VM), which is defined for graphs and can operate on graph signals. VM, which generalizes the coordinate multiplication (CM) operation in time series signals, can be interpreted as an operator that assigns a coordinate structure to a graph. By using the graph domain extension of differentiation and graph Fourier transform (GFT), VM is defined such that it shows Fourier duality that differentiation and CM operations are duals of each other under Fourier transformation (FT). Numerical examples and applications are also presented.