Abstract
Incomplete rankings on a set of items $\{1,\; \ldots,\; n\}$ are orderings of the form $a_{1}\prec\dots\prec a_{k}$, with $\{a_{1},\dots a_{k}\}\subset\{1,\dots,n\}$ and $k < n$. Though they arise in many modern applications, only a few methods have been introduced to manipulate them, most of them consisting in representing any incomplete ranking by the set of all its possible linear extensions on $\{1,\; \ldots,\; n\}$. It is the major purpose of this paper to introduce a completely novel approach, which allows to treat incomplete rankings directly, representing them as injective words over $\{1,\; \ldots,\; n\}$. Unexpectedly, operations on incomplete rankings have very simple equivalents in this setting and the topological structure of the complex of injective words can be interpretated in a simple fashion from the perspective of ranking. We exploit this connection here and use recent results from algebraic topology to construct a multiresolution analysis and develop a wavelet framework for incomplete rankings. Though purely combinatorial, this construction relies on the same ideas underlying multiresolution analysis on a Euclidean space, and permits to localize the information related to rankings on each subset of items. It can be viewed as a crucial step toward nonlinear approximation of distributions of incomplete rankings and paves the way for many statistical applications, including preference data analysis and the design of recommender systems.
Introduction
In modern data science, ranking data is ubiquitous, appearing in everything from search engine results to consumer preference surveys. However, a significant challenge persists: we rarely observe "full rankings" where every item in a large catalog is ordered by a user. Instead, we encounter incomplete rankings, where a user might rank only a small subset ($k$) of the total items ($n$).
Traditional statistical approaches often attempt to handle this by treating an incomplete ranking as a set of all possible "linear extensions"—essentially guessing the order of unranked items. This approach is computationally expensive, scaling at $n!$, and often introduces significant bias. This paper proposes a departure from these methods by treating incomplete rankings directly as injective words and applying a multiresolution analysis (MRA) framework to localize preference information.
Methodology: Injective Words and Localization
Rather than forcing incomplete rankings into the structure of the symmetric group (the mathematics of full permutations), the authors represent an incomplete ranking $a_1 \prec a_2 \prec \dots \prec a_k$ as an injective word $a_1a_2\dots a_k$ over the alphabet $\{1, \dots, n\}$. This shift allows for the use of tools from algebraic topology, specifically the study of boolean complexes.
Information Localization
A core component of this framework is the marginal operator, which projects a ranking onto a smaller subset of items. For instance, the marginal of the ranking (Apple, Orange, Banana) onto the subset {Apple, Banana} is simply (Apple, Banana). By using a deletion operator, the authors can move between different scales of ranking information, effectively "de-zooming" from specific preferences to broader trends.
Multiresolution Analysis (MRA)
Borrowing concepts from signal processing, the authors decompose the space of all ranking functions into a series of nested subspaces. Each subspace $W_A$ is designed to capture information specific to a subset of items $A$ that is not already accounted for by its smaller subsets. This results in a multiresolution decomposition of the space of functions on permutations:
$$L(\mathfrak{S}_n) = V^0 \oplus \bigoplus_{A} W_A$$
This structure allows researchers to analyze preferences at different "resolutions," such as the relative preference between two items versus the complex interactions between three or more.
The Wavelet Framework
To make this decomposition computationally viable, the authors construct an explicit wavelet basis. Using a "diamond operator" ($\diamond$) and an algorithm adapted from algebraic topology, they provide a method (Algorithm 1) to generate a basis adapted to the MRA structure.
One of the most striking theoretical results is the connection to combinatorics: the dimension of the localized information space $W_A$ is exactly equal to the number of derangements (permutations with no fixed points) of the set $A$. This provides a clear link between the complexity of preference information and classic combinatorial problems.
Empirical Illustration and Insights
While primarily theoretical, the paper applies these concepts to the German Political Goals Dataset, which contains rankings from 2,262 citizens regarding four political goals. The analysis demonstrates that the MRA approach can distinguish between "absolute" rank information (an item's position in a full list) and "relative" rank information (how items are ordered against each other), which is often more relevant for understanding true user preferences.
Key insights from this approach include:
- Localization vs. Extension: By treating unranked items as truly missing rather than "yet to be ranked," the model avoids the computational explosion of linear extensions.
- Translation Invariance: The framework's displacement operators behave predictably, allowing for the movement of preference data across different item sets similarly to how translations work in Euclidean wavelets.
Limitations and Future Work
Despite its mathematical elegance, the framework faces certain hurdles:
- Discrete Scale: Unlike continuous wavelets in Euclidean space, there is no perfect "dilation" operator here; the scale is strictly defined by the number of items ranked.
- Computational Complexity: Developing faster decomposition algorithms for very large $n$ is essential for real-world recommender system applications.
- Handling Ties: The current model assumes strict rankings. Future research will look to generalize this to "bucket orders" to accommodate ties in user preferences.
Conclusion
This paper establishes a rigorous mathematical foundation for the analysis of incomplete rankings. By bridging algebraic topology and preference modeling, the authors provide a localized, multiresolution framework that paves the way for more efficient non-linear approximations in statistical analysis and the design of next-generation recommender systems.
Summary updated