Learning to Approximate Adaptive Kernel Convolution on Graphs

Jaeyoon Sim, Sooyeon Jeon, Injun Choi, Guorong Wu, Won Hwa Kim

Abstract

Various Graph Neural Networks (GNNs) have been successful in analyzing data in non-Euclidean spaces; however, they face limitations such as oversmoothing, where information becomes excessively averaged as the number of hidden layers increases. This issue stems from the intrinsic formulation of conventional graph convolution, where nodal features are aggregated from a direct neighborhood across all nodes. As setting a different number of hidden layers per node is infeasible, recent works leverage diffusion kernels to redefine graph structure and incorporate information from farther nodes. Unfortunately, such approaches suffer from heavy diagonalization of a graph Laplacian or learning a large transform matrix. We propose LSAP (Learning Scales via APproximation), a diffusion learning framework where the range of feature aggregation is controlled by the scale of a diffusion kernel. By deriving closed-form derivatives of polynomial approximations of the graph convolution with respect to the scale, node-wise ranges can be adaptively learned. Our model achieves state-of-the-art performance on standard node classification benchmarks and demonstrates practical utility in Alzheimer’s classification using real-world brain network data.

The Challenge of Oversmoothing in GNNs

Standard Graph Convolutional Networks (GCNs) typically employ a "one-size-fits-all" approach to feature aggregation. In each layer, every node aggregates information from its immediate neighbors. As layers are stacked to capture long-range relationships, the features of all nodes tend to converge toward a generic mean—a phenomenon known as oversmoothing.

Ideally, a GNN should be flexible: some nodes may require high-frequency local information, while others benefit from low-frequency global context. However, manually assigning unique neighborhood sizes (scales) to every node is computationally prohibitive. While heat diffusion kernels offer a mathematical way to model information flow over varying distances, their implementation traditionally requires expensive matrix diagonalization ($O(N^3)$), which does not scale to large graphs.

LSAP: Learning Scales via Approximation

The LSAP framework introduces a computationally efficient method to learn unique aggregation scales for every node in a graph. The core methodology relies on three pillars:

  1. Heat Kernel Convolution: Instead of simple neighbor summation, LSAP utilizes a heat diffusion kernel with a scale parameter ($s$) that dictates the reach of information propagation.
  2. Polynomial Approximation: To bypass the cost of eigendecomposition, the heat kernel is approximated using orthogonal polynomials—specifically Chebyshev, Hermite, and Laguerre polynomials.
  3. Differentiable Node-wise Scales: The researchers derived closed-form derivatives for these polynomial coefficients with respect to the scale $s$. This allows the optimal scale for each node to be learned via standard backpropagation alongside the network weights ($W_k$).
LSAP Architecture: The framework learns node-wise scales (s) through backpropagation using closed-form derivatives of polynomial approximations.

Experimental Results and Efficiency

LSAP was evaluated on semi-supervised node classification (Cora, Citeseer, Pubmed) and graph classification for medical diagnosis (ADNI dataset).

  • Performance: The Chebyshev variant (LSAP-C) achieved 87.9% accuracy on Cora, outperforming established models like GCNII and GRAND. On the ADNI dataset, LSAP achieved ~90% accuracy in classifying the five stages of Alzheimer’s, surpassing the best baseline by 1.8%.
  • Computational Speed: By avoiding eigendecomposition, LSAP-L (Laguerre) was approximately 93% faster than "Exact" diffusion methods on the ADNI dataset. The polynomial approximations proved to be highly accurate, performing nearly identically to exact methods while maintaining significantly lower latency.

Neuroscientific Interpretability

A significant advantage of LSAP is its inherent interpretability. When applied to brain networks derived from MRI and PET scans, the model's learned scales provided a spatial map of disease relevance.

Interpretability in Alzheimer’s diagnosis: Learned scales on brain regions align with clinical literature, showing local informative regions.

The model assigned significantly smaller scales to specific regions such as the precuneus and inferior frontal orbital gyrus. This indicates that the model found these localized regions highly informative for Alzheimer’s diagnosis, a finding that aligns closely with established clinical literature. This "Aha!" moment demonstrates that LSAP does not just predict outcomes but also highlights the biological features driving those predictions.

Conclusion and Future Directions

LSAP successfully addresses the oversmoothing problem by enabling node-wise adaptive scaling through efficient polynomial approximations. While it introduces a slight training overhead compared to vanilla GCNs due to the additional $N$ scale parameters, the gains in accuracy and interpretability are substantial. Future work will focus on adapting the framework for graphs with varying topologies and scaling the node-wise optimization to billion-node industrial graphs.

Summary updated

Abstract

Various Graph Neural Networks (GNNs) have been successful in analyzing data in non-Euclidean spaces, however, they have limitations such as oversmoothing, i.e., information becomes excessively averaged as the number of hidden layers increases. The issue stems from the intrinsic formulation of conventional graph convolution where the nodal features are aggregated from a direct neighborhood per layer across the entire nodes in the graph. As setting different number of hidden layers per node is infeasible, recent works leverage a diffusion kernel to redefine the graph structure and incorporate information from farther nodes. Unfortunately, such approaches suffer from heavy diagonalization of a graph Laplacian or learning a large transform matrix. In this regards, we propose a diffusion learning framework, where the range of feature aggregation is controlled by the scale of a diffusion kernel. For efficient computation, we derive closed-form derivatives of approximations of the graph convolution with respect to the scale, so that node-wise range can be adaptively learned. With a downstream classifier, the entire framework is made trainable in an end-to-end manner. Our model is tested on various standard datasets for node-wise classification for the state-of-the-art performance, and it is also validated on a real-world brain network data for graph classifications to demonstrate its practicality for Alzheimer classification.
BibTeX
@inproceedings{sim2024learning,
  author = {Jaeyoon Sim and Sooyeon Jeon and Injun Choi and Guorong Wu and Won Hwa Kim},
  title = {{Learning to Approximate Adaptive Kernel Convolution on Graphs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i5.28291},
}
Figure