Theory' Source code of "Constrained Heat Kernel Graph Diffusion Convolution: A High-Dimensional Statistical Approximation via Information Theory"

Graph neural networks have been widely applied in various domains, handling numerous entities with high-dimensional features. Their success largely stems from the powerful information prop-agation process. Among these networks, diffusion-based approaches, such as generalized graph diffusion convolution, have extended conventional immediate neighborhood aggregation function to a diffusion process based on Newton’s law of cooling. Despite substantial improvements in model performance, the diffusion time is obtained by either grid search or complex bi-level optimization on train sets and validation sets. Furthermore, these methods do not provide explicit explanations for the obtained diffusion time from the specific graph data. To address these issues, we propose the Constrained Heat Kernel Graph Diffusion to estimate the appropriate diffusion time based on information theory and moments. By conceptualizing the graph as a communication network, we approximate the diffusion process as the transmission and reception of graph signal over noisy channels bounded by the channel capacity. Our method demonstrates consistent performance improvements in downstream graph-mining tasks across six public datasets, offering a principled framework and faster approximation method for the diffusion time. The results from the ablation study further validate the effectiveness of the proposed method.