Kissing to Find a Match: Efficient Low-Rank Permutation Representation
Authors: Hannah Dröge
Zorah Lähner
Yuval Bahat
Onofre Martorell Nadal
Felix Heide
Michael Moeller
Venue: NeurIPS 2023 poster (2023)
Keywords: low rank
permutation
kissing number
matrix factorization
assigment problem
TL;DR: We propose an efficient representation for permutation matrices that is well-suited for optimization in learning frameworks.

Abstract: Permutation matrices play a key role in matching and assignment problems across the fields, especially in computer vision and robotics. However, memory for explicitly representing permutation matrices grows quadratically with the size of the problem, prohibiting large problem instances. In this work, we propose to tackle the curse of dimensionality of large  permutation matrices by approximating them using low-rank matrix factorization, followed by a nonlinearity. To this end, we rely on the Kissing number theory to infer the minimal rank required for representing a permutation matrix of a given size, which is significantly smaller than the problem size. This leads to a drastic reduction in computation and memory costs, e.g., up to $3$ orders of magnitude less memory for a problem of size $n=20000$, represented using $8.4\times10^5$ elements in two small matrices instead of using a single huge matrix with $4\times 10^8$ elements. The proposed representation allows for accurate representations of large permutation matrices, which in turn enables handling large problems that would have been infeasible otherwise. We demonstrate the applicability and merits of the proposed approach through a series of experiments on a range of problems that involve predicting permutation matrices, from linear and quadratic assignment to shape matching problems.

Kissing to Find a Match:
Efficient Low-Rank Permutation Representation
Hannah Dröge University of Siegen 57076 Siegen, Germany
Zorah Lähner University of Siegen 57076 Siegen, Germany zorah www.nnerruni-ieeeeee..
hannah. droegeSuni-siegee de
Yuval Bahat
Onofre Martorell
Princeton University
University of Balearic Islands
Princeton, NJ 08544, United States yuval. bahat@gmail.
Investigador ForInDoc del Govern de les Illes Balears 07122 Palma, Illes Balears, Spain martorell@uil cat
Felix Heide
Michael Möller University of Siegen 57076 Siegen, Germany michael. moel er cerrrunn-sieggn.co
Princeton University
Princeton, NJ 08544, United States fheide@cs. princeton. edu
Abstract
Permutation matrices play a key role in matching and assignment problems across the fields, especially in computer vision and roboties. However, memory for explicitly representing permutation matrices grows quadratically with the size of the problem, prohibiting large problem instances. In this work, we propose tackle the curse of dimensionality of large permutation matrices by approximating them using low-rank matrix factorization, followed by nonlinearity. To this end, we rely on the Kissing number theory to infer the minimal rank required for representing a permutation matrix of given size, which is significantly smaller than the problem size. This leads to drastic reduction in computation and memory costs, e.g., up orders magnitude less memory for problem of size n 20000, represented using 8.4 10 elements in two small matrices instead of using single huge matrix with 4 x 10a elements. The proposed representation allows for accurate representations of large permutation matrices, which in turn enables handling large problems that would have been infcasible otherwise. We demonstrate the applicability and merits of the proposed approach through a series of experiments on a range of problems that involve predicting permutation matrices, from linear and quadratic assignment to shape matching problems.
Introduction
Permutation matrices, which encode the reordering of elements, arise naturally in any problem that can be phrased bijection between two equally sized sets. As such, they are fundamental many important computer vision applications, including matching semantically identical key points in images (50] 47
48 49), matching 3D shapes or point clouds [18. 46 27 estimating scene flow on 35 and solving jigsaw puzzles [28 as well as to various sorting tasks [1]
point clouds
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

V
V
1.0
0.0
-1.0
-0.0
0
0.5
0.87
1.0
0.0
0
-0.5
0.87
0.5
0.87
0
2 max
2.0
-1.0
-..0
-0.5
-0.87
-0.5
00.7
0.5
-0.87
0.5
0.87
0.5
0.87
Figure I: Geometric intuition behind our approach on a 2D unit sphere. For well-distributed vectors V E x where the number of vectors determined by the Kissing number (Kiss(2) = 6), the cosine angle between different vectors Vi, and Vj.+ i * j. is (Va.: Vg.)) cos(a) S 0.5, while (V,,, Vi,) = for the same vector. Thus, for any permutation P. the matrix matrix-matrix product of V and (PV)* merely has to be thresholded suitably to represent the permutation P. i.c. P = 2 mPa) 0).
A permutation corresponding to the bijection from the set {1,... n onto itself, can be represented efficiently without permutation matrix by merely enumerating the n elements
(p(1), (()))...,(()) E N
(1)
However, this representation unsuitable for most computer vision problems that involve estimating p through optimization since this representation (i) is inherently discrete, yielding combinatorial problems for which no natural relaxation exists, and (ii) induces solution space with a meaningless distance metric, element i in the set generally is not 'closer' to element i + than it is to any other element j.
As result, almost all methods for predicting permutations, including learning- based methods, favor a permutation matrix representation instead, i.e., formulating permutation as an element in the set
Pa {P E 10,1)"Xn
P 1, Σ Po = 1
with p()) j 1 representation corresponding P.j in the matrix representation form (2) which allows predicting via optimization methods. Yet, the advantages of the matrix form representation (2) come at the cost of a prohibitive increase in memory, as requires storing n² binary numbers P.j E {0, 1), or after commonly used relaxations even m floating point numbers instead of the integers in (T). This renders matching problems with n >> ~ 10 largely infeasible as their corresponding permutation matrix P constitutes over one hundred million entries.
To handle large matrices whose size prohibits explicit processing and storage, existing approaches sparse representations, i.e., storing only small portion of matrix values in
typically either the form of ji, Pi.j) triplets, where P., F 0, or employ low rank representations, i.e., forming a large matrix P as product of matrices
P P=
with V,W _ and m << n. Unfortunately, neither of these approaches is applicable to permutation matrices: sparse representation cannot be used as the sparsity pattern is not only unknown a-priori but actually the sought-after solution the problem. On top of that, since permutation matrices are by definition full rank, a low-rank representation can yield only crude approximation at best.
Contributions. In this work, we alleviate the limitation on problem size by harnessing the well- studied problem of (bounds for) the so-called Kissing number, which, in practice, translates to introducing simple adaptation to the matrix factorization approach (3). In particular, we exploit the fact that for row-normalized matrices V and W, the entries of VW correspond to the cosines of the angles between the matrix rows. We then apply a pointwise non- non-linearity on the product of matrices (3). which allows representing any permutation while using m << n. We use the Kissing number theory provide an estimate for how small an we can use. We elaborate on these theoretical considerations in Section 3 and provide an illustration of the geometric intuition for our
approach in Fig. |

---

We then demonstrate the applicability of the proposed approach through several numerical experi- ments tackling various problems that involve estimating permutations, including a study on point alignment, linear assignment problems (LAPs), quadratic assignment problems (QAPs), and real- world shape matching application. We find that the proposed approach trades off only little accuracy to offer significant memory saving, thus enabling handling bijection mapping problems that are larger than was previously possible, when full permutation matrices had to be stored.
2 Related Work
2.1 Permutation Learning and Representation
Permutation learning aims develop a model capable of predicting the optimal permutation matrix that matches a given input data or label. Previous studies have suggested relaxing permutation matrices to continuous domains, such as the Birkhoff polytope 22 approximate solutions for these optimization problems but still faced the problem of enforcing the sum-to-one constraints, which are commonly approximated using Sinkhorn layers (34). In 2011, Adams et al. (34] proposed the Sinkhorn propagation method, with the goal of iteratively learning doubly-stochastic matrices that allow the prediction of permutation matrices. Following the same research line, Cruz et al. [38] proposed Sinkhorn networks, followed by Mena ef al. [28] proposing
networks, adding Gumbel noise to the Sinkhorn operator to learn latent permutations. Grover et al. [16] made further efforts in the relaxation of a learned permutation matrix and propose to relax the matrix to
become unimodal row-stochastic, meaning that the rows must maintain a total sum of one while having a distinct argmax. More recent studies suggest to circumvent the constraint of row and column sums being one by predicting permutations in Lehmer code, whose matrix form results to be now-stochastic [9]. Other works propose alternative representations of permutations in different domains, as to work in the Fourier domain to give a compact representations of distribution over permutations 17 200 or embed them to the surface of hypersphere 33
2.2 Nonlinear Matrix Decomposition
In previous work nonlinear matrix decomposition, Saul 40 aims find a low-rank matrix I. that approximates a sparse nonnegative matrix P by applying an elementwise nonlinearity a to L,, i.e. P (L). and proposed an alternating minimization method solve for L directly. In further work, [3). Saul analyzed the geometric relationship between the sparse and low-rank matrices, specifically for a as a rectified linear unit (ReLU), For ReLU as nonlinearity, Seraghiti al. 42] subsequently proposed an accelerated method of 44 to solve this problem, and method, working with version on L VW, derived from the product of two matrices. In our work, we exploit this problem of low-rank approximation for permutation matrices and show its relationship to the Kissing number.
2.3 Assignment Problems
The goal of assignment problems is to find permutation between two ordered sets while minimizing the assignment costs. The two most common versions are the linear and quadratic assignment problem (LAP and QAP) which are based on element-wise and pair-wise costs, respectively. An [22]. The QAP was first introduced by Koopmans and Beckmann (21) and can be written minpee, tr(APBP ) + tr(C" P), for A, B E IR nx and C E R nx being a problem where A E R is the cost function between elements of the first object to match, B Rax is the distance function between elements in the second object and C E Raxx is a point-wise energy. The QAP has been proved to be NP-hard so no polynomial time solution can be expected for general cases. As a result, many relaxations of the problem exist, for example by relaxing the permutation constraint [14] or by lifting the problem to higher dimensions [18 [5]. A survey on various relaxation approaches can be found in [24] While the relaxations do ease some aspects of the problems, they normally do not decrease the dimensionality of the problem which remains demanding for large n.
LAP can be solved in cubic time using the Hungarian algorithm
2.4 3D Shape Correspondence
3D shape correspondence also often posed as an assignment problem between the sets of vertices of pair of shapes, for example through point descriptors matched by an LAP in an QAP aiming to
3

---

preserve distances between all point pairs. However, 3D shapes are often discretized with thousands of vertices which makes optimization for a permutation computationally challenging. Hence, the permutation constraint is often relaxed [36] and, even though the tightness of relaxation might be known T0 the optimization variables still scale quadratically with the problem size. [3] and
[46] the QAP is deconstructed into smaller problems and then each of them is optimized with series of LAPs, while [41] solve for permutations as a series of cycles that gradually improve the solution.
Because permutation constraints for large resolution become infeasible, and, hence, the restriction to cases with the same number of vertices, recent methods often do not impose these constraints at all. The functional maps framework [30] converts the output to a mapping between functions on the shapes instead of vertices and can reduce the dimensionality drastically by using the isometry invariance property of the eigenfunctions of the Laplace-Beltramm operator [32]. Other lines of work
rely on a given template to constrain the solution 15 44 impose physical models that regularizes
the deformation between inputs [1] 12 [1], or learn solution space through training [8 23 26]
However, with the exception of template-bare based models, these cannot guarantee permutations.
Low-Rank Permutation Matrix Representation
A common approach solve optimization problems with costs E over the set of permutation matrices Pn, (including those arising from training neural networks for predicting assignments) is to relax the problem by replacing Pn by its convex hull conv(Pn), i.e., the set of doubly-stochastir matrices:
min (Pc)nv(P..)
E(P).
Since P grows quadratically in n, has an unknown sparsity pattern, and the true solution is always full rank, such problems pose significant challenges for large n. In this work, we make the interesting observation that non- non-linearity as simple as a rectified linear unit (ReLU, denoted by σ)) is sufficient not only to restore a full rank, but to represent any permutation matrix exactly. More precisely, we propose to replace the set (on)(P,) in (4) with the set K.m (Pr) (a(2VWT 1) V, W R=xm) and use the so-called Kissing number 22 52 to show that Pa. C (P..) for a surprisingly small
m. Let us first formalize our approach by defining the Kissing number:
Definition 1. For a given m E N, we define the Kissing number Kiss(m) as
Kiss(m) == max E N 3A E Raxm, ||A,.Ile = 1, 2(A,, A S 11, j}.
(5)
Note that the Kissing number can be interpreted geometrically as the maximum number of points that m-dimensional unit sphere such that the angle formed between each pair of
be distributed different points is at least arccos(0.5). This property quickly establishes Pn C (Pm)))):
Proposition 1. Let P E P,, rectified linear unit (ReLU), Then for every m such that S Kiss(m) there exist V, W E = such that
Pn be an arbitrary permutation matrix, and a, a(x) = max (z, 0) denote
P= ==V - 1).
(6)
Proof. Let V E maxm be a matrix that satisfies the equalities and inequalities of 5 and let W = PV. Then it holds that
S if Pr #1 otherwise
2(V.,, W9a)
(7)
2
Consequently
5o
if Pr, + otherwise
W,,),
(8)
11
which proves the assertion.
To determine the minimal rank that is required for representing permutation of elements, we rely on extensive studies in the past few decades which computed either exact values or lower and upper bounds for different values of m 77].

---

Using P = o 1) for relaxing 4 yields relaxation that requires only 2mn instead of n² parameters, with m << n (is For instance. Kiss(24) 196560 implies that matrices of rank m = 24 are sufficient for representing any arbitrary permutation matrix of up to n = 196560 elements, thus requiring 4000 times less storage memory: 2-24 196560 instead of 1965602 parameters. Furthermore, Pn C Km (Pr,) ensures that in stark contrast to direct low-rank factorization - any permutation matrix can still be represented exactly. Empirically, the optimization over parametrizations o (2V W - 1) turned out to cause significant challenges, likely due to the non-convexity and non-smoothness of the problem. To alleviate this problem, we resort to a smoother version of 66) which still approximate permutations to arbitrary desired accuracy:
Proposition 2. Let P E Pn, and denote an arbitrary permutation matrix and an arbitrary entry- wise strictly monotonically increusing function, respectively, and let s denote the row-wise Softmax
function s(A)s,, = Exp Then Vn S Kiss(m) and Ve > 0 there exist V, W E -gxx and
exp
0, such that
P P PP-s(agle (ag(VW()) s.
Proof. Similar to the proof in Proposition W = PV to obtain
I we start by choosing satisfying 5 and setting
(VW*),; = (Ve., Wan)
[=1
if P3,
S 0.5 otherwise
Then Vi, s.t. P. 1 and * (i.e., P. 0) it holds that (VW"))s > g(VW7) )x Finally, to yield the assertion we use the Softmax property of converging to the unit vector in the limit s(a.i.)) 3000 ej (with) j = arg max A, by taking to be large enough.
In practice, we use g(z) = 2x. in accordance with the representation in 66. We use this smoother version to validate the proposed low-rank representation for handling large matching problems the experiments we report next. Please notice that this is only proof of existence of decomposition into V, W, not every V, W lead to a permutation and an optimisation not guaranteed to find a correct decomposition.
4 Experiments
The following experiments validate our efficient permutation estimation method for different applica- tions, and they confirm the ability to scale to very large problem sizes. First, as a proof of concept, we demonstrate our approach on the application of point cloud alignment for the two non- lineeanasss proposed in Section 3 and introduce our sparse training technique. We then validate the effectiveness of our approach in the context of linear assignment problems and show how to handle sparse cost matrices. We perform further experiments the context of generic NP-hard quadratic assignment problems, and integrate our approach into state-of-the-an shape matching pipeline, thus providing the same level of accuracy while enabling a higher spatial resolution.
4.1 Implementation Details
We use the PyTorch Adam optimizer [19 with its default hyperparameters in all our experiments. The estimation of V and is performed in parallel.
Stochastic Optimization. Fully benefiting from our proposed compact representation requires the costs E (or an approximation thereof) to be evaluated without ever forming the full (approximate) permutation matrix, as this step would inherently return to necessitate n² many entries. To this end, we introduce the concept of stochastic optimization, which for our softmax- s(2a//TT) arising from Proposition 2 is not stochastic training in a classical sense: we propose to fix but two entries in each row our approximate permutation. Specifically, in any supervised (learning-basee basedd scenario where it is known that the yi-entry of the i-the row of the final permutation P ought to equal to one, each step of our optimizers merely computes the y and one randomly chosen (r. entry) of each row, and computes the softmax implicitly assuming P., = 0 for j o f.,,r.), i.c.
representation
these two entries only while
P.l....) s(2aV (W (Won.))))))
(9)
5

---

In the above, we used W W..r:l to denote the 2 x m matrix consisting of the yı-th and the r--th row of W. Our stochastic approach requires the computation of 2n entries per gradient descent iteration only and by randomly choosing the r; manages to still approximate the desired objective well.
Normalization of V and W. Since propositions] [ and 2 rely on row-normalized matrices, explic- itly enforce this constraint whenever we compute P. by using Vi, + [V. Vi,,, W,, f [W.,, W
We omit this step from the presentations below for the sake of readability.
Softmax Temperature. Since the values of (V.., W3:) are bounded by one following the aforemen- tioned normalization, the temperature parameter determines the trade-off between approximating a hard maximum (as required for accurately representing permutations, see Prop and favorable opti- mization properties (i.e., meaningful gradients). We specify the schedule (constant or monotonically increasing) in each of the experiments below.
4.2 Point Cloud Alignment
As proof of concept, we demonstrate that proposition is correct and the optimization process converges. We explore the different choices of non-linearity, starting with ReLU and continuing with Softmax, using the task of predicting linear transformation over point clouds. In this task we aim to match a point cloud X1 E R=xm consisting of n m-dimensional points, uniformly distributed on the unit hyper-sphere, to its linearly transformed and randomly permuted version X₂ R=xm, To obtain X2 we multiply X1 by a randomly drawn matrix Our E I " and apply a random permutation. Then, optimize over the estimated transformation matrix @ which in this experiment defines our permutation matrix P(0):
P(O) (2)
(10)
Note that our representation in (6) is fully parameterized by θ, with V = and (()) X2O, and V and W are row-wise normalized in each iteration. Here P(O) is equal to the correct permutation correctly aligns the point clouds, i.e. minimizes the angle between corresponding points in V and (()) while maximizing the angles between non-corresponding points.
We solve for the permutation by performing 20000 minimizing steps with a learning rate set to 0.01
over the negative log-likelihood loss
= arg min
log (()))..)),
(11)
71 i=1
where yi is the index of the point in X₂ which corresponds the hth point in X1. We experiment with different numbers of points n. each time choosing the dimension m to be just big enough to satisfy the Kissing number constraint from Proposition [ i.e., Kiss(m) 2 Kiss(m 1). To check that we were able to find the correct transformation matrix e and therefore the correct permutation matrix throughh optimization, we verify that the nearest neighbor (closest point) for each row in V is located in row j of matrix W that satisfies P.y = 1. We find that this is indeed the case in all experiments with different numbers points n E (10, 100, 1000, 10000}, thus establishing that we could reach the correct permutation through optimization. We achieve equally good results when replacing the point-wise non- lineariy ReLU with Softmax P(O) (2aVW (()"))
Due to the quadratically growing size of the permutation matrix with an increasing number of points, we further propose optimize for the permutation matrix stochastically. as described in Section 4.1 We ran experiments with similar settings as above, wherein we gradually increased the value of the temperature parameter a linearly during optimization from a 5 10-5 5 to a 1000. In these experiments, we again found that each point was paired with its corresponding nearest neighbor. Also, we could reduce the memory consumption, as shown in Fig. 2
4.3 Point Cloud Alignment on Spectral Point Representation
We conduct an additional experiment on point cloud alignment in the context of the functional maps framework 30) Here, the goal to extract a point-to-point correspondence between two shapes X,Y Y from x m-dimmensionl functional map C [30 where m is much smaller than the number of vertices in X and Y. possible interpretation of is that it aligns the spectral point representations xx, By E nx in which each point x is represented by the vector of values

---

of the first m Laplace- Beltrami eigenfunctions at I such that P. Øx 2 By C. where P is the unknown permutation between X and Y. Given C, P can be retrieved by a nearest-neighbor query between 4x, C as proposed in the original paper (see [30,, Section 6.1), or by solving Linear Assignment Problem (LAPP) if bijection is desired. This exactly the same setting as in Section 4.2 with small amount of noise in the point clouds. We use the FAUST registrations ( with the original 6890 vertices, a downsampled version to 502 vertices for those experiments and C' generated by the ground-truth correspondence. Then, xx By C can be directly used for V and W in our method.
We compare our method, which calculates correspondences the same way as described in Section 4.2) to a general LAP solver (specifically the Konker-Volgenee algorithm from sklearn linear sum assigmment), nearest neighbor computation. optimal transport (as implemented in the python POT package), and stochastic matrices generated by Sinkhorn iterations. In Table | we show that our method outperforms all baselines in terms of geodesic error of the final matching and shows positive trends in terms of runtime and memory consumption.
502 vertices, m
20
6890 vertices, m = 50
Method LAP
Error
Time
Memory
Error
Time
Memory
1.3 x 10
0.023s
8.02 MB
3.1 x 10
79.2s
565.31 MB
Nearest-Neighbors
8.2 x 10-1
0.008s
5.22 MB
4.0 x 10-1
2.6s
34.00 MB
Optimal Transport
3.8 x 10
0.524s
12.58 MB
2.0 x 10
182.7s
1862.27 MB
Sinkhorn iterations
1.4 x 10-1
0.030s
9.4 MB
3.0 x 10-1
12.0s
750.55 MB
Ours
2.2 x 10-3
0.801s
18.18 MB
2.5 x 10-2
77.6s
42.35 MB
Table I: Comparisons of point-wise correspondence extraction from ground-truth functional map [30] for FAUST. The error the mean geodesic matching error of all points. Please note that all code except ours and Sinkhorn iterations are from libraries that are likely more optimized in terms of runtime and memory consumption. The memory consumption evaluated on CPU only.
4.4 Linear Assignment Problems
We next validate our method on balanced Linear Assignment Problems (LAPs), which typically involve assigning a set of agents to an equally sized set of tasks, e.g., when optimizing the allocation of resources. We show results on collection of regularized LAPs in the form
arg min V.W
P(V,)) + W)),
(12)
LAP torm
regularizer
where P(V,W)- (2aVWT) is permutation and A E guxn is some given similarity matrix. While the Softmax non-lineant linearitrrtt ensures all rows sum to one, H(P(V, W)) is a regularization term enforeing columns summing to one as well, to satisfy the permutation constraints:
E, 1)
(13)
Due to the row-wise Softmax all rows already sum to one but we incentive the columns to sum to one as well, as necessary for permutations.
Dense Matrices. We evaluate on set of LAPPs based on descriptor similarities of 3D shapes from the FAUST dataset [3], with n randomly chosen vertices per object [I3]. Let Dx , Dy E gaxk be two k-dimensional point-wise descriptors of the shapes X, Y corresponding to n points. We use the SHOT 377 (I x352) and the heat kernel signature 43 [B=x101) with their default parameters as descriptors and stack them together to comprise D. E 2 in total, then A = Dx D.P. Solving an LAP with this type of similarity matrix is used e.g. in 46 as the initialization strategy.
We generate 100 problem instances by pairing each of the 100 shapes in FAUST with a random second shape to get the pair X, Y. Then we evaluate the relative error of the energy compared to the energy of the optimal solution (restricted to valid permutation solutions), and the average Hamming distance to the next valid permutation (namely, the number of elements that violate the permutation constraint). We ran experiments with n 100, 30, a 20 and used a greedy heuristic to generate valid
7

---

-10*
Mem. Cons. in GB
0.6
10
sparse
Relative Error
Runtime in Sec.
dense
0.4
10-1
0.5
0.2
10
0
0.5
12
64
100
150
12
100
150
-109
Instance Size
Instance Size
Figure 2: Memory consumption for point cloud alignment
Figure 3: Relative error and runtime QAPLIB dataset
permutations from the results violating the permutation constraint (iteratively projecting the maximum value the permutation to one, and the rest of the corresponding row and column to zero). Out of the 100 instances, 53 lead to valid permutations without the heuristic. 'he average relative error of immediately valid permutation is 1.8% and after neeudo-projection the Softmax, every matrix has 100 non-zero entries that are all nearly equal
all instances it 2.0%. Due to
On average, the Hamming distance of invalid permutations to the next valid one is 1.38 (1.4% of the problem size) which means in most cases one would have valid permutation after adjusting one entry.
Sparse Matrices. Given a matrix A, that is sparsely populated and only contains non-zero entries in subset S Al. * 0}, compute and optimize the permutation matrix sparsely in ( E S by calculating the matrix factorization only at the required entries, similar to Section but without restricting the number of entries per row of P to two. Also we take into account random entries (q. r) & S. We ran experiments for A with matrix density of |S| = 0.01n² for 20 with increasing a from 1 to 20 iteratively and measure
1000, 5000 and 10000 and Hamming distance of at most 0.28% of the problem size. To get valid permutation matrix, we used the same heuristic as in the dense case and measured a relative error below 7.8%, compared the Hungarian algorithm. Also, we could measure memory reduction by over 65%.
4.5 Quadratic Assignment Problems
Quadratic Assignment Problems (QAPs) is broadly employed mathematical tool for many real-life problems in operations research such as circuit design and shape matching. We demonstrate the application of our approach to non-convex QAPs of the form
arg min PVV, W) WV,,W) V.W
(14)
where pVV, W/) vec(s (2aVWT)) is the vectorized version of the permutation and A E "=" xn" is cost matrix. V and W are normalized. The permutation matrix was optimized in convex-concave manner, by optimizing the objective function
arg min PVV, (A 3I) ((V,W) ((P(V, V.W
(15)
with 3 being iteratively increased from - -||A]|2 to ||A]|2 and with μ(P(V W)) being the same permutation constraint regularizer in (13).
We show results on the QAPLIB 6 library quadratic assignment problems of real-world appli- 12 and 256 and we choose
cations which range between QAPLIB are meant to be challenging and optimal solutions for some the larger problems are not provided because they unknown. Thus, report the gap optimality (when known) of solution and consider a solution good it falls within 10% the optimum. We report the relative error and runtime in Fig. In 75 out of 87 instances the result valid permutation matrix.
ceil 2t The problems in
4.6 Shape Matching
Finally, we further assess the effectiveness of our approach for the the application non-rigid shape matching, common task in computer graphics and computer vision. To this end, incorporate

---

Table 2: Geodesic errors and standard deviation (std) for noise-free and noisy data by Marin er al. (26] and our approach.
@prob
std (Eprob)
Cemb
std (Cemb)
26
0.051
17.4 x 10-4
0.029
3.5 x 10-4
noisy
ours
0.047
26.9 x 10-4
0.026
29.2 10-1
[26]
0.043
16.3 x 10-4
0.022
3.5 x 10-4
noise-free
ours
0.041
8.1 10-4
0.019
3.7 x 10-4
our permutation matrix representation approach into the state-of-the-art shape-matching approach by Marin et al. [26]. which learns the point correspondences using two consecutive networks Ng and Gg. predicting shape embeddings and probe functions, respectively. We propose to replace the calculation of the permutation matrix based on the output of the first network Ne by s (aVWT)) with a 40. The network transforms the vertices of 3D objects X₂ and Xy into embeddings 62 No(22) and Φy No(x))) ) which are used to compute V & (o] P Pyt and W dy. V here replaces transformed embedding. The network is trained on the modified loss function
min Σ Is (20VWT)' x, - x2- pd P
(16)
for given ground truth permutation Pat, and V and W being normalized row-wise, Similar to Marin el al. we train the networks over 1600 epochs on 10000 shapes of the SURREAL dataset [45] and evaluate our experiments on 100 noisy and noise-free objects of different shapes and poses of the FAUST dataset [3], that are provided by (26) in (25).
We follow the evaluation of Marin al. [26] and calculate the geodesic distance between the ground truth matching and the predicted matching match, = ( 0yy for C1 = Gg(x)) (( whereby N is the nearest neighbor. In the following, we refer to the measured geodesic distance as Eprob. A second error (Cemb) which only concerns the first network's predictions, is measured by the geodesic distance towards matchy = (( OyC) for C' = P 6r. which is, again, calculated following Marin et al. (26). The results of our experiments are reported in Table showing the average geodesic errors (over 10 runs for each experiment) for the approach presented in [26] and our method. The table reveals improved results compared to [26].
Stochastic Training. Given that the explicit calculation of the permutation matrix in (66] is memory-intensive for large number of vertices, we employ stochastic training to avoid the need for computing the full permutation matrix. As we describe Sec. [4. we only calculate the loss over few entries where the final permutation ought to be equal to one and on & (here & can be 2 1) randomly chosen entries of each row of P in each iteration. This approach reduces the memory requirement and gives us the possibility In our experiments, we applied the stochastic training technique on the SURREAL dataset, and then evaluated the performance on FAUST by measuring the error rates for varying values of k, as depicted in Fig. 4b] We observed a small relative increase of less than 17% in Cemb, and also a small effect on Cprob, but with a less clear tendency one could see for Cemb- For Eprot measured an average standard deviation of 2.25 x 10-3 and for Cemb of 3.3 x 10-1 Two noise-free examples of correspondences. visualized for full training and for stochastic training with = 1, are shown in Fig. 4a with the reference image the left and the corresponding shapes on the right.
train with larger shapes consisting of more vertices.
To evaluate the impact on the error and memory consumption when dealing with high-resolution objects (with more vertices). we ran experiments using data from the TOSCA dataset [ We train 400 epochs on the objects of the classes victoria and michael (32 objects in total) with up to 20000 sampled vertices. These experiments reveal a significant reduction of memory consumption, see Fig. 55 Additionally, we evaluate the training on the class david and report a relative memory-error trade-off for up to 20k samples of each object, see Fig. 5b The graph indicates a correlation between higher memory usage and lower error values for Bemb- The trends observed in the memory-error trade-off for Cemb are generally applicable to eprob well, although with some outliers.

---

-10
3
noise free
noisy
Coou
2,5
Eprob
4.5
4
ref.
full (ours) k =
1
(a) Visualized results FAUST
(b) Error values for different to
Figure 4: Visualized matching results (a) and error values (b) for the FAUST dataset for different
levels of sparseness during stochastic training
0.1
((26).urr)
Rel. Cproh
1000
5000
Mem. Cons, GB
20
100 (ours)
10000
k
(ours)
15000
only netw:
-0.1
20000
0.1
10
Rel. Femb
-0.1
0
0.5
1.5
2
0.5
-10
Relative Mem. Cons.
(a) Memory usage during non-stochastic training (red), stochastic training for different & (green), and just calculating the network output (blue)
(b) Relative memory error trade-off for vary- ing number of vertices (11)
Figure 5: (a) shows the memory consumption during training for shape matching for objects with varying number of vertices (n) and varying sparseness (A)). (b) shows the relative memory-ene trade- off for varying sparseness (which causes the memory reduction), whereby the memory consumption relative to k 100 and the errors are relative full training by 26 for 1000.
5 Conclusion
In this work, we proposed a strategy to represent permutation matrices by a low-rank matrix fac- torization followed by a nonlinearity and showed that by using the Kissing number theory, we can determine the minimum rank necessary for representing permutation matrix of a given size, allowing for a more memory-efficiee
representation. We validated this method with experiments on LAPs and QAPs as well as a real-world shape matching application and showed improvements in the latter. Additionally, we explored the potential of optimizing permutations stochastically decrease memory usage, which opens the possibility of handling high-resolution data.
Limitations and Broader Impact Our method offers a promising solution to contribute positively the environment by reducing the computational cost of variety of problems involving permutation matrices. We do not see any ethical concerns associated with our approach itself. However, it is important to acknowledge limitation our method. For certain problem formulations, such as Koopmans and Beckmann form QAPs, stochastic learning may not be feasible because the double occurrences of the permutation matrix make the stochastic computation not applicable. Moreover, method requires devising non non-trivee trivial, problem-specifee adaptation.
10

---

Acknowledgment
Yuval Bahat received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Cun grant agreement No 945422. Zorah Lähner is funded by a KI-Starter grant of the Ministry of Culture and Science of the State of North Rhine- Weeteealappaai.. Hannah Dröge acknowledges the support of the German Research Foundation (DFG) grant MO 2962/5-1.
References
[1] Florian Bernard, Christian Theobalt, and Michael Moeller. Ds Tighter lifting-freet ferinng-reee convex relaxations for quadratic matching problems. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages
2018.
[2] Garrett Birkhoff. Tres observaciones sobre el algebra lineal [three observations in linear algebra]. Univ. Nac. Tucuman, Ser. A, 5:147-154, 1946.
[3] Federica Bogo, Javier Romero, Matthew Loper, and Michael J Black. Faust: Dataset and evaluation for 3d mesh registration. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3794-3801, 2014.
[4] Peter Boyvalenkov, Stefan Dodunekov, and Oleg R Musin. survey on the kissing numbers. arXiv preprint arXiv: 2015.
[5] Alexander M Bronstein. Michael M Bronstein, and Ron Kimmel. Numerical geometry of non-rigid shapes. Springer Science & Business Media, 2008
[6] R. E. Burkard, S. E. Karisch, and F. Rendl. Qaplib a quadratic assignment problem libarary. Journal of Global Optimization, 10, 1997.
[7] Fabrício Caluza Machado and Fernando Mário de Oliveira Filho. Improving the semidefinite programming bound for the kissing number by exploiting polynomial symmetry. Experimental Mathematics, 27(3):362-3666 2018
[8] Dongliang Cao and Florian Bernard. Self-supervised learning for multimodal non-rigid 3d shape matching. In Proc. of IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2023.
[9] Aïssatou Diallo, Markus Zopf, and Johannes Fürnkranz. Permutation learning via lehmer codes. In ECAI 2020, pages 1095-1102. IOS Press, 2020.
[10] Nadav Dym, Haggai Maron, and Yaron Lipman. DS++-A flexible, scalable and provably tight relaxation for matching problems. ACM Transactions on Graphics (TOG), 36(6), 2017.
[11] M. Eisenberger, D. Novotny, G. Kerchenbaum, P. Labatut, N. Neverova, D. Cremers, and
A. Vedaldi. Neuromorph: Unsupervised shape interpolation and correspondence in one go. In IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), 2021.
[12] Marvin Eisenberger, Zorah Lähner, and Daniel Cremers. Divergence-free shape correspondence by deformation. In Symposium on Geometry Processing (SGP), 2019.
[13] Maolin Gao, Zorah Lähner, Johan Thunberg, Daniel Cremers, and Florian Bemard. Isometric multi-shape matching. Conference on Computer Vision and Pattern Recognition (CVPR), June 2021.
[14] S. Gold and A. Rangarajan. A graduated assignment algorithm for graph matching. IEEE Trans. on Pattern Analysis and Machine Intelligence, 18, 1996.
[15] Thibault Groueix. Matthew Fisher, Vladimir G. Kim, Bryan Russell, and Mathicu Aubry. 3d-coded: 3d correspondences by deep deformation. In ECCV, 2018.
[16] Aditya Grover, Erie Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations, arXiv preprint
2019.

---

[17] Jonathan Huang, Carlos Guestrin, and Leonidas Guibas. Fourier theoretic probabilistic inference over permutations. Journal of machine learning research, 10(5), 2009.
[18] Itay Kezurer, Shahar Z. Kovalsky, Ronen Basri, and Yaron Lipman. Tight relaxation of quadratic matching. 34(5), 2015.
[19] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA. USA, May 7-9, 2015, Conference Track Proceedings, 2015.
[20] Risi Kondor, Andrew Howard, and Tony Jebara. Multi-object tracking with representations of the symmetric group. In Marina Meila and Xiaotong Shen, editors, Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, volume 2 of Proceedings of Machine Learning Research, pages 211-218, San Juan, Puerto Rico, 21-24 Mar 2007. PMLR.
[21] Tjalling C. Koopmans and Martin Beckmann. Assignment problems and the location of economic activities. Econometrica, 25(1), 1957.
[22] Harold W. Kuhn. The hungarian method for the assignment problem. Naval Research Logistics Quaterly, 1955.
[23] Or Litany, Tal Remez, Emanuele Rodolå, Alex Bronstein, and Michael Bronstein. Deep functional maps: Structured prediction for dense shape correspondence. In Proc. of International Conference on Computer Vision (ICCV), 2017.
[24] E. M. Loiola, N. M. de Abreu, O. B. Netto, Hahn, and T. M. Querido. A survey for the quadratic assignment problem. European Journal of Operational Research, 176(2), 2007.
[25] Riccardo Marin. Correspondence learning via linearly-invariant embedding (pytorch). https 7/gi sgit.ub.coo com hftm://iccarrommm///fffff------- PMAPs- 2022.
[26] Riccardo Marin, Murie-Julie Rakotosaona, Simone Melzi, and Maks Ovsjanikov. Correspon- dence learning via linearly-invarial embedding. Advances in Neural Information Processing Systems, 33:1608-1620, 2020.
[27] Haggai Maron, Nadav Dym, Itay Kezurer, Shahar Kovalsky, and Yaron Lipman. Point reg- istration via efficient convex relaxation. ACM Transactions on Graphics (TOG), 35(4):73, 2016.
[28] Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permuta- tions with gumbel-sinkhom networks. arXiv preprint arXiv:1802.08665. 2018.
[29] Oleg R Musin. The kissing number in four dimensions. Annals of Mathematics, pages 1-32, 2008.
[30] Maks Ovsjanikov, Mirela Ben-Chen, Justin Solomon, Adrian Butscher, and Leonidas Guibas. Functional maps: flexible representation of maps between shapes. ACM Transactions on Graphics (ToG), 31 (1): 2012.
[31] C. Papazov and D. Burschka. Deformable 3d shape registration based local similarity transforms. In Proc. of Symposium on Geometry Processing (SGP), 2011.
[32] Ulrich Pinkall and Konrad Polthier. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics, 2(1):15 - -36, 1993.
[33] Sergey Plis, Stephen McCracken, Terran Lane, and Vince D Calhoun. Directional statisties on permutations. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 600-608. JMLR Workshop and Conference Proceedings, 2011.
[34] Ryan Prescott Adams and Richard S Zemel. Ranking via sinkhorn propagation. arXiv e-prints, pages trXiv-1106. 2011.
12

---

[35] Gilles Puy, Alexandre Boulch, and Renaud Marlet. Flot: Scene flow on point clouds guided by optimal transport. Computer Vision Eeco 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XXVIII, pages 527-544. Springer, 2020.
[36] Emanuele Rodolá, Alex M. Bronstein, Andrea Albarelli, Filippo Bergamasco, and Andrea Torsello. A game-theoretic approach deformable shape matching. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2012.
[37] Samuele Salti, Federico Tombari, and Luigi Di Stefano. Shot: Unique signatures of histograms for surface and texture description. Computer Vision and Image Understanding, 125:25 2014.
[38] Rodrigo Santa Cruz, Basura Fernando, Anoop Cherian, and Stephen Gould. Deeppermnet: Visual permutation learning. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3949-3957, 2017.
[39] Lawrence Saul. A geometrical connection between sparse and low-rank matrices and its application manifold learning. Transactions on Machine Learning Research, 2022.
[40] Lawrence K Saul. A nonlinear matrix decomposition for mining the zeros of sparse data. SIAM Journal on Mathematics of Data Science, 4(2):331-63,, 2022.
[41] Marcel Seelbach Benkner, Zorah Lähner, Vladislav Golyanik, Christof Wunderlich, Christian Theobalt, and Michael Moeller. Q-match: Iterative shape matching via quantum annealing. In International Conference on Computer Vision (ICCV), 2021.
[42] Giovanni Seraghiti, Atharva Awari, Arnaud Vandaele, Margherita Porcelli, and Nicolas Gillis. Accelerated algorithms for nonlinear matrix decomposition with the relu function. arXiv preprint arXiv: 2023.
[43] Sun, M. Ovsjanikov, and L. Guibas. A concise and provably informative multi-scale signature- based on heat diffusion. Computer Graphics Forum (CGF), 28: 28:1383-1392, 2009.
[44] Ramana Sundararaman, Gautam Pai, and Maks Ovsjanikov. Implicit field supervision for robust non-rigid shape matching. In Proc. of European Conference on Computer Vision (ECCV), 2022.
[45] Gül Varol, Javier Romero, Xavier Martin, Naureen Mahmood, Michael Black, Ivan Laptev, and Cordelia Schmid. Learning from synthetic humans. In CVPR. 2017.
[46] Matthias Vestner, Zorah Lähner, Amit Boyarski, Or Litany, Ron Slossberg, Tal Remez, Emanuele Rodolå, Alex M. Bronstein, Michael M. Bronstein, Ron Kimmel, and Daniel Cremers. Efficient deformable shape correspondence via kernel matching. In International Conference on 3D Vision (3DV), 2017.
[47] Runzhong Wang, Junchi Yan, and Xiaokang Yang. Combinatorial learning of robust deep graph matching: an embedding based approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
[48) Runzhong Wang, Junchi Yan, and Xiaokang Yang. Neural graph matching network: Learn- ing lawler's s quadratic assignment problem with extension to hypergraph and multiple-graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(9):5261-5279, 2021.
[49] Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Li. Learning deep graph matching with channel-independent embedding and hungarian attention. In International conference on learning representations, 2020.
[50] Andrei Zanfir and Cristian Sminchisescu. Deep learning of graph matching. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 2684-2693, 2018.
[51] Q. Zhao, S. E. Karisch, F. Rendl, and H. Wolkowicz. Semidefinite programming relaxations for the quadratic assignment problem. Journal of Combinatorial Optimization, 2(1), 1998.
[52] Zong. The kissing numbers of convex bodies-a a brief survey. Bulletin of the London Mathematical Society, 30(1):1-10, 1998.
13


Reviews:
[{"review_id": "1b5qtYfR2p", "reviewer": "Reviewer_AkAs", "summary": "This paper proposes a novel way to decompose a permutation matrix into two low-rank matrices so that a significant amount of  space can be saved to store a permutation. Then the authors further implement such decomposition to solve practical tasks of point cloud alignment, assignment problem and shape matching. ", "questions": "1. Kissing number is based on a threshold of arccos(0.5), does this mean that if we switch to a smaller angle, we can fit more vectors in a unit sphere, thus save more space to store a permutation? If so, why don't we do so?\n\n2. When both $V$ and $W$ need to be optimized, are they optimized in parallel or alternatingly? Specifically which optimization algorithm is used for your numerical tests?\n\n3. How do you implement Stochastic Optimization for LAP and QAP when $A$ is dense? \n\n4. In the part (b) of Fig 5, what is the scale of y axis? The term \"Relative\" here is very confusing and without explanation.  \n", "limitations": "The limitations of the work are mostly mentioned in the weakness section. The authors indeed addressed them but it is still quite confusing to read for the first time.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Overall, the paper is well-written and clearly explains the heuristics behind the method. The method of using Kissing numbers and non-linearity to perform low-rank decomposition of a permutation matrix is very interesting and can possibly inspire future research. Based on Fig 5, the method indeed provides memory saving for supervised learning. ", "weaknesses": "The most troubling weakness of this method lies in its value of application. Specifically, I have the following concerns:\n\n1. The method introduces two complex problems to optimization: bi-variable structure and non-linearity. As mentioned by the authors, this requires devising a non-trivial, problem-specific adaptation for each problem. \n\n2. To avoid forming an $n\\times n$ matrix, the authors propose to only optimize over a handful of entries, which basically requires knowing the ground truth permutation (or assuming some sparse structures as in LAP). This leads to a very limited set of application scenarios.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "#### Question 1\nKissing number is based on a threshold of arccos(0.5), does this mean that if we switch to a smaller angle, we can fit more vectors in a unit sphere, thus save more space to store a permutation? If so, why don't we do so?\n#### Answer 1\nYes, it is correct that the threshold does not need to be 0.5. In fact, if we pick any $V \\in \\mathbb{R}^{n \\times m}$, $m<<n$, with normalized rows that are non-repeating, then the threshold $\\mu := \\max_{i\\neq j} \\langle V_{i,:} , V_{j,:} \\rangle$ allows to use our approach for representing a permutation $P$ by choosing $W=PV$. Even for Gaussian random matrices, this allows to reduce the rank exponentially, see e.g. \"Limiting Laws of Coherence of Random Matrices with Applications to Testing Covariance Structure and Construction of Compressed Sensing Matrices.\" by Cai and Jiang, where it is shown that $\\mu$ behaves like $2\\sqrt{\\frac{\\log(n)}{m}}$ if $n$ is an exponential of $m$. Yet, the ReLU indeed acts as a thresholding such that thresholds approaching 1 make it extremely difficult to still optimize the resulting objective. We found a threshold of $0.5$ to yield a good compromise between the ability to optimize (with first-order methods) and an accurate representation of permutations via a low-rank factorization while benefitting from some additional literature deriving theoretical bounds on the factorized dimension. Adaptive thresholds (e.g. using continuation schemes) and/or softmax approaches with iteratively increasing temperature (converging from soft- to hard-(arg)-max) are of course possible fine-tuning options to improve results in particular applications.  \n\n\n#### Question 2\nWhen both V and W need to be optimized, are they optimized in parallel or alternatingly? Specifically which optimization algorithm is used for your numerical tests?\n#### Answer 2 \nThe estimation of V and W is performed in parallel using the Adam optimization algorithm. We will clarify this aspect in the final version of the paper. We will also upload our code, and make it publicity available upon acceptance.\n\n#### Question 3 \nHow do you implement Stochastic Optimization for LAP and QAP when $A$ is dense? \n#### Answer 3\nFor LAP the similarity matrix $A$ has the dimension $n \\times n$ (the same dimension as the permutation matrix), for QAP the similarity matrix is even larger with $A \\in \\mathbb{R}^{n^2 \\times n^2}$, or for the Koopmans and Beckmann formulation we have two matrices of the dimension  $n \\times n$. If those matrices have to be computed densely, it would require as much memory as a fully calculated permutation matrix or even more, so the stochastic optimization would not make any difference. Yet, considering that the costs are still sums over many terms, stochastic/alternating optimization schemes that only consider a few terms at a time and compute costs on-the-fly could be implemented. We have not tested our approach in this respect yet.\n\n#### Question 4\nIn the part (b) of Fig 5, what is the scale of y axis? The term \"Relative\" here is very confusing and without explanation.\n#### Answer 4\nThe term “relative” means, that the errors are calculated relative to the error of the full training by [26] for $n = 1000$, therefore it is calculated by $error_{relative} = \\frac{error_{ours} - error_{[26]}}{error_{[26]}}$.\nWe will make this more clear in the final version.\n\n#### Unknown Ground Truth and Limitations\n\n- To avoid forming an matrix, the authors propose to only optimize over a handful of entries, which basically requires knowing the ground truth permutation (or assuming some sparse structures as in LAP). This leads to a very limited set of application scenarios.\n- The limitations of the work are mostly mentioned in the weakness section. The authors indeed addressed them but it is still quite confusing to read for the first time.\n\n\n#### Answer  \nWe will make the limitations of our approach more visible by collecting them in a separate section in the final version of our paper. The approach of (sparse) memory-saving optimization is applicable to any fully supervised approach for learning permutation matrices. Additionally, we anticipate that extensions to self-supervised settings like linear assignment problems are possible by turning to stochastic/alternating optimization schemes that do not consider all terms of the cost function at a time."}, {"review_id": "7iqh1D50b4", "reviewer": "Reviewer_1Eor", "summary": "This work addresses the problem of estimating large permutation matrices by approximating them with a low-rank factorization follow by a nonlinear mapping, thereby reducing the storage complexity from O(n^2) to O(n).\n\nThe main contribution of the paper is i) a theoretical derivation and proof of the minimal required rank of the factorization matrices, and ii) the use of a nonlinearity, such that the full rank permutation matrix can be restored *exactly*. i) is based on the Kissing number (or bounds on it), while the nonlinearity in ii) can be a ReLu. Importantly, the possibility to exactly represent any permutation matrix is in strong contrast to direct low-rank factorizations which can only approximate the permutation matrix (since unable to recover the full rank).\n\nThe authors propose practical solutions for the optimization: A smooth version of the nonlinearity (softmax), and an optimization scheme (inspired by stochastic optimization; gradients are considering a row of the factorization matrices at a time) that approximates the full objective, but never requires to build the full permutation matrix, thus fully leveraging the compact representation and resulting storage savings.\n\nExperimental results are extensive and demonstrate the applicability of the method on point cloud alignment, linear and quadratic assignment problems, and shape matching.", "questions": "**Q1** Is there a relation between the Kissing number and the ReLU? Is it conceivable that there exists another non-linear function that allows an even lower rank factorization while still being able to represent that exact permutation matrix?", "limitations": "-", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "**S1** Proposition 1 and Eq. (7) represent a novel contribution. The insight that a non-linear mapping of a matrix factorization is able to recover the full rank permutation matrix is a strong contribution and is of interest for the wider community.\n\n**S2** The proof of the minimal require factorization matrix rank via the Kissing number is an interesting theoretical contribution. Also practically it provides a clear guidance on the required size of factorization matrices such that the exact permutation matrix can be recovered.\n\n**S3** The proposed stochastic optimization in Sec. 4.1 provides a practical algorithm for optimizing the permutation matrix, while leveraging the compact representation (the full permutation matrix is never built, but only computed element-wise at a time). The non-smoothness of the ReLU is addressed by soft-max function with a controllable temperature parameter that allows to approximate the exact solution with desired accuracy over the course of the optimization procedure.\n\n**S4** Experimental results are performed across different application domains and demonstrate the usefulness of the proposed approach.", "weaknesses": "None, but I'm also not an expert in the area. I'm especially not knowledgeable about related work and thus can not judge the novelty of the proposed approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "#### Question\nIs there a relation between the Kissing number and the ReLU? Is it conceivable that there exists another non-linear function that allows an even lower rank factorization while still being able to represent that exact permutation matrix?\n\n#### Answer\nThe ReLU merely serves as a type of thresholding operation and could be replaced by any other function that is zero for all values below a certain threshold and one for an input value of one. In fact, an arbitrarily low rank $\\geq 2$ can still allow to represent any permutation exactly by letting the threshold approach one. Yet, since gradients of any entry below the threshold are zero, such a representation becomes increasingly difficult to optimize (please also see the answer for reviewer AkAs). We will add a discussion on this aspect in the revised version of this paper."}, {"review_id": "hFsBZG3bFz", "reviewer": "Reviewer_KuKh", "summary": "The paper proposes a novel approach for representing permutation matrices with low-rank matrix factorisation. The method employs Kissing number theory to find the minimum rank necessary to represent the target matrix. This is often quite a bit lower than the rank of the original matrix, so allows for a more efficient memory representation. The paper also shows how the approach can be used in practice in various relevant problems, such as point cloud alignment or shape matching.\n\nEdit: I have read the rebuttal, and given the scores from other reviewers and I would like to keep my score.", "questions": "none", "limitations": "These are addressed at the end of the paper.", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* The work deals with a meaningful problem, and produces an elegant solution with wide ranging applicability.\n* The authors demonstrate the performance of their approach in various problems, demonstrating similar / better accuracy with a significant improvement in memory requirement.\n* The paper is very well written and easy to read.\n* The experiments are relevant.\n* The formulation is principled and includes several relevant proofs.\n\nOverall I believe this is a perfect NeurIPS paper. While I have little knowledge of Kissing number theory, the paper solves a very relevant problem in an elegant way, and demonstrates impressive and wide-ranging practical applicability in multiple domains. I therefore strongly believe the work should be accepted.", "weaknesses": "I have very little negative notes about the work, though, I could say that the ablation section could be expanded, e.g. by seeing how increasing the stochastic training k affects speed and accuracy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for your very positive response to our work. We have added an analysis of the relationship between $k$ and the optimization time to the general response. "}, {"review_id": "7bt2Obt13f", "reviewer": "Reviewer_2QBr", "summary": "This paper proposes a formulation for representing high-dimensional permutation matrices. The basic idea is to express the n x n permutation matrix as an elementwise non-linear function of a product of low-rank matrices V,W (n x m). The authors introduce the kissing number theory which gives the minimum number 'm' for which such a decomposition is provably possible and then show intuitive proofs that in scenarios when the decomposition is valid - their construction is appropriate. In addition, they also promote two well-known non-linearities (ReLU and SoftMax) which can be used in the optimization process for the representation.\n\nResults are demonstrated on two synthetic and one recent 3D shape-matching scenario. Broadly the experiments make an impression of a significantly reduced memory consumption and the ability to recover permutations. In the shape-matching example, the proposed formulation also slightly improves on the previous baseline. ", "questions": "See Weaknesses ", "limitations": "I do not think this paper has any direct negative societal impact. Please see the weaknesses for technical limitations. \n\nOverall, this paper has a very interesting idea and a clever conceptual message on representing permutations. My biggest concern is whether the proposed construction is impactful in terms of ease of optimization and acceptable accuracies for the multitude of shape-matching problems that this can be applied to. Given the lack of comparisons to conceptual baselines (i.e. not in terms of a state-of-the art shape matching paper, but even simply comparing with previous permutation representations like stochastic matrices, or spectral decompositions - in any framework), I am inclined towards a weak reject at this point. I can be convinced of the gains in memory complexity of the proposed representation but am not yet sold on its applicability and accuracy. ", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "- The core idea of this paper (low-rank representation of permutations with nonlinearities) is *very* interesting and potentially has a very wide impact in scenarios where matching between pointsets is a crucial problem (linear assignment, quadratic assignment etc)\n- Overall the writing of this paper is very good, and the background and related material on the kissing number theory has been introduced and explained in a way interesting way.  \n- The benefits of the proposed construction are (1.) strong memory reduction in representing permutation matrices (2.) An accompanying optimization scheme that allows for recovering permutations", "weaknesses": "- Broadly, I felt the experimental section is very rudimentary. There are very few comparisons to conceptual baselines: namely using stochastic matrices, optimal transport, Hungarian algorithm and nearest neighbor-like methods. It is not clear from the experiments whether the obtained solutions are: not just some permutations, but the *correct* permutations. \n\n- More specifically, for the point cloud example in section 4.2, what is the accuracy of the recovered transformation $\\Theta$ as a function of n? How do other conceptual baselines compare in this example both in terms of accuracy and memory complexity? \n\n- Despite the experiments on Marin et.al, perhaps a simpler and more convincing demonstration would be to use the proposed permutation representation in either or all of [43], [30], etc. where a linear/quadratic assignment is solved and then compare with the original methods (perhaps yielding an improvement in memory with a comparable or better accuracy)  \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Regarding the request to include conceptual baselines to compare in the point cloud example, we have included experiments that can be found in the general response to all reviewers under the topic \"Comparisons with Permutation Baselines in [30]\". These experiments include comparisons in accuracy, time, and memory performance for extracting point-wise correspondences, compared to the LAP solver, nearest-neighbors, optimal transport, and sinkhorn iteration, within the functional maps framework [30].\n\n\n#### Question 1\nIt is not clear from the experiments whether the obtained solutions are: not just some permutations, but the correct permutations.\n#### Answer 1\nIn the LAP and QAP experiments, we evaluated the permutation matrix from of the relative error of the energy compared to the energy of the optimal solution. We will make this clear in the final version.\n\n#### Question 2\nMore specifically, for the point cloud example in section 4.2, what is the accuracy of the recovered transformation as a function of $n$? \n#### Answer 2\nWe add the accuracy values of the transformation (depending on $n$) in the form of measuring the distance between the true and the transformed point clouds to the final version (see the general response to all reviewers for the accuracy values)."}, {"review_id": "o5404Gpzcw", "reviewer": "Reviewer_tWZ6", "summary": "The authors propose a provably exact and an approximative method for calculating permutation matrices requiring much lower memory than previous approaches. The algorithms are based on Kissing numbers and describe row relationships as their cosine value. This allows for representing the problem with significantly fewer values than the baseline n*n permutation matrix representation. Additionally, the authors propose a relaxation of this exact algorithm, utilizing the SoftMax operator, that alleviates the issues with the optimization for large problems. The authors also show a number of applications where their method is applicable. ", "questions": "Experiments:\n- L191 is translation not considered on purpose?\n- L204-209 This is a little but unclear. Does the propose method always, without failure, find the correct permutation and transformation? If this is the case, this should be highlighted more. If not, an error value should be shown. \n- L209 Equally good results with Softmax. Does this mean that the approximation in this noise-free case can be compensated?\n- L215 refers to Fig.2, but that seems to show something different (Dense/Sparse) and not the topic the authors mention at this line. \n\nTypos:\nL135 \"either exact\" -> \"either as exact\"\nL156 \"valdidate\" -> \"validate\"\nL179 missing dot from the end of the sentence\nL230 \"similariy\" -> \"similarity\"\n", "limitations": "Discussed.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I believe this is a pretty strong work with a very general and useful contribution. Strengths in more details:\n- A provably exact algorithm that significantly reduces the memory consumption of general permutation matrices.\n- Additionally, a relaxation is proposed that has better convergence properties in optimization.\n- The authors demonstrate on a number of applications that their method is applicable and useful. ", "weaknesses": "First, I wanted to give a strong accept, but the experiments left me slightly in doubt. \nMy main problem is the following: The experiments focus a little bit too much on the application side (which is amazing), but miss to do a general comparison to baselines and the proposed methods. I would have liked to see comparisons to SOTA algorithms (related works mention many) on finding permutation matrices, showing run-time, memory, and errors. While the exact algorithm will probably have 0 error, some other methods might have a little bit bigger while being orders of magnitude faster. Also, to my understanding, the exact algorithm breaks down with the problem size, when the SoftMax version is used, which is not exact anymore. Also, it would be good to see the breaking point of the exact algorithm where it does not converge anymore. In brief, a thorough comparison to the SOTA is missing.  \n\nI still like the paper, but without such comparison (considering the theoretical value), I do not give a strong accept. If the authors can provide such an analysis to understand the trade-offs in their rebuttal, I consider improving the rating.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Regarding the request for comparison to baseline methods, please refer to the general response to all reviewers, where we have shown comparisons to baseline methods within the functional maps framework [30].\n\n#### Question 1\nL191 is translation not considered on purpose?\n#### Answer 1\nYes, we didn’t consider translations, as the experiments were primarily focused on a proof of concept, and translation can be removed through centering.\n\n\n#### Question 2\nL204-209 This is a little but unclear. Does the propose method always, without failure, find the correct permutation and transformation? If this is the case, this should be highlighted more. If not, an error value should be shown.\n#### Answer 2 \nIn these experiments the proposed method always finds the correct permutation, and with it also the correct assignment of the transformed vectors. We will further highlight this in the final version. Nevertheless, we have small shiftings in the transformation of the vectors, for which we will add the accuracies (see the general response to all reviewers). \n\n#### Question 3\nL209 Equally good results with Softmax. Does this mean that the approximation in this noise-free case can be compensated?\n#### Answer 3\nYes, for finding the correct assignment in this example, this is the case.\n\n#### Question 4\nL215 refers to Fig. 2, but that seems to show something different (Dense/Sparse) and not the topic the authors mention at this line.\n#### Answer 4\nIn this line, we referred to the memory reduction, which is shown in Fig 2. But we agree with the reviewer that this point does not become clear in the submitted version. We will rewrite this part of the text to ensure that it is correctly understood."}]

Author rebuttal:
We thank all reviewers for their comments that helped us improve the presentation of our work. In the following, we address the concerns that have been raised, and we provide additional experimental results:


# Comparisons with Permutation Baselines in [30]
We conduct an additional experiment where we compare different classical optimization approaches and to point cloud alignment experiment (see Section 4.2) in the context of the functional maps framework [30].
We compare our method, that calculates correspondences the same way as described in the Point Cloud Alignment experiment in Section 4.2., to
a general linear assignment problem (LAP) solver (specifically the Jonker-Volgenant algorithm from sklearn.linear\_sum\_assignment, which is in practice faster than the Hungarian algorithm), nearest neighbor computation, optimal transport (as implemented in the python POT package), and stochastic matrices generated by Sinkhorn iterations.

The experiment setup is as follows (all details will be included in the final version):
The goal is to extract a point-to-point correspondence between two shapes $X, Y$ from a $m \times m$-dimensional functional map [30] where $m$ is much smaller than the number of vertices in $X$ and $Y$.
A possible way to do this is by doing a nearest neighbor (NN) search of the spectral point representations $\Phi_X, \Phi_Y \in \mathbb{R}^{n \times m}$ aligned by the functional map as proposed in the original paper (see [30, Section 6.1]).
However, it is also possible to find an assignment between all rows of $\Phi_X, \Phi_Y$ by other means, for example by solving a linear assignment problem if a bijection is desired. 
This is exactly the point cloud alignment setting from our experiments in Section 4.2 with a small amount of noise in the point clouds, and we show that our method outperforms all baselines in terms of geodesic error of the final matching and shows positive trends in terms of runtime and memory consumption.      
We use the FAUST registrations [3] with the original $6890$ vertices and a downsampled version to $502$ vertices for those experiments. 
The rows of $\Phi_X, \Phi_Y$ are generated by applying the ground-truth functional map to the spectral embedding of each vertex and can be assumed to be permuted, noisy versions of each other such that we can directly use them as $V$ and $W$ for our method.

We will add more details about the exact setup for all methods in the final version. The results of this comparison can be seen in Table 1 in the response PDF.
Our method has the best runtime/memory ratio on the higher dimensional example apart from nearest neighbors (which is known to become quite unreliable if the alignment is not tight) while still providing the most accurate results.







# Clarification of the Method Strengths
Our work proposes a novel efficient approach for representing permutations, which inherently provides a guaranteed minimal decomposition rank $m$ (and therefore the minimal memory requirements) necessary for representing a problem of size $n$. This allows tackling large problems whose size $n$ could not be handled by existing methods. 
We believe that the strength of our method lies in its ability to efficiently represent permutation matrices while still being differentiable and enabling techniques such as sparse/stochastic optimization, which will be particularly efficient in a supervised learning setup. 
However, it is not a plug-and-play solution that can be quickly incorporated into any pipeline. 
Therefore, a direct but fair comparison to other learning-based permutation predictors like Sinkhorn layers is not straightforward to implement but requires individual adaptions of our method for each setting.
We showed that it is possible to considerably improve memory requirements by including it in Marin et al. [26], and we strongly believe this is possible in other methods with more research in this direction. 
 

# Further Experimental Details on Point Cloud Alignment and Shape Matching
We include additional accuracy values on the prediction of a linear transformation over point clouds, by measuring the distance between the true point cloud and its transformed counterpart. We add these additional accuracy values for each problem size ($n$) which were previously outlined in the initial version of our work (see Table 2 in the response PDF). 
To further expand the ablation study, we will include a comparison of the training speed for stochastic optimization in the shape-matching experiment, depending on the stochastic variable $k$, to the results in Figure 4b. The values of this additional experiment can be found in Table 3 in the response PDF.


Meta-review: This paper studies the low-rank representation of the permutation matrices, which have applications in robotics and computer vision, among others. One of the main challenges in the optimization problems defined over permutation matrices is the quadratic dependency of the decision variables on the problem dimension, which makes them prohibitive to solve in massive-scale instances. The authors provide an intuitive, yet elegant approach to alleviate this challenge. They show that a low-rank factorization followed by a ReLU activation layer can capture the set of all permutation matrices. Using this representation, they show that the optimization problems defined over permutation matrices with n^2 variables can be reduced to optimization problems defined over nm variables, where m can be significantly smaller than n. Their extensive numerical experiments showcase the empirical performance of their proposed idea in various settings.

Five reviewers have reviewed the paper, and their overall assessment of the paper was mostly positive. I agree with this assessment and believe the paper provides interesting and useful ideas to improve the complexity of solving optimization problems defined over permutation matrices.

The authors are highly encouraged to take into consideration the comments made by the reviewers. The AC also suggests that the authors include a brief discussion on the exactness of their relaxation, especially in settings where the proposed low-rank factorization +  ReLU introduces infeasible optimal solutions (i.e., optimal solutions that do not correspond to a valid permutation matrix).
Decision: Accept (poster)