Research map / Graph learning / GNN architectures
From Theory to Practice: Rethinking Green and Martin Kernels for Unleashing Graph Transformers
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.
Introduces Green- and Martin-kernel-based structural encodings (GKSE, MKSE), redefined with finite-step random walk quantities, and plugs them into GRIT to improve graph transformer performance on molecular and circuit benchmarks.
Problem
Graph Transformers depend on structural encodings for inductive bias, but existing random-walk encodings (RRWP) are unstable on non-aperiodic substructures and sparse on DAGs; classical Green and Martin kernels are ill-defined for recurrent finite graphs.
Approach
Redefine Green and Martin kernels as finite-step quantities (expected visits within k steps; probability of returning within k steps via first-return time), compute them recursively, and use them as relative and absolute structural encodings in GRIT.
Key results
- GRIT+GKSE reaches MAE 0.0837 on PCQM4Mv2 versus 0.0859 for GRIT+RRWP (single-run baseline reported).
- GRIT+MKSE reaches 77.365% on CIFAR10 and 0.056 MAE on ZINC, both state-of-the-art among the compared models.
- GRIT+GKSE gives MAE 0.0395 on Ckt-Bench101 versus 0.0418 for GRIT+RRWP, and 0.2452 on Peptides-struct versus 0.2460 for RRWP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace RRWP with GKSE | GRIT · ZINC test | MAE: 0.059 ± 0.001 -> 0.058 ± 0.002 | Helped |
| Replace RRWP with MKSE | GRIT · ZINC test | MAE: 0.059 ± 0.001 -> 0.056 ± 0.021 | Helped |
| Replace RRWP with GKSE | GRIT · MNIST test | accuracy: 98.108 ± 0.111 -> 98.305 ± 0.125 | Helped |
| Replace RRWP with MKSE | GRIT · CIFAR10 test | accuracy: 76.468 ± 0.881 -> 77.365 ± 0.640 | Helped |
| Replace RRWP with GKSE | GRIT · Peptides-func test | AP: 0.6988 ± 0.0082 -> 0.6976 ± 0.0097 | No clear effect |
| Replace RRWP with MKSE | GRIT · Peptides-func test | AP: 0.6988 ± 0.0082 -> 0.6784 ± 0.0057 | Hurt |
| Replace RRWP with GKSE | GRIT · Peptides-struct test | MAE: 0.2460 ± 0.0012 -> 0.2452 ± 0.0012 | Helped |
| Replace RRWP with MKSE | GRIT · Peptides-struct test | MAE: 0.2460 ± 0.0012 -> 0.2457 ± 0.0013 | Helped |
| Replace GPS-medium with GKSE | GRIT · PCQM4Mv2 test | MAE: 0.0858 -> 0.0837 ± 0.0002 | Helped |
| Replace RRWP with GKSE | GRIT · Ckt-Bench101 test | MAE: 0.0418 ± 0.0021 -> 0.0395 ± 0.0033 | Helped |
| Replace RRWP with MKSE | GRIT · Ckt-Bench101 test | MAE: 0.0418 ± 0.0021 -> 0.0409 ± 0.0016 | Helped |
| Replace RRWP with GKSE | GRIT · Ckt-Bench301 test | MAE: 0.0190 ± 0.0005 -> 0.0188 ± 0.0004 | Helped |
Surprising findings
- Theorem 4.3 shows MKSE is not constructible over RRWP, so it captures information RRWP cannot represent.
- RRWP produces hexagon- or star-shaped patterns that oscillate with parity on non-aperiodic molecular rings, which the authors attribute to periodicity.
Limitations
- Authors state experiments address only a limited set of cases, so the non-aperiodicity explanation is a hypothesis not confirmed.
- Gains over RRWP are often within reported standard deviations (e.g., ZINC, Peptides-func, CIFAR10).
- Hyperparameter exploration was skipped on PCQM4Mv2 due to time constraints.
Experimental setup
Datasets: ZINC MNIST CIFAR10 Peptides-func Peptides-struct PCQM4Mv2 Ckt-Bench101 Ckt-Bench301
Benchmarks: ZINC MNIST CIFAR10 Peptides-func Peptides-struct PCQM4Mv2 Ckt-Bench101 Ckt-Bench301
Metrics: MAE accuracy AP
Baselines: GRIT+RRWP GPS EGT PNA GatedGCN TokenGT Graphormer GRPE Specformer
Builds on: GRIT RRWP GraphGPS Generalized Distance Weisfeiler-Lehman
Closest papers by meaning
- Simple Path Structural Encoding for Graph Transformers (ICML 2025 · similarity 0.90)
- Homomorphism Counts as Structural Encodings for Graph Learning (ICLR 2025 · similarity 0.89)
- Generalizable Insights for Graph Transformers in Theory and Practice (NeurIPS 2025 · similarity 0.88)
- Learning Long Range Dependencies on Graphs via Random Walks (ICLR 2025 · similarity 0.88)
- Aligning Transformers with Weisfeiler-Leman (ICML 2024 · similarity 0.87)
- From Sequence to Structure: Uncovering Substructure Reasoning in Transformers (NeurIPS 2025 · 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.