# Rotation Invariant Graph Neural Network for 3D Point Clouds
## 3 Theoretical Background
### Spectral Graph Convolution Neural Network  
Spectral graph convolution neural networks in point cloud applications use the modules designed by [29; 35]. The spectral convolution module described by [35] decomposes the Laplacian into eigenvalues and the corresponding eigenvectors as \(L=U\Lambda U^{\top}\), where \(U\in\mathbb{R}^{n\times n}\) is the matrix of eigenvectors and \(\Lambda\in\mathbb{R}^{n\times n}\) is the diagonal matrix of eigenvalues. An input signal is considered to be \(X\in\mathbb{R}^{N\times f_{in}}\), where \(f_{in}\in\mathbb{N}\) is the number of features for each point. \(F(X)=U^{\top}X\), \(F(X)\in\mathbb{R}^{n\times f_{in}}\) is equivalent to converting a signal \(X\) from the spatial domain to the spectral. Taking into account the output signal \(\hat{X}\in\mathbb{R}^{N\times f_{in}}\)\(F^{-1}(\hat{X})=U\hat{X}\) gives us the inverse operation. By converting an input in the spectral domain, we can use a filter \(g\) to manipulate the values in the spectral domain and then use an inverse operation to convert it back into the spatial domain. Thus, the first interpretation of the spectral convolution described in [35] is found in (3). \[\hat{X}=F^{-1}(F(X)*F(g)) \tag{3}\]  
\"\(\ast\)\" is the Hadamard product and \(g\in\mathbb{R}^{n\times f_{in}}\) is a filter of the same dimension as the input. The simplification is carried out considering that the spectral filter \(g^{\prime}\in\mathbb{R}^{n}\) is a 1-dimensional vector applied to each of the \(N\) channels of the input. In this way, the filter \(g^{\prime}\in\mathbb{R}^{n}\) and the input vector \(X\in\mathbb{R}^{n\times F_{in}}\) are of different dimensions. The spectral convolution is rewritten in (4). \[\hat{X}=Udiag(Ug^{\prime})U^{\top}X \tag{4}\]  
\(Ug^{\prime}=\theta\in\mathbb{R}^{n}\) is the parameter of the network which must be fine-tuned and since the eigenvectors depend on the corresponding eigenvalues, the spectral filter can be seen as a function of the eigenvalue diagonal matrix \(\Lambda=diag([\lambda_{1},\lambda_{2},\ldots,\lambda_{N}]^{\top})\),\(\lambda_{k}\in\mathbb{R}\) being an eigenvalue. Thus, the formulation used in graph spectral convolutional networks is described in (5). \[\hat{X}=Uh_{\theta}(\Lambda)U^{\top}X \tag{5}\]  
where \(h_{\theta}(\Lambda)=diag(\theta)=diag(Ug^{\prime})\). By manipulating the eigenvalues, the resulting matrix has graph filtering properties similar to a Fourier decomposition of a signal into multiple harmonic frequencies. A further improvement is the Chebnet spectral graph convolution module described in [29]. This method avoids the expensive Eigen decomposition by expressing the graph filter as a weighted sum of powers of Laplacian. The spectral graph convolutional module used in the network is based on (6). \[h_{\theta}(\Lambda)\approx\sum_{k=0}^{K}\theta_{k}^{\prime}T_{k}(\Lambda) \tag{6}\]  
where \(K\in\mathbb{N}\) is the filter size, \(\theta_{k}^{\prime}\in\mathbb{R}\) are the filter coefficients, and \(T_{k}(\Lambda)\in\mathbb{R}^{n\times n}\) represents the Chebyshev polynomial applied to the diagonal matrix of eigenvalues. In this way, a function of the eigenvalues is represented as a weighted sum of Chebyshev polynomials of the diagonal matrix of eigenvalues. The Chebyshev polynomials can be computed recursively with the starting terms \(T_{0}(X)=I\), \(T_{1}(X)=X\) and \(T_{k}(X)=2T_{k-1}(X)-T_{k-2}(X)\). The spectral convolution function is rewritten in (7). \[h(L)=U\Bigg{(}\sum_{k=0}^{K}\theta_{k}^{\prime}T_{k}(\Lambda)\Bigg{)}U^{\top}= \sum_{k=0}^{K}\theta_{k}^{\prime}T_{k}(L) \tag{7}\]  
If the output signal \(\hat{X}\) has a different number of channels than the input signal \(X\), a further linear model \(W\in\mathbb{R}^{f_{in}\times f_{out}}\) is needed to transform the input signal \(X\in\mathbb{R}^{n\times f_{in}}\) to the output signal \(\hat{X}\in\mathbb{R}^{n\times f_{out}}\), where \(f_{out}\in\mathbb{N}\) is the number of features for each pointin the output vector. Thus, applying also the sigmoid function, the spectral convolution module is described in (8).