Training-free ranking from pairwise comparisons via acyclic graph construction

Abstract

Abstract Ranking from weighted pairwise comparisons asks for a global order that respects observed preferences as well as possible. We study a training-free, deterministic pipeline that builds an acyclic backbone on the comparison digraph using an MWFAS-inspired local-ratio heuristic, restores high-weight arcs under exact cycle-safe reinsertion, optionally applies a secondary weighted min-cut exchange, and extracts scores with optional Phase C refinement (adjacent-swap order updates followed by order-preserving ternary magnitude search). The local-ratio and exact add-back components follow prior lineage; this paper formalizes ranking–MWFAS optimum-value equivalence and practical guarantee boundaries, corrects a fixed-topological-position proxy weakening of add-back, and expands classical and GNN evaluation under timeout-aware common-completion analysis. Empirically, the canonical reachability-aware method ( OURS - Reach ) is strong on simple/naive upset metrics against several baselines, remains competitive rather than uniformly superior to SpringRank on family-aware checks, and is weaker than BTL and corrected RankCentrality on upset_ratio. It is slower than most lightweight classical estimators yet substantially faster than archived trained GNNRank runs under an end-to-end protocol; the near-complete Finance graph marks a large-dense scalability boundary.