# Pedestrian Attribute Recognition with Graph Convolutional Network in Surveillance Scenarios
## 3 Approach
### Preliminary
#### 3.1.2 Graph Convolutional Network  
Graph convolutional network is a branch of the graph neural network [25]. It is an emerging field in recent years which originates from the limitations of convolutional neural networks. CNN has developed rapidly these years due to its translation invariance and weight sharing, which started the new era of deep learning [26]. However, the convolutional neural network normally operates on regular Euclidean data-like images and speech, and in other words, convolutional neural networks are not good at operating on non-Euclidean data-like graphs. Therefore, many researchers started to think how to define the convolution on non-Euclidean structures and extract features for machine learning tasks. Advance strategies in graph convolution are often categorized as spectral approaches and spatial approaches. This paper mainly focuses on spectral approaches.  
Spectral network was proposed by [27]. The convolution operation is defined in the Fourier domain by computing the eigenvalue decomposition of the graph Laplacian. Given Laplacian:  
\[L=I_{N}-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}=U\Lambda U^{T}, \tag{1}\]  
where \(D\) is the degree matrix, \(A\) is the adjacency matrix of the graph, and \(\Lambda\) is the diagonal matrix of its eigenvalues. Notice that \(L\) is a symmetrical and positive semi-definite matrix which means \(L\) can be decomposed and each eigenvalue of \(L\) is called the spectrum of \(L\). Then, researchers define traditional Fourier transform on graph, the graph Fourier transform of a signal \(x\in R^{N}\) is defined as \(U^{T}x\), where \(U\) is the matrix of eigenvectors of the normalized graph Laplacian.  
The convolution on graph can be defined as the multiplication of a signal \(x\in R^{N}\) with a filter \(g_{\theta}=diag(\theta)\) parameterized by \(\theta\in R^{N}\):  
\[g_{\theta}*x=Ug_{\theta}U^{T}x. \tag{2}\]  
Then researchers focus on \(g_{\theta}\) and deduce that the computational complexity of the above operation is \(O\Big{(}n^{3}\Big{)}\), which means this operation may result in intense computational complexity. So, researchers hope to come up with a way equipped with fewer parameters and lower complexity. In [28], the author suggests that \(g_{\theta}\) can be approximated by a truncated expansion in term of Chebyshev polynomials \(T_{k}(x)\) up to \(K\)-th order:  
\[g_{\theta}*x\approx\sum_{k=0}^{K}\theta_{k}T_{k}\Big{(}\widetilde{L}\Big{)}x, \tag{3}\]  
where \(\widetilde{L}=\frac{2}{\lambda_{max}}L-I_{N}\). \(\lambda_{max}\) denotes the largest eigenvalue of \(L\). Notice that the approximate operation only requires complexity of \(O(K\Big{|}E\Big{|})\) and \(K+1\) parameters, where \(E\) is the edge numbers of a graph. Next, [29] limits \(K=1\) and approximates \(\lambda_{max}\approx 2\) as well as constrains the parameters with \(\theta=\theta_{0}^{\prime}=-\theta_{1}^{\prime}\) to simplify the operation, then we can obtain the following expression:  
\[g_{\sigma^{\prime}}*x\approx\theta_{0}^{\prime}x+\theta_{1}^{\prime}(L-I_{N})x =\theta\Big{(}I_{N}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\Big{)}x, \tag{4}\]  
Finally, using renormalization trick, from a macro perspective, the formula can be expressed as follows:  
\[H^{l+1}=\sigma\Big{(}\overline{D}^{-\frac{1}{2}}\overline{AD}^{-\frac{1}{2}}H ^{l}W^{l}\Big{)}, \tag{5}\]  
where \(H^{l}\) denotes the nodes feature of \(l\)-th layer, \(W^{l}\) denotes the parameters to be learned of \(l\)-th layer, \(\sigma(\cdot)\) denotes a non-linear operation.