# Fractional Spectral Graph Wavelets and Their Applications

Authors: Jiasong Wu; Fuzhi Wu; Qihan Yang; Yan Zhang; Xilin Liu; Youyong Kong; Lotfi Senhadji; Huazhong Shu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

One of the key challenges in the area of signal processing on graphs is to design transforms and dictionary methods to identify and exploit structure in signals on weighted graphs. In this paper, we first generalize graph Fourier transform (GFT) to spectral graph fractional Fourier transform (SGFRFT), which is then used to define a novel transform named spectral graph fractional wavelet transform (SGFRWT), which is a generalized and extended version of spectral graph wavelet transform (SGWT). A fast algorithm for SGFRWT is also derived and implemented based on Fourier series approximation. Some potential applications of SGFRWT are also presented.


---

## Body

## 1. Introduction

In traditional signal processing, the most commonly used tools are transforms, among which Fourier transform and wavelet transform play key roles [1]. Fourier transform and wavelet transform were generalized and extended in many contexts in recent years.On the one hand, Fourier transform and wavelet transform were extended to fractional domain, obtaining fractional Fourier transform (FRFT) [2–23] and fractional wavelet transform (FRWT) [24–30]. From a mathematical viewpoint, the FRFT can be seen as a parametric Fourier transform [7], whose fractional order θ is a free parameter which offers more flexibility and generalization properties compared to the classical Fourier transform. From a signal processing point of view, the FRFT can be interpreted as a rotation in the time-frequency plane, i.e., the unified time-frequency transform. With the order θ increasing from 0 to 1, the FRFT can show the characteristics of the signal changing from the time domain to the frequency domain [8]. There are roughly three main research directions for investigating FRFT: firstly, the application of FRFT to deal with many signal processing problems [9], for example, filtering, compression, image encryption, digital watermarking, pattern recognition, edge detection, antennas, radar and sonar, and communication; secondly, the discretization algorithms of the FRFT [10–17]; and lastly, the extension of the fractional idea of FRFT to other transforms, for example, fractional cosine, sine and Hartley transforms [18–21], fractional Krawtchouk transform [22], and short-time FRFT [23]. By cascading of the FRFT and the ordinary wavelet transform, Mendlovic et al. [24] first proposed FRWT. Recently, by introducing a new structure of the fractional convolution [25] associated with the FRFT, Shi et al. [26] proposed a simplified definition of the FRWT which analyzes the signal in time-frequency-FRFD domain, where FRFD denotes fractional Fourier domain. The definition of FRWT in [26] was further improved by Prasad et al. [27], who analyzed the signal only in time-FRFD domain. More recently, Dai et al. [28] presented a new FRWT which displays the time and FRFD-frequency information jointly in the time-FRFD-frequency plane. Srivastava et al. [29] proposed a certain family of fractional wavelet transformations and Shi et al. [30] proposed a novel fractional wavelet packet transform. In general, compared to traditional transforms, fractional transforms may lead to (1) better signal filtering results due to the rotation of the time–frequency plane [9]; (2) better image compression ratios [31], image recognition results [32], and image segmentation results [33] due to the flexible choices of the fractional orders; and (3) better image encryption [34] and image watermarking [35] performances since the fractional order can be used as an additional secret key.On the other hand, Fourier transform and wavelet transform were extended to graph domain, obtaining graph Fourier transform (GFT) [36–43] and graph wavelet transform (GWT) [44–49] to handle signal defined on the vertices of weighted graphs. Two basic approaches to signal processing on graphs have been considered: the first is rooted in the spectral graph theory [50] and builds upon the graph Laplacian matrix [36]. Although spectral decomposition of generalized graph Laplacian with negative edges has been considered for the construction of graph frequency domain [51, 52], in this paper, we limit this approach to undirected graphs with real and nonnegative edge weights for the sake of clarity. The second approach, discrete signal processing on graphs [40, 41], is rooted in the algebraic signal processing theory [53, 54] and builds on the graph shift operator. The latter works as the elementary operator that generates all linear shift-invariant filters for signals with a given structure. In particular, the graph Fourier transform in this framework expands a graph signal into a basis of eigenvectors of the adjacency matrix, and the corresponding spectrum is then given by the associated eigenvalues. Besides graph-based transforms [36–49], recent research works on graph also include, among others, sampling and interpolation on graphs [55, 56], graph signal recovery [57–60], semisupervised classification on graphs [61, 62], graph dictionary learning [63, 64], and graph convolutional neural networks [65–72]. Please refer to [73] for more references on graph signal processing.To the authors’ knowledge, there are only few research works done for discrete signal processing on fractional graph domain, which is a combination of fractional transform domain and graph transform domain. Wang et al. [74, 75] proposed a definition of fractional Fourier transform on graphs named graph fractional Fourier transform (GFRFT), which is based on algebraic signal processing theory [53, 54]. However, similar to Fourier transform, GFRFT is a global transform and does not provide useful localization properties in fractional graph domain. Furthermore, GFRFT does not allow multiresolution analysis of graph signals. In this paper, based on spectral graph theory, we first propose a new spectral graph fractional Fourier transform (SGFRFT), which is then used to define a new spectral graph fractional wavelet transform (SGFRWT), which can be seen as an extended version of spectral graph wavelet transform (SGWT) [44].The remainder of the paper is organized as follows. Section2 recalls the main foundations of fractional wavelet transform, spectral graph theory, and spectral graph wavelet transform (SGWT). The spectral graph fractional Fourier transform (SGFRFT) and the spectral graph fractional wavelet transform (SGFRWT) are defined in Section 3. Section 4 is dedicated to the Fourier series approximation-based fast algorithm for forward and inverse SGFRWT. Several applications of SGFRWT for addressing different problems are shown in Section 5. Section 6 concludes the paper.


## 2. Preliminary

In the following, we first recall the forward and inverse fractional Fourier transform (FRFT) [2–5] and then the forward and inverse fractional wavelet transform (FRWT) [24, 26–28] and also show how scaling operator may be expressed in the FRFT domain. Table 1 summarizes the definitions of various transforms for classical signal processing and also those for graph signal processing.Table 1
The definitions of various transforms for classical signal processing and for graph signal processing.
Classical signal processingFourier transformFractional Fourier transformWavelet transformFractional wavelet transformf^u=f,e2πiux=∫−∞+∞fxe−2πiuxdx Discrete form of Fourier matrix: FN=VNDNVNT=VNdiag1,e−j,…,e−jN−1VNT where diag(.) denotes a diagonal matrix formed from its vector argument.f^θu=f,Kθ∗=∫−∞+∞fxKθx,udxKθx,u=∑k=0∞exp−jθkξkuξkk where ξkk is the kth-order normalized Hermite function. Discrete form of fractional Fourier matrix: FNθ=VNDNθVNT=VNdiag1,e−jθ,…,e−jN−1θVNT.Wfs,a=f,ψs,a=∫−∞∞fxψs,a∗xdx with ψs,ax=1/sψx−a/sWfθs,a=f,ψθ,s,a=∫−∞∞fxψθ,s,a∗xdxψθ,s,ax=e−j/2x2−a2x−a/s2cotθψs,ax with ψs,ax=1/sψx−a/s And è is the fractional order.Graph signal processingAlgebraic signal processing (ASP) [40, 41]Spectral graph theory [53, 54]Graph Fourier transformGraph fractional Fourier transformSpectral graph Fourier transformSpectral graph fractional Fourier transformSpectral graph wavelet transformSpectral graph fractional wavelet transformf^′ℓ=f,χℓ′=∑n=1Nfnχℓ′n∗,ℓ=0,1,…,N−1, where χ′=v−1=χ0′1…χN−1′1⋮⋱⋮χ0′N…χN−1′N is obtained by the Jordan decomposition of the adjacency matrix W as follows: W=VJAV−1.f^θ′ℓ=f,γℓ′=∑n=1Nfnγℓ′n∗,ℓ=0,1,…,N−1, where γ′=χ′θ=γ0′1…γN−1′1⋮⋱⋮γ0′N…γN−1′N where è is the fractional order.f^′ℓ=f,χℓ=∑n=1Nfnχℓ∗n,ℓ=0,1,…,N−1, where χ=χ01⋯χN−11⋮⋱⋮χ0N⋯χN−1N is obtained by the eigenvalue decomposition of the graph Laplacian matrix L as follows: L=D−W=χΛχH, where D is the diagonal degree matrix and W is the adjacency matrix.f^θℓ=f,γℓ=∑n=1Nfnγℓ∗n,ℓ=0,1,…,N−1 where γ=χθ=γ01…γN−11⋮⋱⋮γ0N…γN−1N where è is the fractional order.Wfs,n=Tgsfn=∑ℓN−1gsλℓf^ℓχℓn,n=1,…,N, where Tgs=gsL and L is the graph Laplacian matrix.Wfθ,s,n=Tgsfn=f,ψθ,s,n=∑m=1N−1fmψθ,s,n∗m,n=1,…,N, where ψθ,s,nm=∑ℓN−1gsλℓθγℓmγℓ∗n,m=1,…,N,Tgθs=gsLθ, and Lè is the graph fractional Laplacian matrixLθ=γΛθγH


### 2.1. Fractional Fourier Transform (FRFT)

Theθ-order forward FRFT [2–5] is the decomposition of a function f according to the fractional Fourier kernel, i.e.,(1)f^θu=f,Kθ∗=∫−∞+∞fxKθx,udx,where(2)Kθx,u=Aθexpj/2x2+u2cotθ−jxucscθ,θ≠nπ,δx−u,θ=2nπ,δx+u,θ=2n+1π,(3)Aθ=1−jcotθ2π,where θ indicates the rotation angle of the transform and δx represents the Dirac distribution.The inverse FRFT is given by [2–5](4)fx=f^θ,Kθ=∫−∞+∞f^θuKθ∗x,udu.The kernel in equation (2) can be obtained by its spectral expansion [5]:(5)Kθx,u=∑k=0∞exp−jθkξkuξkx.ξkx in equation (5) is the kth-order normalized Hermite function [11, 12], which is the eigenfunction of the Fourier transform. From (5), we can see that FRFT is a generalized version of the Fourier transform, since they share the same eigenfunction ξkx and the eigenvalues of the FRFT are the θth root of the eigenvalues of the Fourier transform [2]. When the rotation angle θ = π/2, the FRFT defaults to Fourier transform.The discrete form of equation (5) can be expressed as follows [11, 12]:(6)FNθ=VNDNθVNT=VNdiag1,e−jθ,…,e−jN−1θVNT,where diag(.) denotes a diagonal matrix formed from its vector argument. FNθ denotes the θ-order forward FRFT matrix of size N×N. VN=v0v1⋯vN−1, vk is the kth-order DFT Hermite eigenvector. Note that FNθ becomes identity matrix when θ = 0 and Fourier matrix when θ = π/2.


### 2.2. Fractional Wavelet Transform (FRWT)

There are several definitions for fractional wavelet transform (FRWT) [24, 26–28]. In this part, we choose the definition in [28] since it displays the signal in the joint time-FRFD-frequency plane.Theθ-order forward FRWT is defined as [28](7)Wfθs,a=f,ψθ,s,a=∫−∞∞fxψθ,s,a∗xdx,where(8)ψθ,s,ax=e−j/2x2−a2−x−a/s2cotθψs,ax,with ψs,ax=1/sψx−a/s.The unitarity property of the FRFT applied to (7) leads to an equivalent form of FRWT:(9)Wfθs,a=Tθsfa=2π1−jcotθ∫−∞∞ej/2s2u2cotθf^θuψ^θ∗suKθ∗u,adu,where f^θ stands for the θ-order FRFT of f. Here also, as for the classical CWT [1], the scaling is operated in the transformed domain “u” and not directly in the time domain.The inverse of the FRWT is given by [28](10)fx=12πsinθCθ,ψ∫−∞∞∫−∞∞Wfθs,aψθ,s,axdsdas,when the following admissibility condition is satisfied [28]:(11)∫0∞ψ^θs2sds=Cθ,ψ<∞.


### 2.3. Spectral Graph Theory and Spectral Graph Wavelet Transform

In this section, we briefly review the spectral graph theory and also the spectral graph wavelet transform [44].


#### 2.3.1. Spectral Graph Theory

We consider an undirected, connected, weighted graphG=V,ℰ,W, composed of a finite set of vertices V (with CardV=N), a set of edges ℰ, and an adjacency symmetric and positive-valued matrix W. A real-valued signal f defined on the vertices V of the graph G is an N×1 vector where each entry is the value fn assigned to the vertex n. The (nonnormalized) graph Laplacian operator is the matrix defined by L=D−W∈ℝN×N, where D is the diagonal degree matrix defined by dm,m=∑nwm,n. dm,m is the degree of vertex m.As the matrixL is real and symmetric, then it is diagonalizable and its eigenvectors χ0,χ1,…,χN−1, sorted according to the ascending order of the corresponding eigenvalues 0=λ0<λ1≤λ2≤⋯≤λN−1, form an orthonormal basis. Therefore, with the unitary column matrix:(12)χ=χ0,χ1,…,χN−1,and the diagonal matrix Λ=diagλ0,λ1,…,λN−1, we have(13)L=χΛχH,where the superscript H denotes the Hermitian transpose operation. The graph Fourier transform (GFT) of the signal f is then the sequence provided by the scalar products [36]:(14)f^ℓ=f,χℓ=∑n=1Nfnχℓ∗n,ℓ=0,1,…,N−1,and f can be recovered (inverse GFT) by means of the reconstruction formula:(15)fn=f^,χℓ∗=∑ℓ=0N−1f^ℓχℓn,n=1,…,N.Using vectors and matrices notations, equations (14) and (15) become(16)f^=f^0f^1⋯f^N−1T=χHf,f=f1f2⋯fNT=χf^.The graph Fourier transform obeys the Parseval theorem; that is, for any signalsf and h defined on the graph G, we have(17)f,h=f^,h^.


#### 2.3.2. Spectral Graph Wavelet Transform (SGWT)

The spectral graph wavelet transform (SGWT) of the signalf with the kernel g is defined by [44](18)Wfs,n=Tgsfn=∑ℓ=0N−1gsλℓf^ℓχℓn,n=1,…,N,where(19)Tgs=gsL,and the kernel g is continuous positive-valued function defined on ℝ+ satisfying(20)g0=limx⟶+∞gx=0∫0+∞gxx2dx=Cg∈ℝ+.Using equation (14), the SGWT becomes(21)Wfs,n=Tgsfn=∑m=1Nfmψs,n∗m=f,ψs,n,n=1,…,N,with(22)ψs,nm=∑ℓ=0N−1gsλℓχℓmχℓ∗n,m=1,…,N.The signalf can be recovered up to its mean value using the inverse formula [44]:(23)fm−f,χ0χ0m=1Cg∑n=1N∫0∞Wfs,nψs,nmdss,m=1,…,N.


## 2.1. Fractional Fourier Transform (FRFT)

Theθ-order forward FRFT [2–5] is the decomposition of a function f according to the fractional Fourier kernel, i.e.,(1)f^θu=f,Kθ∗=∫−∞+∞fxKθx,udx,where(2)Kθx,u=Aθexpj/2x2+u2cotθ−jxucscθ,θ≠nπ,δx−u,θ=2nπ,δx+u,θ=2n+1π,(3)Aθ=1−jcotθ2π,where θ indicates the rotation angle of the transform and δx represents the Dirac distribution.The inverse FRFT is given by [2–5](4)fx=f^θ,Kθ=∫−∞+∞f^θuKθ∗x,udu.The kernel in equation (2) can be obtained by its spectral expansion [5]:(5)Kθx,u=∑k=0∞exp−jθkξkuξkx.ξkx in equation (5) is the kth-order normalized Hermite function [11, 12], which is the eigenfunction of the Fourier transform. From (5), we can see that FRFT is a generalized version of the Fourier transform, since they share the same eigenfunction ξkx and the eigenvalues of the FRFT are the θth root of the eigenvalues of the Fourier transform [2]. When the rotation angle θ = π/2, the FRFT defaults to Fourier transform.The discrete form of equation (5) can be expressed as follows [11, 12]:(6)FNθ=VNDNθVNT=VNdiag1,e−jθ,…,e−jN−1θVNT,where diag(.) denotes a diagonal matrix formed from its vector argument. FNθ denotes the θ-order forward FRFT matrix of size N×N. VN=v0v1⋯vN−1, vk is the kth-order DFT Hermite eigenvector. Note that FNθ becomes identity matrix when θ = 0 and Fourier matrix when θ = π/2.


## 2.2. Fractional Wavelet Transform (FRWT)

There are several definitions for fractional wavelet transform (FRWT) [24, 26–28]. In this part, we choose the definition in [28] since it displays the signal in the joint time-FRFD-frequency plane.Theθ-order forward FRWT is defined as [28](7)Wfθs,a=f,ψθ,s,a=∫−∞∞fxψθ,s,a∗xdx,where(8)ψθ,s,ax=e−j/2x2−a2−x−a/s2cotθψs,ax,with ψs,ax=1/sψx−a/s.The unitarity property of the FRFT applied to (7) leads to an equivalent form of FRWT:(9)Wfθs,a=Tθsfa=2π1−jcotθ∫−∞∞ej/2s2u2cotθf^θuψ^θ∗suKθ∗u,adu,where f^θ stands for the θ-order FRFT of f. Here also, as for the classical CWT [1], the scaling is operated in the transformed domain “u” and not directly in the time domain.The inverse of the FRWT is given by [28](10)fx=12πsinθCθ,ψ∫−∞∞∫−∞∞Wfθs,aψθ,s,axdsdas,when the following admissibility condition is satisfied [28]:(11)∫0∞ψ^θs2sds=Cθ,ψ<∞.


## 2.3. Spectral Graph Theory and Spectral Graph Wavelet Transform

In this section, we briefly review the spectral graph theory and also the spectral graph wavelet transform [44].


### 2.3.1. Spectral Graph Theory

We consider an undirected, connected, weighted graphG=V,ℰ,W, composed of a finite set of vertices V (with CardV=N), a set of edges ℰ, and an adjacency symmetric and positive-valued matrix W. A real-valued signal f defined on the vertices V of the graph G is an N×1 vector where each entry is the value fn assigned to the vertex n. The (nonnormalized) graph Laplacian operator is the matrix defined by L=D−W∈ℝN×N, where D is the diagonal degree matrix defined by dm,m=∑nwm,n. dm,m is the degree of vertex m.As the matrixL is real and symmetric, then it is diagonalizable and its eigenvectors χ0,χ1,…,χN−1, sorted according to the ascending order of the corresponding eigenvalues 0=λ0<λ1≤λ2≤⋯≤λN−1, form an orthonormal basis. Therefore, with the unitary column matrix:(12)χ=χ0,χ1,…,χN−1,and the diagonal matrix Λ=diagλ0,λ1,…,λN−1, we have(13)L=χΛχH,where the superscript H denotes the Hermitian transpose operation. The graph Fourier transform (GFT) of the signal f is then the sequence provided by the scalar products [36]:(14)f^ℓ=f,χℓ=∑n=1Nfnχℓ∗n,ℓ=0,1,…,N−1,and f can be recovered (inverse GFT) by means of the reconstruction formula:(15)fn=f^,χℓ∗=∑ℓ=0N−1f^ℓχℓn,n=1,…,N.Using vectors and matrices notations, equations (14) and (15) become(16)f^=f^0f^1⋯f^N−1T=χHf,f=f1f2⋯fNT=χf^.The graph Fourier transform obeys the Parseval theorem; that is, for any signalsf and h defined on the graph G, we have(17)f,h=f^,h^.


### 2.3.2. Spectral Graph Wavelet Transform (SGWT)

The spectral graph wavelet transform (SGWT) of the signalf with the kernel g is defined by [44](18)Wfs,n=Tgsfn=∑ℓ=0N−1gsλℓf^ℓχℓn,n=1,…,N,where(19)Tgs=gsL,and the kernel g is continuous positive-valued function defined on ℝ+ satisfying(20)g0=limx⟶+∞gx=0∫0+∞gxx2dx=Cg∈ℝ+.Using equation (14), the SGWT becomes(21)Wfs,n=Tgsfn=∑m=1Nfmψs,n∗m=f,ψs,n,n=1,…,N,with(22)ψs,nm=∑ℓ=0N−1gsλℓχℓmχℓ∗n,m=1,…,N.The signalf can be recovered up to its mean value using the inverse formula [44]:(23)fm−f,χ0χ0m=1Cg∑n=1N∫0∞Wfs,nψs,nmdss,m=1,…,N.


## 2.3.1. Spectral Graph Theory

We consider an undirected, connected, weighted graphG=V,ℰ,W, composed of a finite set of vertices V (with CardV=N), a set of edges ℰ, and an adjacency symmetric and positive-valued matrix W. A real-valued signal f defined on the vertices V of the graph G is an N×1 vector where each entry is the value fn assigned to the vertex n. The (nonnormalized) graph Laplacian operator is the matrix defined by L=D−W∈ℝN×N, where D is the diagonal degree matrix defined by dm,m=∑nwm,n. dm,m is the degree of vertex m.As the matrixL is real and symmetric, then it is diagonalizable and its eigenvectors χ0,χ1,…,χN−1, sorted according to the ascending order of the corresponding eigenvalues 0=λ0<λ1≤λ2≤⋯≤λN−1, form an orthonormal basis. Therefore, with the unitary column matrix:(12)χ=χ0,χ1,…,χN−1,and the diagonal matrix Λ=diagλ0,λ1,…,λN−1, we have(13)L=χΛχH,where the superscript H denotes the Hermitian transpose operation. The graph Fourier transform (GFT) of the signal f is then the sequence provided by the scalar products [36]:(14)f^ℓ=f,χℓ=∑n=1Nfnχℓ∗n,ℓ=0,1,…,N−1,and f can be recovered (inverse GFT) by means of the reconstruction formula:(15)fn=f^,χℓ∗=∑ℓ=0N−1f^ℓχℓn,n=1,…,N.Using vectors and matrices notations, equations (14) and (15) become(16)f^=f^0f^1⋯f^N−1T=χHf,f=f1f2⋯fNT=χf^.The graph Fourier transform obeys the Parseval theorem; that is, for any signalsf and h defined on the graph G, we have(17)f,h=f^,h^.


## 2.3.2. Spectral Graph Wavelet Transform (SGWT)

The spectral graph wavelet transform (SGWT) of the signalf with the kernel g is defined by [44](18)Wfs,n=Tgsfn=∑ℓ=0N−1gsλℓf^ℓχℓn,n=1,…,N,where(19)Tgs=gsL,and the kernel g is continuous positive-valued function defined on ℝ+ satisfying(20)g0=limx⟶+∞gx=0∫0+∞gxx2dx=Cg∈ℝ+.Using equation (14), the SGWT becomes(21)Wfs,n=Tgsfn=∑m=1Nfmψs,n∗m=f,ψs,n,n=1,…,N,with(22)ψs,nm=∑ℓ=0N−1gsλℓχℓmχℓ∗n,m=1,…,N.The signalf can be recovered up to its mean value using the inverse formula [44]:(23)fm−f,χ0χ0m=1Cg∑n=1N∫0∞Wfs,nψs,nmdss,m=1,…,N.


## 3. Spectral Graph Fractional Transforms

We first propose a novel spectral graph fractional Fourier transform (SGFRFT) in Section3.1 and then give the definition of spectral graph fractional wavelet transform (SGFRWT) in Section 3.2.


### 3.1. Spectral Graph Fractional Fourier Transform

Similar to (13), we define the graph fractional Laplacian operator Lθ as follows:(24)Lθ=γRγH,where 0 < θ ≤ 1 and γ is the power matrix given by(25)γ=γ0,γ1,…,γN−1=χθ,with χ being the unitary (i.e., inverse graph Fourier transform matrix) shown in (12). Note that as χ is unitary, then γ=χθ is also unitary. And(26)R=diagr0,r1,…,rN−1=Λθ,that is,(27)rℓ=λℓθ,ℓ=0,1,…,N−1.Consideringλℓ∈0,λN−1, and from (27), we can easily get rℓ∈0,rN−1. The reason why we choose Lθ as the definition of graph fractional Laplacian operator will be discussed in Section 3.2.The forward spectral graph fractional Fourier transform (SGFRFT) of any signalf defined on the vertices V of the graph G is defined by(28)f^θℓ≔f,χℓ=∑n=1Nfnγℓ∗n,ℓ=0,1,…,N−1,or by the following matrix form:(29)f^θ=f^θ0f^θ1⋯f^θN−1T=γHf.Forθ = 1, the proposed SGFRFT in (29) is no more than the GFT in (18) defined by Shuman et al. [36]. For other values of θ, we can compute γ=χθ by using Schur–Padé algorithm [76, 77] which is found to be superior in accuracy and stability to several alternatives, including eigendecomposition method and also the approaches based on the formula χθ=eθlogχ.The inverse SGFRFT is given by(30)fn=f^θ,γℓ∗=∑ℓ=0N−1f^θℓγℓn,n=1,…,N,or by the following matrix form:(31)f=f1f2⋯fNT=γf^θ.The graph fractional Fourier transform obeys the Parseval theorem; that is, for any signalsf and h defined on the graph G, we have(32)f,h=f^θ,h^θ.Note that the forward and inverse SGFRFTs defined here are different from the forward and inverse graph fractional Fourier transforms (GFRFTs) [74, 75], which are, respectively, given by(33)f^θ′=f^θ′0f^θ′1⋯f^θ′N−1T=γ′f,(34)f=f1f2⋯fNT=γ′−1f^θ′,where(35)σ′=χ′θ,and χ′=V−1 is obtained by the Jordan decomposition of the adjacency matrix W as follows [74, 75]:(36)W=VJWV−1,where V is a matrix composed of eigenvector and JW is a block-diagonal matrix. For more details, please refer to Appendix A of [74].From (13), (29), (31), and (33)–(36), we can see that the differences are that the proposed SGFRFTs are based on the decomposition of the graph Laplacian matrix L, while the GFRFTs are based on the decomposition of the adjacency matrix W.


### 3.2. Spectral Graph Fractional Wavelet Transform (SGFRWT)

Similar to (21), we can define the spectral graph fractional wavelet transform (SGFRWT) operator Tgθs as follows:(37)Wfθ,s,n=Tgθsfn=∑m=1Nfmψθ,s,n∗m=f,ψθ,s,n,n=1,…,N,where(38)Tgθs=gsLθ,(39)ψθ,s,nm=∑l=0N−1gsλℓθγℓmγℓ∗n,m=1,…N.Why we chooseLθ in (24) as the definition of graph fractional Laplacian operator and choose ψθ,s,nm in (39) as the basis of SGFRWT? There are two reasons. (1) We want to define the basis of SGFRWT ψθ,s,nm based on a new function γℓn instead of the same function χℓn as basis of SGWT ψs,nm in (23). The SGFRWT and SGWT will have different characteristics since they are based on different functions γℓn and χℓn, respectively. (2) We want to define the basis of  SGFRWT ψθ,s,nm which changes directly with λℓθ. Since the parameter θ acts on the eigenvalues of the Fourier matrix in the form of exponents in the spectral expansion of FRFT in (5), similarly, we also want to obtain the form that the parameter θ can directly affect λℓ in the proposed definition of SGFRWT. Two other possible definitions of SGFRWT are also discussed in Appendices A and B, respectively.From (37), we can see that the proposed SGFRWT is a generalization of SGWT in (21) defined by Hammond et al. [44]; that is, when θ = 1, the proposed SGFRWT defaults to the SGWT. The proposed SGFRWT can be seen as a parametric generalization of SGWT [7]. Furthermore, the proposed SGFRWT converts a graph signal into an intermediate domain between vertex and spectral graph wavelet. With the order θ increasing from 0 to 1, the SGFRWT can provide much more domain choices of expressions for a graph signal.The scaling functions are then obtained by(40)ϕθn=Thθδn=hLθδn,and the coefficients by(41)Sθ,fn=ϕθ,n,f.Stable recovery of the original signalf from the SGFRWT coefficients will be assured if the quantity Gr=h2r+∑j=1Jg2sjr, where sj denotes jth scale, is bounded away from zero on the fractional Laplacian Lθ. Moreover, under the same conditions, Lemmas 5.1, 5.2, 5.3, and 5.4 and Theorems 5.5 and 5.6 in [44] are verified by the SGFRWT, whose properties are shown in Appendix C.


## 3.1. Spectral Graph Fractional Fourier Transform

Similar to (13), we define the graph fractional Laplacian operator Lθ as follows:(24)Lθ=γRγH,where 0 < θ ≤ 1 and γ is the power matrix given by(25)γ=γ0,γ1,…,γN−1=χθ,with χ being the unitary (i.e., inverse graph Fourier transform matrix) shown in (12). Note that as χ is unitary, then γ=χθ is also unitary. And(26)R=diagr0,r1,…,rN−1=Λθ,that is,(27)rℓ=λℓθ,ℓ=0,1,…,N−1.Consideringλℓ∈0,λN−1, and from (27), we can easily get rℓ∈0,rN−1. The reason why we choose Lθ as the definition of graph fractional Laplacian operator will be discussed in Section 3.2.The forward spectral graph fractional Fourier transform (SGFRFT) of any signalf defined on the vertices V of the graph G is defined by(28)f^θℓ≔f,χℓ=∑n=1Nfnγℓ∗n,ℓ=0,1,…,N−1,or by the following matrix form:(29)f^θ=f^θ0f^θ1⋯f^θN−1T=γHf.Forθ = 1, the proposed SGFRFT in (29) is no more than the GFT in (18) defined by Shuman et al. [36]. For other values of θ, we can compute γ=χθ by using Schur–Padé algorithm [76, 77] which is found to be superior in accuracy and stability to several alternatives, including eigendecomposition method and also the approaches based on the formula χθ=eθlogχ.The inverse SGFRFT is given by(30)fn=f^θ,γℓ∗=∑ℓ=0N−1f^θℓγℓn,n=1,…,N,or by the following matrix form:(31)f=f1f2⋯fNT=γf^θ.The graph fractional Fourier transform obeys the Parseval theorem; that is, for any signalsf and h defined on the graph G, we have(32)f,h=f^θ,h^θ.Note that the forward and inverse SGFRFTs defined here are different from the forward and inverse graph fractional Fourier transforms (GFRFTs) [74, 75], which are, respectively, given by(33)f^θ′=f^θ′0f^θ′1⋯f^θ′N−1T=γ′f,(34)f=f1f2⋯fNT=γ′−1f^θ′,where(35)σ′=χ′θ,and χ′=V−1 is obtained by the Jordan decomposition of the adjacency matrix W as follows [74, 75]:(36)W=VJWV−1,where V is a matrix composed of eigenvector and JW is a block-diagonal matrix. For more details, please refer to Appendix A of [74].From (13), (29), (31), and (33)–(36), we can see that the differences are that the proposed SGFRFTs are based on the decomposition of the graph Laplacian matrix L, while the GFRFTs are based on the decomposition of the adjacency matrix W.


## 3.2. Spectral Graph Fractional Wavelet Transform (SGFRWT)

Similar to (21), we can define the spectral graph fractional wavelet transform (SGFRWT) operator Tgθs as follows:(37)Wfθ,s,n=Tgθsfn=∑m=1Nfmψθ,s,n∗m=f,ψθ,s,n,n=1,…,N,where(38)Tgθs=gsLθ,(39)ψθ,s,nm=∑l=0N−1gsλℓθγℓmγℓ∗n,m=1,…N.Why we chooseLθ in (24) as the definition of graph fractional Laplacian operator and choose ψθ,s,nm in (39) as the basis of SGFRWT? There are two reasons. (1) We want to define the basis of SGFRWT ψθ,s,nm based on a new function γℓn instead of the same function χℓn as basis of SGWT ψs,nm in (23). The SGFRWT and SGWT will have different characteristics since they are based on different functions γℓn and χℓn, respectively. (2) We want to define the basis of  SGFRWT ψθ,s,nm which changes directly with λℓθ. Since the parameter θ acts on the eigenvalues of the Fourier matrix in the form of exponents in the spectral expansion of FRFT in (5), similarly, we also want to obtain the form that the parameter θ can directly affect λℓ in the proposed definition of SGFRWT. Two other possible definitions of SGFRWT are also discussed in Appendices A and B, respectively.From (37), we can see that the proposed SGFRWT is a generalization of SGWT in (21) defined by Hammond et al. [44]; that is, when θ = 1, the proposed SGFRWT defaults to the SGWT. The proposed SGFRWT can be seen as a parametric generalization of SGWT [7]. Furthermore, the proposed SGFRWT converts a graph signal into an intermediate domain between vertex and spectral graph wavelet. With the order θ increasing from 0 to 1, the SGFRWT can provide much more domain choices of expressions for a graph signal.The scaling functions are then obtained by(40)ϕθn=Thθδn=hLθδn,and the coefficients by(41)Sθ,fn=ϕθ,n,f.Stable recovery of the original signalf from the SGFRWT coefficients will be assured if the quantity Gr=h2r+∑j=1Jg2sjr, where sj denotes jth scale, is bounded away from zero on the fractional Laplacian Lθ. Moreover, under the same conditions, Lemmas 5.1, 5.2, 5.3, and 5.4 and Theorems 5.5 and 5.6 in [44] are verified by the SGFRWT, whose properties are shown in Appendix C.


## 4. Fourier Series Approximation and Fast SGFRWT

If we compute the SGFRWT by using equation (37) directly, we have to compute the entire set of eigenvectors and eigenvalues of Lθ shown in (24). Both the computational complexity and the memory consumption become unacceptable when the data is larger than hundreds of thousands or millions of dimensions. Therefore, in this section, we propose a fast algorithm for computing the SGFRWT based on approximating the scaled generating kernels gθ by low-order Fourier series. It should be noted that the proposed fast SGFRWT algorithm is an extension of the fast SGWT algorithm from real domain to complex domain. The proposed fast SGFRWT algorithm is different from the fast graph Fourier transform proposed by Magoarou et al. [39], who use the modified Jacobi eigenvalue algorithm for approximating the graph Laplacian matrix. Note that the proposed SGFRWT algorithm can approximate an arbitrary matrix while the algorithm in [39] is only practicable for approximating symmetric matrix.The following lemma shows that the polynomial approximation ofgsx may be taken over a finite range containing the spectrum of Lθ.Lemma 1.
Letrmax ≥ rN−1 be any upper bound on the fractional spectrum of Lθ. For fixed s > 0, let px be a polynomial approximant of gsx with L∞ error B=supx∈0,rmaxgsx−px. Then the approximate SGFRWT coefficients W˜fθ,s,n=pLθfn satisfy Wfθ,s,n−W˜fθ,s,n≤Bf.The proof of Lemma1 is similar to Lemma 6.1 in [44].In [44], Hammond et al. approximated gsL shown in (19) by truncated Chebyshev expansions. The reason is that gsL is real as the original L shown in (13) is a real matrix. However, the Chebyshev polynomial approximation method is not suitable for our problem of approximating gsLθ shown in (38), because gsLθ may be complex as gsLθ shown in (33) may be a complex matrix. Therefore, in this part, we will use the truncated Fourier series expansion instead of Chebyshev expansions to approximate gsLθ shown in (38).The Fourier series of a general functionfx is given by [78](42)fy=∑k=−∞∞ckexpiky,where(43)ck=12π∫02πfyexp−ikydy=a0,k=0,ak−ikb2,k>0,ak−ikb2,k<0,a0=12π∫02πfy,ak=1π∫02πfycoskydy,bk=1π∫02πfysinkydy.We now assume a fixed set of wavelet scalessn. For each n, approximating gsnx for x∈0,rmax can be done by scaling the domain of exp−iky, y∈0,2π, using the transformation x = yrmax/(2π). Then, gsnx can be written by(44)gsnx=∑k=−∞∞cn,kFkx,x∈0,rmax,with(45)cn,k=12πrmax∫0rmaxgsnxF−kxdx,(46)Fkx=expi2πkxrmax.Note that(47)Fkx=F−kx∗.The above equation is due to the fact that(48)∫0rmaxFkxF−lx1rmaxdx=δkl.For each scalesj, gsjx can be approximated by the truncated Fourier expansion (42) to 2Mj+1 terms; that is,(49)pjx=∑k=−MjMjcn,kFkx,x∈0,rmax.We may choose an appropriateMj in practice to achieve a balance between accuracy and computational complexity. We can also use exactly the same scheme to approximate the scaling function kernel hθ shown in (40) by p0. Then, the approximated SGFRWT wavelet and scaling function coefficients are, respectively, given by(50)W˜fθ,sj,n=∑k=−MjMjcj,kFkLθfn,(51)S˜fθ,n=∑k=−M0M0c0,kFkLθfn,where(52)FkLθ=expi2πkLθrmax.Note that (52) is easily obtained by applying the function Fk(.) in (46) to the matrix Lθ, and we have(53)FkLθ=F−kLθ∗.The efficiency of this algorithm depends on the following recursive formula:(54)FkLθf=F1LθFk−1Lθf,k∈−Mj,Mj.As the signalf∈ℝN, taking equation (53) into consideration, equation (54) can only be computed for k∈1,Mj, and the other k∈−Mj,−1 can be obtained by conjugate operation.The computational complexity of the proposed fast SGFRWT algorithm is analyzed as follows:(1)
The computation ofγ from χ in (25) by using Schur–Padé algorithm [76, 77] needs O(N3) operations.(2)
The computation cost of eachFkLθf in (54) is O(6|E|), where |E| is the number of nonzero edges in the graph, and 6|E| because F1Lθ is a complex matrix and a complex multiplication requires 4 real multiplications and 2 real additions (6 operations). Therefore, the computation of all FkLθf,k=1,2,…,Mj needs O(6Mj|E|) operations.(3)
It requiresO(6N) operations at scale j for each k ≤ Mj in (50) and (51). Therefore, the computation of (50) and (51) needs O6N∑j=0JMj operations.Therefore, the total computational complexity of the fast SGFRWT algorithm isON3+6MjE+6N∑j=0JMj.Implementation of (54) requires memory of size 2N. The total memory requirement for the proposed fast SGFRWT is 2NJ+1+2N.


### 4.1. Fast Computation of Adjoint

Given a fixed set of wavelet scalessjj=1J, and including the scaling functions ϕn, the SGFRWT Wθf=ThθfT,Tgθs1fT,…,TgθsJfTT can be seen as a linear map Wθ:ℝN⟶ℂNJ+1, where ℂ denotes the complex domain. Let W˜θf=p0LθfT,p1LθfT,…,pJLθfTT denote the approximated fractional wavelet transform by using the fast SGFRWT algorithm. In this section, we show that both the adjoint Wθ∗:ℂNJ+1⟶ℝN and the composition Wθ∗Wθ:ℝN⟶ℝN can be computed efficiently by using the Fourier series approximation.For anyη∈ℂNJ+1, we consider η as the concatenation η=η0T,η1T,…,ηJTT with each ηj∈ℂN for 0 ≤ j ≤ J; we have(55)η,WθfNJ+1=η0,Thθf+∑j=1Jηj,TgθsjfN=Thθ∗η0,f+∑j=1JTgθsj∗ηj,fN=Thθ∗η0+∑j=1JTgθsj∗ηj,fN.Consideringη,WθfNJ+1=Wθ∗η,fN, we have(56)Wθ∗η=Thθ∗η0+∑j=1JTgθsj∗ηj.Similar to (50) and (51), the adjoint operator Wθ∗ in (56) can be approximated by(57)W˜θ∗η=∑j=0Jpj∗Lθηj.In the following, we derive a fast algorithm for the computation ofW˜θ∗W˜θ, which is an approximation of the composition W∗W. In general, when computing W˜θ∗W˜θ, we first apply W˜θ and then apply W˜θ∗ by the fast SGFRWT, which needs 2J Fourier series expansions. However, the computational complexity of W˜θ∗W˜θ can further be reduced. Note that(58)W˜θ∗W˜θf=∑j=0Jpj∗LθpjLθf=∑j=0Jpj∗LθpjLθf.In the following, we derive a fast algorithm for the computation ofW˜θ∗W˜θf.Lemma 2.
SetPx=∑j=0Jpj∗xpjx, which has degree M∗=2maxMj. Then, Px can be computed by(59)Px=∑k=−M∗M∗dkFkx,where dk=∑j=0Jdj,k, and dj,k=∑i=−Mj−iMjcj,i∗cj,k+i,−2Mj≤k≤−1∑i=−MjMj−kcj,i∗cj,k+i,0<k≤2Mj.Proof.
(60)pj∗xpjx=∑k=−MjMjcj,kFkx∗∑l=−MjMjcj,lFlx=∑k=−MjMj∑l=−MjMjcj,k∗cj,lFk∗xFlx=∑k=−MjMj∑l=−MjMjcj,k∗cj,lFl−kx,=∑k=−MjMj∑k′+k=−MjMjcj,k∗cj,k′+kFk′x=∑i=−MjMj∑k+i=−MjMjcj,i∗cj,k+iFkx=∑i=−MjMj∑k=−Mj−iMj−icj,i∗cj,k+iFkx,=∑k=−2Mj−1∑i=−Mj−iMjcj,i∗cj,k+iFkx+∑k=02Mj∑i=−MjMj−kcj,i∗cj,k+iFkx=∑k=−M∗M∗dj,kFkx.
Note thatFk∗xFlx=Fl−kx is used in the above derivation.
Therefore,(61)Px=∑j=0Jpj∗xpjx=∑j=0J∑k=−M∗M∗dj,kFkx=∑k=−M∗M∗∑j=0Jdj,kFkx=∑k=−M∗M∗dkFkx.
The proof of Lemma2 is now completed.
Combining (58) and (59), we have(62)W˜θ∗W˜θf=PLθf=∑k=−M∗M∗dkFkLθf.
From (62), we can see that W˜θ∗W˜θf can be computed by a single Fourier series expansion with twice the length, which reduces the computational cost by a factor J comparing to the direct computation of W˜θ∗W˜θf.


### 4.2. Reconstruction by Using the Fast Adjoint Algorithm

In this part, we show the reconstruction of proposed SGFRWT by using the fast adjoint algorithm in Section4.1.The SGFRWT is an overcomplete transform since it maps an input signalf of size N to the N(J + 1) factional wavelets coefficients(63)c=Wθf.The pseudoinverse of the above equation can be obtained by solving the following square matrix equation:(64)Wθ∗Wθf=W∗c.Equation (64) can be solved by the conjugate gradients method [79], whose computation in each step is dominated by applying Wθ∗Wθ to a single vector. What is more, Wθ∗Wθf can be fast approximated by W˜θ∗W˜θf shown in (62). Therefore, we can reconstruct input signal f from c.


## 4.1. Fast Computation of Adjoint

Given a fixed set of wavelet scalessjj=1J, and including the scaling functions ϕn, the SGFRWT Wθf=ThθfT,Tgθs1fT,…,TgθsJfTT can be seen as a linear map Wθ:ℝN⟶ℂNJ+1, where ℂ denotes the complex domain. Let W˜θf=p0LθfT,p1LθfT,…,pJLθfTT denote the approximated fractional wavelet transform by using the fast SGFRWT algorithm. In this section, we show that both the adjoint Wθ∗:ℂNJ+1⟶ℝN and the composition Wθ∗Wθ:ℝN⟶ℝN can be computed efficiently by using the Fourier series approximation.For anyη∈ℂNJ+1, we consider η as the concatenation η=η0T,η1T,…,ηJTT with each ηj∈ℂN for 0 ≤ j ≤ J; we have(55)η,WθfNJ+1=η0,Thθf+∑j=1Jηj,TgθsjfN=Thθ∗η0,f+∑j=1JTgθsj∗ηj,fN=Thθ∗η0+∑j=1JTgθsj∗ηj,fN.Consideringη,WθfNJ+1=Wθ∗η,fN, we have(56)Wθ∗η=Thθ∗η0+∑j=1JTgθsj∗ηj.Similar to (50) and (51), the adjoint operator Wθ∗ in (56) can be approximated by(57)W˜θ∗η=∑j=0Jpj∗Lθηj.In the following, we derive a fast algorithm for the computation ofW˜θ∗W˜θ, which is an approximation of the composition W∗W. In general, when computing W˜θ∗W˜θ, we first apply W˜θ and then apply W˜θ∗ by the fast SGFRWT, which needs 2J Fourier series expansions. However, the computational complexity of W˜θ∗W˜θ can further be reduced. Note that(58)W˜θ∗W˜θf=∑j=0Jpj∗LθpjLθf=∑j=0Jpj∗LθpjLθf.In the following, we derive a fast algorithm for the computation ofW˜θ∗W˜θf.Lemma 2.
SetPx=∑j=0Jpj∗xpjx, which has degree M∗=2maxMj. Then, Px can be computed by(59)Px=∑k=−M∗M∗dkFkx,where dk=∑j=0Jdj,k, and dj,k=∑i=−Mj−iMjcj,i∗cj,k+i,−2Mj≤k≤−1∑i=−MjMj−kcj,i∗cj,k+i,0<k≤2Mj.Proof.
(60)pj∗xpjx=∑k=−MjMjcj,kFkx∗∑l=−MjMjcj,lFlx=∑k=−MjMj∑l=−MjMjcj,k∗cj,lFk∗xFlx=∑k=−MjMj∑l=−MjMjcj,k∗cj,lFl−kx,=∑k=−MjMj∑k′+k=−MjMjcj,k∗cj,k′+kFk′x=∑i=−MjMj∑k+i=−MjMjcj,i∗cj,k+iFkx=∑i=−MjMj∑k=−Mj−iMj−icj,i∗cj,k+iFkx,=∑k=−2Mj−1∑i=−Mj−iMjcj,i∗cj,k+iFkx+∑k=02Mj∑i=−MjMj−kcj,i∗cj,k+iFkx=∑k=−M∗M∗dj,kFkx.
Note thatFk∗xFlx=Fl−kx is used in the above derivation.
Therefore,(61)Px=∑j=0Jpj∗xpjx=∑j=0J∑k=−M∗M∗dj,kFkx=∑k=−M∗M∗∑j=0Jdj,kFkx=∑k=−M∗M∗dkFkx.
The proof of Lemma2 is now completed.
Combining (58) and (59), we have(62)W˜θ∗W˜θf=PLθf=∑k=−M∗M∗dkFkLθf.
From (62), we can see that W˜θ∗W˜θf can be computed by a single Fourier series expansion with twice the length, which reduces the computational cost by a factor J comparing to the direct computation of W˜θ∗W˜θf.


## 4.2. Reconstruction by Using the Fast Adjoint Algorithm

In this part, we show the reconstruction of proposed SGFRWT by using the fast adjoint algorithm in Section4.1.The SGFRWT is an overcomplete transform since it maps an input signalf of size N to the N(J + 1) factional wavelets coefficients(63)c=Wθf.The pseudoinverse of the above equation can be obtained by solving the following square matrix equation:(64)Wθ∗Wθf=W∗c.Equation (64) can be solved by the conjugate gradients method [79], whose computation in each step is dominated by applying Wθ∗Wθ to a single vector. What is more, Wθ∗Wθf can be fast approximated by W˜θ∗W˜θf shown in (62). Therefore, we can reconstruct input signal f from c.


## 5. Application Examples

Similar to [44], in this section, we will show several application examples of the SGFRWT on different real and synthetic datasets by modifying the GSPBOX toolbox [80]. The first and the third experiments are implemented in MATLAB programming language on a PC machine, which sets up Microsoft Windows 7 operating system and has an Intel® Core™ i7-2600 CPU with speed of 3.40 GHz and 16 GB RAM. The second experiment is implemented using PyTorch on a PC machine, which sets up Ubuntu 16.04 operating system and has an Intel® Core™ i7-4790 CPU with speed of 4.00 GHz and 32 GB RAM and has also two NVIDIA GTX1080-Ti GPUs.


### 5.1. SGFRWT Design Details

We should design two kernels in SGFRWT. One is the wavelet kernelgx, and the other is the scaling function h(x).For the wavelet kernel g(x), we choose the same cubic spline in [44] as follows:(65)gx=x1−αxα,forx<x1,sx,forx1≤x≤x2,x2βx−β,forx>x2,where α and β are integers and they are used to determine the decay rate of spline. x1 and x2 are boundary of transitions region. Note that g is normalized such that gx1 = gx2 = 1. The coefficients of the cubic polynomial s(x) are determined by s(x1) = s(x2) = 1, s′x1 = α/x1, and s′x2 = −β/x2. All of the examples in this paper were produced using α = β = 2, x1 = 1, and x2 = 2; in this case, s(x) = −5 + 11x − 6x2 + x3. For the SGFRWT, we can easily substitute x in (65) by Lθ shown in (24) to get gLθ.For the scaling function kernelh(x), we take hx=ρexp−x/0.6λmin4 with ρ=h0.


### 5.2. SGFRWT Application Examples

#### 5.2.1. SGFRWT on Synthetic Graph Data

In the first example, we perform the proposed SGFRWT on “Swiss roll,” which is a dataset whose points are sampled randomly from a two-dimensional (2D) manifold as follows:(66)x⟶t1,t2=t1cost24π,t1,t2sint24π,−1≤t1≤1,π≤t2≤4π.Figure1 shows the Swiss roll data cloud. We take 500 points sampled uniformly on the manifold and then build a weighted graph, whose edge weight is defined as follows:(67)ai,j=exp−xi−xj22σ2.Figure 1
Spectral fractional graph wavelets on Swiss roll data cloud. The figure shows vertex at which SGFRWT is centered; that is, we will apply SGFRWT on the signal value of centered vertex.Note that the definition of the edge weight is a critical issue in graph construction. The most direct way to compute the edge weight is based on a given (dis)similarity measure. In practice, the edge weight is generally defined using different measures for better interpretability. As discussed in [81], Gaussian kernel and its variants (i.e., heat kernel or RBF kernel) are one of the most popular schemes to assign edge weights for a graph. Therefore, we take the Gaussian kernel in (67) to calculate the edge weight to simplify our discussion in this paper. We perform SGFRWT with fractional order θ ∈ [0.1, 1.0] on Swiss roll data cloud with J = 5 wavelet scales, and the results of some fractional orders θ ∈ {0.1, 0.5, 0.8, 1.0} are shown in Figure 2. The last column of Figure 2 shows the results of performing SGWT [44] on Swiss roll, from which we can see that SGWT [44] searches for the optimal expression domain only along the dimension of scale. However, the proposed SGFRWT searches for the optimal expression domain not only along the dimension of scale but also along the dimension of fractional order. That is, compared with SGWT, the proposed SGFRWT can express Swiss roll in higher dimensions, which makes the expression space larger and is therefore more likely to obtain a better expressive domain for the original problem. Just like [31–33], the fractional order θ is a hyperparameter depending on the original problem and you should search for a suitable value of θ. For example, the fractional order θ = 0.4 is an appropriate value for gland segmentation when using fractional wavelet scattering network [33].Figure 2
Spectral fractional graph wavelets on Swiss roll data cloud, with wavelet scaleJ = 5 and fractional order θ ∈ {0.1, 0.5, 0.8, 1.0}. (a) Wavelet scale j = 0, 1, 2 and fractional order θ ∈ {0.1, 0.5, 0.8, 1.0}. Note that j = 0 denotes the scaling function (b) wavelet scale j = 3, 4 and fractional order θ ∈ {0.1, 0.5, 0.8, 1.0}.
(a)(b)As a comparison, we also give the results of the proposed spectral graph fractional Fourier transform (SGFRFT) and graph fractional Fourier transform (GFRFT) proposed in [74, 75] on the “Swiss roll” in Figure 3, respectively. As we can see from Figure 3, the results of the proposed SGFRFT are different from those of GFRFT in [74, 75]. Furthermore, both SGFRFT and GFRFT are global transform and are not easily to be used for local analysis. However, let us see the third column of Figure 2, that is, the results of SGFRWT with J = 5 and fractional order θ = 0.8; the localization is more and more obvious along scale dimension. Comparing the third column of Figure 2 with the third column of Figure 3, we can see that, compared with SGFRFT and GFRFT, the proposed SGFRWT allows localization in fractional graph domain, which may lead to better local analysis in spectral graph domain. The experiment results of Figure 3 verify the local properties of SGFRWT shown in Appendix C (i.e., Lemmas C2–C4 and Theorem C5) to a certain extent.Figure 3
Spectral graph fractional Fourier transform (SGFRFT) and graph fractional Fourier transform (GFRFT) [74, 75] on Swiss roll data with fractional order θ ∈ {0.1, 0.4, 0.7, 1.0}.
(a)(b)


#### 5.2.2. SGFRWT on MNIST Database

In the second example, we will see that the proposed SGFRWT can be used as a data augmentation method in the preprocessing of convolutional neural networks, which require as many input images as possible. Because, as shown in the first example, the proposed SGFRWT allows deriving many images from the original image by considering several fractional orders. In the following, a series of experiments are performed on the MNIST dataset to verify the effectiveness of the proposed SGFRWT as a method of data augmentation.We construct the graph for each image in MNIST dataset. The vertices of the graph are made up of pixels in the image and each pixel is connected with its vertical and horizontal neighbor pixel. The edge weight is calculated by a Gauss kernel weighting function [36] as follows: (68)wi,j=exp−disti,j22τ2,if disti,j≤k,0,otherwise,where wi,j is the weight on the edge connection of the vertex vi and vj, and dist (i, j) represents the distance between pixel i and pixel j.In order to prove the effectiveness of SGWT and SGFRWT, we augment MNIST dataset by the following strategies: (i) The original MNIST database has a training set of 60,000 images and a testing set of 10,000 images, which are used as a control group. (ii) For each image of the MNIST training set, we perform SGWT [44] with J = 5 wavelet scales and generate a total of 360,000 images. The original 10,000 test images are still used as the testing set. (iii) For each image of the MNIST training set, we apply the proposed SGFRWT with J = 5 wavelet scales and fractional order θ ∈ {0.2, 0.4, 0.6, 0.8, 1.0}, generating a total of 1,800,000 training images. The details of the generated four datasets are shown in Table 1. Figure 4 shows all sample images by processing an image of the digit “zero” by SGFRWT with J = 5 wavelet scales and fractional order θ ∈ {0.2, 0.4, 0.6, 0.8, 1.0}.Figure 4
Spectral graph fractional wavelets on an image “zero,” withJ = 5 wavelet scales and fractional order θ ∈ {0.2, 0.4, 0.6, 0.8, 1.0}. (θ, j, θ denotes the fractional order; j denotes the scale.To evaluate the data augmentation performance of the proposed approach, we train and test a simple convolutional neural network, which is shown in Figure5, using the three datasets mentioned above. The CNN model consists of 2 convolutional layers, 2 pooling layers, and a fully connected layer with a 10-way Softmax classifier. The inputs of the CNN are images of size 28 × 28. The first convolutional layer has 32 kernels with size 5 × 5, while the other layer has 64 kernels with size 3 × 3. The Rectified Linear Units (ReLUs) are chosen as the activation function. Every convolutional layer is followed by a nonoverlapping max-pooling with filter of size 2 × 2. Stochastic gradient descent algorithm is employed to optimize the network with a learning rate of 0.001. When the network converges, we evaluate the classification accuracy on the testing set with an average value of 10 times. The last column of Table 2 shows the classification performance comparison of the three different datasets. As we can see from Table 2, if we use traditional data augmentation methods (flipping, rotating, and adding noise), then the recognition rate can achieve 98.41%. When the training dataset of MNIST is augmented by SGWT without traditional data augmentation, the recognition rate can increase to 98.71%. From the last row of Table 2, we can see that our proposed SGFRWT can further improve the accuracy.Figure 5
The convolutional neural network used in our experiment.Table 2
Dataset generation implementation details. Comparison of classification performance of three different datasets with three different augmentation methods on the same CNN network.
DatasetAugmentation details of training setValidation setAccuracy (%)(i)MNIST training set augmented with flipping, rotating, and adding noise.Original MNIST testing set98.41(ii)MNIST training set augmented with SGWTOriginal MNIST testing set98.71(iii)MNIST training set augmented with SGFRWTOriginal MNIST testing set98.86


#### 5.2.3. Face Recognition by Fusing SGFRWT Features

In the third example, the application of SGFRWT to provide features for face recognition is investigated. We use four classical face databases, whose MATLAB formats are provided in [82, 83]. (1) Yale Database [84]. It contains 165 grayscale images (15 individuals, 11 images per individual). (2) AR Database [85]. We use a nonoccluded subset of AR database containing 700 images (50 male subjects and 50 female subjects, 7 images per subject). (3) CMU PIE Face Database [86]. We also use a nonoccluded subset of CMU PIE database which contains 11560 images (68 persons, 170 images per person). (4) ORL Database [87]. It contains 400 grayscale images (40 individuals, 10 images per individual). Note that all the images are resized to 32 × 32 pixels.The experiment is carried out by the following three steps:(1)
For each image of the four face databases, we apply the propoJ=trSb/trSw,sed SGFRWT with wavelet scale J = 10 and fractional order θ ∈ {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0}, obtaining 100 times the images of original datasets.(2)
We then extract the SGFRWT features of three fractional orders which have the highest trace ration [88] as follows:(69)J=trSbtrSw,where tr(.) denotes the trace.Sb and Sw are between-class scatter matrix and the within-class scatter matrix, respectively,(70)Sb=∑i=1cNiA−AiT,Sw=∑i=1cNiAi−xθ,jAi−xθ,jT,where the superscriptT denotes transposition. C denotes the number of classes. A is the mean of Ai and Ai is the mean image of class Xi and Ni is the number of images in class Xi.| X(θ, j)| denotes the modulus of SGFRWT coefficient with the fractional order θ and the wavelet scale j.(3)
The SGFRWT features of three fractional orders are fused by canonical correlation analysis (CCA) [89] to obtain the feature vector, whose dimension is then reduced by principal component analysis (PCA) and Linear Discriminant Analysis (LDA). Finally, we feed the feature vector to the support vector machine (SVM).We conduct experiments on 18 different datasets which are constructed by four classical face databases mentioned above. Each set of datasets is compared with three different methods (baseline, SGWT, and SGFRWT), and we evaluate the classification accuracy on the testing set with an average value of 10 times. The recognition comparison results of the proposed SGFRWT feature building, the SGWT feature, and the baseline (only PCA + LDA + SVM used) on four face databases are shown in Table3, from which we can see that the proposed SGFRWT feature building approach can achieve promising results and perform better than SGWT feature and also the SVM baseline.Table 3
The recognition results of the proposed SGFRWT feature, the SGWT feature, and the baseline on four face databases (Yale, AR, ORL, and CMU PIE). We randomly selected several images per individual as training set and the remaining images as testing set. “i train” means that we randomly choose i images in each class for training. The accuracy is the average results of ten random testing experiments.
DatasetNumber of categoriesConstruction detailsBaseline (SVM) (%)SGWT + SVM (%)The proposed SGFRWT + SVM (%)Yale: 165 grayscale images (15 individuals, 11 images per individual)151 train, 10 test each class91.9399.27100152 train, 9 test each class93.2699.48100153 train, 8 test each class93.4299.86100154 train, 7 test each class94.57100100155 train, 6 test each class95.56100100AR: 700 images (50 male subjects and 50 female subjects, 7 images per subject)1001 train, 6 test each class49.5390.9296.521002 train, 5 test each class70.7893.2498.141003 train, 4 test each class78.5396.5898.4ORL: 400 grayscale images (40 individuals, 10 images per individual)401 train, 9 test each class93.9498.1699.86402 train, 8 test each class9798.599.81403 train, 7 test each class97.7299.2999.89404 train, 6 test each class97.8399.3399.83405 train, 5 test each class9899.35100CMPUPIE: 11560 images (68 persons, 170 images per person)681 train, 169 test each class15.177.981.13685 train, 165 test each class40.989.2290.096810 train, 160 test each class52.4591.1191.956815 train, 155 test each class60.2891.1492.366820 train, 150 test each class64.8191.6792.7


## 5.1. SGFRWT Design Details

We should design two kernels in SGFRWT. One is the wavelet kernelgx, and the other is the scaling function h(x).For the wavelet kernel g(x), we choose the same cubic spline in [44] as follows:(65)gx=x1−αxα,forx<x1,sx,forx1≤x≤x2,x2βx−β,forx>x2,where α and β are integers and they are used to determine the decay rate of spline. x1 and x2 are boundary of transitions region. Note that g is normalized such that gx1 = gx2 = 1. The coefficients of the cubic polynomial s(x) are determined by s(x1) = s(x2) = 1, s′x1 = α/x1, and s′x2 = −β/x2. All of the examples in this paper were produced using α = β = 2, x1 = 1, and x2 = 2; in this case, s(x) = −5 + 11x − 6x2 + x3. For the SGFRWT, we can easily substitute x in (65) by Lθ shown in (24) to get gLθ.For the scaling function kernelh(x), we take hx=ρexp−x/0.6λmin4 with ρ=h0.


## 5.2. SGFRWT Application Examples

### 5.2.1. SGFRWT on Synthetic Graph Data

In the first example, we perform the proposed SGFRWT on “Swiss roll,” which is a dataset whose points are sampled randomly from a two-dimensional (2D) manifold as follows:(66)x⟶t1,t2=t1cost24π,t1,t2sint24π,−1≤t1≤1,π≤t2≤4π.Figure1 shows the Swiss roll data cloud. We take 500 points sampled uniformly on the manifold and then build a weighted graph, whose edge weight is defined as follows:(67)ai,j=exp−xi−xj22σ2.Figure 1
Spectral fractional graph wavelets on Swiss roll data cloud. The figure shows vertex at which SGFRWT is centered; that is, we will apply SGFRWT on the signal value of centered vertex.Note that the definition of the edge weight is a critical issue in graph construction. The most direct way to compute the edge weight is based on a given (dis)similarity measure. In practice, the edge weight is generally defined using different measures for better interpretability. As discussed in [81], Gaussian kernel and its variants (i.e., heat kernel or RBF kernel) are one of the most popular schemes to assign edge weights for a graph. Therefore, we take the Gaussian kernel in (67) to calculate the edge weight to simplify our discussion in this paper. We perform SGFRWT with fractional order θ ∈ [0.1, 1.0] on Swiss roll data cloud with J = 5 wavelet scales, and the results of some fractional orders θ ∈ {0.1, 0.5, 0.8, 1.0} are shown in Figure 2. The last column of Figure 2 shows the results of performing SGWT [44] on Swiss roll, from which we can see that SGWT [44] searches for the optimal expression domain only along the dimension of scale. However, the proposed SGFRWT searches for the optimal expression domain not only along the dimension of scale but also along the dimension of fractional order. That is, compared with SGWT, the proposed SGFRWT can express Swiss roll in higher dimensions, which makes the expression space larger and is therefore more likely to obtain a better expressive domain for the original problem. Just like [31–33], the fractional order θ is a hyperparameter depending on the original problem and you should search for a suitable value of θ. For example, the fractional order θ = 0.4 is an appropriate value for gland segmentation when using fractional wavelet scattering network [33].Figure 2
Spectral fractional graph wavelets on Swiss roll data cloud, with wavelet scaleJ = 5 and fractional order θ ∈ {0.1, 0.5, 0.8, 1.0}. (a) Wavelet scale j = 0, 1, 2 and fractional order θ ∈ {0.1, 0.5, 0.8, 1.0}. Note that j = 0 denotes the scaling function (b) wavelet scale j = 3, 4 and fractional order θ ∈ {0.1, 0.5, 0.8, 1.0}.
(a)(b)As a comparison, we also give the results of the proposed spectral graph fractional Fourier transform (SGFRFT) and graph fractional Fourier transform (GFRFT) proposed in [74, 75] on the “Swiss roll” in Figure 3, respectively. As we can see from Figure 3, the results of the proposed SGFRFT are different from those of GFRFT in [74, 75]. Furthermore, both SGFRFT and GFRFT are global transform and are not easily to be used for local analysis. However, let us see the third column of Figure 2, that is, the results of SGFRWT with J = 5 and fractional order θ = 0.8; the localization is more and more obvious along scale dimension. Comparing the third column of Figure 2 with the third column of Figure 3, we can see that, compared with SGFRFT and GFRFT, the proposed SGFRWT allows localization in fractional graph domain, which may lead to better local analysis in spectral graph domain. The experiment results of Figure 3 verify the local properties of SGFRWT shown in Appendix C (i.e., Lemmas C2–C4 and Theorem C5) to a certain extent.Figure 3
Spectral graph fractional Fourier transform (SGFRFT) and graph fractional Fourier transform (GFRFT) [74, 75] on Swiss roll data with fractional order θ ∈ {0.1, 0.4, 0.7, 1.0}.
(a)(b)


### 5.2.2. SGFRWT on MNIST Database

In the second example, we will see that the proposed SGFRWT can be used as a data augmentation method in the preprocessing of convolutional neural networks, which require as many input images as possible. Because, as shown in the first example, the proposed SGFRWT allows deriving many images from the original image by considering several fractional orders. In the following, a series of experiments are performed on the MNIST dataset to verify the effectiveness of the proposed SGFRWT as a method of data augmentation.We construct the graph for each image in MNIST dataset. The vertices of the graph are made up of pixels in the image and each pixel is connected with its vertical and horizontal neighbor pixel. The edge weight is calculated by a Gauss kernel weighting function [36] as follows: (68)wi,j=exp−disti,j22τ2,if disti,j≤k,0,otherwise,where wi,j is the weight on the edge connection of the vertex vi and vj, and dist (i, j) represents the distance between pixel i and pixel j.In order to prove the effectiveness of SGWT and SGFRWT, we augment MNIST dataset by the following strategies: (i) The original MNIST database has a training set of 60,000 images and a testing set of 10,000 images, which are used as a control group. (ii) For each image of the MNIST training set, we perform SGWT [44] with J = 5 wavelet scales and generate a total of 360,000 images. The original 10,000 test images are still used as the testing set. (iii) For each image of the MNIST training set, we apply the proposed SGFRWT with J = 5 wavelet scales and fractional order θ ∈ {0.2, 0.4, 0.6, 0.8, 1.0}, generating a total of 1,800,000 training images. The details of the generated four datasets are shown in Table 1. Figure 4 shows all sample images by processing an image of the digit “zero” by SGFRWT with J = 5 wavelet scales and fractional order θ ∈ {0.2, 0.4, 0.6, 0.8, 1.0}.Figure 4
Spectral graph fractional wavelets on an image “zero,” withJ = 5 wavelet scales and fractional order θ ∈ {0.2, 0.4, 0.6, 0.8, 1.0}. (θ, j, θ denotes the fractional order; j denotes the scale.To evaluate the data augmentation performance of the proposed approach, we train and test a simple convolutional neural network, which is shown in Figure5, using the three datasets mentioned above. The CNN model consists of 2 convolutional layers, 2 pooling layers, and a fully connected layer with a 10-way Softmax classifier. The inputs of the CNN are images of size 28 × 28. The first convolutional layer has 32 kernels with size 5 × 5, while the other layer has 64 kernels with size 3 × 3. The Rectified Linear Units (ReLUs) are chosen as the activation function. Every convolutional layer is followed by a nonoverlapping max-pooling with filter of size 2 × 2. Stochastic gradient descent algorithm is employed to optimize the network with a learning rate of 0.001. When the network converges, we evaluate the classification accuracy on the testing set with an average value of 10 times. The last column of Table 2 shows the classification performance comparison of the three different datasets. As we can see from Table 2, if we use traditional data augmentation methods (flipping, rotating, and adding noise), then the recognition rate can achieve 98.41%. When the training dataset of MNIST is augmented by SGWT without traditional data augmentation, the recognition rate can increase to 98.71%. From the last row of Table 2, we can see that our proposed SGFRWT can further improve the accuracy.Figure 5
The convolutional neural network used in our experiment.Table 2
Dataset generation implementation details. Comparison of classification performance of three different datasets with three different augmentation methods on the same CNN network.
DatasetAugmentation details of training setValidation setAccuracy (%)(i)MNIST training set augmented with flipping, rotating, and adding noise.Original MNIST testing set98.41(ii)MNIST training set augmented with SGWTOriginal MNIST testing set98.71(iii)MNIST training set augmented with SGFRWTOriginal MNIST testing set98.86


### 5.2.3. Face Recognition by Fusing SGFRWT Features

In the third example, the application of SGFRWT to provide features for face recognition is investigated. We use four classical face databases, whose MATLAB formats are provided in [82, 83]. (1) Yale Database [84]. It contains 165 grayscale images (15 individuals, 11 images per individual). (2) AR Database [85]. We use a nonoccluded subset of AR database containing 700 images (50 male subjects and 50 female subjects, 7 images per subject). (3) CMU PIE Face Database [86]. We also use a nonoccluded subset of CMU PIE database which contains 11560 images (68 persons, 170 images per person). (4) ORL Database [87]. It contains 400 grayscale images (40 individuals, 10 images per individual). Note that all the images are resized to 32 × 32 pixels.The experiment is carried out by the following three steps:(1)
For each image of the four face databases, we apply the propoJ=trSb/trSw,sed SGFRWT with wavelet scale J = 10 and fractional order θ ∈ {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0}, obtaining 100 times the images of original datasets.(2)
We then extract the SGFRWT features of three fractional orders which have the highest trace ration [88] as follows:(69)J=trSbtrSw,where tr(.) denotes the trace.Sb and Sw are between-class scatter matrix and the within-class scatter matrix, respectively,(70)Sb=∑i=1cNiA−AiT,Sw=∑i=1cNiAi−xθ,jAi−xθ,jT,where the superscriptT denotes transposition. C denotes the number of classes. A is the mean of Ai and Ai is the mean image of class Xi and Ni is the number of images in class Xi.| X(θ, j)| denotes the modulus of SGFRWT coefficient with the fractional order θ and the wavelet scale j.(3)
The SGFRWT features of three fractional orders are fused by canonical correlation analysis (CCA) [89] to obtain the feature vector, whose dimension is then reduced by principal component analysis (PCA) and Linear Discriminant Analysis (LDA). Finally, we feed the feature vector to the support vector machine (SVM).We conduct experiments on 18 different datasets which are constructed by four classical face databases mentioned above. Each set of datasets is compared with three different methods (baseline, SGWT, and SGFRWT), and we evaluate the classification accuracy on the testing set with an average value of 10 times. The recognition comparison results of the proposed SGFRWT feature building, the SGWT feature, and the baseline (only PCA + LDA + SVM used) on four face databases are shown in Table3, from which we can see that the proposed SGFRWT feature building approach can achieve promising results and perform better than SGWT feature and also the SVM baseline.Table 3
The recognition results of the proposed SGFRWT feature, the SGWT feature, and the baseline on four face databases (Yale, AR, ORL, and CMU PIE). We randomly selected several images per individual as training set and the remaining images as testing set. “i train” means that we randomly choose i images in each class for training. The accuracy is the average results of ten random testing experiments.
DatasetNumber of categoriesConstruction detailsBaseline (SVM) (%)SGWT + SVM (%)The proposed SGFRWT + SVM (%)Yale: 165 grayscale images (15 individuals, 11 images per individual)151 train, 10 test each class91.9399.27100152 train, 9 test each class93.2699.48100153 train, 8 test each class93.4299.86100154 train, 7 test each class94.57100100155 train, 6 test each class95.56100100AR: 700 images (50 male subjects and 50 female subjects, 7 images per subject)1001 train, 6 test each class49.5390.9296.521002 train, 5 test each class70.7893.2498.141003 train, 4 test each class78.5396.5898.4ORL: 400 grayscale images (40 individuals, 10 images per individual)401 train, 9 test each class93.9498.1699.86402 train, 8 test each class9798.599.81403 train, 7 test each class97.7299.2999.89404 train, 6 test each class97.8399.3399.83405 train, 5 test each class9899.35100CMPUPIE: 11560 images (68 persons, 170 images per person)681 train, 169 test each class15.177.981.13685 train, 165 test each class40.989.2290.096810 train, 160 test each class52.4591.1191.956815 train, 155 test each class60.2891.1492.366820 train, 150 test each class64.8191.6792.7


## 5.2.1. SGFRWT on Synthetic Graph Data

In the first example, we perform the proposed SGFRWT on “Swiss roll,” which is a dataset whose points are sampled randomly from a two-dimensional (2D) manifold as follows:(66)x⟶t1,t2=t1cost24π,t1,t2sint24π,−1≤t1≤1,π≤t2≤4π.Figure1 shows the Swiss roll data cloud. We take 500 points sampled uniformly on the manifold and then build a weighted graph, whose edge weight is defined as follows:(67)ai,j=exp−xi−xj22σ2.Figure 1
Spectral fractional graph wavelets on Swiss roll data cloud. The figure shows vertex at which SGFRWT is centered; that is, we will apply SGFRWT on the signal value of centered vertex.Note that the definition of the edge weight is a critical issue in graph construction. The most direct way to compute the edge weight is based on a given (dis)similarity measure. In practice, the edge weight is generally defined using different measures for better interpretability. As discussed in [81], Gaussian kernel and its variants (i.e., heat kernel or RBF kernel) are one of the most popular schemes to assign edge weights for a graph. Therefore, we take the Gaussian kernel in (67) to calculate the edge weight to simplify our discussion in this paper. We perform SGFRWT with fractional order θ ∈ [0.1, 1.0] on Swiss roll data cloud with J = 5 wavelet scales, and the results of some fractional orders θ ∈ {0.1, 0.5, 0.8, 1.0} are shown in Figure 2. The last column of Figure 2 shows the results of performing SGWT [44] on Swiss roll, from which we can see that SGWT [44] searches for the optimal expression domain only along the dimension of scale. However, the proposed SGFRWT searches for the optimal expression domain not only along the dimension of scale but also along the dimension of fractional order. That is, compared with SGWT, the proposed SGFRWT can express Swiss roll in higher dimensions, which makes the expression space larger and is therefore more likely to obtain a better expressive domain for the original problem. Just like [31–33], the fractional order θ is a hyperparameter depending on the original problem and you should search for a suitable value of θ. For example, the fractional order θ = 0.4 is an appropriate value for gland segmentation when using fractional wavelet scattering network [33].Figure 2
Spectral fractional graph wavelets on Swiss roll data cloud, with wavelet scaleJ = 5 and fractional order θ ∈ {0.1, 0.5, 0.8, 1.0}. (a) Wavelet scale j = 0, 1, 2 and fractional order θ ∈ {0.1, 0.5, 0.8, 1.0}. Note that j = 0 denotes the scaling function (b) wavelet scale j = 3, 4 and fractional order θ ∈ {0.1, 0.5, 0.8, 1.0}.
(a)(b)As a comparison, we also give the results of the proposed spectral graph fractional Fourier transform (SGFRFT) and graph fractional Fourier transform (GFRFT) proposed in [74, 75] on the “Swiss roll” in Figure 3, respectively. As we can see from Figure 3, the results of the proposed SGFRFT are different from those of GFRFT in [74, 75]. Furthermore, both SGFRFT and GFRFT are global transform and are not easily to be used for local analysis. However, let us see the third column of Figure 2, that is, the results of SGFRWT with J = 5 and fractional order θ = 0.8; the localization is more and more obvious along scale dimension. Comparing the third column of Figure 2 with the third column of Figure 3, we can see that, compared with SGFRFT and GFRFT, the proposed SGFRWT allows localization in fractional graph domain, which may lead to better local analysis in spectral graph domain. The experiment results of Figure 3 verify the local properties of SGFRWT shown in Appendix C (i.e., Lemmas C2–C4 and Theorem C5) to a certain extent.Figure 3
Spectral graph fractional Fourier transform (SGFRFT) and graph fractional Fourier transform (GFRFT) [74, 75] on Swiss roll data with fractional order θ ∈ {0.1, 0.4, 0.7, 1.0}.
(a)(b)


## 5.2.2. SGFRWT on MNIST Database

In the second example, we will see that the proposed SGFRWT can be used as a data augmentation method in the preprocessing of convolutional neural networks, which require as many input images as possible. Because, as shown in the first example, the proposed SGFRWT allows deriving many images from the original image by considering several fractional orders. In the following, a series of experiments are performed on the MNIST dataset to verify the effectiveness of the proposed SGFRWT as a method of data augmentation.We construct the graph for each image in MNIST dataset. The vertices of the graph are made up of pixels in the image and each pixel is connected with its vertical and horizontal neighbor pixel. The edge weight is calculated by a Gauss kernel weighting function [36] as follows: (68)wi,j=exp−disti,j22τ2,if disti,j≤k,0,otherwise,where wi,j is the weight on the edge connection of the vertex vi and vj, and dist (i, j) represents the distance between pixel i and pixel j.In order to prove the effectiveness of SGWT and SGFRWT, we augment MNIST dataset by the following strategies: (i) The original MNIST database has a training set of 60,000 images and a testing set of 10,000 images, which are used as a control group. (ii) For each image of the MNIST training set, we perform SGWT [44] with J = 5 wavelet scales and generate a total of 360,000 images. The original 10,000 test images are still used as the testing set. (iii) For each image of the MNIST training set, we apply the proposed SGFRWT with J = 5 wavelet scales and fractional order θ ∈ {0.2, 0.4, 0.6, 0.8, 1.0}, generating a total of 1,800,000 training images. The details of the generated four datasets are shown in Table 1. Figure 4 shows all sample images by processing an image of the digit “zero” by SGFRWT with J = 5 wavelet scales and fractional order θ ∈ {0.2, 0.4, 0.6, 0.8, 1.0}.Figure 4
Spectral graph fractional wavelets on an image “zero,” withJ = 5 wavelet scales and fractional order θ ∈ {0.2, 0.4, 0.6, 0.8, 1.0}. (θ, j, θ denotes the fractional order; j denotes the scale.To evaluate the data augmentation performance of the proposed approach, we train and test a simple convolutional neural network, which is shown in Figure5, using the three datasets mentioned above. The CNN model consists of 2 convolutional layers, 2 pooling layers, and a fully connected layer with a 10-way Softmax classifier. The inputs of the CNN are images of size 28 × 28. The first convolutional layer has 32 kernels with size 5 × 5, while the other layer has 64 kernels with size 3 × 3. The Rectified Linear Units (ReLUs) are chosen as the activation function. Every convolutional layer is followed by a nonoverlapping max-pooling with filter of size 2 × 2. Stochastic gradient descent algorithm is employed to optimize the network with a learning rate of 0.001. When the network converges, we evaluate the classification accuracy on the testing set with an average value of 10 times. The last column of Table 2 shows the classification performance comparison of the three different datasets. As we can see from Table 2, if we use traditional data augmentation methods (flipping, rotating, and adding noise), then the recognition rate can achieve 98.41%. When the training dataset of MNIST is augmented by SGWT without traditional data augmentation, the recognition rate can increase to 98.71%. From the last row of Table 2, we can see that our proposed SGFRWT can further improve the accuracy.Figure 5
The convolutional neural network used in our experiment.Table 2
Dataset generation implementation details. Comparison of classification performance of three different datasets with three different augmentation methods on the same CNN network.
DatasetAugmentation details of training setValidation setAccuracy (%)(i)MNIST training set augmented with flipping, rotating, and adding noise.Original MNIST testing set98.41(ii)MNIST training set augmented with SGWTOriginal MNIST testing set98.71(iii)MNIST training set augmented with SGFRWTOriginal MNIST testing set98.86


## 5.2.3. Face Recognition by Fusing SGFRWT Features

In the third example, the application of SGFRWT to provide features for face recognition is investigated. We use four classical face databases, whose MATLAB formats are provided in [82, 83]. (1) Yale Database [84]. It contains 165 grayscale images (15 individuals, 11 images per individual). (2) AR Database [85]. We use a nonoccluded subset of AR database containing 700 images (50 male subjects and 50 female subjects, 7 images per subject). (3) CMU PIE Face Database [86]. We also use a nonoccluded subset of CMU PIE database which contains 11560 images (68 persons, 170 images per person). (4) ORL Database [87]. It contains 400 grayscale images (40 individuals, 10 images per individual). Note that all the images are resized to 32 × 32 pixels.The experiment is carried out by the following three steps:(1)
For each image of the four face databases, we apply the propoJ=trSb/trSw,sed SGFRWT with wavelet scale J = 10 and fractional order θ ∈ {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0}, obtaining 100 times the images of original datasets.(2)
We then extract the SGFRWT features of three fractional orders which have the highest trace ration [88] as follows:(69)J=trSbtrSw,where tr(.) denotes the trace.Sb and Sw are between-class scatter matrix and the within-class scatter matrix, respectively,(70)Sb=∑i=1cNiA−AiT,Sw=∑i=1cNiAi−xθ,jAi−xθ,jT,where the superscriptT denotes transposition. C denotes the number of classes. A is the mean of Ai and Ai is the mean image of class Xi and Ni is the number of images in class Xi.| X(θ, j)| denotes the modulus of SGFRWT coefficient with the fractional order θ and the wavelet scale j.(3)
The SGFRWT features of three fractional orders are fused by canonical correlation analysis (CCA) [89] to obtain the feature vector, whose dimension is then reduced by principal component analysis (PCA) and Linear Discriminant Analysis (LDA). Finally, we feed the feature vector to the support vector machine (SVM).We conduct experiments on 18 different datasets which are constructed by four classical face databases mentioned above. Each set of datasets is compared with three different methods (baseline, SGWT, and SGFRWT), and we evaluate the classification accuracy on the testing set with an average value of 10 times. The recognition comparison results of the proposed SGFRWT feature building, the SGWT feature, and the baseline (only PCA + LDA + SVM used) on four face databases are shown in Table3, from which we can see that the proposed SGFRWT feature building approach can achieve promising results and perform better than SGWT feature and also the SVM baseline.Table 3
The recognition results of the proposed SGFRWT feature, the SGWT feature, and the baseline on four face databases (Yale, AR, ORL, and CMU PIE). We randomly selected several images per individual as training set and the remaining images as testing set. “i train” means that we randomly choose i images in each class for training. The accuracy is the average results of ten random testing experiments.
DatasetNumber of categoriesConstruction detailsBaseline (SVM) (%)SGWT + SVM (%)The proposed SGFRWT + SVM (%)Yale: 165 grayscale images (15 individuals, 11 images per individual)151 train, 10 test each class91.9399.27100152 train, 9 test each class93.2699.48100153 train, 8 test each class93.4299.86100154 train, 7 test each class94.57100100155 train, 6 test each class95.56100100AR: 700 images (50 male subjects and 50 female subjects, 7 images per subject)1001 train, 6 test each class49.5390.9296.521002 train, 5 test each class70.7893.2498.141003 train, 4 test each class78.5396.5898.4ORL: 400 grayscale images (40 individuals, 10 images per individual)401 train, 9 test each class93.9498.1699.86402 train, 8 test each class9798.599.81403 train, 7 test each class97.7299.2999.89404 train, 6 test each class97.8399.3399.83405 train, 5 test each class9899.35100CMPUPIE: 11560 images (68 persons, 170 images per person)681 train, 169 test each class15.177.981.13685 train, 165 test each class40.989.2290.096810 train, 160 test each class52.4591.1191.956815 train, 155 test each class60.2891.1492.366820 train, 150 test each class64.8191.6792.7


## 6. Conclusion

This paper investigates the issue of extension of spectral graph wavelet transform (SGWT) to fractional domain. The main contributions of this paper can be summarized as follows. (1) A novel transform named spectral graph fractional wavelet transform (SGFRWT) is defined. (2) A Fourier series approximation-based fast algorithm for SGFRWT is derived and implemented since the SGFRWT includes complex domain computations compared to SGWT. (3) Applications of SGFRWT to synthetic and real datasets are also given to highlight its potential usefulness. In summary, the proposed fractional spectral graph wavelets provide a new choice for the graph signal processing. Further research may include the extension of the proposed SGFRWT for dealing with the directed graphs [40, 41] and the extension of the idea of SGFRWT to critically sampled graph wavelets like GraphBio [46].



---

*Source: 2568179-2020-11-06.xml*