← 研踪 PaperTrailarXiv:2607.01546 · v2
The General Stability of Ranking
首次提交 2026-07-02 07:55
版本更新 2026-11-04 05:32
雷达观测 2026-11-05 11:11
摘要
Rankings derived from weighted scoring functions are widely used in university rankings and employment candidate evaluations. Since ranking weights are often chosen by organizations or analysts, ranking stability asks whether a reported ranking persists under reasonable weight changes. Prior work defines volume-based stability as the fraction of the weight space that induces the target ranking exactly. This exact-match requirement can be too blunt: once a perturbed weight vector produces a different ranking, exact stability gives it no credit, whether the change replaces the top-ranked item or only swaps two nearly tied lower-ranked items. We propose general stability, a distance-based generalization that aggregates ranking regions according to a user-defined distance from the target ranking. This lets users specify which ranking changes matter in the application, while recovering exact stability as a special case. We extend existing methods and identify distance properties that permit faster general-stability computation with accuracy guarantees. Our sampling algorithm, $GSC_{md}$, can take exponential time in the worst case, but a property we call uniform boundedness gives a sample budget independent of database size and dimension at fixed accuracy and confidence. We develop Prefix-GSC, a sampling optimization that reduces sorting for distances satisfying a further property, tail decay with bounded influence. We also develop Conv-SC to approximate stability through convex volumes for distances satisfying a property we term quasiconvexity. Experiments on seven real-data sources and generated inputs show how distance affects robustness conclusions and when the algorithms save time. On three 500-item university datasets, Prefix-GSC achieves median query speedups of $1.22$--$1.98\times$ over $GSC_{md}$ at 2% relative error and 95% confidence, including method setup.
作者备注：13 pages, 3 figures. Code and data: https://github.com/umich-dbgroup/General-Stability-of-Ranking
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-04 05:32 · 最新观测版本
The General Stability of Ranking
Rankings derived from weighted scoring functions are widely used in university rankings and employment candidate evaluations. Since ranking weights are often chosen by organizations or analysts, ranking stability asks whether a reported ranking persists under reasonable weight changes. Prior work defines volume-based stability as the fraction of the weight space that induces the target ranking exactly. This exact-match requirement can be too blunt: once a perturbed weight vector produces a different ranking, exact stability gives it no credit, whether the change replaces the top-ranked item or only swaps two nearly tied lower-ranked items. We propose general stability, a distance-based generalization that aggregates ranking regions according to a user-defined distance from the target ranking. This lets users specify which ranking changes matter in the application, while recovering exact stability as a special case. We extend existing methods and identify distance properties that permit faster general-stability computation with accuracy guarantees. Our sampling algorithm, $GSC_{md}$, can take exponential time in the worst case, but a property we call uniform boundedness gives a sample budget independent of database size and dimension at fixed accuracy and confidence. We develop Prefix-GSC, a sampling optimization that reduces sorting for distances satisfying a further property, tail decay with bounded influence. We also develop Conv-SC to approximate stability through convex volumes for distances satisfying a property we term quasiconvexity. Experiments on seven real-data sources and generated inputs show how distance affects robustness conclusions and when the algorithms save time. On three 500-item university datasets, Prefix-GSC achieves median query speedups of $1.22$--$1.98\times$ over $GSC_{md}$ at 2% relative error and 95% confidence, including method setup.
查看此版本解读 →查看此版本原文 ↗