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:
- 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.
- Polynomial Approximation: To bypass the cost of eigendecomposition, the heat kernel is approximated using orthogonal polynomials—specifically Chebyshev, Hermite, and Laguerre polynomials.
- 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$).
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.
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