In my previous blog linked below, we saw how we can arrive at the graph spectral domain using graph Laplacian matrix.
In this blog, we will take a slightly different approach and start with time shift in digital signal processing and define a shift for graph signals. Then we can move onto frequency representation for graph signals. We will heavily borrow from the ideas in [1].
I will assume that the reader has some knowledge on the following signal processing topics. Feel free to use the resources linked in the references section or any other suitable resource to learn these topics.
- Z-transform
- Discrete Fourier Transform
Shifts in Digital Signal Processing
Consider N samples of a signal sn,
The z-transform of this signal can be written as follows,
The discrete Fourier transform (DFT) of the signal sn can be written as follows.
The following inverse Fourier transform can be used to reconstruct the original signal from its spectral components.
Now, let’s consider that we have a finite impulse response (FIR) filter and hn is the impulse response of this filter. Then, the frequency response of this FIR filter can be written in terms of the z-transform of the impulse response of the filter as follows.
Now we will analyze what happens when a signal sin is filtered using our FIR filter. Let the output signal as sout. In the frequency domain, we can represent filtering as multiplication of the transfer function h(z) and the input signal’s frequency representation sin(z) as follows.
Now, let’s define a shift filter as follows.
Replacing the shift filter in the filtering equation we get
Recall the time-shifting property of z-transform,
Using this property, we can write sout as follows,
Before looking at the shifts for graphs signals, let’s recall the shift-invariance property in DSP. This means that the shift filter is commutative with any other filter.
Defining Shifts for Graph Signals
Let’s suppose that the values of the signal sn are the samples indexed by the nodes of a graph with N vertices. Let’s rewrite the signal as a vector.
The FIR filter h can be represented by a matrix H and the filtering operation can be expressed as a matrix-vector multiplication as follows.
Let’s consider a shift operation. We know the output of a shift operation for a given input signal sin. For a shift of 1, the last term gets moved as the first and the rest gets shifted down by 1 as we have seen in the previous section in shift for DSP. We can write shift of graph signal as follows,
Note that we have replaced the filter matrix H with Ac. Ac is called the circulant matrix and it will provide a cyclic shift to a graph signal. Ac is as follows.
Let’s try to view this matrix as the adjacency/weight matrix of a graph Gc.
Here, V is the set of vertices and E the edges. V will have N number of nodes. The n-th row in Ac will represent the edges ending on the n-th vertex. The graph that has its adjacency matrix as Ac will look like the following.
Note that this is a directed graph. For an undirected graph, the adjacency matrix will be symmetric. Let’s denote it as A. We can define a degree matrix D as that contains information about the sum of weights of edges that are incident on each vertex. It will be a diagonal matrix and can be mathematically defined as follows.
Now, we can define the combinatorial graph Laplacian as follows,
We can also define the symmetric normalized Laplacian matrix as follows,
Continuing our analogy with the classical DSP, we will define shift-invariance of filtering with a filter H as follows. The shift matrix and the filter matrix will be commutative.
As proven by Sandryhaila et al in [7], under certain conditions, every filter commuting with A can be written as a polynomial in A.
Frequency Representation for Graph Signals
Consider a signal sin that is invariant when filtered using a linear filter h. Then the filtered signal will be the same as the input signal multiplied by some scalar α
In GSP, we denote filters by a matrix H. We can define the eigenvectors of matrix H as the eigensignals of the filter h.
We saw in the previous section that shift-invariant filters can be written as a polynomial of the adjacency matrix A of some graph. Consider the eigendecomposition of the matrix A as follows.
Where V is the matrix of N eigenvectors as follows,
and the diagonal matrix with the eigenvalues of A is as follows
We can verify that the eigenvectors of the filter H are the same as eigenvectors of the adjacency matrix A by following. Note that the degree of the polynomial h is taken as M.
Here the diagonal matrix of eigenvalues of H is as follows,
Additionally, we can verify that the eigenvectors of A are the eigenfunctions of the filter H by multiplying the filter H by an arbitrary eigenvector vm of the adjacency matrix A.
where em is the zero vector except for the entry m which is 1. Note that the final line in the above steps is similar to the following form.
Now we have proven that for any filter matrix H that commutes with the adjacency matrix A of a graph, the eigenvectors are the same for H and A.
Before introducing the notion of Fourier transform for graph signals, let’s try to find the eigen decomposition of the circulant matrix. Consider the DFT matrix which expresses the discrete Fourier transform as a transformation matrix,
where
One amazing property of the circulant matrix is that its eigenvectors are the Fourier modes. Read through [6] and [9] if you need to convince yourself of this. Then we can write the circulant matrix Ac in terms of the DFT matrix as follows.
Comparing this form with the eigendecomposition of matrix A in terms of V (the matrix of eigenvectors of A) and eigenvalues, we can say that the graph Fourier transform is the inverse of matrix V.
From this, it follows that the columns of V, which are the eigenvectors of shift A, are the graph spectral components, and the diagonal entries λk are the graph frequencies. The graph Fourier transform of a graph signal s can be written as follows,
where f0, … fN-1 are the row vectors in the inverse matrix of V. Now we can use the inverse Fourier transform and write the spectral decomposition of original signal s as follows.
Interpreting Graph Frequencies
We can view vertex domain filtering of a graph signal sin by a filter H as matrix-vector multiplication.
Recall that we can write the eigendecomposition of H as follows,
Replacing this form in the filtering equation we get the following,
Note that the last two terms are the graph Fourier transform of the sin graph signal. We can replace the last two terms by the Fourier coefficients of sin. Recall that h(^) is a diagonal matrix whose elements are h-filtered eigenvalues of the adjacency matrix A.
Replacing these two components in the equation above, we get the following form,
Since the last term, Fourier coefficients of sin, is an N-dimensional vector, we can multiply the diagonal matrix and the vector to get the following form.
Note that matrix V multiplied by some N-dimentional vector, is the inverse graph Fourier transform.
In conclusion, filtering by a filter H of a vertex domain signal sin can be done using the following steps,
- take graph Fourier transform of sin (input signal)
- point-wise multiply the Fourier coefficients by the filter frequency response diagonal matrix
- take the inverse Fourier transform of the resulting N-dimensional vector
This is the graph Fourier filtering theorem.
Now, let’s look at what it means to be a low-pass graph signal. We have seen that in GSP the frequencies are defined by the eigenvalues of the shift matrix. We can incrementally order the graph frequencies by relating them to the complexity of the spectral component. We can measure the complexity of the spectral component by defining a total variation (TVg)of a spectral component vk as follows,
where,
and
Using this total variation, we can say that graph frequency λm is larger than graph frequency λl if
Using this we can define a low-pass signal s as a signal for which the graph Fourier coefficients are zero for Ωk, k > l, for some l, 0 ≤ l < N − 1. We can similarly define band- and high pass signals and filters.
References
[1] Ortega et al. (2018) Graph Signal Processing: Overview, Challenges, and Applications. Proceedings of the IEEE
[2] Introduction to Z-Transform — https://www.youtube.com/watch?v=mJgVOV9jRZU
[3] Discrete Fourier Transform — Simple Step by Step — https://www.youtube.com/watch?v=mkGsMWi_j4Q
[4] Time Shifting Property of Z-Transform — https://www.youtube.com/watch?v=MOvn9DNZeAg
[5] https://en.wikipedia.org/wiki/Eigendecomposition_of_a_matrix
[6] https://en.wikipedia.org/wiki/Circulant_matrix
[7] Sandryhaila et al (2013) Discrete signal processing on graphs
[8] https://en.wikipedia.org/wiki/DFT_matrix
[9] https://web.mit.edu/18.06/www/Spring17/Circulant-Matrices.pdf
