The Graph Cut Kernel for Ranked Data
Authors: Michelangelo Conserva
Marc Peter Deisenroth
K S Sesh Kumar
Venue: Accepted by TMLR ()

Abstract: Many algorithms for ranked data become computationally intractable as the number of objects grows due to the 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 the geometric structure of ranked data and additional available information about the objects to derive a kernel for ranking based on the graph cut function. The graph cut kernel combines the efficiency of submodular optimization with the theoretical properties of kernel-based methods. We demonstrate that our novel kernel drastically reduces the computational cost while maintaining the same accuracy as state-of-the-art methods.

Published in Transactions on Machine Learning Research (06/2022)
The Graph Cut Kernel for Ranked Data
Michelangelo Conserva Department of EECS
m.consserau@muullccc
Queen Mary University of London
Marc Peter Deisenroth
m. m.ddeisenroth@uullccccm
UCL Centre for Artificial Intelligence University College London
K S Sesh Kumar
s. karrii@mmeriall.c. uk
Data Science Institute Imperial College London
Reviewed OpenReview: Sttps://openreen net/ form? id= SEUGkraMPs
Abstract
Many algorithms for ranked data become computationally intractable as the number of objects grows due to the complex geometric structure induced by rankings. An additional challonge is posed by partial rankings, i.c. 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 the geometric structure of ranked data and additional available information about the objects to derive kernel for ranking based on the graph cut function. The graph cut kernel combines the efficiency of submodular optimization with the theoretical properties of kernel-based hodh We demonstrate that our novel kernel drastically reduces the computational cost while maintaining the same accuracy as stale-of-thhe-rt methods.
1 Introduction
Ranked data arises in many real-world applications, e.g., multi-objects tracking (Hu al. 2020 and prefer- ence learning (F [Fürnkranz & Hüllermeier 2003). However, the classical application is recommender systems [Karatzoglou et al. 2013). for example movics (Harper & Konstan, 2015) or jokes (Goldberg et al. 2001) In such scenarios, rankings can lake different forms (full, top-k or interleaving) and, typically, contain infor- mation only for a subset of the objects. The main challenge of machine learning applications for ranked data is computational as rankings present a super exponential growth. Given n objects, there are n! possible full rankings and about log(2) )"+!n! n! partial rankings Gross 1962).
Several approaches have been proposed to model ranked data. Balcan et al. (2008) and Ailon et al. (2008) propose to interpret rankings as a sequence of binary decisions between objects whereas Lebanon & Mao (2008), Helmbold & Warmuth (2009) and Huang et al. (2009) define a distribution over permutations. These approaches, however, do not scale when the number of objects is large since they do not exploit the underlying structure of ranked data.
Ranked data, despite being high dimensional, is structured, and being able to compute similaritios suffices in many applications. For example, in recommender systems, the similarity of two users based on their preferences vital to propose algorithms that provide recommendations to them. For this reason, kernels, which can be viewed as measures of similarities, are particularly well suited to model ranked data.
The first application of kernels to ranked data is the diffusion kernel (onndor Lafferty 2002). However, the diffusion kernel is prohibitively expensive compute in real-world settings its time complexity scales

---

Published in Transactions on Machine Learning Research (06/2022)
Full
Top-k
Exhaustive
Non-exhaustive
Mallows kernel
/
x
X
Kendall kernel
/
/
X
Graph cut kernel (ours)
1
V
Table I: Kernel for the different kinds of rankings data.
exponentially with the number of objects. Jiao & Vert 2015 propose the Kendall and Mallows kernels, which are based on the Kendall distance for rankings (Kendall 1948), and a tractable algorithm to calculate them. These kernels correspond to the linear kernel and the squared exponential kernel on the symmetric group (Diaconis. 1988). which is the space yielded by interpreting rankings as permutations. For set of n objects, the time complexity for both kernels is n log n for full rankings. In the specific case of the Kendall kernel, the algorithm can be extended to partial rankings. Jiao & Vert (2018) propose weighted version of the Kendall kernel to model the different contributions of the different pairs in the rankings but the O(nlogn) time complexity algorithm is only valid for full and top-k rankings. Finally, [omeli et al. (2019) derive a Monte Carlo kernel estimator for the Mallows kernel for the specific case of top-l rankings. The main challenge full, top-k and interleaving. Previous kernels for ranked data (Jiao & Vert 2015 Lomeli et al., 2019) have been tailored for specific types of rankings; see Table I for an overview of the state of the art.
applying kernel methods to ranked data to efficiently deal with all kinds of rankings:
In this paper, propose the graph cut kernel, which attain good performance at low computation budget regardless of the specific kind of ranking. To achieve this challenging objective, we interpret ranked data in terms of ordered partitions, rather than permutations on the symmetric group. This allows us to use the efficient. machinery of submodular functions. Submodular functions, which the graph cut function is an example of, have been previously applied to ratings in the form of Lovász Bregman divergences ([yer & Bilmes 2013). In this paper, we propose novel kernel for rankings. The main contribution of the paper is the graph cut kernel for all kinds of rankings (full, top-k, exhaustive interleaving and non-exhaustive interleaving). The graph cut kernel exploits the goometric structure of ranked data to drastically reduce the computational cost while still retaining good empirical performance.
The structure of the article is as follows. In Section 2 we show how to encode all kinds of rankings as ordered partitions and their relationship with submodular functions, in particular with the graph cut function. 3 we propose a monolonic feat ure map using the submodular functions that is consistent with the ranking of the objects. Finally, in Section we support our claims and demonstrate scalability empirically using synthetic and a real datasets.
Section
2 Ordered partitions and submodular functions
In Section 2.1 we introduce the different types of rankings and how to encode them as ordered partitions and, in Section 2.2 we revise submodular functions. Further, in Section we introduce the base polytope, geometrical representation of the space of ordered partitions, which is yiclded by submodular functions and is characterised by an exponential growth of the number constrains with the number of objects. Section 2.5 presents the tangent cone, an outer approximation of the base polytope, which is instead characterised by constraints that scale linearly in the number of objects. This cheap but representative approximation for rankings will be used to derive the feature map of the graph cut kernel in Section 3 It turns out that the monotonicity of the feature map is consistent. with the ranking of the objects.
2.1 Ranked data and ordered partitions
Ranked data is often available in different forms. Table contains the most common kinds of rankings objects, where < b denotes the preference of b over a. In full rankings, the pairwise ordering between
Ratings differ from rankings in the way the preference expressed. Ratings defined using a scale of preference, whereas rankings only encode the order of preferences.
2

---

Published in Transactions on Machine Learning Research (06/2022)
Table 2: Examples of rankings from a set of 5 objects.
TYPE
RANKING
ORDERED PARTITION
Full
2<1<3 < 4
(1) (5)
Top-2
243
(4)
Exh.
1 1<2 <2
1<543n1<5-4
Non-exh. 2<1
(2) [1} <
all objects is known. In top-k rankings, the information on the pairwise ordering is only available for the k most favourite objects. This implicitly means that the order the remaining objects is unknown. For exhaustive rankings, we know the exact ordering of some subsets the items but not the pairwise ordering of the items inside the subsets. For example, given {1,2] x (3,4), 4), we know that both and are preferred to and 2 but lack the information about the exact ordering of 3 compared to 4 and 1 compared to 2. Kon-exhaustive rankings only contain information on subset of objects and, therefore, the ordering of the other objects is unknown. For instance, in the example of non-exhaustive ranking given in Table 2 object 3 may lic between object 2 and object or object 1 and object 4.
In this paper, we encode rankings using ordered partitions to achieve a compact and general representation. Let V the set of objects, then an ordered partition can be represented by mutually exclusive sets : Ar, such that
A <.... A
(1)
If the subsets cover all objects, i.e. 4/-14 = V, then we refer to this as an exhaustive ordered partition, otherwise as a non-erhaustive ordered partitions. Full and top-k rankings are special cases of exhaustive ordered partition. However, non-exhaustive rankings can only be represented by non-exhaustive partial
ordering.
In the following, we introduce submodular functions and specific polytope related submodular functions whose faces are characterized by ordered partitions. In Section 3 then define monotonic feature map that is consistent with ranking that is represented by an ordered partition.
2.2 Submodular functions
Submodular functions are set functions characterized by diminishing returns, which makes them suitable for many applications ranging from game theory to electrical networks. Formally, let a be the number of objects in V. A set function defined on the power set F ; 2 + R is submodular if, for all subsets A,, Aj C V
F(A:) + F(A)) 2 U(A, F(A,
(2)
The power set. 2 is naturally identified by the vertices [0. 13 of an n-dimensional unit hypercube. Therefore, set function F: 2 - R defined on the power set of V is the same defining it on the vertices of the n-dimensional unit hypercube. Each set function may be extended to the complete hypercube [0, 1J"h using the Lovász extension (Lovász) [9822), which we refer to as f 10m + R. For any vector w E [0, 1]", we may calculate the value of the function f(w) and find the permutation of objects fi,...,fn such that
uy 2 ... 2 Win. Then
f(w) = wj. Ft........................... .nH) + Σ (w)r Wjot. )F(fi,...............
(3)
k=
For example, let us take the set V= (a, b} with power set 2 = (Ø, {a}. (b), {a, 6}}. Each subset may be represented by an indicator vector of length |V] = 2. The first index of the indicator vector of the subset represents the presence of the object {a} in while the second index represents the presence of the object [b). Therefore, the corresponding indicator vectors {(0,0]" [1,0]", [0,1]", [1,1]T} form the corners of the
3

---

Published in Transactions on Machine Learning Research (06/2022)
Wa
then the Lovász extension f is two-dimensional unit hypercube [0, 112. wb
f(w) = (w) wa (((b)) + w. F(fa,b)) b)) if wb 2 war
(4)
(w)a-)))((aa)) u,a b}) if wa 2 wb.
This extension is piecewise linear for any set function F, and it is tight at the corners of the hypercube. Furthermore, f is convex if and only if the corresponding set function F is submodular (Lovász 1982) The
Lovász extension may be defined on R" using the same notion.
(2)33)11)
(23))())
(2)
(=)
B(F)
(1
(1)(2){3)
(1(33))
(3/(12))
(1223))
(--1((2))
R2233
(K (13)(2) (()(())())
(a) Geometrical represen- tation from its support- ing hyperplanes (s(A) =
(b) Each face (point or
Outer approximation B (L).
dd Outer approximation B (L))).))))))))
segment) of B(F) is as-
sociated with an ordered
F(A)}.
partition.
Figure 1: Overview of the base polytope and its outer approximations for n=
2.3 Base polytope
Any piecewise linear convex function may be represented as the support function f(w) max,ek (w, s) of a certain polytope K (Rockafellar) 1997). For the Lovász extension of a submodular function, there is an explicit description of K, known as the base polytope, which we now describe.
Definition 2.1 Base polytope. Let s(B) EiEB St: where s; is the 7th element of E R". The base polytope
B(F) = Bs( - F(B) n(V)) F(V] V}}
is included in the affine hyperplane s(V) F(V). All the adjacent faces of the hyperplane in Figure la may
be used to get ranking in Figure lb A key result in submodular analysis (Fujishige) 2005 is that the Lovász extension the support function of base polytope B(F), ie., for any w E R2, we have
f(w) = sup (w,s). se .F
(6)
2.4
Graph cuts
In this paper, we are mainly interested in using a class of submodular functions called graph cuts. Let assume we have weighted undirected graph with the weights function V + R4. A graph cut is defined any subset A of the nodes of the graph V as
F(A) Σ all,)))LEA ligal, -geal: isj
where i,j E V. This is the sum of weights of all the edges of the graph that connect nodes in the set A to the nodes that are not in set A, i... V A. The corresponding Lovász extension is defined as
f(w) = Σ ((..))(u: - wyl.
where [0, 1
4

---

Published in Transactions on Machine Learning Research (06/2022)
This function is of particular interest to this paper because assume value function oracle that may be evaluated in time linear in the number of edges of the graph. There are other rich classes of information- theoretic functions like entropy and mutual information that belong to the class of submodular functions. Although these functions can be successfully used to model several important problems, evaluating them is significantly expensive. This one of the reasons we focus on graph cuts this paper. Investigating applications that allow for efficient computation of such functions represent an interesting future direction.
2.5 Tangent cone
However, the number of constraints for the base polytope, Eq. ( grows exponentially with the cardinality of V, i.c. 2 1. For an ordered partition A, we can define the tangent cone of the base polytope B(F), a form of outer approximation with constraints linear in the length of A,
Definition 2.2 Tangent come. Let B, = Ai ...... .U..UU, A, which also represent using 1}=1A, for brevity, We define the tangent cone of the base polytope ((F) characterized by the ordered partition A as
(A(F)= = (s(() S F(B)) ((B:))s(V)) F(V). (1 (L....,1-13)
(7)
The tangent cone considers only constraints the exponentially many constraints used to define the base polytope, and it forms an outer approximation of the ordered partitions as illustrated in Figure Ic and for ([1,2] < (3)) and ((1} (2) < (3)), respectively.
Since the number of constraints of the tangent cone is linear in the length of the ordered partition, is possible to leverage efficient submodular optimization techniques to retrieve cheap approximation for ranked data using their tangent cone representations. The graph cut kernel is built on top of this approximation explained in Section 3.1.
3 Kernel for ordered data
Using the connections between ordered partitions and submodularity (Section 3.1 map for the graph cut kernel. Section non-oxhaustive rankings.
we propose a feature 3.2 extends the kernel to non-exhaustive ordered partitions, i.e.
3.1 From the feature map to the kernel
We propose to use the min-norm point on the tangent cone of the base polytope BA(F) as the feature map
1 arg min マ |s| R", (F)
((A)= =
(8)
where n the number of objects. Kumar Bach (2017) showed that this dual to the isotonic regression problem, i.e, assuming that Bo
min n. -((B)-F(BB.))) + AAlu? /u3
1=1
s.l.
(9)
where the optimal solution 8t of Eq. ( and the optimal solution of Eq. 9 are related via
0f LA.
(10)
We re-derive the details and show the pseudocode for the PAVA algorithm in Appendix
Note that of corresponds to the set A, while 8f corresponds the object j and 87 -uf if object j belongs to the subset. Az. The isotonic regression problem may be solved using the pool adjacent violator
5

---

Published in Transactions on Machine Learning Research (06/2022)
values
2
0
-2
(8
(1) {9 2 103
{5}
{4}
{6)
Figure 2: Optimal values 0², Eq. 11 sushi dataset for A.
using the submodular cut function and the information graph of the
algorithm (PAVA) Best & Chakravarti 1990). the optimal solution 2² has the same values for some of the partitions, Le. Vi- = V2+1 for some fl....,/ 1}, this corresponds to a merge A; and A If these merges are made, we obtain basic ordered partition such that our optimal v* has strictly decreasing values. Because none of the constraints tight, primal stationarity leads to explicit values of e" given by
of = F(BB))F(BB
(11)
i.e. the exact solution to the isotonic regression problem in Eq. 9 may be obtained in closed form.
We now present an example of a feature map for
A 5 x 8 < 3 < 4 <2 10 < 77<4 <6
support the choice of the feature map. Using allows us derive a geometrically meaningful kernel.
Figure 2 reports example of v" associated with A. Higher values correspond to more preferred objects and lower values to less preferved ones, whereas objects in the middle tend to be associated with values closer to zero. This particular structure of v² is characteristic of submodular functions F. The values v* are related to the feature map in Eq. (10) in the sense that each dimension of ((A) corresponds to an object, and d(A)a is the value in v" corresponding to d. From the example in Figure 2 Φ(A)s = -422 ((A)3 d(A)s 2.36 and so on. Therefore, a natural and efficient way to exploit this pattern to use the linear kernel the resulting feature maps:
(A,
Σ ((A)ao(A)) o(A)), d=0
(12)
If two rankings A and A', an object is ranked similarly then this results in the multiplication of two numbers with the same sign, i.e. ((A))((A)) multiplication would happen between numbers with different signs and thus d(A))o(A') 0. How much greater or less than zero depends on the position of the d in the rankings. Figure 3 reports ((A) and s(A') where A' is the inverse of A along with the multiplication factor ((A)ao(A'))
On the contrary, if d is ranked differently then the
3.2 Kernel for non-exhaustive partial orderings
To extend the graph cut kernel from exhaustive to non-exhaustive ordered partitions, we recur to the convolution kernel (Haussler) 1999) by defining the set of exhaustive order partitions that are coherent with a non-exhaustive ranking, R(-). The convolution kernel over the graph cut. kernel is
h. (A, A') [R(A)][R(A')
Σ Σ ka DER(A)
(13)
"Given submodular function F and ordered partition A, when the unique solution problem in Eq. such that fi ... fi, say that basic ordered partition for F. Given any ordered partition, isatonic regression allows compute coarser partition (obtained by partially merging some sets) which basic.

---

Published in Transactions on Machine Learning Research (06/2022)
((A) ((A))
8
d
d
5
2
-4.0
-2.0
0.0
2.0
4.0
-20.0
-15.0
-10.0
-5.0
0.0
(a) Values each dimension of the 10 dimensional feature maps d(A) and 6(A').
(b) Multiplication values for each dimension of ((A) and ((A)).
Figure 3: Geometrical interpretation of the linear kernel of feature map ((A) and o(A'), where A' is the inverse of A.
where A, A' are non-cxhaustive rankings ordered partitions and R(A), R(A') the sct of exhaustive ordered partitions that are coherent with A, A' respectively. Due to the linearity of the inner product, reduce ke(+s-) to the inner product between the average of the feature maps over R(A) and R(A'), so that
kc = (R(A))|R(AA))
E
Σ
ls a')
GER(A) d'ER(AY)
Σ
E
(o(a), o(a'))
(((A))IR(A))
(ER(A)('E((A)
(14)
Σ o(a),
1
Σ o(a'))
(R(A))
[R(A']
AER(A)
d'ER(A))
= (A(A), ((A)))
where A) is the mean of the feature map over the set of exhaustive ordered partitions that are coherent with A. Similarly to kas we can pre-compute these feature maps.
The main drawback of using the convolution kernel for non-exhaustive rankings is that the time complexity for calculating the feature maps becomes exponential due to the exponential growth of R(A) in the number of objects. Given interleaving ranking A of length for objects, R(A) has cardinality (1+ (1+1)==1_ In this case, we sample from the set of coherent ordered partitions and calculate the average feature map the sampled subset of R(A). This approximation allows us to scale well also for large sets of items. In Section we show that we empirically obtain competitive results using this sampling procodure that removes the burden of the computational complexity.
3.3 The graph cut kernel
In summary, the algorithm to calculate the graph cut kernel happens two sequential steps, (i) given a submodular function, we extract low-dimensional features from the data using PAVA, see Alg, and (ii) use the computationally inexpensive linear kernel. Assuming complexity O(p) and exhaustive ordered partition of length for samples, the time complexity for calculating the Gram matrix using the submodular kernel is O(mpln + m²n). Note that these complexities hold only if all the rankings are exhaustive ordered partitions of at most size I. The time complexity for Gram matrix for rankings that are non -on-auhaust is given by (msspn + m²n), where the mumber of samples when we use sampling as explained in Scction 3.2, In the next scssion, we empirically show that the graph cut kernel is, at the same time, able to match or outperform state-of-the-art performance in an est established classification task for kernel-based methods.
oracle submodular function with time

---

Published in Transactions on Machine Learning Research (06/2022)
Algorithm PAVA(A, F)
Input:
-Ordered partition A of length Z. -Submodular function F.
Initialize // Define set to contain the optimal values Initialize B1, B,,... Br // using Eq.
k +- // To retrieve sets BB- and Bk
while |0| < [A] do
o' + F(B, 1)-F(B)) // optimal solution Eq. 11
BB-1
if o' violates the isotonic constraints, i.c. of > uk then Merge partitions A& and Ag-1 and remove Bx.
else
kk + v - k
end end while Return
4 Experiments
The goal of this section is to demonstrate the (i) scalability, (ii) accuracy and (iii) flexibility of the graph cut kernel. We use downstream classification task which is traditional testbed for kernel-based hods
for rankings (Jiao & Vert 2015 Lomeli et al. 2019). The code is available at attps://github. com/
Mi Miccle/..nnsoooooeerr////ffnnnno
4.1 Datasets
The downstream classification task is performed on synthetic dataset that we now describe and on an established real-world dataset.
Synthetic dataset.
The synthetic dataset resembles food preferences eight dishes
[Cake, Biscuit, Gelato}. (Pasta, Pizza], {Steak, Burger, Sausage}.
partitioned in three groups based on the numerical features, which respectively describe them: Sweetness, Savouriness and Juiciness. The exact values for the features are reported in Table 3 There is a clear distinction between the first group and the others and mild distinction between the second and the third one. Suppose that there are two lypes of users with opposite preferences {Sweel Savouriness Juicy) (type users) and (Juicy Savouriness Sweet) (type two users), the classification task is to distinguish the types of users by their preferences.
cake
biscuit
gelato
steak
burger
sausage
pasta
pizza
sweet
0.9
0.7
1.0
0.0
0.2
0.1
0.4
0.4
savouriness
0.0
0.1
0.0
0.8
0.8
1.0
0.7
0.9
juicy
0.3
0.0
0.7
0.8
0.9
1.0
0.7
0.6
Table Numerical features for the objects of the synthetic dataset.
The main objective of this dataset is to reproduce a synthetic setting in which the features of the objects play an important role determining the rankings. A probabilistic model that expresses such a sctting is not available. We thus propose the following sampling procedure assuming that the two mentioned types of users rank the objects. We assume that both type one and type two users give different and identical importance
8

---

Published in Transactions on Machine Learning Research (06/2022)
to the features of the objects when ranking them. We choose the weights for the most preferred feature to be 1, for the second 0.17 and for the last one 0.09 to reproduce exponential decay in the preference. For example, type one presents a unitary importance weight for Sweet, a 0.17 importance weight for Savouriness and a 0.09 importance weight for Juicy. By summinn the mumerical features of the objects given in Table 3 using the importance weights the two types of users we obtained two sets of scores for the objects, which Table reports. From the table, it is easy to see that the scores given the objects greatly vary for the two
Cake
Biscuit
Gelato
Steak
Burger
Sausage
Pasta
Pizza
Type one
0.93
0.72
1.06
0.21
0.42
0.36
0.58
0.6
Type two 0.38
0.08
0.79
0.93
1.05
1.18
0.85
0.79
Table 4:
Scores given to the food objects by the two different types of users.
types of users and they have strong connection with the underlying feature preferences. In order to creale more challenging classification lask, it is possible to inject Gaussian noise with slandard deviation to the scores and return the vector of indices sorted according to the jittered scores. Formally, the sample procedure is,
Rankingueers ArgSort(Scoreesee + +N(0,02ls)) E Sgg
Rankingueer2 ArgSort (Sooor((Seeeee2222 + oo(00²2 E Sg,
where Sg is the permutation space yielded by the eight objects in the datasel, ArgSort returns the indices the list in imput and Scoreveer refers to the scores as in Table 4
In Table 5 we report the underlying noisc-free preferences of the two types of users which can be derived from Table The preferences are expressed in increasing order, i.e. zero is associated with the least favourite object and to the most preferred.
Cake
Biscuit
Gelato
Steak
Burger
Sausage
Pasta
Pizza
Type one
6
5
7
0
2
3
4
Type two
0
5
7
4
3
Table 5: Noise-free objects preferences for the two types of users. Higher values correspond to more preferred objects.
Real-world dataset. The state-of-the-arl dataset for rankings data is the sushi datasel (Kamishima 2003). Japanese users were asked to rank two different sets sushis. In the first set, there are 10 sushis and the users express full rankings whereas the second sot there are one hundred sushis and the users express non-exhaustive rankings of len of them. We refer to them as small and large sushi datasets. The preference in sushis varies between the two parts of the country the origin of the person can meaningfully be the label for classification task (Kamishima 2003
4.2 Classification
To assess the generalization capability of the graph cut kernel and to compare it with the stato-of-tho-art kernels, fit Gaussian process (GP) classifiers. For the synthetic dataset, choose sample size of 250 for full and top-k rankings and, due to the computational cost of the Kendall kernel, 100 for exhaustive interleaving rankings. For both the small and the large sushi datasets, we use 2500 rankings.
Experimental setting. Samples are split into train 80% and test sets 20%. Results are reported in terms of Fi-scores (Chinchor 1992). which provides a reliable estimate of the actual capabilities of the model as it penalizes the classifier for false positives and false negatives. Note that for a perfectly balanced dataset, i.e. equal number of samples for each category, the F1-score is equal to the accuracy score. To train the
9

---

Published in Transactions on Machine Learning Research (06/2022)
GP classifier use the python package GPftow (Mtthhwws al. 2017 which extended with custom classes. The cut function is applied to graph built from the information on the objects, i.e., the dishes in the synthetic dataset and the sushis in the real dataset. The edges of such graph are calculated using the squared exponential kernel as the similarity score function, i.c.,
e(v, exp (
1 ||u r'113 2
(15)
The lengthscale & is selected using the inverse median heuristic (Schōlkopf & Smola 2002 For the large sushi datasel, use 600 samples from the set of exhaustive ordered partitions R and we retain the top 10% edges of the graph.
Kensal
1.0
0.9
Out (Duns
0.7
0.6
0.5
0.1
0.5
1.0
1.5
2.0
2.5
3.0
(a) Full rankings.
(b) Top-6 rankings.
0.8
0.8
0.7
0.7
0.6
0.5
0.5
1.5
3.0
3.0
(c) Top-3 rankings.
(d) Exhaustive interleaving rank- ings.
(e) Interleaving rankings.
We perform a train/test procedure on the synthetic datasel using 250 samples for each increasing level of noise and all the different kinds rankings. We report the Fl-scores calculated on test data. generated from the synthetic dataset. We average the results over seods.
Figure 4:
Synthetic dataset. The synthetic dataset aims to show the ability of the kernels to handle noisy data. Figure 4 reports the Fl-scores on the lest sets obtained by the GP classifiers for the different kernels on increasing levels of noise. The graph cut kernel performs in line with state-of-the-art kernels and, for the specific case of top-6 rankings, Figure 4b slightly better. We note that the performance of graph cut kernel for full and for the top-6 rankings matches. This shows that, given mild level of censoring top-6 scenario, the graph cut function on the information graph can successfully reconstruct the underlying Weeferences.The Mallows kernel exhibits a sharp drop in performance in the top-6 scenario and significantly worse performance in the top-3 one, Figure 4b For both the cxhaustive (Figure 4d and non-exhaustive interleaving rankings (Figure 4ep. the graph cut. kernel matches the performance of the staie--ffthe-art Kendall kernel. The last two mentioned scenarios present a higher level of variability in performance. For the exhaustive intorlcaving rankings scenario, this is caused by the small sample size of 100, whercas for interleaving rankings, the variability is due to the task difficulty.
in the
Real-world datasct. The sushi dataset is becoming the benchmark dataset to show the generalization capabilities of kernel methods on rankings, (Kondor & Lafferty] 2002 Lomeli el al. 2019). For this challenging classification task the performance on the test set, regardless of the kernel, is limited to an Fl-score of 0.6. Nonetheless, our graph cut kernel slightly outperforms the stato-of-tho-art kernels. More specifically, in the full rankings scenario, Figure 5a| the Fi-scores achieved by the graph cut kernel slightly better compared to the Mallows kernel and better than the Kendall kernel. For the case of the top-6 ranking, Figure 5b the
10

---

Published in Transactions on Machine Learning Research (06/2022)
graph cut kernel is the only kernel to achieve better than random performance. The case of interleaving rankings presents challenge both for the Kendall and the graph cut. kernel, Figure 5c and Figure 5d We note that the performance of the graph cut kernel can still be considered superior to the Kendall kernel as it is less variable across different seeds and slightly better in the large dataset, Figure 5d
Using synthetic and real datasets we demonstrated that the graph cut kernel works least as well as state-of-the-ard kernels used for ranking.
Elbo
F1-score
Elbo
F1-score
0.60
-1400
1500
0.55
Y
-2500
-1600
Cut (Ours)
0.50
-3000
(Durs)
0.50
Kendall
0.45
Kendall
0.45
-1800
0.40
4500
4000
Mallows
0.40
Kendall
Kendall
Iteration
Iteration
(a) Full rankings (small dataset).
(b) Top-6 rankings (small dataset).
Elbo
F1-score
Elbo
F1-score
0.60
0.60
-1500
-1400
0.55
-200
0.50
0.50
-2500
Out (Ours)
0.45
-1450
Out (Ours)
0.45
Kendall
0.40
Kondall
4
16
Kendall
Cut (Ours)
16
32
Kendall
Out (Ours)
Iteration
Iteration
(c) Interleaving rankings (small dataset).
(d) Interleaving rankings (large dataset)..
Figure 5: Train/test procedure for GP repeated over six seeds for the sushi dataset. The small sushi dataset is employed for full (a), top-6 (b) and exhaustive rankings (c), whereas the large sushi dataset used for non-exhaustive rankings (d). For each kind of ranking, we report the evidence lower bound (ELBO) during
training (Left) and the Fl-scores calculated on the test sets with uniform dummy classifier baseline (Right), Note that the r-axis for the ELBO plot is in logarithmic scale and the mcan, first quartile and third quartile
are reported in bright colours in the violin plots.
4.3 Empirical time complexity
In the following, we compare the empirical time complexity for all kernels and highlight the steep advantage of the graph cut kernel. For algorithms meant to be employed in real-world applications, is essential to analyse the empirical time complexity of computing the Gram matrix, in addition to the thcoretical one that was covered in Section 3 In this section, we provide this empirical analysis using rankings sampled from the synthetic datasct.
Experimental setting. The values for the empirical time complexity are averaged over seven trials on Intel Core 17-7700HI CPU @ 2.80GHz. Differently from state-of-the-art methods, the computation of the graph cut kernel make use of GPU hardware acceleration. However, present fair comparison, limit the graph cut kernel calculation to CPU only. The accessibility of hardware acceleration for the graph cut kernel is casily accessible using Python packages such as GPFlow. In other words, after obtaining the feature maps for the rankings, the user can directly feed them into GPFlow that takes care of the GPU acceleration and additional optimizations. To give an idea of the scale of such optimization we report the total time required calculate the Gram matrix for the entire datasct, i.c. 5000 samples. We found that the time required to caleulate the feature maps 6.31s + 88. 6m,, while the time required compute the Gram matrix from the feature maps is 576ms + 19.7ms with hardware acceleration using single Nvidia
11

---

Published in Transactions on Machine Learning Research (06/2022)
Kendail
Mallows
Cut (Ours)
Empirical time complexity for Gram matrix
1
10s
38s
85
151s2
355
8s
31s
695
1236187
0.0s 0.0s 0.1s 0.15 0.26
66s
1175184g
0.15
Seconds
Out [Ours] Kondall
3
10%
40s
89c
159
48h
7s
29s
6és
18:
0.0%
0.15
0.15 0.25 0.36
Nallows
11s
435
96s
17152684
7s
29
66s
118s183:
0:05
0.15
0.15 0.25 0.3s
11s
44:
99s
179-200s
29c
66s
188s184s
0.0s 0.1s 0.2s 0.3s
11s
45s
005s18952995
75
29s
665
117s183s
0.05
0.15
0.2s 0.25 0.35
90
130
210
270
330
390
430
510
570
120
180
240
300
360
420
480
540
100
200
300
400
500
100 200 300 400
500 100 200
300
40a 500
Sample size
sample
(a) Full rankings.
(b) Top-k rankings.
Kendall
Cut (Ours)
Kendall
Cut (Ours)
2
NA
NA
NA
NA
0.Os O. 0.0s 0.0s 0.25 0.2s
2
10s
36
82s
150s238
20s
41s 59s 79s
101s
3
NA
NA
NA
NA
0.0s 0.1s 0.0s 0.25 0.2s
Interleaving length
3
10s
38
86
159x251
36
73s 106614221800
4
3665
NA
NA
NA
0.05 0.1s 0.05 0.25 0.25
411
41s
93s
1725267s
275
525
76s
99s
1295
5
34s
80s
128: 185
0.0s 0.1s 0.0s 0.25 0.3s
5
11s
42s
96s
1773276s
10s
20s
295
376
48s
6
7s
166
28s
44s
0.0s 0.15 0.05 0.25 0.3s
11s
43s
96s
177s277s
24
58
75
98
11s
3s
7s
13s
18s 0.05 0.15 0.05 0.35 0.35
11s
45s
96s
177s276s
05
15
15
2s
2s
40
60
80
100 100 200 300 400 500
100
200
300
400 500
100 200 300
400
500
sample size
sample size
(c) Generic exhaustive rankings.
(d) Non-exhaustive rankings.
Figure 6: Comparison empirical time complexity for calculating the Gram matrix using the submodular kernel and state--ffthh-art kernels. Each figure reports the results for different kind of ranking. Note that the symbol NA is reported when the empirical time complexity exceeds the maximum allowed time per simulation (seven minutes).
GeForce GTX 1060 GPU. Considering that the calculation of the feature maps does not happen when fitting the model, it is clear that the graph cut. kernel can be confidently employed for large-scale datasets.
Experiments. Figure f reports the time spent for computing the Gram matrix as function of the sample size and, for partial rankings, also of the level of censoring. For all kinds of exhaustive interleaving rankings (Figure d and ccb computing the Gram matrix of the graph cut kernel is extremely cheap compared to srate-of-the-ate kernels. For the interleaving case, Figure Bdl, due to the exponential factor, the time required is high but still significantly lower than the time required kernel. In Figure [6 some values for the Kendall kernel are not reported. This is because the Kendall kernel becomes computationally intractable in practice when a high number of ties are present in the rankings it happens for low values of exhaustive interleaving ranking length. The massive speed advantage of the graph cut kernel comes from the fact that the computationally intensive caleulations are donc once per feature map and that the space complexity of storing the feature maps is linear both in the sample size and in the number of object In practice, the graph cut kernel scales almost linearly with the sample size.
compute the Gram matrix using the Kendall
5 Discussion
The graph cut kernel is a theoretically founded kernel that builds on top of the efficient machinery of submodular optimization. Thanks to this efficiency, we have shown a drastic reduction in the computational cost compared previous bernel-based methods for ranked data. Additionally, it inherits all the theoretical properties of the linear kernel since is built on top of it.
3Te time for calculating the feature maps included the presented empirical time complexity for the graph cut kernel.
12

---

Published in Transactions on Machine Learning Research (06/2022)
Permutohedrons are discrete objects best suitable for encoding ranked data. However, they have exponen- tially many vertices where each vertex corresponds to permutation. This property makes the computation of the feature representation complex. In our approach, we use the graph cut function that shows a prin- cipled way to represent the permutohedron through its base polytope. These functions are designed using additional applicalion-specite information. This provides us with principled approach traverse through the base polytope to provide an efficient feature representation. We have shown this empirically through several experiments.
Graph cuts submodular functions and it is only this property that we have used to design the kernels. We believe general submodular functions specific to an application (e.g. entropy, mutual information etc.) may be used to design such kernels. This does not require any changes from our approach apart from designing submodular functions and using application-specifi data.
6 Conclusion
In this paper, we presented theoretically founded methodology to apply submodular function optimization for ranked data of all kinds: full, top-k and interleaving. This allowed us to define the graph cut kernel that attains good empirical performance while only incurring fairly small computational costs. Thanks to the graph cut kernel, we enabled the use of kernel-based methods for large-scale datasets of rankings with the hope of encouraging a more widespread use of kernel methods for rankings. We support our claims by empirically training Gaussian process classifiers using both syuthetic and real datasets and reporting the empirical time complexity. The graph cut kernel has proved match or outperform the performance of the stale-of-the-art kernels both in terms of accuracy on the classification task and of clock time.
We believe that the graph cut kernel will greatly benefit both practitioners, as they now have access to wider range of tools for real-world applications, and theoreticians, as we have consolidated the theoretical connection between the graph cut function optimization and ranked data. We have thus opened several exciting research directions. We leave as an open problem the extension of the graph cut kernel to general submodular functions, which will require a different way to extract information from the rankings. Another possible future research direction to adapt the graph cut kernel from ranking to ratings.
Acknowledgments
The work is supported by Data Science Institute, Imperial College London.
References
Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. Journal of the ACM, 55(5):1-22 2008.
Francis Bach. Learning with submodular functions: A convex optimization perspective. Foundations and Trends in Machine Learning, 6(2-3):145-33) 2013.
Maria-Flowd Florina Balcan, Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, and Gregory B. Sorkin. Robust reductions from ranking to classification. Machine Learning, 72(1-2):130-153, 2008.
Michael J. Best and Nilotpal Chakravarti. Active set algorithms for isotonic regression: a unifying framework. Mathematical Progrumming, 47(1):425-439) 1990.
Nancy Chinchor. MUC-4 evaluation metrics. Proceedings of the Conference on Message Understanding, 1992.
Persi Diaconis. Group representations in probability and statisties. Lecture Notes, 11:i 192, 1988.
Satoru Fujishige (cd.). Submodulor Functions and Optimization, volume 58 of Annals of Discrete Mathemat- ícs. Flsevier, 2005.
13

---

Published in Transactions on Machine Learning Research (06/2022)
Johannes Fürnkranz and Eyke Hüillermcier. Pairwise preference learning and ranking. In Proceedings of the European Conference on Machine Learning, 2003.
Ken Goldberg, Theresa Roeder, Dhruv Gupta, and Chris Perkins. Eigentaste: A constant time collaborative filtering algorithm. Information Retrieval, 4(2):133- 151, 2001.
O. A. Gross, Preferential arrangements. The American Mathematical Monthly, 69(1):4-8, 1962.
F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Transactions on Interactive Intelligent Systems, 5(4), 2015.
David Haussler. Convolution kernels on discrete structures. Technical report, Technical report, Department of Computer Science, University of California, 1999.
David P. Helmbold and Manfred K. Warmuth. Learning permutations with exponential weights. Journal of Machine Learning Research, 10(7):1705 1736, 2009.
Tao Hu, Lichao Huang, and Han Shen. Multi-object tracking via end-to-ena to-end tracklet searching and ranking, arXiv preprint Xiv: 02795, 2020.
Jonathan Huang, Carlos Guestrin, and Leonidas Guibas. Fourier theoretic probabilistic inference over per- mutations. Journal of Machine Learning Research, 10(5):997-1070, 2009.
Rishabh Iyer and Jeff Bilmes. The Lovász Bregman divergence and connections to rank aggregation, clus- tering, and web ranking. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, 2013.
Yunlong Jiao and Jean-Philippe Vert. The Kendall and Mallows kernels for permutations. In Proceedings of the International Conference Machine Learning, 2015.
Yunlong Jiao and Jean-Philippe Vert. The weighted Kendall and high-order kernels for permutations. In Proceedings of he International Conference Machine Learning. 2018.
Toshihiro Kamishima. Nantonac collaborative filtering: Recommendation based order responses. In Proceedings of the International Conference Knowledge Discovery and Dala Mining, 2003.
Alexandros Karatzoglou, Linas Baltrunas, and Yue Shi. Learning to rank for recommender systems. In Proceedings of the Conference on Recommender Systems, 2013.
Maurice George Kendall. Rank Correlation Methods. Griffin, 1948.
Risi Kondor and John Lafferty. Diffusion kernels on graphs and other discrete structures. In Proceedings of the International Conference on Machine Learning, 2002.
K. S. Sesh Kumar and Francis Bach. Active-set methods for submodular minimization problems. Journal of Machine Learning Research, 18(1):4809 -8399, 2017.
Guy Lebanon and Yi Mao. Non-parametric modeling of partially ranked data. Journal of Machine Learning Research, 9:2401-2444 2008.
Maria Lomeli, Mark Rowland, Arthur Grelton, and Zoubin Ghahramani. Antithetic and Monte Carlo kernel estimators for partial rankings. Statistics and Computing, 29(5): 2019.
Laszlo Lovász. Submodular functions and convexity. Mathematical Programming: The State of the Art, pp. 235 235-257, 1982.
Alexander G. de G. Matthews, Mark van der Wilk, Tom Nickson, Keisuke. Fujii, Alexis Boukouvalas, Pablo Leôn- Villagrá, Zoubin Ghahramani, and James Hensman. GPflow: A Gaussian process library using TensorFlow. Journal of Machine Learning Research, 18(40):1 6, 2017.
R. Tyrell Rockafellar. Corver Analysis. Princeton University Press, 1997.
Bernhard Schölkopf and Alexander J. Smola. Learning with Kernels: Support Vector Machines, Regulariza- lion, Optimization, and Beyond. MIT Press, 2002.
14

---

Published in Transactions on Machine Learning Research (06/2022)
A Duality between isotonic regression and min-norm-point on the tangent cone
Let us recall that F: 2 + b+ is submodular functions and let f: bb + b+ be its Lovász extension. We represent the base polytope of F by B(F). Given an ordered partition A = (A1,...,AA) of the set of objects V, we recall the definition of langent cone of the base polytope and derive its support function. Note that it is already derived by Kumar Bach (2017) that we re-derive here for completion.
A.1 Tangent cone and its support function.
Let B, Az We define the tangent cone of the base polytope B(F) characterized by the ordered partition as
( S F(B)) F(V) L(...
(16)
We can now proceed to compute the support function of the tangent cone BA(F), which an upper bound f(w) since this set is an outer approximation of BFF):
sup w s= = sup inf w BEBA(F)
wss=
A(s(BB)) - F(B,)) using Lagrangian duality,
(17)
ab" x xb
1=1
Σ (A: + +... (A,++...+)Aa)))) + Σ(A+ + I(A+...+ + (BA+++)BB -
inf
sup 8
w
(18)
XEb xb
i=1
1=1
inf 2 ()(B(B) - F(B--1)
(19)
XEb xb 1=1
such that w Σ +...+++)))a:;
(20)
Thus, by defining o; = - Aτ, which are decreasing, the support function is finite for w having ordered level sets corresponding
the ordered partition A (we then say that w compatible with A). In other words, if w = Ei= U, the support functions is equal to the Lovász extension f(w). Otherwise, when w is not compatible with A, the support function is infinite.
Let us now denote WA as a set of all weight vectors w that are compatible with the ordered partition A. This can be defined as
WM_ = En 3e E E w
Σ 1=1
U,A., v1 ... 22.22 21
(21)
Therefore,
[(w) if E W4 otherwise.
sup w 8
(22)
(F)
A.2 Duality
For all w E WA, Le., w = E 14 L
01 .... ...2..0 - 1i.
s(w) + #| = Σ'= ;; [F(B)) F(B-1)] +
/ E 14/
(23)
Let us now consider the minimization of the above optimization problem. It can be rewritten weighted isotonic regression problem of the form
min
Σ
B3(a;-a))
(24)
ogbioo S...S iz1
15

---

Published in Transactions on Machine Learning Research (06/2022)
where E b' and 3 b4 are given. Note the change of direction of monotonicity from to for standard isotonic regression setting. We now derive the dual of the above problem as
min f(w) 2110012 wEWn
min wEb" (F)
sTw + 2/1011
(25)
max min 8 TT w + 2 maX SEBA(P) web
(26)
where s* = w- at optimal and the dual problem, max - - 2| is to find the min-norm-pooi on the tangent cone of the base polytope.
The isolonic regression problem of the form Eq. 24 may be optimized using the PAVA algorithm proposed by Best & Chakravarti (1990) in time (In) time complexity. This has also been used in the context of submodular function minimization (Appendix A.3 of Bach (2013); Kumar Bach (2017))
16


Reviews:
[{"review_id": "EZIJDYpl5m", "reviewer": "Reviewer_w9xB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Strengths\n  * Methods work for different kinds of ranking data, cf. Table 1.\n  * Well-written, most parts are easy to follow\n  * Review of related work seems adequate\n\n* Weakness \n  * The methodological contributions are rather weak or *incremental*, that is, the kernel computation is based on known, established techniques, which are only applied here.\n  * Given the above incremental contribution, the experiential evaluation is not very extensive and restricted to two (small) datasets, one synthetic and small (ground set has cardinality **8**).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper deals with kernels for ranking data. The authors introduce the known connection between submodular functions (here the graph cut function) and the base polytope (Lovász, 1982, Rockafellar, 1997).  The connection to ordered partitions, and thus rankings, arises since the faces of the base polytope are characterized by ordered partitions. Since the number inequalities to describe the base polytope scale exponentially with the ground set (to be ranked), the authors resort to a standard outer approximation based on the tangent cone, requiring a linear number of inequalities.\n\nBased on the above approximation they define the feature map of the graph cut kernel as the min-norm point of the tangent cone, which can be computed via isotonic regression (Kumar & Bach, 2017). The isotonic regression problem can be computed using the PAVA algorithm (Best & Chakravarti, 1990), whose solution induces the needed ranking.\n\nFurther, the authors, show how the kernel can be easily extended to non-exhaustive partial orderings via Haussler's convolutional kernel, see Eq. 13, and present a simple sampling scheme to speed up the computation of the kernels.   \n\nFinally, the authors report empirical evidence on two datasets (one of them synthetic) for various ranking settings, using a Gaussian process classifier, showing that their method is slightly better than the two baseline approaches while reporting lower computation times.  \n\n\n\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "\n\n**Major points**\n\nGiven the incremental nature of the paper, the authors should invest more work into the experimental section, i.e.,\n* conduct experiments on more datasets, especially large-scale ones, showing a clear computational benefit over the baselines \n* Conduct experiments in all three settings of Table 1\n* The (submodular) graph cut function seems to be never introduced formally\n* Make more clear why you focus on the graph cut function\n\n**Minor points**\n* Page 3, also explain exhaustive ranking, the ordered partition in Table 2 might not be clear immediately \n* Page 3, Eq. 2., add some intuition for those not familiar with submodular functions.\n* Algorithm 1 is hard to parse, think of a better presentation\n\n**Questions:**\n- Can anything be said about the quality of the rankings induced by the original base polytope versus its outer approximation? \n- How did you pick the number of samples for the method described in Section 3.2 in the experiments?\n- What are the challenges when applying the method to other submodular functions beyond the cut function.\n- Is there a reason to use Gaussian processes over other classifiers, e.g., SVM.", "broader_impact_concerns": "I do not see any ethical implications of the work that would require adding a Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1HdaJgaucC", "reviewer": "Reviewer_iCnv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Significance and impact\n\n> The paper proposes a new feature representation for rankings with many potential applications. However the theoretical properties of this representation are not discussed and the experimental section is not exploring the impact of these properties. The application of the proposed representation may prove to be limited to rare cases.\n\nMy main concern regards the fact that a set of extremely different rankings may share the same representation. Indeed, as soon as the set of constraints $s(B_i)\\leqslant F(B_i)$ is made of large thresholds $F(B_i)$, the point $\\bar s := \\frac{1}{|{\\cal V}|}[1,\\dots,1]$ belongs to the Tangent cone and $\\Phi(A)=\\bar s$. I wonder to which extend this is a bad behavior with respect to the targeted machine learning task.\n\nIt seems that with graph-cut submodular function, these rankings are the one which are incoherent with the inherent clustering of items. Such rankings should be unfrequent in the dataset, and anyway they cannot be classified by any model.\n\nSimilarly, the paper would be more convincing if it would give some theoretical insights on the link between the graph $G$ and the corresponding feature space and/or linear kernel.\n\n# Clarity\n> While the paper is well-written and clear, it suffers several mistakes. \n\nFirst, Kumar & Bach (2017) where considering ordered partitions presented in decreasing order, while current paper use the opposite convention. Unfortunately, some Equations and Algorithm 1 are not coherent with this choice. Here are the errors I have spotted, but I may have missed some others:\n\n* in Section 2.4 and in algorithm 1, $B_i$ should be the union from $i$ to $l$\n* in Equation (9), the constraint should be $v_1 \\leqslant \\dots \\leqslant v_l$.\n\nSimilarly, the labels of Figure 1a are incoherent with the labels of Figure 1b.\n\nSecondly, current version of Algorithm 1 is of complexity ${\\cal O}(l^2)$ due to the \"computation from scratch\" of $B_{k-1}$ and $B_k$. \n\nFinally, the clarity could be improved with some minor changes or additions:\n\n* In Section 2.4, remind that $sup_{s\\in \\hat B^A(F)} ws^T = f(w)$ or $\\infty$ depending on $w$.\n* Close to Equation (9), remind that $B_0 = \\emptyset$.\n* In section 3, define $m$.\n* In algorithm 1, \"Define a*** set to contain ...\"\n* From a figure to another, the proposed approach is denoted *Our*, *Ours* or *Cut (Ours)*. Please be coherent.\n* In figure 6b, the y-axis is increasing, while in Figures 6c and 6d it is decreasing. Please be coherent.\n* The y-axis of Figure 6c is missing its label.\n* The experimental setting would be easier to understand if the classification model would be more usual (SVM, random forest, logistic regression, ...).\n* In Section 5, the second sentence of the second paragraph is missing a verb.\n\n\n# Accurate evaluation \n> The interest of the proposed representation is only supported by experiments.\n\n> These experiments and the corresponding results are interesting, but the experiments remain frugal and there is some incoherences in the shared code.\n\nFirst, while the proposed representation may be used in many ways, the experiments limit themselves to one submodular function, one kernel, and one classification model. \n\nSecondly, the representation designed by the proposed approach consists in weighting items, with an higher weight for top-ranked items. We may design a trivial representation with the same property: associate the $k$-th item to the weight $n-k$. What would be the results obtained with such naive representation?\n\nThirdly, in current implementation, Mallows and Kendall-Tau kernels are obtained by computing the appropriate kernel on-top of a representation of the examples in a $n(n-1)/2$ feature-space. I wonder to which extend such indirect computation may artificially increase the computation time of corresponding experiments.\n\nFinally, current implementation of the proposed representation\n\n* differs from an experiment to another,\n* is wrong for full_and_topk experiments (constraint violations are not handled),\n* is quadratic\n    * due to the `B_i_ = B_i.copy()`, L.56 in full_and_topk\n    * due to `reduce(lambda a, b: a.union(b), ...)`, L.113 and L.114 in interleaving\n\n\n# Positioning (clarity bis)\n> In my opinion, current positioning of the paper is not the right-one, and hinders the clarity of the paper.\n \nLet me first remind the official positioning (given paper's title, abstract and introduction): \"A new and efficient to compute kernel for ranking based on the graph cut function\". In my opinion, this positioning is misleading in two aspects:\n\n* The linear kernel is not required to use the proposed representation.  Any standard Machine Learning model may be used on-top of it.\n* A graph cut function is not required to define the proposed kernel, any submodular function would do the job. However, I appreciate that the paper demonstrates the utility of this kernel through a graph cut function, as such functions are easy to define in many applications.\n\nThe discrepancy between what brings current paper and what is claimed at the beginning of the paper hinders its clarity. The technical sections (2 and 3) are defining a family of kernels, but not the graph-cut one:\n\n* given a submodular function $F$, Sections 2 and 3.1 explain how to get a representation;\n* given a representation, Section 3.2 explains how to get a kernel;\n* given a submodular function $F$ of complexity ${\\cal O}(p)$, Section 3.3 gives the overall complexity of the proposed approach (it also reminds the PAVA algorithm, which is the one used to get the representation).\n\nThis family of kernel is used in combination with the graph cut function only in experiments (and in figures 2 and 3).\n\nTo resume, the pitch mentions a \"graph-cut kernel\", but the technical part presents a much more general framework, and this framework is used to get a \"graph-cut kernel\" only in applications. It's up to the reader to guess that it will be so.\n\nAnd the worst is that it has to be a guess. The fact that \"graph-cut kernel\" means \"the proposed kernel applied with a $F =$ graph-cut function\" has to be inferred from the reader, it is neither mentioned. the closest sentence are\n* \"In Section 2, we show how to encode all kinds of rankings as ordered partitions and their relationship with submodular functions, in particular with the graph cut function\" (Section 1)\n* \"Optimal values $v^*$, Eq. (11), using the submodular cut function and the information graph of the sushi dataset for $A$.\" (legend of figure 2)\n* \"In our approach, we use graph cut functions that shows a principled way to represent the permutohedron through its base polytope.\" (Section 5 Discussion)\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a new feature representation of rankings, which is defined for both exhaustive and non-exhaustive partial rankings.\nThis representation is parameterized by a submodular function $F$ on a set of items $\\cal V$. One of the main property of this representation is its sparing computation cost: ${\\cal O}(pl)$ for an exhaustive ranking, where $p$ is the computation cost of $F$, and $l$ is the number of equivalence classes of the partial ranking.\n\nSome experiments demonstrate the interest of the proposed representation for a supervised binary-classification task where examples are rankings on a finite set of objects $\\cal V$.\n* First, a similarity graph $G$ on items is built from item features and the submodular function $F$ is defined as the graph-cut function on $G$.\n* Secondly, each example is associated to the feature representation derived from $F$.\n* Finally, the classification task is handled by a Gaussian Process with linear kernel on-top of this feature representation.\n\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "The only critical adjustment is the correction of the errors in the text, figures and algorithms.\n\nRegarding the experiments,\n\n* I would prefer the experiments to be redone with a correct and more fair implementation,\n* I would appreciate the addition of the naive baseline \"the weight  of the $k$-th item is $n-k$\",\n* and I would appreciate the use of more standard Machine Learning algorithm.\n\nBut I guess it would not change the conclusions of the experiments, so do not consider this changes as mandatory.\n\nI would also prefer the positioning of the paper to be updated, but it's also not mandatory. Note that if the positioning of the paper is changed, the title of the paper has to change too.\nOn the other hand, if the positioning remains the current one, please give a complete definition somewhere (Maybe in Section 3.3).\n", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WhPfSy4EAR", "reviewer": "Reviewer_moz1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: Background is adequately discussed, and the idea itself has good potential.\n\nWeaknesses: \n\nI would classify this paper as somewhat of a “methods” paper i.e. the paper proposes a new similarity metric that to aid in relatively fast similarity evaluations based on full or partial order rankings. While the paper does not propose a new algorithm, the proposed kernel, especially because of its ease of computation could be impactful in several problems. However, given that the potential usefulness or impact isn’t analyzed theoretically (with guarantees etc.), the empirical section is less than convincing. I would disagree with the authors’ assertion on the sushi dataset being “state of the art” for evaluation. Is there a reason not to extract out partial rankings from user-movie datasets, for example, and do a more thorough evaluation? The currently presented experiments are hardly “proof of concept”, rather than being a useful indicator of applicability of the proposed kernel. \n\nThe paper also lacks motivation for using the said feature embedding as appropriate for measuring ranking similarity. There is an example that the authors take for a size 10 full ranking order, but it is unclear how the absolute value of \\phi_d is indicative of similarity, especially for the case when the order is not full but only partial. Expanding on this will be helpful. \n\nThis is especially aggravated by the fact that the partial rankings are handled by mere averaging. Moreover, to speed up large computations, random subsampling is proposed which leads to large variances in performance. Further concentrated efforts are required to assert if the proposed kernel is practically viable. \n\nOne way to expand on the empirical side would be to use ratings datasets, as mentioned above. It is unclear why is this not straightforward and the authors have left it as future work in their conclusion? As most ratings are arbitrary anyways, and what really matters is preferences in users. Why then can the authors not extract preference information from ratings and use these preferences as partial orders for their framework? This will help strengthen the otherwise weak empirical section. Currently the propose method seems to perform reasonably well compared to baselines on full rankings, but the performance on the tradeoff between speed vs accuracy has large variances for the limited experimental evaluation on a single real-world dataset that is presented. The timing experiments are not suprising, given how the computations are performed.\n\nThe authors state in the conclusion -- “as we have consolidated the theoretical connection between the graph cut function optimization and ranked data “. I think this is an over-sell, the base polytope is already well-known, so is the lovasz extension that is defined on partitions governed by rankings. \n\nRegarding “Extension to general submodular functions” – Can the authors please clarify this a bit more? What would such use-cases look-like ? An example or two would be very helpful. \n\n\nMinor clarifications/Typos: \n\n``and it is traditionally represented by the projection onto that hyperplane” in Def 2.1 is unclear. While the mathematical formulations are clear, the statement made for the projection onto the hyperplane does not make sense to me. In the same vain, Fig 1(b) could use more discussion. I would suggest a 3d image for Fig 1(a) to clarify the implication on the ranking shown in Fig 1(b).\n\nDef 2.2: Please define A within the definition before saying B = \\cup_i A_i. What is “l” and where was it defined ? Please write it as size of A explicitly. \n\nWhy is it called “graph cut kernel” ? \nClarify -- “Note that vi∗ corresponds to the set Ai, while s∗j corresponds to the object j and s∗j = −vi∗, if object j \nbelongs to the subset Ai. “\nIndices in eq 18 seem to be incorrect. \nWhat is ‘m’ in eq 17? Is it supposed to be ‘l’ ? \nPlease label the dots in Fig 3b with respective indices. There are 9 dots because d=9,10 result in the same similarity value ?\n“which is yield by submodular functions “ \n\n“ exponential number of constrains in the number of objects. “\n\nSec 4.1 for the synthetic dataset, the ordering mentioned to identify type one and type two users is exactly the same. Please fix to differentiate. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes making use of min-norm point of the tangent cone of the base polytope as the feature embedding space to evaluate similarity amongst rankings. The entire machinery for the setup is already present in previous works. This paper's contribution is identifying this feature embedding space as a potential similarity embedding metric, and presents a few experiments to justify the use of proposed kernel space, in terms of classification accuracy and speedup. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Please see the weakness section for more detailed discussion. The main points would be a more thorough empirical investigation, cleaning up the writing, better motivation of the use of the said kernel especially for partial rankings. ", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers judged this paper as presenting a potentially promising approach with a proof of concept empirical section. While the empirical section was deemed a bit weak, the reviewers judged that it was sufficient to illustrate the potential of the approach, which could be investigated more thoroughly by the community. All reviewers recommended acceptance and thought it was of interest to the TMLR community.

As the authors have already addressed most of the corrections asked by the reviewers in their revision, the paper can be accepted as is. Any missing clarification can be included in the camera ready version (please detail in a comment on Openreview any other changes made to the final version of the paper and how it relates to the reviews).
Decision: Accept (poster)