Research map / Graph learning / Graph algorithms and clustering
Graph Resistance and Learning from Pairwise Comparisons
Julien Hendrickx, Alexander Olshevsky, Venkatesh Saligrama
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 log-least-squares estimation from edgewise win ratios instead of the earlier eigenvector method | BTL pairwise-comparison learning · Line | asymptotic relative-error bound: b^{5/2} n^2 -> b \sqrt{n} | Improved |
| Use log-least-squares estimation from edgewise win ratios instead of the earlier eigenvector method | BTL pairwise-comparison learning · Circle | asymptotic relative-error bound: b^{5/2} n^2 -> b \sqrt{n} | Improved |
| Use log-least-squares estimation from edgewise win ratios instead of the earlier eigenvector method | BTL pairwise-comparison learning · 2D grid | asymptotic relative-error bound: b^{5/2} n -> b | Improved |
| Use log-least-squares estimation from edgewise win ratios instead of the earlier eigenvector method | BTL pairwise-comparison learning · 3D grid | asymptotic relative-error bound: b^{5/2} n^{2/3} -> b | Improved |
| Use log-least-squares estimation from edgewise win ratios instead of the earlier eigenvector method | BTL pairwise-comparison learning · Star graph | asymptotic relative-error bound: b^{5/2} \sqrt{n} -> b | Improved |
| Use log-least-squares estimation from edgewise win ratios instead of the earlier eigenvector method | BTL pairwise-comparison learning · 2 stars joined at centers | asymptotic relative-error bound: b^{5/2} n^{1.5} -> b | Improved |
| Use log-least-squares estimation from edgewise win ratios instead of the earlier eigenvector method | BTL pairwise-comparison learning · Barbell graph | asymptotic relative-error bound: b^{5/2} n^{3.5} -> b \sqrt{n} | Improved |
| Use log-least-squares estimation from edgewise win ratios instead of the earlier eigenvector method | BTL pairwise-comparison learning · Geometric random graph | asymptotic relative-error bound: b^{5/2} n -> b | Improved |
| Use log-least-squares estimation from edgewise win ratios instead of the earlier eigenvector method | BTL pairwise-comparison learning · Erdos-Renyi | asymptotic relative-error bound: b^{5/2} -> b | Improved |
| Increase comparisons per edge k | Log-least-squares · Erdos-Renyi graphs | relative estimation error | Improved |
| Increase expected degree while keeping node count fixed | Log-least-squares · Erdos-Renyi graphs | average relative estimation error | Improved |
| Increase node count while keeping expected degree fixed | Log-least-squares · Erdos-Renyi graphs | average relative estimation error | No clear effect |
Closest papers by meaning
- Minimax Rate for Learning From Pairwise Comparisons in the BTL Model (ICML 2020 · similarity 0.89)
- No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets (ICML 2025 · similarity 0.85)
- Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.84)
- Carrot and Stick: Eliciting Comparison Data and Beyond (NeurIPS 2024 · similarity 0.83)
- Stochastic contextual bandits with graph feedback: from independence number to MAS number (NeurIPS 2024 · similarity 0.83)
- Don’t Label Twice: Quantity Beats Quality when Comparing Binary Classifiers on a Budget (ICML 2024 · similarity 0.83)
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.
