# High Performance Graph Data Imputation on Multiple GPUs
## 3 Convolutional Imputation Algorithm
### Overview of the Convolutional Imputation Algorithm  
The convolution imputation algorithm [2] was proposed for recovering missing slices in a graph tensor (i.e., here we consider the case of missing slices, the slice-sampling pattern). In the slice-sampling pattern, the data matrix of each vertex is either fully observed or fully missing. Figure 1 shows an example of a social network that can be abstracted into a graph \(\mathbf{G}\). Each user is represented by a vertex \(v_{k}\), and each relationship between users is represented by an edge \((v_{k},v_{\ell})\). The graph-tensor in Figure 1b is composed of the data matrix of each vertex, in which two frontal slices are missing due to the complete loss of users \(v_{1}\) and \(v_{4}\)'s information. To recover the missing slices is a graph-tensor completion problem in the slice-sampling pattern.  
The pseudo code of the convolutional imputation algorithm [2] is given in Algorithm 1. We use \(\Omega\subseteq[N]\) to denote the slice-sampling index set, and \(\frac{1}{\Omega}\) is a complement set to \(\Omega\). The projection operator \(\mathcal{P}_{\Omega}\) is defined to sample the graph-tensor by retaining only entities that are indexed in the set \(\Omega\). Given an observed low-rank graph-tensor \(\mathcal{P}_{\Omega}(\mathcal{G})\), a graph Fourier transform matrix \(\mathbf{U}\), and a sequence of regularization parameters \(\lambda^{1}>\lambda^{2}>...>\lambda^{C}\), the imputation algorithm [2] iteratively performs imputation of \(\mathcal{G}^{\text{impute}}\) and singular value soft-threshold of \(\widetilde{\mathcal{G}}^{\text{impute}}\) to find the minimizer of the optimization problem. According to the convolution of graph-tensors, in the spectral domain, we denote singular value soft-threshold as \(S_{\lambda^{j}_{k}}(\widetilde{\mathcal{G}}(k))=\mathbf{U}(\mathbf{S}-\lambda^{j}_{k} \mathbf{I})_{+}\mathbf{V}^{T}\), where \((\cdot)_{+}\) means keeping only positive values, and \(\widetilde{\mathcal{G}}(k)=\mathbf{U}\mathbf{S}\mathbf{V}^{T}\) is the singular value decomposition (SVD), \(j\in[C]\), \(k\in[N]\).  
```
1:\(\mathcal{P}_{\Omega}(\mathcal{G})\in\mathbb{R}^{m\times n\times N}\), number of iterations \(C\), maximum number of iterations \(T\).
2:Initialize:\(\mathcal{G}_{0}^{\text{est}}=0,t=0\),
3: Generate graph Fourier transform matrix \(\mathbf{U}\),
4: Generate regularization parameters \(\lambda^{1}>\lambda^{2}>...>\lambda^{C}\), where \(\lambda^{j}=(\lambda^{j}_{k}),k=1,...,N\),
5:for\(j=1\) to \(C\)do
6:while\(t\leq T\) and NOT convergeddo
7:\(t\gets t+1\),
8:\(\widetilde{\mathcal{G}}^{\text{impute}}=\mathcal{P}_{\Omega}(\mathcal{G})+ \mathcal{P}_{\frac{1}{\Omega}}(\mathcal{G}_{t-1}^{\text{est}})\),
9:\(\widetilde{\mathcal{G}}^{\text{impute}}_{t}=\mathbf{U}\widetilde{\mathcal{G}}^{ \text{impute}}\),
10:\(\widetilde{\mathcal{G}}^{\text{est}}_{t}(k)=S_{\lambda^{j}_{k}}(\widetilde{ \mathcal{G}}^{\text{impute}}(k))\),
11:\(\mathcal{G}^{\text{est}}_{t}=\mathbf{U}^{-1}\widetilde{\mathcal{G}}^{\text{est}}_ {t}\),
12:endwhile
13:\(\mathcal{G}_{\lambda^{j}}=\mathcal{G}^{\text{est}}_{t}\),
14:endfor
15:solution \(\mathcal{G}_{\lambda^{C}}\).
```  
**Algorithm 1** Iterative convolutional imputation.  
For \(\lambda^{j}\) in each iteration, the algorithm selects the maximum singular value of \(\widetilde{\mathcal{G}}(k)\) as \(\lambda^{1}_{k}\), and decays \(\lambda^{j}\) at a constant speed \(\lambda^{j+1}=c\lambda^{j}\). For more details on convergence and computational complexity, please refer to [2].