Research map / Graph learning / GNN architectures
Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
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 HyMN, a Subgraph GNN that samples only the top-T nodes by walk-based Subgraph Centrality for node marking and adds centrality-based structural encodings, cutting cost while matching or beating full-bag and learned sampling methods.
Problem
Subgraph GNNs with node marking process a bag of N subgraphs (one per node), giving O(N^2 d_max) cost that makes them impractical on graphs beyond a few tens of nodes.
Approach
Select which nodes to mark using walk-based centrality (Subgraph Centrality), motivated by a perturbation bound linking walk counts to marking-induced change, and reuse the power-series terms of that centrality as Centrality-based Structural Encodings (CSE) on node features.
Key results
- HyMN (GIN, T=2) reaches 81.01 ± 1.17 test ROC-AUC on MOLHIV, outperforming the full-bag Subgraph GNN (76.54) and POLICY-LEARN (79.13) at T=2.
- On Peptides-Func, HyMN (GCN, T=1) increases GCN training time per epoch by only 42% and inference time by 25%, far cheaper than GPS and Graph-ViT.
- On MalNet-Tiny, HyMN (GIN, T=1) reaches 92.84 ± 0.52 accuracy, above GIN (91.10) and GPS variants (up to 92.14), and is almost six times faster than the best GPS variant.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add CSE feature augmentation to HyMN with T=2 (ablation) | HyMN (GIN) · MOLHIV | ROC-AUC: 79.77 $\pm$ 0.70 -> 81.01 $\pm$ 1.17 | Helped |
| add CSE feature augmentation to HyMN with T=2 (ablation) | HyMN (GIN) · MOLBACE | ROC-AUC: 78.22 $\pm$ 4.02 -> 81.16 $\pm$ 1.21 | Helped |
| add CSE feature augmentation to HyMN with T=2 (ablation) | HyMN (GIN) · MOLTOX21 | ROC-AUC: 77.68 $\pm$ 0.71 -> 77.30 $\pm$ 0.35 | Hurt |
| increase marked subgraphs from T=1 to T=2 (ablation) | HyMN (GIN) · Peptides-Func | average precision: 0.6857 $\pm$ 0.0055 -> 0.6863 $\pm$ 0.0050 | Helped |
| increase marked subgraphs from T=1 to T=2 (ablation) | HyMN (GIN) · Peptides-Struct | MAE: 0.2464 $\pm$ 0.0013 -> 0.2457 $\pm$ 0.0012 | Helped |
| increase marked subgraphs from T=1 to T=2 (ablation) | HyMN (GCN) · Peptides-Func | average precision: 0.6912 $\pm$ 0.0170 -> 0.6948 $\pm$ 0.0052 | Helped |
| increase marked subgraphs from T=1 to T=2 (ablation) | HyMN (GCN) · Peptides-Struct | MAE: 0.2481 $\pm$ 0.0013 -> 0.2477 $\pm$ 0.0010 | Helped |
| select nodes with maximum rather than minimum Subgraph Centrality for marking | Subgraph GNN node-marking policy · Erdos-Renyi graphs, N=20, p=0.3 | Pearson correlation with substructure counts: 0.644 -> 0.947 (Tri); 0.643 -> 0.956 (4-Cyc); 0.634 -> 0.958 (Tailed Tri); 0.698 -> 0.972 (Star) | Helped |
| select nodes with maximum rather than random Subgraph Centrality-based marking | Subgraph GNN node-marking policy · Erdos-Renyi graphs, N=20, p=0.3 | Pearson correlation with substructure counts: 0.712 -> 0.947 (Tri); 0.708 -> 0.956 (4-Cyc); 0.723 -> 0.958 (Tailed Tri); 0.723 -> 0.972 (Star) | Helped |
| augment GIN node features with CSEs | GIN · Peptides-Func | average precision: 0.6555 $\pm$ 0.0088 -> 0.6619 $\pm$ 0.0077 | Helped |
| augment GIN node features with CSEs | GIN · Peptides-Struct | MAE: 0.2497 $\pm$ 0.0012 -> 0.2479 $\pm$ 0.0011 | Helped |
| augment GCN node features with CSEs | GCN · Peptides-Func | average precision: 0.6739 $\pm$ 0.0024 -> 0.6812 $\pm$ 0.0037 | Helped |
Surprising findings
- Marking only the top-1 or top-2 nodes by Subgraph Centrality matches or exceeds full-bag Subgraph GNN performance on several benchmarks.
- Learnable sampling policies (Policy-Learn) are matched by a simple non-learned centrality ranking.
Limitations
- Sampling does not account for already-sampled subgraphs, unlike learned or sequential methods.
- No optimality guarantee for the sampling strategy; multi-node marking effects are not analysed.
- CSEs are not always beneficial (e.g., MOLTOX21 and MalNet-Tiny).
Experimental setup
Datasets: OGB molhiv OGB molbace OGB moltox21 LRGB Peptides-Func LRGB Peptides-Struct MalNet-Tiny REDDIT-BINARY ZINC synthetic substructure counting (triangles)
Benchmarks: OGB molhiv OGB molbace OGB moltox21 Peptides-Func Peptides-Struct MalNet-Tiny REDDIT-BINARY triangle counting
Metrics: ROC-AUC average precision MAE accuracy wall-clock training and inference time
Baselines: GCN GIN RANDOM sampling POLICY-LEARN CS-GNN MAG-GNN GPS Graph-MLP-Mixer Graph-ViT SIN CIN OSAN
Builds on: GIN Policy-Learn DS-GNN Subgraph Centrality GPS
Closest papers by meaning
- A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening (NeurIPS 2024 · similarity 0.91)
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.89)
- Translating Subgraphs to Nodes Makes Simple GNNs Strong and Efficient for Subgraph Representation Learning (ICML 2024 · similarity 0.89)
- Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.89)
- Efficient Subgraph GNNs by Learning Effective Selection Policies (ICLR 2024 · similarity 0.88)
- An Empirical Study of Realized GNN Expressiveness (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.