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.
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.
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