## 3 Proposed Method
### Graph Convolutional Network Clustering (GCNC)
At each step, we sample a cluster \(V_{t}\) and the conduct SGD to update based on the gradient of \(L_{\overline{A}^{\prime}_{tt}}\) and this only requires the subgraph \(A_{tt}\), the \(X_{t}\), and the \(Y_{t}\) on the current batch models \(\left\{w^{l}\right\}_{l=1}^{L}\). Compared to the neighbourhood search strategy employed in earlier SGD-based training methods, the implementation merely calls for matrix components' forward and retrograde transmission (one block of (5)). As previously mentioned, the embedding utilisation is similar to the within-cluster linkages for each; therefore, these are exactly what we require. (1) Assuming that each node and its neighbours are often found in the same cluster, neighbourhood nodes have a high probability of remaining in the same cluster after a few hops. (2) We need to design a partition to reduce the number of between-cluster links since we replace A with its block diagonal approximation A and the error is proportional to those links. Each node in \(v_{t}\) of \(A_{tt}\) only links to other nodes inside of \(v_{t}\). Each batch's computation will only involve matrix products \(\overline{A}^{\prime}_{tt}X^{(l)}_{t}w^{(l)}\) and a few element-wise operations; thus the  
Figure 4: The distinction between our suggested cluster technique and conventional graph convolution is the neighbourhood expansion. The extension of neighbourhood nodes begins at the red node. The growing convolution suffers from hyperbolic neighbourhood growth; however, our technique can stop expensive neighbourhood expansion. total computation time is \(O\big{(}\big{\|}A_{H}\big{\|}_{0}F+bF^{2}\big{)}\). As a result, \(O\big{(}\big{\|}A\big{\|}_{0}F+NF^{2}\big{)}\) is the overall temporal complexity per epoch. On average, each batch only needs to compute \(O(bL)\) embeddings, which is exponential to \(L\) rather than linear. For embedding storage, we simply must load b examples per batch, and the per layer's extracted features are saved using \(O(bLF)\) memory. Boost Graph Convolutional Network Clustering (BGCNC)  
To achieve good computational and memory complexity, two potential concerns still exist:  
* Certain links (the part in \(\Delta\) Equation (2)) are eliminated from the graph after it has been partitioned. As a result, the performance can be impacted. * Algorithms for graph clustering frequently group related nodes together. As a result, a cluster's distribution may deviate from the original data set, which could cause a skewed estimation of the complete gradient while doing SGD updates. Based on the label distribution of each cluster, we determine its entropy value. When compared to random partitioning, it is evident that most clusters have lower entropies, which suggests that the label distributions of the clusters are skewed towards particular labels. This raises the variance between batches and could have an impact on SGD convergence [32]. We suggest a stochastic multiple clustering strategy to incorporate between-cluster linkages and lessen volatility across batches in order to overcome the aforementioned problems. Then, we divide the graph into \(p\) clusters \(V_{1}\dots\dots\dots V_{p}\) using a sizable \(p\). Instead of taking into account just one cluster while building a batch B for an SGD update, we pick q clusters at random, denoted as \(t_{1},\dots\dots\dots t_{q}\) and add their nodes as part of the batch using the notation \(\Big{\{}V_{t_{1}}\cup\dots\dots\cup V_{t_{q}}\Big{\}}\). Moreover, the connections between the selected clusters are re-added. \[\big{\{}A_{ij}\big{|}i,j\in t_{1},\dots\dots t_{q}\big{\}} \tag{6}\]  
In this way, the cluster combinations reduce the variance between batches and reintegrate the between-cluster linkages. Algorithm 1 presents our final Boost Graph Convolutional Network Clustering Technique.