Research map / Graph learning / Graph algorithms and clustering
Identifiability Matters: Revealing the Hidden Recoverable Condition in Unbiased Learning to Rank
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.
Shows that relevance recoverability in unbiased learning to rank is equivalent to connectivity of an identifiability graph built from the dataset, and proposes node intervention and node merging to restore connectivity.
Problem
Unbiased learning to rank fits click data under the examination hypothesis, but true relevance may be unrecoverable from clicks when bias factors are numerous or data is sparse; no fundamental condition for relevance recovery existed.
Approach
Defines identifiability of the ranking model as recovering true relevance up to a scale factor, shows this is equivalent to connectivity of an identifiability graph (IG) over bias factors, and uses this to design minimal-cost node intervention (swapping documents across bias factors via an MST) and node merging (tying observation parameters of similar bias factors) to restore connectivity.
Key results
- On the K=2 simulated dataset, DLA with node intervention reaches MCC 1.000 versus 0.707 for plain DLA, and Two-Tower goes from 0.830 to 1.000 with node intervention.
- On TianGong-ST, using positions and all vertical types (20,704 bias factors) yields an IG with 2,900 connected components, showing unidentifiability occurs on a real large-scale dataset.
- Under contextual PBM bias with 5,000 context types, DLA + node merging improves Yahoo! test nDCG@10 from 0.741 to 0.745 and Istella-S from 0.682 to 0.684.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply node intervention before DLA training | DLA · K=2 simulation, PBM | MCC: 0.707 _{\pm .105} -> \mathbf{1.000 _{\pm .000}} | Helped |
| Apply node merging before DLA training | DLA · K=2 simulation, PBM | MCC: 0.707 _{\pm .105} -> 0.975 _{\pm .000} | Helped |
| Apply node intervention before Regression-EM training | Regression-EM · K=2 simulation, PBM | MCC: 0.580_{\pm .117} -> \mathbf{0.980_{\pm .023}} | Helped |
| Apply node merging before Regression-EM training | Regression-EM · K=2 simulation, PBM | MCC: 0.580_{\pm .117} -> 0.975_{\pm .000} | Helped |
| Apply node intervention before Two-Tower training | Two-Tower · K=2 simulation, PBM | MCC: 0.830 _{\pm .050} -> \mathbf{1.000 _{\pm .000}} | Helped |
| Apply node merging before Two-Tower training | Two-Tower · K=2 simulation, PBM | MCC: 0.830 _{\pm .050} -> 0.975 _{\pm .000} | Helped |
| Apply node merging before DLA training | DLA · Yahoo, CPBM | MCC: 0.750_{\pm.000} -> 0.771_{\pm.000} | Helped |
| Apply node merging before DLA training | DLA · Yahoo, CPBM test | nDCG@5: $0.693_{\pm.001}$ -> $0.697_{\pm.001}$ | Helped |
| Apply node merging before DLA training | DLA · Istella-S, CPBM | MCC: 0.764_{\pm.000} -> 0.772_{\pm.000} | Helped |
| Apply node merging before DLA training | DLA · Istella-S, CPBM test | nDCG@5: $0.633_{\pm.001}$ -> $0.636_{\pm.001}$ | Helped |
| Select intervention pairs using random cost instead of min cost (ablation) | DLA + Node intervention · K=2 simulation, PBM | MCC | Mixed |
| Merge positions 1 & 4 instead of the proposed positions 3 & 4 (ablation) | DLA + Node merging · K=2 simulation, PBM | MCC | Hurt |
Surprising findings
- Click MSE can be near zero for ULTR baselines even when relevance is unrecoverable, so fitting clicks perfectly does not guarantee correct ranking.
- Merely 20 (Istella-S) or 200 (Yahoo!) context types are enough to disconnect the identifiability graph.
Limitations
- Theory assumes perfect fitting of click probabilities; approximation error propagation in the IG is not analyzed.
- Analysis restricted to the examination hypothesis; trust bias and vector-based examination models are not covered.
- Node merging introduces approximation error that grows with the MST diameter and degrades for K=4.
Experimental setup
Datasets: Yahoo! LETOR Istella-S TianGong-ST fully synthetic simulated dataset
Benchmarks: Yahoo! LETOR Istella-S simulated K-component dataset
Metrics: MCC nDCG@1 nDCG@3 nDCG@5 nDCG@10 Click MSE
Baselines: No debias DLA Regression-EM Two-Tower
Builds on: examination hypothesis DLA Regression-EM Two-Tower
Closest papers by meaning
- LBD: Decouple Relevance and Observation for Individual-Level Unbiased Learning to Rank (NeurIPS 2022 · similarity 0.90)
- Data-driven Rank Breaking for Efficient Rank Aggregation (ICML 2016 · similarity 0.86)
- A Large Scale Search Dataset for Unbiased Learning to Rank (NeurIPS 2022 · similarity 0.86)
- Learning to Rank from Incomplete Rankings (ICML 2026 · similarity 0.85)
- Statistical Inference for Incomplete Ranking Data: The Case of Rank-Dependent Coarsening (ICML 2017 · similarity 0.85)
- UniRank: Unified List-wise Reranking via Confidence-Ordered Denoising (NeurIPS 2026 · 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.