Research map / Graph learning / Graph self-supervised learning
MaxCutPool: differentiable feature-aware Maxcut for pooling in graph neural 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 MaxCutPool, a differentiable, feature-aware MaxCut solver built from heterophilic message passing, and uses it as a sparse, trainable graph pooling layer for GNNs, plus a new synthetic heterophilic Multipartite dataset.
Problem
Maximum cut in attributed graphs is typically solved with continuous relaxations that are unstable on non-bipartite graphs, and existing differentiable graph poolers are either dense, feature-agnostic one-every-K methods or scoring-based methods that produce locally clustered pooled graphs, poorly s
Approach
Use a GNN (ScoreNet) built from heterophilic message passing (delta>1) to produce node scores whose top-K selection gives a MaxCut-like partition; train end-to-end with an auxiliary normalized cut loss, assign remaining nodes to supernodes via a parallel BFS, and reduce features with score-weighted Hadamard products so gradients reach the ScoreNet.
Key results
- On GSet, MaxCutPool finds the best cut on 6 of 7 graphs (e.g., G55 0.8068 vs 0.7865 for GCN), with one exception G50 where NDP is best (0.9800 vs 0.9750).
- For graph classification, DiffNDP-E ranks top with a score of 7 across 7 datasets, and both DiffNDP variants reach 100% on EXPWL1 and about 90% on Multipartite, outperforming all competitors.
- For node classification, DiffNDP-E is in the top tier on all five heterophilic datasets, reaching 60% on Roman-empire versus 22-26% for TopK, k-MIS and NDP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MaxCutPool (DiffNDP) instead of the strongest listed baseline | MAXCUT partitioning · PyGSP and GSet graphs (except G50) | cut-edge fraction: 0.7292 vs 0.7240; 0.6814 vs 0.6805; 0.7105 vs 0.6920; 1.0000 vs 1.0000; 0.9815 vs 0.9787; 0.9130 vs 0.9104; 0.9040 vs 0. | Helped |
| Use MaxCutPool (DiffNDP) instead of NDP | MAXCUT partitioning · G50 | cut-edge fraction: 0.9800 vs 0.9750 | Hurt |
| Replace the standard RED operation with expressive RED (DiffNDP-E) (ablation) | MaxCutPool graph classification · COLLAB, EXPWL1, Mutag., NCI1 | accuracy: COLLAB 77 ±2 vs 77 ±2; EXPWL1 100 ±0 vs 100 ±0; Mutag. 77 ±2 vs 79 ±1; NCI1 75 ±2 vs 76 ±2 | Mixed |
| Remove the auxiliary cut loss (DiffNDP-NL) (ablation) | MaxCutPool graph classification · GCB-H, Mutag., NCI1, REDDIT-B | accuracy: 73 ±3 -> 61 ±6; 77 ±2 -> 76 ±3; 75 ±2 -> 74 ±2; 89 ±3 -> 86 ±3 | Hurt |
| Remove the auxiliary cut loss (DiffNDP-NL) (ablation) | MaxCutPool graph classification · COLLAB | accuracy: 77 ±2 -> 77 ±3 | No clear effect |
| Use DiffNDP-E instead of the strongest listed baseline | Graph classification · COLLAB and EXPWL1 | accuracy: 77 ±2 vs 72 ±3; 100 ±0 vs 99 ±1 | Helped |
| Use DiffNDP-E instead of the strongest listed baseline | Graph classification · Multipartite | accuracy: 87 ±5 vs 58 ±2 | Helped |
| Use DiffNDP-E instead of NDP | Node classification · Roman-Empire | accuracy: 60 ±4 vs 22 ±5 | Helped |
| Use DiffNDP-E instead of the strongest listed baseline | Node classification · Tolokers | AUROC: 91 ±2 vs 89 ±5 | Helped |
Surprising findings
- The non-expressive DiffNDP-NL variant reaches 100% on EXPWL1, the first known non-expressive pooler to pass that expressiveness test.
- On Roman-empire, the pooling baselines TopK, k-MIS and NDP score 22-26% while the no-pool model reaches 59%, suggesting pooling can badly hurt heterophilic node classification.
Limitations
- The auxiliary MaxCut loss targets a partition whose size may not match the chosen pooling ratio; the pooling ratio is best near 0.5 for approximately uniform degrees.
- Graclus and soft-clustering poolers were excluded from node classification due to RAM and VRAM exhaustion on large graphs.
- Some GSet comparisons and PyGSP entries lack GW results because the solver failed to converge.
Experimental setup
Datasets: PyGSP graphs GSet COLLAB DD NCI1 ENZYMES MUTAG Mutagenicity PROTEINS REDDIT-BINARY GCB-H EXPWL1
Benchmarks: GSet PyGSP graphs COLLAB EXPWL1 Multipartite Mutagenicity MUTAG NCI1 REDDIT-BINARY GCB-H Roman-empire Amazon-ratings
Metrics: percentage of cut edges classification accuracy AUROC
Baselines: Goemans-Williamson Laplacian eigenvector method (NDP cut) GCN-based MaxCut GNN DiffPool DMoN MinCut pooling TopK Graclus k-MIS EdgePool ECPool
Builds on: Graph Isomorphism Network Goemans-Williamson MaxCut relaxation Normalized Decimation Pooling TopK pooling k-MIS pooling GCN
Closest papers by meaning
- Geometry-Aware Edge Pooling for Graph Neural Networks (NeurIPS 2025 · similarity 0.90)
- SkipPool: Improved Sparse Hierarchical Graph Pooling with Differentiable Exploration (AAAI 2025 · similarity 0.89)
- ENAHPool: The Edge-Node Attention-based Hierarchical Pooling for Graph Neural Networks (ICML 2025 · similarity 0.87)
- Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks (NeurIPS 2025 · similarity 0.85)
- Enhancing Graph Classification Robustness with Singular Pooling (NeurIPS 2025 · similarity 0.85)
- ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems (ICML 2025 · similarity 0.85)
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.