Research map / Graph learning / GNN architectures
Efficient Subgraph GNNs by Learning Effective Selection Policies
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 Policy-learn, a sequential learnable subgraph selection policy for Subgraph GNNs (Gumbel-Softmax, end-to-end), proving it can identify (n,ℓ)-CSL graphs with ℓ subgraphs where random and OSAN cannot.
Problem
Subgraph GNNs process bags of n node-marked subgraphs, which is computationally expensive; random subgraph subsets lose expressivity, so the goal is to learn small, task-adaptive subgraph selection policies.
Approach
A two-network architecture where a Subgraph GNN selection network iteratively samples root nodes (via straight-through Gumbel-Softmax) conditioned on the current bag of already-selected subgraphs, feeding the final small bag to a Subgraph GNN predictor trained end-to-end.
Key results
- On ZINC-12k under 500k budget, Policy-learn T=5 achieves MAE 0.109 vs Random T=5 0.113 and OSAN 0.177 (Full 0.087).
- On Reddit-Binary, Policy-learn T=2 reaches 93.0% accuracy, while full-bag Subgraph GNN runs out of memory.
- On ogbg-molhiv, Policy-learn T=2 achieves 79.13 ROC-AUC vs Full 76.54 and Random T=2 77.55.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use learned rather than random selection with T=2 | Subgraph GNN on ZINC-12k · ZINC-12k test | MAE: 0.136$\pm$0.005 -> 0.120$\pm$0.003 | Helped |
| Use learned rather than random selection with T=2 | Subgraph GNN on Reddit-Binary · Reddit-Binary | accuracy: 92.4$\pm$1.0 -> 93.0$\pm$0.9 | Helped |
| Use learned rather than random selection with T=2 | Subgraph GNN on molesol · molesol | RMSE: 0.951$\pm$0.039 -> 0.877$\pm$0.029 | Helped |
| Use learned rather than random selection with T=2 | Subgraph GNN on moltox21 · moltox21 | ROC-AUC: 76.65$\pm$0.89 -> 77.47$\pm$0.82 | Helped |
| Use learned rather than random selection with T=2 | Subgraph GNN on molbace · molbace | ROC-AUC: 75.36$\pm$4.28 -> 78.40$\pm$2.85 | Helped |
| Use learned rather than random selection with T=2 | Subgraph GNN on molhiv · molhiv | ROC-AUC: 77.55$\pm$1.24 -> 79.13$\pm$0.60 | Helped |
| Increase the selected subgraph count from T=2 to T=5 (ablation) | Policy-learn on ZINC-12k · ZINC-12k test | MAE: 0.120$\pm$0.003 -> 0.109$\pm$0.005 | Helped |
| Increase the selected subgraph count from T=2 to T=5 (ablation) | Policy-learn on molesol · molesol | RMSE: 0.877$\pm$0.029 -> 0.883$\pm$0.032 | Hurt |
| Increase the selected subgraph count from T=2 to T=5 (ablation) | Policy-learn on moltox21 · moltox21 | ROC-AUC: 77.47$\pm$0.82 -> 77.36$\pm$0.60 | Hurt |
| Increase the selected subgraph count from T=2 to T=5 (ablation) | Policy-learn on molbace · molbace | ROC-AUC: 78.40$\pm$2.85 -> 78.39$\pm$2.28 | No clear effect |
| Increase the selected subgraph count from T=2 to T=5 (ablation) | Policy-learn on molhiv · molhiv | ROC-AUC: 79.13$\pm$0.60 -> 78.49$\pm$1.01 | Hurt |
Surprising findings
- OSAN performs worse than the random baseline on ZINC, attributed to implementation differences in the prediction network.
- Policy-learn with only 2 selected subgraphs outperforms the full-bag Subgraph GNN on several OGB datasets (moltox21, molhiv).
Limitations
- Full-bag baseline cannot run on large graphs such as Reddit-Binary (OOM), so comparison is limited there.
- Gains over random selection on several OGB datasets are small relative to standard deviations.
- Theoretical advantages are shown for a constructed CSL-based graph family rather than real-world data.
Experimental setup
Datasets: ZINC-12k Reddit-Binary ogbg-molesol ogbg-moltox21 ogbg-molbace ogbg-molhiv
Benchmarks: ZINC-12k Reddit-Binary OGB molesol OGB moltox21 OGB molbace OGB molhiv
Metrics: MAE accuracy RMSE ROC-AUC
Baselines: GCN GIN PNA GSN CIN OSAN Random subgraph selection Full-bag Subgraph GNN SIN
Builds on: Subgraph GNN (node marking / DS-GNN) OSAN Gumbel-Softmax
Closest papers by meaning
- Ordered Subgraph Aggregation Networks (NeurIPS 2022 · similarity 0.91)
- A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening (NeurIPS 2024 · similarity 0.90)
- Translating Subgraphs to Nodes Makes Simple GNNs Strong and Efficient for Subgraph Representation Learning (ICML 2024 · similarity 0.89)
- Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Products (ICML 2024 · similarity 0.88)
- Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality (ICML 2025 · similarity 0.88)
- EiG-Search: Generating Edge-Induced Subgraphs for GNN Explanation in Linear Time (ICML 2024 · 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.