KDD 2025

TSPRank: Bridging Pairwise and Listwise Methods with a Bilinear Travelling Salesman Model

Weixian Waylon Li · Yftah Ziser · Yifei Xie · Shay B. Cohen · Tiejun Ma

University of Edinburgh · NVIDIA Research

Code ACM Paper arXiv Data Checkpoints

TSPRank turns pairwise ranking scores into a globally optimized tour, combining the simplicity of pairwise comparison with the structure of listwise inference.

TSPRank architecture showing backbone embeddings, bilinear scoring, adjacency matrix learning, and TSP solver inference. — TSPRank scores directed entity pairs, builds a graph, and recovers a coherent ranking via Travelling Salesman Problem optimization.

Abstract

Traditional Learning-To-Rank methods often optimize either pairwise comparisons or entire lists, leaving a practical gap between robust pairwise modeling and globally coherent listwise inference. TSPRank bridges this gap by reframing ranking as a Travelling Salesman Problem. A bilinear model produces directed pairwise scores from backbone embeddings, and a solver then selects the ranking that maximizes the global tour score.

Experiments across stock ranking, information retrieval, and historical event ordering show that TSPRank can serve as a general ranking component on top of existing embeddings. Qualitative analysis further suggests that the solver improves the use of global information and provides tolerance to local pairwise errors.

Method

The model keeps the scoring interface simple: encode entities, score directed edges, then solve for the best ordering.

Pairwise scoring

A trainable bilinear layer scores ordered entity pairs after an optional Transformer encoder or domain backbone.

Graph construction

Pairwise scores form a directed adjacency matrix, making the ranking problem explicit as graph optimization.

Listwise inference

TSP decoding selects a globally coherent route through all entities rather than independent local decisions.

Results

TSPRank was evaluated across tabular, retrieval, and textual ordering tasks.

0.0447 NASDAQ Kendall’s τ

TSPRank-Global improves over LambdaMART at 0.0071 and Rankformer at 0.0110.

0.8884 MQ2008 NDCG@10

Top-10 retrieval setting with the strongest reported NDCG@10.

0.6302 OTD2 Kendall’s τ

Historical event ordering at group size 30 using text-embedding-3-small.

Rankformer prediction visualization for historical event ordering. — Rankformer predictions.

TSPRank prediction graph visualization for historical event ordering. — TSPRank predictions with global graph structure.

Citation

@inproceedings{10.1145/3690624.3709234,
  author = {Li, Weixian Waylon and Ziser, Yftah and Xie, Yifei and Cohen, Shay B. and Ma, Tiejun},
  title = {TSPRank: Bridging Pairwise and Listwise Methods with a Bilinear Travelling Salesman Model},
  year = {2025},
  publisher = {Association for Computing Machinery},
  doi = {10.1145/3690624.3709234},
  booktitle = {Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1},
  pages = {707--718},
  series = {KDD '25}
}