## 2 Related Work
### Advances in Graph Convolution definition  
The application of graph representation in computer vision is usually conducted based on GCNNs. GCNNs emerged from the spectral-based graph convolution method, and many studies have been derived from this, as GCNNs produce good result. Therefore, as a step towards understanding GCNNs, we describe the advances in graph convolution definition, from the initial definition of graph convolution operation to the recent one, in this section. [PERSON] et al. [28] initially defined the spectral graph convolutional method based on the convolution theorem in signal and image processing. In this paper, they defined a symmetric normalized Laplacian matrix (\(\mathcal{L}^{\text{sym}}\)) with a degree matrix (\(\mathcal{D}\)) and adjacency matrix (\(\mathcal{A}\)) from the structural graph information in Equation (1) and defined graph convolution using the eigenvector and eigenvalue from the eigendecomposition of \(\mathcal{L}^{\text{sym}}\) in Equation (2):  
\[\mathcal{L}^{\text{sym}}=\text{I}-\mathcal{D}^{-\frac{1}{2}}\mathcal{A} \mathcal{D}^{-\frac{1}{2}}=U^{T}\Lambda U, \tag{1}\]  
\[X^{l+1}=U(U^{T}X^{l}\odot U^{T}W^{l}_{spectral}). \tag{2}\]  
where I denotes the identity matrix, \(U\in\mathbb{R}^{nxn}\) is the Fourier basis in which eigenvectors are treated with column vectors, \(\Lambda\in\mathbb{R}^{nxn}\) is defined as a diagonal matrix of eigenvalues, \(X^{l}\in\mathbb{R}^{nxF}\) is a feature vector in \(l^{lh}\) layer, \(\odot\) represents the element-wise Hadamard product, and \(W^{l}_{spectral}\in\mathbb{R}^{nxF}\) denotes the spectral convolutional filter. However, due to the high dependence of graph size encoded by the eigenvector, it cannot be applied to the variable structure of the large-scale graph data. The computational cost is high because the complexity of the eigendecomposition related to the Fourier basis \(U\) is \(\mathcal{O}(n^{2})\), where \(n\) is the number of nodes in the graph. To overcome this issue, [PERSON] et al. [29] proposed the Chebyshev graph convolutional network (GCN) called ChebNet based on the Chebyshev polynomial in Equation (3), and the initial term is in Equation (4):  
\[T_{i}(x)=2 xT_{i-1}(x)-T_{i-2}(x), \tag{3}\]  
\[T_{0}(x)=1,\ T_{1}(x)=x. \tag{4}\]  
Based on the approximated filter by the \(K\)-order Chebyshev polynomial, the above graph convolutional method defines a localized filter by recursively aggregating only the information of nodes up to the \(K^{th}\) distance from each node. Equation (5) defines an approximated filter \(g_{\theta}\), and the convolutional operation for the input graph \(G\) based on the filter is defined in Equation (6):  
\[g_{\theta}\approx\Sigma_{k=0}^{K-1}\theta_{k}T_{k}(\ \widetilde{\Lambda}), \tag{5}\]  
\[G\ast g_{\theta}\approx U(\Sigma_{k=0}^{K-1}\theta_{k}T_{k}(\ \widetilde{\Lambda}))U^{T}G, \tag{6}\]  
Figure 1: Sample of segmenting the original image into pixel-based and SLIC-based graph representation. where \(T_{k}(\widetilde{\Lambda})\in\mathbb{R}^{nxn}\) denotes the \(K^{th}\)-order Chebyshev polynomial based on the diagonal matrix of eigenvalues \(\widetilde{\Lambda}\), with values from \(-1\) to \(1\), in Equation (7), and \(\theta_{k}\in\mathbb{R}^{K}\) represents the coefficient of the Chebyshev polynomial:  
\[\widetilde{\Lambda}=\frac{2\Lambda}{\lambda_{\text{max}}}-\text{I}. \tag{7}\]  
By redefining the graph convolution that is unaffected by the Fourier basis \(U\) in Equation (9), according to Equation (8), [PERSON] reduced the computational complexity to \(\mathcal{O}(K|\epsilon|)\ll\mathcal{O}(n^{2})\), where \(|\epsilon|\) is the number of edge sets:  
\[T_{i}(\widetilde{\mathcal{L}})=UT_{k}(\widetilde{\Lambda})U^{T}, \tag{8}\]  
\[G*g_{\theta}\coloneqq\Sigma_{k=0}^{K-1}\theta_{k}T_{k}(\widetilde{\mathcal{L }})G, \tag{9}\]  
\[X^{l+1}=U(U^{T}X^{l}\odot U^{T}W^{l}_{spectral}). \tag{2}\]0  
where \(\widetilde{\mathcal{L}}\) denotes the rescaled Laplacian matrix, defined in Equation (10).