用更少计算量实现图核的高效表达,提升大规模图学习性能。
Simplifying Graph Kernels for Efficient
- 用K步消息聚合替代深层堆叠,避免重复计算。
- 在标准数据集上达到可比准确率,运行时间显著降低。
- 适合需要高效图学习的工业级应用场景。
核方法与图神经网络各有优势,但融合面临效率与可扩展性挑战。图神经正切核从神经正切核视角解释了GNN,但依赖深层堆叠导致重复计算。本文提出简化图核,以$K$步消息聚合取代深层堆叠,消除层间迭代传播,使框架更简洁高效,且不损失图任务表达能力。此外,基于高斯过程理论,提出另一简化图核,通过分析非线性激活在无限宽度下的统计行为,解析计算核值,无需显式模拟网络深度,进一步降低复杂度。在标准图分类与节点分类基准测试中,该方法在保持竞争力准确率的同时显著缩短运行时间,适用于大规模图学习。完整代码与可复现材料见:https://anonymous.4open.science/r/SGNK-1CE4/。
原文摘要 · Abstract (English)
While kernel methods and Graph Neural Networks offer complementary strengths, integrating the two has posed challenges in efficiency and scalability. The Graph Neural Tangent Kernel provides a theoretical bridge by interpreting GNNs through the lens of neural tangent kernels. However, its reliance on deep, stacked layers introduces repeated computations that hinder performance. In this work, we introduce a new perspective by designing the simplified graph kernel, which replaces deep layer stacking with a streamlined $K$-step message aggregation process. This formulation avoids iterative layer-wise propagation altogether, leading to a more concise and computationally efficient framework without sacrificing the expressive power needed for graph tasks. Beyond this simplification, we propose another Simplified Graph Kernel, which draws from Gaussian Process theory to model infinite-width GNNs. Rather than simulating network depth, this kernel analytically computes kernel values based on the statistical behavior of nonlinear activations in the infinite limit. This eliminates the need for explicit architecture simulation, further reducing complexity. Our experiments on standard graph and node classification benchmarks show that our methods achieve competitive accuracy while reducing runtime. This makes them practical alternatives for learning on graphs at scale. Full implementation and reproducibility materials are provided at: https://anonymous.4open.science/r/SGNK-1CE4/.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。