Research map / Label-efficient and robust learning / Semi-supervised learning
Extensions of Karger's Algorithm: Why They Fail in Theory and How They Are Useful in Practice
Erik Jenner, Enrique Fita Sanmartín, Fred A. Hamprecht
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 |
|---|---|---|---|
| use Karger-contraction potential instead of random walker potential | seeded label propagation · USPS semi-supervised (20 labeled seeds) | accuracy (%): 53.7 -> 62.2 | Improved |
| use Karger-contraction potential instead of random walker potential | seeded label propagation · USPS semi-supervised (40 labeled seeds) | accuracy (%): 68.0 -> 73.1 | Improved |
| use Karger-contraction potential instead of random walker potential | seeded label propagation · USPS semi-supervised (100 labeled seeds) | accuracy (%): 87.7 -> 89.0 | Improved |
| use Karger-contraction potential instead of random walker potential | seeded label propagation · USPS semi-supervised (200 labeled seeds) | accuracy (%): 92.4 -> 92.6 | No clear effect |
| use Karger-contraction potential instead of random walker potential | seeded segmentation · Grabcut (seeded segmentation) | accuracy (%): 96.0 -> 96.3 | No clear effect |
| use Karger-contraction potential instead of random walker potential | seeded segmentation · Grabcut (seeded segmentation) | ARI: 0.82 -> 0.82 | No clear effect |
| use Karger-contraction potential instead of random walker potential | seeded segmentation · Grabcut (seeded segmentation) | VoI: 0.25 -> 0.24 | No clear effect |
| use random walker instead of watershed | seeded label propagation · USPS semi-supervised (100 labeled seeds) | accuracy (%): 74.3 -> 87.7 | Improved |
| use Power Watershed instead of watershed | seeded label propagation · USPS semi-supervised (200 labeled seeds) | accuracy (%): 80.0 -> 80.8 | No clear effect |
| use Power Watershed instead of watershed | seeded segmentation · Grabcut (seeded segmentation) | ARI: 0.83 -> 0.83 | No clear effect |
Closest papers by meaning
- Faster Global Minimum Cut with Predictions (ICML 2025 · similarity 0.88)
- Continuous Partitioning for Graph-Based Semi-Supervised Learning (NeurIPS 2024 · similarity 0.86)
- ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems (ICML 2025 · similarity 0.84)
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.84)
- Differentiable Generalized Sliced Wasserstein Plans (NeurIPS 2025 · similarity 0.84)
- Approximate Forest Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees (ICML 2025 · 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.
