## 3 Clustering via Adaptive Graph Convolution Using Heat Kernel
### Adaptive Graph Convolution Using Heat Kernel  
#### 3.2.1 Graph Convolution Using Heat Kernel  
We propose a novel graph convolution model based on heat kernel to enhance low-frequency signals and suppress high-frequency signals, which can capture the smoothness of node features or labels sufficiently [13]. The heat kernel is defined as  
\[f\big{(}\lambda_{q}\big{)}=e^{-s\lambda_{q}}, \tag{8}\]  
where the scaling parameter \(s>0\) determines the range of heat diffusion. The frequency response function based on heat kernel is defined as \(g_{\theta}=\sum_{p=0}^{P-1}\theta_{p}\Lambda_{s}^{p}\)[13], where \(\Lambda_{s}=diag\big{\{}e^{-s\lambda_{q}}\big{\}}_{q=1}^{N}\), and graph convolution via heat kernel denotes  
\[y=Ug_{\theta}U^{T}x=U(\sum_{p=0}^{P-1}\theta_{p}\Lambda_{s}^{p})U^{T}x=\sum_{p =0}^{P-1}\theta_{p}e^{-psL}x. \tag{9}\]To preserve the locality of graph convolution based on heat kernel and keep the tradeoff between low-pass performance and computational complexity, the frequency response function \(g\big{(}\lambda_{q}\big{)}=1+e^{-s\lambda_{q}}\) is obtained by setting \(P=2\), and the associated graph filter is  
\[y=\Big{(}I+e^{-sL}\Big{)}x. \tag{10}\]  
The above graph filter can preserve more low-frequency signals by assigning the weight \(e^{-s\lambda_{q}}\) to the basis signal \(u_{i}u_{i}^{T}\), and \(e^{-s\lambda_{q}}\) decreases exponentially as \(\lambda_{q}\) increases. Furthermore, for datasets with different node connection structures, we can dynamically regulate the allocation strategy of various basis signal weights by adjusting the scaling coefficient \(s\) of the heat kernel.  
From the perspective of heat diffusion, \(\left(e^{-sL}\right)_{ij}\) reflects the similarity metric, which captures the amount of energy from node \(v_{i}\) to node \(v_{j}\), and a target node \(v_{j}\) can be regarded as the neighboring node of the center node \(v_{i}\) when the similarity metric \(\left(e^{-sL}\right)_{ij}\) between nodes \(v_{i}\) and \(v_{j}\) is higher than the threshold \(\varepsilon\), which offers us a more flexible approach to define neighboring nodes of the center node and accelerates the computation by setting the threshold \(\varepsilon\). Figure 1 depicted by the Graph Signal Processing toolbox [14] illustrates that the range of heat diffusion controlled by the scaling parameter \(s\) becomes larger as \(s\) increases. Different from the graph convolution methods in Section 2.2, which constrain neighboring nodes via the shortest path distance, graph convolution based on heat kernel leverages a continuous manner to determine the neighborhood, which can utilize high-order neighbor nodes sufficiently and discard some irrelevant low-order neighbor nodes [13].  
Compared with the linear frequency response function \(g\big{(}\lambda_{q}\big{)}=1-\frac{1}{2}\lambda_{q}\) proposed in AGC [7], we leverage the exponential frequency function \(g\big{(}\lambda_{q}\big{)}=1+e^{-s\lambda_{q}}\) based on heat kernel, which highlights low-frequency signals exponentially to make the graph smoother. Figure 2 illustrates \(g\big{(}\lambda_{q}\big{)}=1+e^{-s\lambda_{q}}\) assigns larger weights to low-frequency basis signals compared with \(g\big{(}\lambda_{q}\big{)}=1-\frac{1}{2}\lambda_{q}\) so that connected nodes have more similar features, which indicates that graph convolution based on heat kernel might perform graph clustering better.  
Figure 1: Heat diffusion comparison as \(s\) increases on an example graph. The center node is represented in yellow, and the similarity between the neighbor nodes and the center node decreases as the node color becomes darker. The range of heat diffusion increases from a small scale (**a**) to a large scale (**b**).