Serialrank: Spectral Ranking using Seriation
summary
Constructs a similarity matrix S_match similarity by counting how many pairwise outcomes two items agree on and shows that for a consistent total order this matrix is a strict R-matrix/seriation so sorting the Laplacian’s Fiedler vector ordering exactly recovers the ranking. Analysis computes the spectrum explicitly, gives perturbation bounds and shows tolerance to about sqrt(n) random corruptions (exact recovery needs Θ(n^2) comparisons; weaker n log n rates suffice for approximate error). Empirically outperforms score, PageRank-style and Bradley–Terry baselines on several datasets.
AI-written summary · about
chapters (10)
- 0:00Introduction to ranking
- 2:58Survey of ranking methods
- 7:17Performance and complexity
- 10:48Scoring and ELO systems
- 13:50Markov chain-based rankings
- 17:38Likelihood estimation
- 22:31Seriation connection
- 25:08Spectral clustering for rank
- 31:11Similarity-based ranking
- 36:47Robustness and conclusion
related talks
39mLocalization and Nonmetric Multidimensional Scaling via Paired Comparisons
36mExtracting Relevant Metrics with Spectral Clustering
01h 48mRecommendation engines explained
32mHow to measure Diversity of Search Results
47mAssessing the quality of a clustering
39mMachine Learning for Relevance and Serendipity
51mHow to Effectively Rank All of Runet's Products
43mAfternoon Session: Individuals, Groups, Pattern Recognition and Rich Data