Learning to Approximate Adaptive Kernel Convolution on Graphs

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

Introduction

Graph Neural Networks (GNNs) have become the standard for processing non-Euclidean data. However, traditional GNN architectures like Graph Convolutional Networks (GCNs) suffer from a fundamental limitation: oversmoothing. As layers are stacked to capture long-range dependencies, node features tend to converge, losing their discriminative power. This issue stems from a "one-size-fits-all" approach to neighborhood connectivity, where the receptive field is fixed across the entire graph.

The LSAP Framework

To address this, we present LSAP (Learning Scales via APproximation), a framework that treats the neighborhood "scale" as a learnable parameter for every individual node. Instead of relying on a fixed adjacency matrix, LSAP utilizes the heat kernel ($e^{-s\lambda}$) to define information flow.

Overview of the LSAP architecture, showing the forward-propagation of features through approximated convolution layers and the back-propagation of gradients to update node-specific scales $s$ and network weights $W_k$.

The core technical innovation lies in the use of polynomial approximations (Chebyshev, Hermite, and Laguerre) to avoid the computationally prohibitive eigendecomposition of the graph Laplacian. By deriving closed-form derivatives for these polynomial coefficients with respect to the scale parameter ($s$), LSAP enables the model to optimize the receptive field of each node through standard backpropagation.

Computational Efficiency

A primary advantage of LSAP is its scalability. While exact spectral methods provide a theoretical baseline, they are often too slow for large-scale graphs. LSAP's polynomial approximation provides a "good enough" representation of the heat kernel at a fraction of the cost.

Comparison of computation time (ms) per epoch between the "Exact" spectral method and LSAP variants (C, H, L) across four datasets. LSAP consistently achieves significant speedups, particularly on larger datasets like Pubmed.

As shown in our benchmarks, LSAP is approximately 93% faster per epoch than exact methods on the Pubmed dataset while maintaining or exceeding classification accuracy.

Experimental Results

LSAP was evaluated on standard citation benchmarks and a real-world medical dataset from the Alzheimer’s Disease Neuroimaging Initiative (ADNI).

  • Node Classification: LSAP-C (Chebyshev) achieved an accuracy of 87.90% on the Cora dataset, significantly outperforming vanilla GCN (81.50%) and GCNII (85.50%).
  • Medical AI: On the ADNI dataset, LSAP reached ~90% accuracy in classifying Alzheimer's stages. Beyond performance, the model offered interpretability; the learned scales highlighted brain regions like the precuneus, which are clinically recognized as relevant to disease progression.

Conclusion

LSAP provides a robust solution to the oversmoothing problem by enabling node-wise adaptive connectivity. By combining the theoretical strengths of spectral diffusion with the practical efficiency of polynomial approximation, it offers a scalable and interpretable approach for complex graph-based tasks. Future work will focus on further optimizing the selection of polynomial types and scaling to massive graphs with millions of nodes.

Summary updated

Abstract

Various Graph Neural Networks (GNN) 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