Research map / Graph learning / Graph self-supervised learning
Translating Subgraphs to Nodes Makes Simple GNNs Strong and Efficient for Subgraph Representation Learning
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 Subgraph-To-Node (S2N) translation, which turns each subgraph into a node of a coarse graph (with edges from shared-edge counts), plus a coarsened variant CoS2N, enabling simple GCN/GCNII to classify subgraphs far more efficiently than GLASS at similar accuracy.
Problem
Subgraph representation learning is usually done with specialized GNNs on a large global graph, which demands heavy memory and computation and does not model the hierarchical structure of subgraphs well.
Approach
Translate the global graph and a set of subgraphs into a new coarse graph where each subgraph is a node and edge weights count shared original edges between subgraphs (normalized and sparsified), so subgraph classification becomes node classification with simple GNNs; optionally add virtual subgraphs from graph coarsening (CoS2N) for data-scarce settings.
Key results
- Best S2N models reach 99.9% to 102.9% of GLASS's micro F1 on the four real-world datasets while processing 183x to 711x more subgraphs per training second.
- S2N models outperform GLASS in 9 of 16 real-world settings and SubGNN in all 16, and use about 0.2x to 0.45x GLASS's GPU memory on most datasets.
- Translated S2N graphs have 0.006x to 0.27x the nodes and 1e-4x to 0.45x the edges of the original global graphs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add S2N translation instead of using GLASS | GCNII with RWPE · PPIBP | micro F1-score: 61.9_{\pm 0.7} -> 64.3_{\pm 1.8}^{*} | Helped |
| Add S2N translation instead of using GLASS | GCNII with RWPE · HPONeuro | micro F1-score: 68.5_{\pm 0.5} -> 68.6_{\pm 0.8}^{\sim} | No clear effect |
| Add S2N translation instead of using GLASS | GCNII with RWPE · HPOMetab | micro F1-score: 61.4_{\pm 0.5} -> 63.9_{\pm 1.7}^{*} | Helped |
| Add S2N translation instead of using GLASS | GCNII with RWPE · EMUser | micro F1-score: 88.8_{\pm 0.6} -> 89.0_{\pm 3.1}^{\sim} | No clear effect |
| Add RWPE (ablation) | S2N+A GCNII · PPIBP | micro F1-score: 63.7_{\pm 2.3}^{\sim} -> 64.3_{\pm 1.8}^{*} | Helped |
| Add RWPE (ablation) | S2N+A GCNII · HPONeuro | micro F1-score: 68.4_{\pm 1.0}^{\sim} -> 68.6_{\pm 0.8}^{\sim} | No clear effect |
| Add RWPE (ablation) | S2N+A GCNII · HPOMetab | micro F1-score: 63.2_{\pm 2.7}^{\sim} -> 63.9_{\pm 1.7}^{*} | Helped |
| Add RWPE (ablation) | S2N+A GCNII · EMUser | micro F1-score: 89.0_{\pm 1.6}^{\sim} -> 89.0_{\pm 3.1}^{\sim} | No clear effect |
| Add RWPE (ablation) | S2N+A GCNII · Density | micro F1-score: 93.2_{\pm 2.6}^{\sim} -> 93.6_{\pm 2.0}^{\sim} | No clear effect |
| Add RWPE (ablation) | S2N+A GCNII · CutRatio | micro F1-score: 56.0_{\pm 0.0} -> 89.2_{\pm 2.6} | Helped |
| Add RWPE (ablation) | S2N+A GCNII · Coreness | micro F1-score: 85.7_{\pm 5.8}^{\sim} -> 72.6_{\pm 6.2} | Hurt |
| Add internal subgraph edges (ablation) | S2N GCNII · Coreness | micro F1-score: 57.0_{\pm 4.9} -> 85.7_{\pm 5.8}^{\sim} | Helped |
Surprising findings
- The translated S2N graphs are non-homophilous (edge homophily around 0.2 to 0.5), yet simple GNNs still perform well on them.
- Latency comparisons favor S2N only when batch size is ignored, since S2N uses full-batch computation.
Limitations
- Large S2N graphs arise when there are many subgraphs, since all subgraphs are translated to nodes.
- Performance varies across datasets and the best structure must be found empirically.
- Synthetic benchmarks capture only narrow subgraph properties, leaving a gap to real-world tasks.
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 throughput evaluation throughput latency parameters max allocated GPU VRAM
Baselines: Sub2Vec GBDT SubGNN GLASS Separated form GCN/GCNII Connected form GCN/GCNII
Builds on: GLASS SubGNN GCN GCNII RWPE
Closest papers by meaning
- A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening (NeurIPS 2024 · similarity 0.93)
- Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Products (ICML 2024 · similarity 0.91)
- GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning (ICML 2025 · similarity 0.91)
- Union Subgraph Neural Networks (AAAI 2024 · similarity 0.90)
- Subgraph Invariant Learning Towards Large-Scale Graph Node Classification (AAAI 2025 · similarity 0.90)
- An Efficient Subgraph-Inferring Framework for Large-Scale Heterogeneous Graphs (AAAI 2024 · similarity 0.90)
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.