Research map / Graph learning / GNN architectures
Learning to Approximate Adaptive Kernel Convolution on Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LSAP, a GNN that learns a per-node diffusion (heat kernel) scale via closed-form gradients of polynomial approximation coefficients, avoiding eigendecomposition, and evaluates on citation/co-purchase benchmarks and ADNI brain-network classification.
Problem
Oversmoothing in GCNs arises because every layer aggregates from direct neighbors uniformly across all nodes; existing diffusion-kernel GNNs need costly Laplacian diagonalization or large learned transform matrices, and use a single global scale.
Approach
Approximates heat kernel convolution with orthogonal polynomials (Chebyshev, Hermite, Laguerre) and derives closed-form derivatives of the expansion coefficients with respect to a learnable node-wise scale, so each node's aggregation range is trained end-to-end by backpropagation without diagonalization.
Key results
- LSAP-C reaches 87.90% accuracy on Cora, 76.50% on Citeseer, and LSAP-L reaches 84.10% on Pubmed, outperforming listed baselines (by 2.4% on Cora per the text).
- On ADNI FDG features, LSAP-L achieves 90.40% accuracy for 5-way AD stage classification versus 88.60% for the best baseline ADC.
- LSAP-L cuts per-epoch time by about 93% relative to exact heat kernel computation on ADNI.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace uniform neighborhood aggregation with learned node-wise adaptive heat-kernel scales | LSAP versus conventional baselines · Cora, Citeseer, Pubmed | accuracy: 87.90 vs. 85.50; 76.50 vs. 75.40; 84.10 vs. 83.00 | Helped |
| Use polynomial approximation instead of exact heat-kernel computation | LSAP · Cora, Citeseer, Pubmed and ADNI | accuracy: 87.90 vs. 88.20; 76.50 vs. 78.10; 84.10 vs. 85.30; 90.40 ± 1.38 vs. 90.18 ± 2.67 | Mixed |
| Use Chebyshev rather than Hermite or Laguerre approximation | LSAP · Cora and Citeseer | accuracy: 87.90 vs. 85.00; 76.50 vs. 76.10 | Helped |
| Use Laguerre rather than Chebyshev or Hermite approximation | LSAP · Pubmed and ADNI FDG | accuracy: 84.10 vs. 83.30 and 82.60; 90.40 ± 1.38 vs. 89.24 ± 2.23 and 90.11 ± 2.44 | Helped |
| Use Hermite rather than Chebyshev or Laguerre approximation | LSAP · Amazon Photo | accuracy: 96.65 ± 0.67 vs. 95.96 ± 1.65 and 95.35 ± 0.85 | Helped |
| Use Chebyshev rather than Hermite or Laguerre approximation | LSAP · Amazon Computer and Coauthor CS | accuracy: 94.43 ± 1.16 vs. 93.64 ± 0.86 and 92.76 ± 0.48; 94.81 ± 0.55 vs. 93.52 ± 0.97 and 93.58 ± 0.82 | Mixed |
| Vary the number of convolution layers from 2 to 3 or 4 (ablation) | LSAP · Cora and ADNI | accuracy | Hurt |
| Increase convolution depth from 1 to 2 layers (ablation) | LSAP · Cora and ADNI | accuracy | Helped |
Surprising findings
- Approximations (LSAP) sometimes match or outperform the exact heat kernel computation on several benchmarks, e.g., LSAP-C beats Exact on Amazon Computers (94.43 vs 93.52 mean accuracy).
Limitations
- Training takes longer than conventional uniform-convolution GNNs because per-node scales must be learned.
- Graph classification assumes a fixed node set across graphs.
- Memory complexity of building the polynomial basis is O(N^2).
Experimental setup
Datasets: Cora Citeseer Pubmed Amazon Computers Amazon Photo Coauthor CS ADNI
Benchmarks: Cora Citeseer Pubmed Amazon Computers Amazon Photo Coauthor CS ADNI
Metrics: accuracy precision recall training time per epoch
Baselines: GCN GAT APPNP GDC SGC GraphHeat GCNII GRAND DAGNN ADC 3ference DSF
Builds on: GraphHeat GCN Chebyshev polynomial approximation ADC
Closest papers by meaning
- Diffusion Improves Graph Learning (NeurIPS 2019 · similarity 0.91)
- A Generalized Neural Diffusion Framework on Graphs (AAAI 2024 · similarity 0.88)
- Neurodegenerative Brain Network Classification via Adaptive Diffusion with Temporal Regularization (ICML 2024 · similarity 0.88)
- Diffusing to the Top: Boost Graph Neural Networks with Minimal Hyperparameter Tuning (ICLR 2025 · similarity 0.88)
- SDMG: Smoothing Your Diffusion Models for Powerful Graph Representation Learning (ICML 2025 · similarity 0.87)
- How Graph Neural Networks Learn: Lessons from Training Dynamics (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.