Research map / Graph learning / Graph algorithms and clustering
Graph Parsing Networks
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 Graph Parsing Networks (GPN), which use a grammar-induction-inspired graph parsing algorithm to learn a personalized, end-to-end pooling tree per graph, clustering nodes instead of dropping them.
Problem
Hierarchical graph pooling faces a trade-off between memory efficiency and preserving node information (node dropping loses nodes, node clustering uses dense assignments), and existing methods fix pooling ratios or number of pooling layers for all graphs rather than learning a per-graph pooling stru
Approach
A bottom-up graph parsing algorithm decodes discrete, locality-preserving cluster assignments from learned edge scores (dominant-edge selection, neighbor expansion), so the number of pooling layers and nodes per layer are inferred per graph; gradients flow through edge-score masks since the parser itself is non-differentiable.
Key results
- GPN achieves best graph classification accuracy on four of five TUDatasets (e.g., NCI1 80.87±0.43, FRANKENSTEIN 70.45±0.53), and 26.65±0.31 average precision on ogbg-molpcba, beating GMT (23.70).
- On node classification GPN reaches 88.07 on Cora, 89.61 on PubMed and state-of-the-art 38.11 on Film, surpassing SEP on all four datasets.
- Efficiency tests show GPN scales with lower memory than MinCutPool and runs in O(n) time versus EdgePool's O(m), handling dense graphs where baselines run out of memory.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GPN instead of the strongest listed baseline, GMT | Graph classification · DD | accuracy: 77.09 ± 0.81 vs 78.11 ± 0.76 | Hurt |
| Use GPN instead of SPGP | Graph classification · PROTEINS | accuracy: 75.62 ± 0.74 vs 75.20 ± 0.74 | Helped |
| Use GPN instead of EdgePool | Graph classification · NCI1 | accuracy: 80.87 ± 0.43 vs 78.93 ± 2.22 | Helped |
| Use GPN instead of HoscPool | Graph classification · NCI109 | accuracy: 79.20 ± 0.47 vs 78.36 ± 0.52 | Helped |
| Use GPN instead of EdgePool | Graph classification · FRANKENSTEIN | accuracy: 70.45 ± 0.53 vs 69.42 ± 2.28 | Helped |
| Use GPN instead of SPGP | Graph classification · ogbg-molpcba | Average Precision: 26.65 ± 0.31 vs 23.95 ± 0.97 | Helped |
| Use GPN instead of leading node-classification baselines | Node classification · Cora, CiteSeer, PubMed, Film | accuracy: 88.07 ± 0.87 vs 88.37 ± 1.25; 77.02 ± 1.65 vs 78.02 ± 1.15; 89.61 ± 0.34 vs 90.15 ± 0.43; 38.11 ± 1.23 vs 37.81 ± 1.15 | Mixed |
| Replace GCN with GAT (ablation) | GPN graph/node classification · Cora | accuracy: 88.07 ± 0.87 -> 87.46 ± 1.13 | Hurt |
| Replace GCN with GAT (ablation) | GPN graph/node classification · CiteSeer | accuracy: 77.02 ± 1.65 -> 77.16 ± 1.50 | No clear effect |
| Replace GCN with GIN (ablation) | GPN · PROTEINS | accuracy: 75.62 ± 0.74 -> 75.02 ± 1.25 | Hurt |
| Replace DeepSets with mean pooling (ablation) | GPN · PROTEINS | accuracy: 75.62 ± 0.74 -> 75.26 ± 1.13 | No clear effect |
| Replace DeepSets with max pooling (ablation) | GPN · Cora | accuracy: 88.07 ± 0.87 -> 87.08 ± 1.26 | Hurt |
Surprising findings
- Replacing the graph parsing algorithm with a complete graph drops PROTEINS accuracy to 74.12 and Cora to 74.85, showing locality matters more than the GNN or aggregator choice.
- GPN underperforms on DD (77.09 vs. GMT 78.11), which the authors attribute to large sparse graphs needing long-range information.
Limitations
- Batched graphs with different inferred pooling heights reduce time efficiency, since graphs with fewer layers wait for others.
- Sub-optimal on DD (large, sparse graphs) where global-attention methods like GMT perform better.
- Very large inferred pooling heights may cause over-smoothing on large graphs; a max height limit is suggested as mitigation.
Experimental setup
Datasets: DD PROTEINS NCI1 NCI109 FRANKENSTEIN ogbg-molpcba Cora CiteSeer PubMed Film ring and grid synthetic graphs Erdos-Renyi synthetic graphs
Benchmarks: DD PROTEINS NCI1 NCI109 FRANKENSTEIN ogbg-molpcba Cora CiteSeer PubMed Film ring/grid graph reconstruction
Metrics: accuracy average precision mean squared error GPU memory running time
Baselines: Set2Set Global-Attention GCN SortPool GMT TopKPool SAGPool HGP-SL GSAPool ASAP SPGP DiffPool
Builds on: GCN DeepSets EdgePool SEP TopKPool
Closest papers by meaning
- SkipPool: Improved Sparse Hierarchical Graph Pooling with Differentiable Exploration (AAAI 2025 · similarity 0.88)
- Geometry-Aware Edge Pooling for Graph Neural Networks (NeurIPS 2025 · similarity 0.88)
- Tracing Hyperparameter Dependencies for Model Parsing via Learnable Graph Pooling Network (NeurIPS 2024 · similarity 0.87)
- Graph Classification via Reference Distribution Learning: Theory and Practice (NeurIPS 2024 · similarity 0.87)
- Bonsai: Gradient-free Graph Condensation for Node Classification (ICLR 2025 · similarity 0.86)
- ENAHPool: The Edge-Node Attention-based Hierarchical Pooling for Graph Neural Networks (ICML 2025 · similarity 0.86)
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.