Research map / Graph learning / Graph algorithms and clustering
Maximum Independent Set: Self-Training through Dynamic Programming
Lorenzo Brusca, Lars C.P.M. Quaedvlieg, Stratis Skoulakis, Grigorios Chrysos, Volkan Cevher
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add the greedy algorithm's solution to model roll-out estimates (ablation) | CMP · RB MIS | approximation ratio: 0.770 ± 0.107 -> 0.836 ± 0.083 | Improved |
| Add the greedy algorithm's solution to model roll-out estimates (ablation) | CMP · COLLAB MIS | approximation ratio: 0.990 ± 0.051 -> 0.990 ± 0.049 | No clear effect |
| Add the greedy algorithm's solution to model roll-out estimates (ablation) | CMP · TWITTER MIS | approximation ratio: 0.967 ± 0.083 -> 0.977 ± 0.031 | Improved |
| Add the greedy algorithm's solution to model roll-out estimates (ablation) | CMP · SPECIAL MIS | approximation ratio: 0.996 ± 0.029 -> 0.994 ± 0.035 | Hurt |
| Add the greedy algorithm's solution to model roll-out estimates (ablation) | Comparator · ER MIS | approximation ratio: 0.930 ± 0.068 -> 0.954 ± 0.058 | Improved |
| Add the greedy algorithm's solution to model roll-out estimates (ablation) | Comparator · BA MIS | approximation ratio: 0.922 ± 0.089 -> 0.942 ± 0.055 | Improved |
| Add the greedy algorithm's solution to model roll-out estimates (ablation) | Comparator · WS MIS | approximation ratio: 0.823 ± 0.119 -> 0.831 ± 0.116 | Improved |
| Use the DP-inspired self-trained graph comparator instead of neural baselines | MIS solver · RB, COLLAB, TWITTER, SPECIAL | approximation ratio | Improved |
Closest papers by meaning
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.86)
- BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks (NeurIPS 2025 · similarity 0.85)
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 2025 · similarity 0.85)
- On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.85)
- On the Expressivity and Sample Complexity of Node-Individualized Graph Neural Networks (NeurIPS 2024 · similarity 0.85)
- Efficient Subgraph GNNs by Learning Effective Selection Policies (ICLR 2024 · similarity 0.84)
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.
