Multi-dimensional graph fractional Fourier transform and its application

A weighted graph $\mathcal{G}=\{\mathcal{V},\mathcal{E},W\}$ consists of a finite set of vertices $\mathcal{V}=\{v_{0},\cdots,v_{N-1}\}$, where $N=|\mathcal{V}|$ is the number of nodes, a set of edges $\mathcal{E}=\{(i,j)|i,j\in\mathcal{V},j\sim i\}\subseteq\mathcal{V}\times\mathcal{V}$, and a weighted adjacency matrix $W$. We assume that the graph is undirected with positive edge weights. The non-normalized graph Laplacian is a symmetric difference operator $\mathcal{L}=D-W$ [18], where $D$ is a diagonal degree matrix of $\mathcal{G}$. Let $\{\chi_{0},\chi_{1},\cdots,\chi_{N-1}\}$ be the set of orthonormal eigenvectors. Suppose that the corresponding Laplacian eigenvalues are sorted as $0=\lambda_{0}<\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{N-1}:=\lambda_{max}$. We have $\mathcal{L}=\mathbf{\chi}\mathbf{\Lambda}\mathbf{\chi}^{H}$, where $\mathbf{\chi}=[\chi_{0},\chi_{1},\cdots,\chi_{N-1}]$, and the diagonal matrix is $\mathbf{\Lambda}=diag([\lambda_{0},\lambda_{1},\cdots,\lambda_{N-1}])$. The superscript $H$ represents the Hermitian transpose operation.

The fractional order is introduced to the Laplacian operator [15]. The graph fractional Laplacian operator $\mathcal{L}_{\alpha}$ is defined by $\mathcal{L}_{\alpha}=\mathbf{\kappa}R\mathbf{\kappa}^{H}$, where $\alpha$ is the fractional order, $0<\alpha\leq 1$, $\ell=0,1,\cdots,N-1$ [15]. Note that $\mathbf{\kappa}=\begin{bmatrix}\kappa_{0},&\kappa_{1},&\cdots,&\kappa_{N-1}\end{bmatrix}={\chi}^{\alpha}$, and $R=\text{diag}({\begin{bmatrix}r_{0},&r_{1},&\cdots,&r_{N-1}\end{bmatrix}})=\mathbf{\Lambda}^{\alpha}$, so that $r_{\ell}=\lambda_{\ell}^{\alpha}$. In the follow-up part of this paper, computing the $\alpha$ power of a matrix always uses matrix power function.

Cartesian product graph is a type of graph multiplication [19]. Consider two graphs $\mathcal{G}_{1}=\{\mathcal{V}_{1},\mathcal{E}_{1},W_{1}\}$ and $\mathcal{G}_{2}=\{\mathcal{V}_{2},\mathcal{E}_{2},W_{2}\}$. The graphs $\mathcal{G}_{1}$, $\mathcal{G}_{2}$ are factor graphs of the Cartesian product $\mathcal{G}_{1}\square\mathcal{G}_{2}$. $\mathcal{G}_{1}\square\mathcal{G}_{2}$ to be the graph with vertex set $\mathcal{V}_{1}\times\mathcal{V}_{2}$ and $\mathcal{V}_{1}=\{0,\cdots,N_{1}-1\},\mathcal{V}_{2}=\{0,\cdots,N_{2}-1\}$.

The adjacency matrix $W_{1}\oplus W_{2}$ and Laplacian matrix $\mathcal{L}_{1}\oplus\mathcal{L}_{2}$ of $\mathcal{G}_{1}\square\mathcal{G}_{2}$ can be expressed by those of its factor graphs.

where $I_{n}$ is the identity matrix of size $n$ [20].

We give an example of Cartesian product graph using in graph signal processing. In Fig. 1, the sensor network measurements are decomposed as the Cartesian product of sensor network and time series.

Given a natural number $m$, consider $m$ graphs $\mathcal{G}_{i}=\{\mathcal{V}_{i},\mathcal{E}_{i},W_{i}\}$ with vertex set $\mathcal{V}_{i}$ and $\mathcal{V}_{i}=\{0,\cdots,N_{i}-1\}$, $i={1,2,\dots,m}$. $\mathcal{L}_{i}$ is the Laplacian matrix of $\mathcal{G}_{i}$ and its eigendecomposition is $\mathcal{L}_{i}=\mathbf{\chi}_{i}\mathbf{\Lambda}_{i}\mathbf{\chi}_{i}^{H}$. The corresponding graph fractional Laplacian operator is

where

and

These $m$ graphs form a Cartesian product graph $\mathcal{G}_{1}\square\cdots\square\mathcal{G}_{m}$. Because the Cartesian product graph

we have the following eigendecomposition of the fractional Laplacian operator of $\mathcal{G}_{1}\square\cdots\square\mathcal{G}_{m}$:

Define a signal on a Cartesian product graph as a ”multi-dimensional signal”. Using the eigenvalues and eigenfunctions of $\mathcal{L}_{\alpha}^{(1)}\oplus\cdots\oplus\mathcal{L}_{\alpha}^{(m)}$ in (7), we propose the Laplacian-based multi-dimensional graph fractional Fourier transform (L-MGFRFT).

In addition to Laplacian-based method, there is another important method related to adjacency matrix in graph signal processing. Using the same Cartesian product graph as in Section III-A, the eigendecomposition of the adjacency operator $W_{i}$ of graph $\mathcal{G}_{i}$ is $W_{i}=\mathbf{V_{i}J_{W_{i}}V_{i}^{-1}}$. The eigendecomposition of adjacency matrix $W_{1}\oplus\cdots\oplus W_{m}$ is

Using the above eigendecomposition, we define adjacency-based multi-dimensional graph fractional Fourier transform (A-MGFRFT).

Though the spectrum obtained by these two MGFRFTs is usually different for the same graph signal $f$, the process of signal analysis is similar. Therefore, we mainly focus the Laplacian method in this paper. As for the adjacency method, we only give the definition.

For a signal on Cartesian product graph, the proposed MGFRFTs provide the following advantages over the traditional GFRFT and SGFRFT. We use the two-dimensional transform based on Laplacian matrix as an example to illustrate how the advantages are reflected in the graph signal processing.

As the spectrum of the multi-dimensional graph signal obtained by 1-D transforms is often multi-valued at a specific frequency and the GFRFT and SGFRFT can only show 1-d spectrum. These two traditional methods are not suitable for multi-dimensional graph signals. In Fig 2, with $\alpha=0.9$, we visually display the shortcoming of the SGFRFT and the advantage of L-MGFRFT. Fig 2(a) is a random 2-D graph signal on the grid graph. In Fig 2(b), we see that at certain frequencies, the spectrum is double-valued. We use red line to give an example of double-valued spectrum. In Fig 2(c), all the spectrum are single-valued, and we use the same red color to show that the double-valued spectrum in Fig 2(b) can be identified and separated by our new transform. MGFRFT can rearrange the 1-D spectrum obtained by the SGFRFT into the m-D frequency domain, and provide the m-D spectrum of the signal. Therefore, MGFRFT can solve the multi-valuedness of the spectral functions.

Another advantage that can not be ignored is time consumption. The Cartesian product graph can represent multi-domain data effectively [19]. Whenever the underlying graph can be decomposed into two or more factor graphs with fewer nodes, the computational cost of these operations can be reduced significantly. Considering a Cartesian product graph $\mathcal{G}_{1}\square\mathcal{G}_{2}$, the MGFRFT costs $O(N_{1}^{2}N_{2}+N_{1}N_{2}^{2})$ time, whereas the traditional SGFRFT costs $O(N_{1}^{2}N_{2}^{2})$ on the same graph. When we use factor graphs $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ instead of the original graph to calculate the eigendecomposition of the graph fractional Laplacian, it also takes less time.