## 3 Clustering via Adaptive Graph Convolution Using Heat Kernel
### Adaptive Graph Convolution Using Heat Kernel
#### 3.2.4 Architecture and Algorithm  
Based on the design and analysis of the previous chapter, we summarize the proposed AGCHK algorithm as follows. Firstly, we construct a low-pass filter based on the heat kernel, which is defined as \(\left(I+e^{-sL}\right)^{k}\), where \(k=1\). Next, we exploit the low-pass filter to filter the original graph signals to obtain a smoother graph representation. Then, we can obtain the left singular vectors \(U\) of \(\overline{X}^{k}\) by the singular value decomposition and perform \(k\)-means on \(U\) 10 times, getting the cluster partition \(C^{k}\). Finally, we calculate the DBI of the cluster partition \(C^{k}\); if the DBI decreases, we set \(k=k+1\) and continue the above loop, else, we stop the loop, and the final cluster partition is \(C^{k}\). Figure 4 is the architecture of the novel AGCHK model. Algorithm 1 describes in detail the algorithm of obtaining the better cluster partition by performing AGCHK. We utilize the low-pass filter based on heat kernel in the adaptive graph convolution architecture to enhance the smoothness of the graph representation, which can adaptively determine the order of graph convolution and does not require training parameters, unlike the other methods based on graph neural network [4; 5; 6].  
Figure 4: The architecture of proposed adaptive graph convolution using heat kernel model for attributed graph clustering (AGCHK).  
Figure 3: Spectral clustering visualization of \(k\)-order graph convolution for dataset Cora. Colors of different nodes represent various labels, and the representation of nodes with the same label is closer as the value of \(k\) increases. Low-order graph convolution makes node features indistinguishable, while high-order graph convolution might cause node features over-smoothing.  
```
Input: Node features \(\mathbf{X}\), adjacency matrix \(\mathbf{A}\), and maximum iteration number \(max\_iter\). Output: Cluster partition \(\mathbf{C}\).
1. Initialize \(\mathbf{k}=0\), \(\mathbf{rep}=0\), \(\mathbf{REP}=10\), Compute the normalized graph Laplacian \(\mathbf{L}=\mathbf{I}_{N}-\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}\).
2. Compute graph filter \(\mathbf{I}+e^{-\mathbf{s}\mathbf{L}}\).
3. repeat
4. Set \(\mathbf{k}=\mathbf{k}+1\).
5. Calculate \(\mathbf{k}\)-order graph convolution by Equation (11) and obtain filtered features \(\mathbf{\overline{X}}^{\mathbf{k}}\).
6. \(\mathbf{\overline{X}}^{\mathbf{k}}=\mathbf{normalize}\mathbf{\overline{X}}^{\mathbf{k}}\).
7. Obtain the left singular vectors \(\mathbf{U}\)_of \(\mathbf{\overline{X}}^{\mathbf{k}}\)_ by SVD.
8. repeat
9. Set \(\mathbf{rep}=\mathbf{rep}+1\)
10. Perform \(\mathbf{k}\)-means on \(\mathbf{U}\) and obtain clustering partition \(\mathbf{C}^{\mathbf{k}}\).
11. Calculate \(\mathbf{DBI}\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{ }}}}}}}}}}}}}}(\mathbf{C}^{\mathbf{k}})\)\(|\mathbf{rep}|\) by Equation (12).
12. until\(\mathbf{rep}=\mathbf{REP}\)
13. Compute the mean of \(\mathbf{REP}\) partition scores \(\mathbf{DBI}\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{ }}}}}}}}}}}}}}(\mathbf{C}^{\mathbf{k}})\)\(|0:\mathbf{rep}|\).
14. until\(\mathbf{d\_DBI}\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{ \mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{ }}}}}}}}}}}}}}}}}(\mathbf{C} \mathbf{C}\mathbf{k})\)? or \(\mathbf{t}>\mathbf{max\_iter}\)
15. return final clustering partition \(\mathbf{C}^{\mathbf{k}}\).
```  
**Algorithm 1**AGCHK