# High Performance Graph Data Imputation on Multiple GPUs
## 3 Convolutional Imputation Algorithm
### Notations  
We use lowercase boldface letters \(\mathbf{x}\in\mathbb{R}^{n_{1}}\) to denote vectors and uppercase boldface letters \(\mathbf{X}\in\mathbb{R}^{n_{1}\times n_{2}}\) to denote matrices. Let \(i,j\) index the rows and columns of a matrix, respectively, and \(\mathbf{X}_{ij}\) or \(\mathbf{X}(i,j)\) to denote the \((i,j)\)-th matrix entry. Third-order tensors are denoted by uppercase calligraphic letters, \(\mathcal{X}\in\mathbb{R}^{n_{1}\times n_{2}\times n_{3}}\). Let \(i,j,k\) index the first, second, and third dimensions of a tensor, respectively, and \(\mathcal{X}_{ijk}\) or \(\mathcal{X}(i,j,k)\) to denote the \((i,j,k)\)-th entry. Let \([n]\) denote the set \(\{1,2,\cdots,n\}\), then \(i\in[n_{1}],j\in[n_{2}]\), \(k\in[n_{3}]\) unless otherwise specified. Please refer to Table 1 for the notations of major symbols. **Graph-Tensor**: a weighted graph is defined by \(\mathbf{G}=(V,E)\), where \(V=\{v_{1},...,v_{N}\}\) is a set of \(N\) vertices and \(E\) is a set of edges. We use the weighted adjacency matrix \(\mathbf{A}\in\mathbb{R}^{N\times N}\) to describe the the relationship between vertices in the graph. Two vertices \(v_{k}\) and \(v_{\ell}\) are adjacent if \((v_{k},v_{\ell})\subseteq E\) is an edge, \(k,\ell\in[N]\). Let \(\mathbf{A}_{k\ell}\) denote the weight on the edge \((v_{k},v_{\ell})\), otherwise, let \(\mathbf{A}_{k\ell}=0\). Assuming the data on each vertex \(v_{k}\) is a matrix of size \(m\times n\), we define a graph-tensor \(\mathcal{G}\in\mathbb{R}^{m\times n\times N}\) by stacking data matrices of all vertices along the third dimension. The data matrix of the \(k\)-th vertex \(v_{k}\) is denoted by \(\mathcal{G}(:,:,k)\) or \(\mathcal{G}(k)\) for simplicity. The Frobenius norm of a graph-tensor is \(\|\mathcal{G}\|_{F}=\sqrt{\sum_{i=1}^{m}\sum_{j=1}^{n}\sum_{k=1}^{N}\left| \mathcal{G}_{ijk}\right|^{2}}\). Tubes and slices: a tube (also called a fiber) is a 1D vector defined by fixing all indices but one, while a slice is a 2D matrix defined by fixing all but two indices. Tubes can be categorized into model-1, model-2, and model-3 tubes, and slices can be categorized into frontal, lateral, and horizontal slices [3]. We use \(\mathcal{G}(i,j,:)\) to denote the \((i,j)\)-th model-3 tube and \(\mathcal{G}(:,:,k)\) to denote the \(k\)-th frontal slice. We call \(\mathcal{G}(:,:,k)\) or \(\mathcal{G}(k)\) the data matrix if it is a vertex value, and frontal slice otherwise. **Graph Fourier Transform (GFT):** the graph Fourier transform extends the concept of the discrete Fourier transform to a general graph, which is to transform a graph signal in the spatial domain into the spectral domain. For a graph \(\mathbf{G}\) with the adjacent matrix \(\mathbf{A}\), the normalized graph Laplacian matrix is defined as \(\mathbf{L}=\mathbf{I}-\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}\), where \(\mathbf{D}\) is a diagonal matrix with entries \(\mathbf{D}_{ii}=\sum_{j}\mathbf{A}_{ij}\). The graph Fourier transform matrix \(\mathbf{U}\), a unitary \(N\times N\) matrix, is given by the eigendecomposition of \(\mathbf{L}=\mathbf{U}\mathbf{\Lambda}\mathbf{U}^{-1}\), where columns of \(\mathbf{U}\) are the eigenvectors of \(\mathbf{L}\), and \(\mathbf{\Lambda}\) is the diagonal matrix whose diagonal elements are eigenvalues of \(\mathbf{L}\). The graph Fourier transform (GFT) of a graph-tensor \(\mathcal{G}\) is defined as \(\widetilde{\mathcal{G}}=\mathbf{U}\mathcal{G}\), where \(\widetilde{\mathcal{G}}\in\mathbb{R}^{m\times n\times N}\) is a stack of \(N\) matrices in the spectral domain of the graph. Furthermore, each frontal slice in the spatial domain is a linear combination of data matrices on the graph, \(\widetilde{\mathcal{G}}(k)=\sum_{\ell\in[N]}\mathbf{U}_{k\ell}\mathcal{G}(\ell)\). The inverse graph Fourier transform (iGFT) is defined as \(\mathcal{G}(k)=\sum_{\ell\in[N]}\mathbf{U}_{k\ell}^{-1}\widetilde{\mathcal{G}}(\ell)\), correspondingly.