提出WLKS方法，用多跳邻域提升子图表示学习效果。
Generalizing Weisfeiler-Lehman Kernels to Subgraphs
- 在诱导k跳邻域上应用WL算法，捕捉子图内外复杂交互
- 在8个数据集上5个超越领先方法，训练时间降至0.01~0.25倍
- 无需邻域采样，兼顾表达力与计算效率，适合子图分类任务
子图表示学习在解决各类现实问题中表现有效。然而，当前图神经网络（GNNs）因无法充分捕捉子图内及子图间的复杂交互，导致子图级别任务性能欠佳。为提供更具表达力且高效的方法，我们提出WLKS——一种将Weisfeiler-Lehman（WL）核推广至子图的新方法，通过在诱导k跳邻域上应用WL算法实现。通过融合不同k跳层级的核，捕获现有模型未充分编码的丰富结构信息。该方法可通过避免邻域采样，在表达力与效率间取得平衡。在八个真实世界与合成基准上的实验表明，WLKS在五个数据集上显著优于领先方法，同时训练时间减少至最先进方法的0.01至0.25倍。
原文摘要 · Abstract (English)
Subgraph representation learning has been effective in solving various real-world problems. However, current graph neural networks (GNNs) produce suboptimal results for subgraph-level tasks due to their inability to capture complex interactions within and between subgraphs. To provide a more expressive and efficient alternative, we propose WLKS, a Weisfeiler-Lehman (WL) kernel generalized for subgraphs by applying the WL algorithm on induced $k$-hop neighborhoods. We combine kernels across different $k$-hop levels to capture richer structural information that is not fully encoded in existing models. Our approach can balance expressiveness and efficiency by eliminating the need for neighborhood sampling. In experiments on eight real-world and synthetic benchmarks, WLKS significantly outperforms leading approaches on five datasets while reducing training time, ranging from 0.01x to 0.25x compared to the state-of-the-art.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。