Research map / Graph learning / Graph algorithms and clustering
Long-range Meta-path Search on Large-scale Heterogeneous 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 LMSPS, an MLP-based meta-path search framework that uses progressive sampling and sampling-based evaluation to pick a constant number (30) of effective long-range meta-paths for heterogeneous graph node classification.
Problem
Utilizing long-range dependencies on large-scale heterogeneous graphs is hard because the number of meta-paths grows exponentially with maximum hop, raising cost and over-smoothing/noise issues.
Approach
Build a search space of all target-related meta-paths, shrink it progressively via Gumbel-softmax path strengths while sampling only M paths per iteration (search cost independent of hop count), then select the best M-path set by repeatedly sampling subsets and evaluating validation loss, and retrain an MLP-only target net on those paths.
Key results
- LMSPS reaches 54.83% test accuracy on OGBN-MAG versus 51.45% for the best competitor (SeHGNN), and 95.66% Micro-F1 on DBLP.
- On sparsified OGBN-MAG-5, LMSPS improves over SeHGNN by 4.78 points (40.82 vs 36.04 test accuracy).
- Replacing HAN's and SeHGNN's meta-paths with LMSPS-searched ones improves Micro-F1 (e.g., SeHGNN on Freebase 63.41 to 65.37).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use LMSPS instead of SeHGNN | OGBN-MAG · OGBN-MAG | Test accuracy: 51.45±0.29 -> 54.83±0.20 | Helped |
| use LMSPS instead of SlotGAT | LMSPS · DBLP | Macro-F1: 94.95±0.20 -> 95.35±0.22 | Helped |
| use LMSPS instead of SeHGNN | LMSPS · DBLP | Micro-F1: 95.24±0.13 -> 95.66±0.20 | Helped |
| use LMSPS instead of SeHGNN | LMSPS · IMDB | Macro-F1: 66.63±0.34 -> 66.99±0.32 | Helped |
| use LMSPS instead of SlotGAT | LMSPS · IMDB | Micro-F1: 68.64±0.33 -> 68.70±0.26 | No clear effect |
| use LMSPS instead of SlotGAT | LMSPS · ACM | Macro-F1: 93.99±0.23 -> 94.73±0.41 | Helped |
| use LMSPS instead of SlotGAT | LMSPS · Freebase | Micro-F1: 66.83±0.30 -> 66.09±0.51 | Hurt |
| add progressive sampling (ablation) | LMSPS · OGBN-MAG | Test accuracy: 47.66 ± 0.45 -> 54.83±0.20 | Helped |
| add progressive sampling (ablation) | LMSPS · DBLP | Micro-F1: 95.00±0.19 -> 95.66±0.20 | Helped |
| add sampling evaluation (ablation) | LMSPS · OGBN-MAG | Test accuracy: 52.94 ± 0.34 -> 54.83±0.20 | Helped |
| add sampling evaluation (ablation) | LMSPS · DBLP | Micro-F1: 95.48±0.24 -> 95.66±0.20 | Helped |
| replace concatenation with transformer and use all meta-paths (ablation) | LMSPS · IMDB | Micro-F1: 68.58±0.34 -> 68.70±0.26 | Hurt |
Surprising findings
- Removing certain meta-paths (e.g., PC and PCP on ACM) improved SeHGNN's Micro-F1 by about 0.52%, suggesting some meta-paths are harmful.
- Transformer-based semantic attention over all meta-paths performed slightly worse than the searched MLP-based fusion and ran out of memory on larger datasets.
Limitations
- Evaluated only on node classification in the transductive setting; other downstream tasks left as future work.
- Search space and number of selected meta-paths (M=30, V=2M) are fixed hyperparameters chosen per dataset rather than adaptively determined.
Experimental setup
Datasets: DBLP IMDB ACM Freebase OGBN-MAG
Benchmarks: DBLP IMDB ACM Freebase OGBN-MAG
Metrics: Macro-F1 Micro-F1 test accuracy
Baselines: MLP GraphSAGE RGCN HAN GTN HGT Simple-HGN SeHGNN NARS PMMM DiffMG HINormer
Builds on: SeHGNN DARTS SPOS HGB benchmark
Closest papers by meaning
- GraphMSE: Efficient Meta-path Selection in Semantically Aligned Feature Space for Graph Neural Networks (AAAI 2021 · similarity 0.87)
- Learning Long Range Dependencies on Graphs via Random Walks (ICLR 2025 · similarity 0.86)
- On Measuring Long-Range Interactions in Graph Neural Networks (ICML 2025 · similarity 0.86)
- Get a GRIP, this will be a long TRIP: A Quantifiable Long-Range Framework for Verifying Over-squashing (NeurIPS 2026 · similarity 0.85)
- Long Range Propagation on Continuous-Time Dynamic Graphs (ICML 2024 · similarity 0.85)
- TMetaNet: Topological Meta-Learning Framework for Dynamic Link Prediction (ICML 2025 · similarity 0.84)
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.