Submodular Kernels for Efficient Rankings
  Many algorithms for ranked data become computationally intractable as the
number of objects grows due to complex geometric structure induced by rankings.
An additional challenge is posed by partial rankings, i.e. rankings in which
the preference is only known for a subset of all objects. For these reasons,
state-of-the-art methods cannot scale to real-world applications, such as
recommender systems. We address this challenge by exploiting geometric
structure of ranked data and additional available information about the objects
to derive a submodular kernel for ranking. The submodular kernel combines the
efficiency of submodular optimization with the theoretical properties of
kernel-based methods. We demonstrate that the submodular kernel drastically
reduces the computational cost compared to state-of-the-art kernels and scales
well to large datasets while attaining good empirical performance.
