Research map / Graph learning / GNN architectures
Generalizing Weisfeiler-Lehman Kernels to Subgraphs
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.
Generalizes the 1-WL graph kernel to subgraphs by running WL on induced k-hop neighborhoods, combining k=0 and k=diameter kernels, yielding a fast GPU-free subgraph classifier that beats GNN baselines on 5 of 8 benchmarks.
Problem
Subgraph-level classification with GNNs is suboptimal because they cannot capture complex interactions within and between subgraphs, and existing subgraph models are costly to train and need pre-computation or sampling.
Approach
Apply the WL algorithm to induced k-hop neighborhoods of each subgraph to form WL histogram kernels, linearly combine kernels across k, and restrict k to {0, diameter D} so that no neighborhood sampling is needed and WL runs once on the global graph for k=D.
Key results
- WLKS-{0,D} achieves the highest micro F1 on 5 of 8 datasets (e.g., Density 96.0, Coreness 91.3, Component 100.0), outperforming the best baselines on those datasets.
- Training time of WLKS-{0,D} is roughly 0.01x to 0.25x that of the state-of-the-art GNN baselines on real-world datasets (e.g., 3.5 s vs 16.7 s for S2N+0 on PPI-BP).
- Adding an RWSE inner-product kernel raises CutRatio performance from 60.0 to 96.0 for WLKS-{0,D}.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| combine k=0 and k=D kernels rather than use either alone (ablation) | WLKS · Coreness | micro F1-score: 87.0 -> 91.3; 39.1 -> 91.3 | Helped |
| combine k=0 and k=D kernels rather than use k=2 alone (ablation) | WLKS · PPIBP | micro F1-score: 64.2 -> 64.8 | No clear effect |
| add a continuous WL kernel on features (ablation) | WLKS-{0,D} · EMUser | micro F1-score: 91.8 -> 93.9 | Helped |
| add a continuous WL kernel on features (ablation) | WLKS-{0,D} · HPONeuro | micro F1-score: 65.3 -> 66.2 | Helped |
| add a continuous WL kernel on features (ablation) | WLKS-{0,D} · HPOMetab | micro F1-score: 57.9 -> 59.6 | Helped |
| add a continuous WL kernel on features (ablation) | WLKS-{0,D} · CutRatio | micro F1-score: 60.0 -> 64.0 | Helped |
| add a continuous WL kernel on features (ablation) | WLKS-{0,D} · Density | micro F1-score: 96.0 -> 96.0 | No clear effect |
| add an inner product kernel of Random Walk Structural Encoding (ablation) | WLKS-{0,D} · CutRatio | micro F1-score: 60.0 to 96.0 | Helped |
| add an inner product kernel of Random Walk Structural Encoding (ablation) | WLKS-{0,D} · other seven benchmarks | micro F1-score | No clear effect |
| apply GNNs to the WLKS kernel matrix as S2N+0 (ablation) | WLKS-{0,D} · CutRatio | micro F1-score: 60.0 -> 51.2 | Hurt |
| apply GNNs to the WLKS kernel matrix as S2N+A (ablation) | WLKS-{0,D} · HPONeuro | micro F1-score: 65.3 -> 68.4 | Helped |
| apply GNNs to the WLKS kernel matrix as S2N+A (ablation) | WLKS-{0,D} · CutRatio | micro F1-score: 60.0 -> 48.0 | Hurt |
Surprising findings
- Theoretically, WL histograms at k+1 hops are not strictly more expressive than at k hops, contrary to the intuition that larger neighborhoods always help.
- On PPI-BP, k=2 performs as well as k=D despite the largest component having diameter 8.
Limitations
- WL histogram lacks expressiveness on some tasks (e.g., CutRatio, HPO-Neuro, HPO-Metab) where WLKS trails the state-of-the-art.
- Integrating continuous node features into WLKS yields mixed gains; combining with GNNs requires kernel sparsification that loses structural information.
- Baseline results are reprinted from original papers rather than re-run under identical settings.
Experimental setup
Datasets: PPI-BP HPO-Neuro HPO-Metab EM-User Density CutRatio Coreness Component
Benchmarks: PPI-BP HPO-Neuro HPO-Metab EM-User Density CutRatio Coreness Component
Metrics: micro F1 training time (s) inference time (1 epoch)
Baselines: SubGNN GLASS VSubGAE SSNP-NN S2N+0 S2N+A
Builds on: Weisfeiler-Lehman graph kernel S2N (Subgraph-to-Node translation) GCNII
Closest papers by meaning
- Exploring Consistency in Graph Representations: from Graph Kernels to Graph Neural Networks (NeurIPS 2024 · similarity 0.88)
- Translating Subgraphs to Nodes Makes Simple GNNs Strong and Efficient for Subgraph Representation Learning (ICML 2024 · similarity 0.88)
- Weisfeiler-Leman at the margin: When more expressivity matters (ICML 2024 · similarity 0.88)
- Union Subgraph Neural Networks (AAAI 2024 · similarity 0.88)
- Subgraph Aggregation for Out-of-Distribution Generalization on Graphs (AAAI 2025 · similarity 0.87)
- A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening (NeurIPS 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.