Graph Signal Processing

Graph Fourier Transformation

For a diagonalizable graph shift operator $S = V \Lambda V^H$ and a graph signal $x$, the projection of $x$ onto $V$ is called the Graph Fourier Transform of $x$.

$$\text{GFT}(x) = \hat{x} = V^{H}x$$

And the inverse transform is,

$$x = V \hat{x}$$

The GFT generalizes the Discrete Fourier Transform in Euclidean space to the graph signal space. If S is the Laplacian, the resulting GFT can be seen as the Fourier coefficients of the Laplacian eigenvalues, the canonical frequencies of the graph signal. If S is unitarily diagonalizable, then the basic vectors are orthogonal to each other and the energy of the signal is preserved. If S is not diagonalizable, a GFT can be defined using the Jordan decomposition with a defective basis.

Linear Graph Filter

A linear graph filter H for a graph with $\|V\|=n$ is,

$$H : \mathbb{R}^n \to \mathbb{R}^n$$

Hence it is a linear map from graph signals to graph signals. However, any filter of this form is not necessarily useful in practical applications as they don't respect the graph structure by potentially allowing nodes without shared edges to share direct information, is fixed in size once designed, and the elements to design grows quadratically. This gives rise to defining a class of linear graph filters called the convolutional graph filters, or linear shift-invariant filters.

Convolutional Graph Filter

A convolutional graph filter (or linear shift-invariant filter) H is defined as a polynomial of a graph shift operator S.

$$H(S) = \sum_{k=0}^{K-1} h_k S^k, \quad h_0, \ldots, h_{K-1} \in \mathbb{R}$$

Notice that for each $k$, $S^k$ is an operator acting on the k-neighbourhood of each vertex where $h_k$ determines the weight of the linear combination for that neighbourhood. This can be clearly seen in filtering a graph signal $x$,

$$H(S)x = h_0 x + h_1 Sx + h_2 S^2 x + \cdots + h_{K-1} S^{K-1} x$$

The convolutional graph filter has several important properties,

1. Locality The filter is local since it is a polynomial in the graph shift operator. Each power $S^k$ aggregates information from the $k$-hop neighbourhood of every node. Therefore, $H(S)x$ depends only on nodes within $K-1$ hops. No global operations (such as eigendecomposition of $S$) are required.
2. Shift Invariance Let $\hat{x} = H(S)x$. For a shifted signal $x' = Sx$, we have

$$H(S)x' = H(S)Sx = SH(S)x = S\hat{x},$$

since $H(S)$ is a polynomial in $S$ and thus commutes with $S$. Therefore, shifting the input results in an equivalent shift of the output.

1. Permutation Equivariance Let $P$ be a permutation matrix and define the permuted shift operator $S' = PSP^\top$ and signal $x' = Px$. Then

$$H(S')x' = \sum_{k=0}^{K-1} h_k (S')^k x' = \sum_{k=0}^{K-1} h_k (PS^kP^\top)(Px) = P \left( \sum_{k=0}^{K-1} h_k S^k x \right) = P H(S)x.$$

Hence, permuting the node labels permutes the output in the same way, so the filter is permutation equivariant.