Research map / Graph learning / Knowledge and temporal graphs
An Efficient Subgraph-Inferring Framework for 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 SubInfer, a distributed framework that trains and infers heterogeneous GNNs on meta-path-based graph partitions completed with top-degree global nodes, reducing time and memory versus full-graph inference.
Problem
Heterogeneous GNNs on large-scale graphs require training or inferring on the entire graph, leading to prohibitive time and memory overhead, and existing partition methods ignore node/edge types and cause label-distribution skew between subgraphs.
Approach
Partition the meta-path semantic graph with Metis, greedily allocate remaining nodes to minimize lost edges, complete each subgraph with top-k degree nodes from the full graph to reduce label-distribution differences, batch subgraphs across meta-paths, and run training and inference per subgraph in a distributed setting.
Key results
- On Ogbn-mag, SubInfer-RGAT reduces inference time from 51s to 10s and memory from 31.9G to 11.3G, with test accuracy 48.13 vs 49.66 for R-GAT.
- On DBLP, SubInfer-NARS uses about 8-9% of NARS memory (e.g., 9.4G vs 107G training memory) with accuracy 53.21 vs 54.70.
- Ablation on Ogbn-mag shows meta-path partitioning plus completion raises test accuracy from 35.07 (Metis only) to 48.13.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train and infer with SubInfer-SeHGNN rather than SeHGNN on Ogbn-mag | SeHGNN · Ogbn-mag | accuracy: 56.45 -> 54.03 | Hurt |
| Train and infer with SubInfer-SeHGNN rather than SeHGNN on DBLP | SeHGNN · DBLP | accuracy: 58.12 -> 62.39 | Helped |
| Train and infer with SubInfer-SeHGNN rather than SeHGNN on Freebase | SeHGNN · Freebase | accuracy: 66.59 -> 66.45 | Hurt |
| Propagate messages on subgraphs with SubInfer-NARS rather than NARS | NARS · DBLP link prediction | AUC: 58.55 -> 56.78 | Hurt |
| Propagate messages on subgraphs with SubInfer-NARS rather than NARS | NARS · PubMed link prediction | AUC: 67.09 -> 65.34 | Hurt |
| Propagate messages on subgraphs with SubInfer-SeHGNN rather than SeHGNN | SeHGNN · Yelp link prediction | AUC: 75.02 -> 71.31 | Hurt |
| Add global-information completion to Metis-partitioned subgraphs (ablation) | RGAT on Ogbn-mag · Ogbn-mag | test accuracy: 35.07 -> 47.08 | Helped |
| Replace Metis partitioning with random partitioning (ablation) | RGAT with completion on Ogbn-mag · Ogbn-mag | test accuracy: 47.08 -> 39.40 | Hurt |
| Partition with meta-paths instead of Metis, retaining global-information completion (ablation) | RGAT on Ogbn-mag · Ogbn-mag | test accuracy: 47.08 -> 48.13 | Helped |
Surprising findings
- SubInfer-SeHGNN outperforms SeHGNN on DBLP (62.39 vs 58.12 accuracy), which the authors attribute to label-heterogeneity noise being mitigated by partitioning.
Limitations
- Partition-based methods cannot handle link prediction directly because edge endpoints may fall in different subgraphs; SubInfer required decoupled-method adaptations for link prediction.
- Accuracy drops relative to full-graph inference in several settings (e.g., Ogbn-mag, R-GAT 49.66 vs 48.13), and performance declines as the number of partitions grows.
Experimental setup
Datasets: Ogbn-mag DBLP PubMed Yelp Freebase
Benchmarks: Ogbn-mag DBLP Freebase PubMed Yelp
Metrics: accuracy AUC precision runtime memory
Baselines: R-GCN R-GAT R-GraphSAGE R-GraphSAINT R-GSN R-HGNN Cluster-RGCN NARS SeHGNN
Builds on: Metis Cluster-GCN R-GCN NARS SeHGNN
Closest papers by meaning
- Bootstrapping Heterogeneous Graph Representation Learning via Large Language Models: A Generalized Approach (AAAI 2025 · similarity 0.90)
- Translating Subgraphs to Nodes Makes Simple GNNs Strong and Efficient for Subgraph Representation Learning (ICML 2024 · similarity 0.90)
- Subgraph Invariant Learning Towards Large-Scale Graph Node Classification (AAAI 2025 · similarity 0.89)
- Heterogeneous Graph Neural Network on Semantic Tree (AAAI 2025 · similarity 0.89)
- A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening (NeurIPS 2024 · similarity 0.89)
- HeterSEED: Semantics–Structure Decoupling for Heterogeneous Graph Learning under Heterophily (NeurIPS 2026 · similarity 0.88)
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.