# GRNN: Graph-Retraining Neural Network for Semi-Supervised Node Classification
## 4 GRNN: Graph-Retraining Neural Network
### The Loss Function of GRNN  
With the increase in the smoothing model iteration, the labeled labels \(Y_{L_{t}}\) are gradually ignored. Therefore, the loss function of GRNN is improved by combining Equations (8) and (15), and the formula is as follows:  
\[G(\bar{k})=-\sum_{l\in L_{t}}\sum_{r=1}^{q}\gamma_{lr}\text{ln}f^{(\bar{k})}( X)_{lr} \tag{17}\]  
\[\widetilde{G}(\bar{k})=-\sum_{l\in(lU\cup L_{r})}\sum_{r=1}^{q}\widetilde{Y}_ {lr}^{(\bar{k})}\text{ln}f^{(\bar{k})}(X)_{lr} \tag{18}\]  
\[f^{(\bar{k}+1)}=\underset{f^{(\bar{k})}}{argmin}(R(G(\bar{k}))+R(G(\bar{k})+ \widetilde{G}(\bar{k}))) \tag{19}\]  
where \(R(\centerdot)\) is a univariate function.  
In order to eliminate the uncertainty of the system at the least cost, the univariate function \(R(\centerdot)\) satisfies the condition of the convex function. Furthermore, the univariate function \(R(\centerdot)\) also needs to satisfy \(R(x)\geqslant x\) in which \(R(x)=x\) if and only if \(x=0\), which avoids the loss value that is too close to zero resulting in gradient disappearance. There is a function \(R(x)=exp(x)-1\) satisfying the above conditions. Therefore, the loss function of GRNN is as follows:  
\[\mathcal{L}(\bar{k})=exp(G(\bar{k}))+exp(G(\bar{k})+\widetilde{G}(\bar{k}))-2 \tag{20}\]  
The time complexity of a single benchmark neural network (GRNN-0) attention-head computing \(p_{1}\) features can be expressed as \(O(mp_{1}p)\). Therefore, the time complexity of a GRNN attention-head computing \(p_{1}\) features can be expressed as \(O(kmp_{1}p)\), which shows that the time cost depends mainly on the GNNs and the number of iterations. Moreover, the complexity of GCN [11] and GAT [12] are \(O(mp_{1}p)\) and \(O(np_{1}p+mp_{1})\), respectively.  
Obviously, the complexity of GRNN-0 is slightly lower than that of GAT, and the complexity of GRNN is \(\bar{k}\) times of GCN.  
The detailed GRNN algorithm is summarized in Algorithm 1.  
```
0: An undirected graph \(G\);  The matrix of node features \(X\);  The set of partially observed labels \(Y_{L_{t}}\);  The total layers \(K\) of the benchmark neural network;  The total iterations \(\bar{K}\) of the GRNN.
```
0: The set of labels \(Y_{U}\).  Initialization: \(\alpha\in[0,1]\); \(\beta\in[0,1]\); repeat  Compute \(H^{(0)}\) using Equation (4) with \(\alpha\); for\(k=1,2,\ldots,K-1\)do  Update \(\bar{H}^{(k)}\) base on Equation (5) with \(\beta\);  Update \(H^{(k)}\) base on Equation (6); endfor  Compute \(H^{(K)}\)(which is equivalent to \(g(X)\)) using Equation (7); until The classification loss is minimized according to Equation (8);  Compute \(\widetilde{Y}^{(0)}\) using Equation (11); for\(\bar{k}=1,2,\ldots,\bar{K}\)do repeat  Compute \(H^{(0)}\) using Equation (4) with \(\alpha\); for\(k=1,2,\ldots,K-1\)do  Update \(\widetilde{H}^{(k)}\) base on Equation (5) with \(\beta\);  Update \(H^{(k)}\) base on Equation (6); endfor  Compute \(H^{(K)}\)(which is equivalent to \(f^{(\bar{k})}(X)\)) using Equation (7); until The classification loss is minimized according to Equation (20);  Update \(\widetilde{Y}^{(k)}\) base on Equation (12); endfor return\(Y_{U}\)(which is the subset of \(\widetilde{Y}^{(\bar{K})}\)) ```  
**Algorithm 1** GRNN for semi-supervised node classification