Fanny Dufossé
email: fanny.dufosse@inria.fr

Kamer Kaya
email: kaya@sabanciuniv.edu

Ioannis Panagiotas
email: ioannis.panagiotas@ens-lyon.fr

Bora Uçar
email: bora.ucar@ens-lyon.fr

Effective heuristics for matchings in hypergraphs

Keywords: d-dimensional matching, Tensor scaling, Matching in hypergraphs, Karp-Sipser heuristic

Effective heuristics for matchings in hypergraphs

Introduction

A hypergraph H = (V, E) consists of a finite set V and a collection E of subsets of V . The set V is called vertices, and the collection E is called hyperedges. A hypergraph is called d-partite and d-uniform, if V = d i=1 V i with disjoint V i s and every hyperedge contains a single vertex from each V i . A matching in a hypergraph is a set of disjoint hyperedges. In this paper, we investigate effective heuristics for finding large matchings in d-partite, d-uniform hypergraphs.

Finding a maximum cardinality matching in a d-partite, d-uniform hypergraph for d ≥ 3 is NP-Complete; the 3-partite case is called the Max-3-DM problem [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. This problem has been studied mostly in the context of local search algorithms [START_REF] Hurkens | On the size of systems of sets every t of which have an sdr, with an application to the worst-case ratio of heuristics for packing problems[END_REF], and the best known algorithm is due to Cygan [START_REF] Cygan | Improved approximation for 3-dimensional matching via bounded pathwidth local search[END_REF] who provides ((d + 1 + ε)/3)-approximation, building on previous work [START_REF] Cygan | How to sell hyperedges: The hypermatching assignment problem[END_REF][START_REF] Halldórsson | Approximating discrete collections via local improvements[END_REF]. It is NP-Hard to approximate Max-3-DM within 98/97 [START_REF] Berman | Improved approximation lower bounds on small occurence optimization[END_REF]. Similar bounds exist for higher dimensions: the hardness of approximation for d = 4, 5 and 6 are shown to be 54/53 -ε, 30/29 -ε, and 23/22 -ε, respectively [START_REF] Hazan | On the complexity of approximating kdimensional matching[END_REF].

Finding a maximum cardinality matching in a d-partite, d-uniform hypergraph is a special case of the d-Set-Packing problem [START_REF] Hazan | On the complexity of approximating k-set packing[END_REF]. It has been shown that d-Set-Packing is hard to approximate within a factor of O(d/ log d) [START_REF] Hazan | On the complexity of approximating k-set packing[END_REF]. The maximum/perfect set packing problem has many applications, including combinatorial auctions [START_REF] Gottlob | Decomposing combinatorial auctions and set packing problems[END_REF] and personnel scheduling [START_REF] Froger | A set packing approach for scheduling passenger train drivers: the French experience[END_REF]. Such a matching can also be used in the coarsening phase of multilevel hypergraph partitioning tools [START_REF] Aykanat | PaToH: A Multilevel Hypergraph Partitioning Tool[END_REF], when the input is d-uniform and d-partite, such as those used in modeling and partitioning tensors [START_REF] Kaya | Scalable sparse tensor decompositions in distributed memory systems[END_REF].

Our contributions in this paper are as follows. We propose five heuristics. The first two are adaptations of the well-known greedy [START_REF] Dyer | Randomized greedy matching[END_REF] and Karp-Sipser [START_REF] Karp | Maximum matching in sparse random graphs[END_REF] heuristics widely used for finding matchings in bipartite graphs. We use Greedy g and Karp-Sipser g to refer to these heuristics, and Greedy and Karp-Sipser for the proposed generalizations. Greedy traverses the hyperedge list in random order and adds a hyperedge to the matching whenever possible. Karp-Sipser introduces certain rules to Greedy to improve the cardinality. The third heuristic is inspired by a recent scaling-based approach proposed for the maximum cardinality matching problem on graphs [START_REF] Dufossé | Scaling matrices and counting perfect matchings in graphs[END_REF][START_REF] Dufossé | Two approximation algorithms for bipartite matching on multicore architectures[END_REF][START_REF] Dufossé | Approximation algorithms for maximum matchings in undirected graphs[END_REF]. The fourth heuristic is a modification of the third one that allows for faster execution time. The last one finds a matching for a reduced, (d -1)-dimensional problem and exploits it for d dimensions. This heuristic uses an exact algorithm for the bipartite matching problem. We perform experiments to evaluate the performance of these heuristics on special classes of random hypergraphs and real-life data.

Another way to tackle the problem at hand is to create the line graph G for a given hypergraph H. The line graph is created by identifying each hyperedge of H with a vertex in G, and by connecting two vertices of G with an edge, iff the corresponding hyperedges share a common vertex in H. Then, successful heuristics for computing large independent sets in graphs, e.g., KaMIS [START_REF] Lamm | Finding Near-Optimal Independent Sets at Scale[END_REF], can be used to compute large matchings in hypergraphs. This approach, although promising quality-wise, could be impractical. This is so, since building G from H requires quadratic run time and storage (in terms of the number of hyperedges) in the worst case. While this can be acceptable in some instances, in others it is not. We have such instances in the experiments.

The rest of the paper is organized as follows. Section 2 introduces the notation and summarizes the background material. The proposed heuristics are summarized in Section 3. Section 4 presents the experimental results and Section 5 concludes the paper.

Background and notation

Tensors are multidimensional arrays, generalizing matrices to higher orders. Let T be a d-dimensional tensor whose size is

n 1 × • • • × n d .
The elements of T are shown with T i1,...,i d , where i j ∈ {1, . . . , n j }. A marginal is a (d -1)-dimensional section of a d-dimensional tensor, obtained by fixing one of its indices. A ddimensional tensor where the entries in each of its marginals sum to one is called d-stochastic. In a d-stochastic tensor, all dimensions necessarily have the same size n. A d-stochastic tensor where each marginal contains exactly one nonzero entry (equal to one) is called a permutation tensor. Franklin and Lorenz [START_REF] Franklin | On the scaling of multidimensional matrices[END_REF] show that if a nonnegative tensor T has the same zero-pattern as a d-stochastic tensor B, then one can find a set of d vectors x (1) , x (2) , . . . , x (d)

such that T i1,...,i d • x (1) i1 •• • ••x (d) i d = B i1,...,i d for all i 1 , . . . , i d ∈ {1, . . . , n}.
In fact, a multidimensional version of the algorithm for doubly-stochastic scaling (of matrices) by Sinkhorn and Knopp [START_REF] Sinkhorn | Concerning nonnegative matrices and doubly stochastic matrices[END_REF] can be used to obtain these d vectors.

A

d-partite, d-uniform hypergraph H = (V 1 ∪ • • • ∪ V d , E
) can be naturally represented by a d-dimensional tensor. This is done by associating each tensor dimension with a vertex class. Let |V i | = n i , and the tensor T ∈ {0, 1} n1ו••×n d have a nonzero element T v1,...,v d iff (v 1 , . . . , v d ) is a hyperedge of H. Then, T is called the adjacency tensor of H. In H, if a vertex is a member of only a single hyperedge we call it a degree-1 vertex. Similarly, if it is a member of only two, we call it a degree-2 vertex.

In the k-out random hypergraph model, given V , each vertex u ∈ V selects k hyperedges from the set E u = {e : e ⊆ V, u ∈ e} in a uniformly random fashion and the union of these hyperedges forms E. We are interested in the d-partite, duniform case, and hence

E u = {e : |e ∩ V i | = 1 for 1 ≤ i ≤ d, u ∈ e}.
This model generalizes random k-out bipartite graphs [START_REF] Walkup | Matchings in random regular bipartite digraphs[END_REF]. Devlin and Kahn [START_REF] Devlin | Perfect fractional matchings in k-out hypergraphs[END_REF] investigate fractional matchings in these hypergraphs, and mention in passing that k should be exponential in d to ensure that a perfect matching exists.

Heuristics for maximum d-dimensional matching

A matching which cannot be extended with more hyperedges is called maximal. In this work, we propose heuristics for finding maximal matchings on d-partite, d-uniform hypergraphs. For such hypergraphs, any maximal matching is a dapproximate matching. The bound is tight and can be verified for d = 3. Let H be a 3-partite 3 × 3 × 3 hypergraph with the following hyperedges e 1 = (1, 1, 1), e 2 = (2, 2, 2), e 3 = (3, 3, 3) and e 4 = (1, 2, 3). The maximum matching is {e 1 , e 2 , e 3 }, and the hyperedge {e 4 } alone forms a maximal matching.

A Greedy heuristic for Max-d-DM

There exist two variants of Greedy g in the literature. The first one [START_REF] Dyer | Randomized greedy matching[END_REF] randomly visits the edges and adds the current edge to the matching if both end points are available. The second one randomly visits the vertices [START_REF] Pothen | Computing the block triangular form of a sparse matrix[END_REF], and matches the vertex with the first available neighbor, if any, visited in a random order. We adapt the first variant to our problem and call it Greedy. It traverses the hyperedges in random order and adds the current hyperedge to the matching whenever possible. Since any maximal matching is possible as its output, Greedy is a d-approximation heuristic. It obtains matchings of varying quality, depending upon the order in which the hyperedges are processed.

Karp-Sipser for Max-d-DM

A widely-used heuristic to obtain large matchings in graphs is Karp-Sipser g [START_REF] Karp | Maximum matching in sparse random graphs[END_REF]. On a graph, the heuristic iteratively adds a random edge to the matching and reduces the graph by removing its endpoints, as well as their edges. Whenever possible, Karp-Sipser g does not apply a random selection but reduces the problem size, i.e., number of vertices in the graph by one via two rules:

-At any time during the heuristic, if a degree-1 vertex appears it is matched with its only neighbor.

-If a degree-2 vertex u appears with neighbors {v, w} and no degree-1 vertex exists, u (and its edges) is removed from the current graph, and v and w are merged to create a new vertex vw whose set of neighbors is the union of those of v and w (except u). A maximum cardinality matching for the reduced graph can be extended to obtain one for the current graph by matching u with either v or w depending on vw's match. Both rules are optimal in the sense that they do not reduce the cardinality of a maximum matching in the current graph they are applied on. We now propose an adaptation of Karp-Sipser g for d-partite, d-uniform hypergraphs, and call this heuristic Karp-Sipser. Similar to the original one, Karp-Sipser iteratively adds a random hyperedge to the matching, remove its d endpoints and their hyperedges. However, the random selection is not applied whenever hyperedges defined by the lemmas below appear.

Lemma 1. During the heuristic, if a hyperedge e with at least d -1 degree-1 endpoints appears, there exists a maximum cardinality matching in the current hypergraph containing e.

Proof. Let H be the current hypergraph at hand and e = (u 1 , . . . , u d ) be a hyperedge in H whose first d -1 endpoints are degree-1 vertices. Let M be a maximum cardinality matching in H . If e ∈ M , we are done. Otherwise, assume that u d is the endpoint matched by a hyperedge e ∈ M (note that if u d is not matched M can be extended with e). Since u i , 1 ≤ i < d, are not matched in M , M \ {e } ∪ {e} defines a valid maximum cardinality matching for H . We note that it is not possible to relax the condition by using a hyperedge e with less than d -1 endpoints of degree-1; in M , two of e's higher degree endpoints could be matched with two different hyperedges, in which case the substitution as done in the proof of the lemma is not valid. Lemma 2. During the heuristic, let e = (u 1 , . . . , u d ) and e = (u 1 , . . . , u d ) be two hyperedges sharing at least one endpoint where for an index set I ⊂ {1, . . . , d} of cardinality d -1, the vertices u i , u i for all i ∈ I only touch e and/or e . That is for each i ∈ I, either u i = u i is a degree-2 vertex or u i = u i and they are both degree-1 vertices. For j / ∈ I, u j and u j are arbitrary vertices. Then, in the current hypergraph, there exists a maximum cardinality matching having either e or e .

Proof. Let H be the current hypergraph at hand and j / ∈ I be the remaining part id. Let M be a maximum cardinality matching in H . If either e ∈ M or e ∈ M , we are done. Otherwise, u i and u i for all i ∈ I are unmatched by M . Furthermore, since M is maximal, u j must be matched by M (otherwise, M can be extended by e). Let e ∈ M be the hyperedge matching u j . Then M \ {e } ∪ {e} defines a valid maximum cardinality matching for H . Whenever such hyperedges appear, the rules below are applied in the same order:

-Rule-1: At any time during the heuristic, if a hyperedge e with at least d-1 degree-1 endpoints appears, instead of a random hyperedge, e is added to the matching and removed from the hypergraph.

-Rule-2: Otherwise, if two hyperedges e and e as defined in Lemma 2 appear, they are removed from the current hypergraph with the endpoints u i , u i for all i ∈ I. Then, we consider u j and u j . If u j and u j are distinct, they are merged to create a new vertex u j u j , whose hyperedge list is defined as the union of u j 's and u j 's hyperedge lists. If u j and u j are identical, we rename u j as u j u j . After obtaining a maximal matching on the reduced hypergraph, depending on the hyperedge matching u j u j , either e or e can be used to obtain a larger matching in the current hypergraph. When Rule-2 is applied, the two hyperedges identified in Lemma 2 are removed from the hypergraph, and only the hyperedges containing u j and/or u j have an update in their vertex list. Since the original hypergraph is d-partite and duniform, that update is just a renaming of a vertex in the concerned hyperedges (hence the resulting hypergraph is d-partite and d-uniform).

Although the extended rules usually lead to improved results in comparison to Greedy, Karp-Sipser still adheres to the d-approximation bound of maximal matchings. To see this, we use the toy example given as a worst-case for Greedy.

For the example given at the beginning of Section 3, Karp-Sipser generates a maximum cardinality matching by applying Rule-1. However, if e 5 = (2, 1, 3) and e 6 = (3, 1, 3) are added to the example, neither of the two rules can be applied. As before, if e 4 is randomly selected, it forms a maximal matching.

Karp-Sipser-scaling for Max-d-DM

Karp-Sipser can be modified for better decisions in case neither of the two rules applies. In this variant, called Karp-Sipser-scaling, instead of a random selection, we first scale the adjacency tensor of H and obtain an approximate d-stochastic tensor T. We then augment the matching by adding the hyperedge which corresponds to the largest value in T. The modified heuristic is summarized in Algorithm 1.

Our inspiration comes from the d = 2 case and more specifically from the relation between scaling and matching. It is known due to Birkhoff [4] that the polytope of n × n doubly stochastic matrices is the convex hull of the n × n permutation matrices. A nonnegative matrix A where all entries participate in some perfect matching can be scaled with two positive diagonal matrices R and C such that RAC is doubly stochastic. Otherwise, provided that A has a perfect matching, it can still be scaled to a doubly stochastic form asymptotically. In this case, the entries not participating in any perfect matching tend to zero in the scaled matrix. This fact is exploited to design randomized approximation algorithms for the maximum cardinality matching problem in graphs [START_REF] Dufossé | Two approximation algorithms for bipartite matching on multicore architectures[END_REF][START_REF] Dufossé | Approximation algorithms for maximum matchings in undirected graphs[END_REF]. By scaling the adjacency matrix in a preprocess and choosing edges with a probability corresponding to the scaled value of the associated matrix entry, the edges which are not included in a perfect matching become less likely to be chosen. The current algorithm differs from these approaches by selecting a single hyperedge at each step and applying scaling again before the next selection.

For d ≥ 3, there is no equivalent of Birkhoff's theorem as demonstrated by the following lemma.

Algorithm 1: Karp-Sipser-scaling

Input: A d-partite, d-uniform n1 × • • • × n d hypergraph H = (V, E) Output: A maximal matching M of H 1: M ← ∅ Initially M is empty 2: S ← ∅
Stack for the merges for Rule-2 3: while H is not empty do 4:

Remove the isolated vertices from H 5:

if ∃e = (u1, . . . , u d ) as in Rule-1 then 6:

M ← M ∪ {e} Add e to the matching 7:

Apply the reduction for Rule-1 on H 8:

else if ∃e = (u1, . . . , u d ), e = (u 1 , . . . , u d ) and I as in Rule-2 then 9:

Let j be the part index where j / ∈ I 10:

Apply the reduction for Rule-2 on H by introducing the vertex uju j 11: Let e ∈ M be the hyperedge matching uju j 25:

E = {(v1, . . . ,
if e ∈ E then 26:

Replace uju j in e with u j 27:

M ← M ∪ {e } 28: else 29:

Replace uju j in e with uj 30:

M ← M ∪ {e} Lemma 3. For d ≥ 3, there exist extreme points in the set of d-stochastic tensors which are not permutations tensors.

The proof can be found in the accompanying technical report [START_REF] Dufossé | Effective heuristics for matchings in hypergraphs[END_REF], where we give extreme points that are not permutation tensors. Due to the lemma above, we do not have the theoretical foundation to imply that hyperedges corresponding to the large entries in the scaled tensor must necessarily participate in a perfect matching. Nonetheless, the entries not in any perfect matching tend to become zero (not guaranteed for all though). For the worst case example of Karp-Sipser described above, the scaling indeed helps the entries corresponding to e 4 , e 5 and e 6 to become zero. Additionally even if the heuristic selects an entry in the non-zero pattern of an extreme point without a perfect matching, we do not necessarily reduce our chances of obtaining a good matching (see the discussion following the proof of Lemma 3 in the technical report). On a d-partite, d-uniform hypergraph H = (V, E), the Sinkhorn-Knopp algorithm used for scaling operates in iterations, each of which requires O(|E| × d) time. In practice, only a few iterations (e.g., 10-20) can be performed. Since we can match at most |V |/d hyperedges, the overall run time of scaling is O(|V | × |E|). A straightforward implementation of the second rule can take quadratic time in the case of a large number of repetitive merges with a given vertex. In practice, more of a linear time behavior should be observed.

Hypergraph matching via pseudo scaling

In Algorithm 1, applying scaling at every step can be very costly. Here we propose an alternative idea inspired by the specifics of the Sinkhorn-Knopp algorithm to reduce the overall cost.

The Sinkhorn-Knopp algorithm scales a d-dimensional tensor T in a series of iterations by updating the set of vectors x (1) , . . . , x (d) where initially all values in all vectors are equal to 1. During an iteration, the coefficient vector x (j) for a given dimension j is updated by using x (j)

i j = x (j) i j i 1 ,...,i j-1 ,i j+1 ,...i d Ti 1 ,...,i j ,...,i d d k=1 x (k) i k , for all ij ∈ {1, . . . , nj} . (1)
These updates are done in a sequential order and for simplicity we assume that they happen in the dimension order: 1, . . . , d. Each vector entry x (j) ij corresponds to a vertex in the hypergraph. Let λ ij denote the degree of the vertex i j from jth part. For the first iteration of (1), each x

i1 is set to 1 λi 1 since all values in the vectors are one. The pseudo scaling approach applies d parallel executions of updates (1) and sets each x

(j) ij = 1 λi j
for all j ∈ {1, . . . , d} and i j ∈ {1, . . . , n j }. That is, each vertex gets a value inversely proportional to its degree. This avoids 10-20 iterations of Sinkhorn-Knopp and the O(|E|) cost for each. However, as the name of the approach implies, this scaling is not exact.

With this approach each hyperedge {i 1 , . . . , i d } is associated with a value 1

d j=1 λ ij
. The selection procedure is the same as that of Algorithm 1, i.e., the hyperedge with the maximum value is added to the matching set. We refer to this algorithm as Karp-Sipser-mindegree, as it selects a hyperedge based on a function of the degrees of the vertices. With a straightforward implementation, finding this hyperedge takes O(|E|) time.

Reduction to bipartite graph matching

A perfect matching in a d-partite, d-uniform hypergraph H remains perfect when projected on a (d -1)-partite, (d -1)-uniform hypergraph obtained by removing one of H's vertex parts. Matchability in (d -1)-partite sub-hypergraphs has been investigated [START_REF] Aharoni | Hall's theorem for hypergraphs[END_REF] to provide an equivalent of Hall's Theorem for d-partite hypergraphs. These observations lead us to propose a heuristic called Bipartitereduction. This heuristic tackles the d-partite, d-uniform case by recursively asking for matchings in (d -1)-partite, (d -1)-uniform hypergraphs and so on, until d=2.

Let us start with d = 3. Let G = (V G , E G ) be the bipartite graph where the vertex set

V G = V 1 ∪ V 2 is obtained by deleting V 3 from a 3-partite, 3-regular hypergraph H = (V, E). The edge (u, v) ∈ E G iff
there exists a hyperedge (u, v, z) ∈ E. One can assign weights to the edges during this step, e.g., w(u, v) = |{z : (u, v, z) ∈ E}|. A maximum weighted matching algorithm can be used to obtain a matching

M G on G. A second bipartite graph G = (V G , E G ) is then created with V G = (V 1 × V 2 ) ∪ V 3 and E G = {(uv, z) : (u, v) ∈ M G , (u, v, z) ∈ H}.
Any matching in G corresponds a valid matching in H. Furthermore, if the weight function defined above is used with a maximum weighted matching algorithm, the number of edges surviving for G is maximized.

For d-dimensional matching, a similar process is followed. First, an ordering i 1 , i 2 , . . . , i d of the dimensions is defined. At the jth bipartite reduction step, the matching is found between the dimension cluster i 1 i 2 • • • i j and the dimension i j+1 by similarly solving a bipartite matching problem, where the edge (u 1 • • • u j , v) exists in the bipartite graph iff the vertices u 1 , . . . , u j were matched previously, and there exists a hyperedge (u 1 , . . . , u j , v, z j+2 , . . . , z d ) in H. Unlike the previous heuristics, Bipartite-reduction does not have any approximation guarantee, as stated in the following lemma (the proof is in the accompanying technical report [START_REF] Dufossé | Effective heuristics for matchings in hypergraphs[END_REF], where we describe a family of hypergraphs for which Bipartite-reduction yields 5 n -approximation for n ≥ 5).

Lemma 4. If algorithms for the maximum cardinality or the maximum weighted matching (with the suggested edge weights) problems are used, then Bipartitereduction has a worst-case approximation ratio of Ω(n).

Performing local search

A local search heuristic is proposed by Hurkens and Schrijver [START_REF] Hurkens | On the size of systems of sets every t of which have an sdr, with an application to the worst-case ratio of heuristics for packing problems[END_REF]. It starts from a feasible maximal matching M and performs a series of swaps until it is no longer possible. In a swap, k hyperedges of M are replaced with at least k + 1 new hyperedges from E \M so that the cardinality of M increases by at least one. These k hyperedges from M can be replaced with at most d×k new edges. Hence, these hyperedges can be found by a polynomial algorithm enumerating all the possibilities. The approximation guarantee improves with higher k values. Local search algorithms are limited in practice due to their high time complexity. The algorithm might have to examine all |M | k subsets of M to find a feasible swap at each step. The algorithm by Cygan [START_REF] Cygan | Improved approximation for 3-dimensional matching via bounded pathwidth local search[END_REF] which achieves d+1+ε 3 -approximation is based on a different swap scheme but is also not suited for large hypergraphs.

Experiments

To understand the relative performance of the proposed heuristics, we conducted a wide variety of experiments with both synthetic and real-life data. The experiments were performed on a computer equipped with intel Core i7-7600 CPU and 16GB RAM. For d = 3, we also implemented a local search heuristic [START_REF] Hurkens | On the size of systems of sets every t of which have an sdr, with an application to the worst-case ratio of heuristics for packing problems[END_REF], called Local-Search, which replaces one hyperedge from a maximal matching M with at least two hyperedges from E \ M to increase the cardinality of M . We did not consider local search schemes for higher dimensions or with better approximation ratios as they are computationally too expensive. For each hypergraph, we perform ten runs of Greedy and Karp-Sipser with different random decisions and take the maximum cardinality obtained. Since Karp-Sipser-scaling or Karp-Sipsermindegree do not pick hyperedges randomly, we run them only once. We perform 20 steps of the scaling procedure in Karp-Sipser-scaling. We refer to quality of a matching M in a hypergraph H as the ratio of M 's cardinality to the size of the smallest vertex partition of H.

Experiments on random hypergraphs

We perform experiments on two classes of d-partite, d-uniform random hypergraphs where each part has n vertices. The first class contains random k-out hypergraphs, and the second one contains sparse random hypergraphs.

Random k-out, d-partite, d-uniform hypergraphs Here, we consider random k-out, d-partite, d-uniform hypergraphs described in Section 2. Hence (ignoring the duplicate ones), these hypergraphs have around d × k × n hyperedges. These k-out, d-partite, d-uniform hypergraphs have been recently analyzed in the matching context by Devlin and Kahn [START_REF] Devlin | Perfect fractional matchings in k-out hypergraphs[END_REF]. They state in passing that k should be exponential in d for a perfect matching to exist with high probability. The bipartite graph variant of the same problem has been extensively studied in the literature [START_REF] Frieze | Maximum matchings in a class of random graphs[END_REF][START_REF] Karoński | Existence of a perfect matching in a random (1+e -1 )-out bipartite graph[END_REF][START_REF] Walkup | Matchings in random regular bipartite digraphs[END_REF]; a perfect matching almost always exists in a random 2-out bipartite graph [START_REF] Walkup | Matchings in random regular bipartite digraphs[END_REF].

k k d d d-3 d d-2 d d-1 d d d-3 d d-2 d d-1 2
-0.87 1.00 2 -0.84 1.00 3 0.80 1.00 1.00 3 0.88 1.00 1.00 n = 10 4 1.00 1.00 1.00 n = 30 4 0.99 1.00 1.00 5 1.00 1.00 1.00 5 * 1.00 1.00 2 -0.88 1.00 2 -0.87 1.00 3 0.85 1.00 1.00 3 0.84 1.00 1.00 n = 20 4 1.00 1.00 1.00 n = 50 4 * 1.00 1.00 5 1.00 1.00 1.00 5 * * * We first investigate the existence of perfect matchings in random k-out, dpartite, d-uniform hypergraphs. For this purpose, we implemented the linear program of d-dimensional matching in CPLEX and found the maximum cardinality of a matching in these hypergraphs with k ∈ {d d-3 , d d-2 , d d-1 } for d ∈ {2, . . . , 5} and n ∈ {10, 20, 30, 50}. For each (k, d, n) triple, we created five hypergraphs and computed their maximum cardinality matchings. For k = d d-3 , we encountered several hypergraphs with no perfect matching, especially for d = 3. The hypergraphs with k = d d-2 were also lacking a perfect matching for d = 2. However, all the hypergraphs we created with k = d d-1 had at least one. Based on these results, we experimentally confirm Devlin and Kahn's statement. We also conjecture that d d-1 -out random hypergraphs have perfect matchings almost surely. The average maximum matching cardinalities we obtained in this experiment are given in Table 1. In this table, we do not have results for k = d d-3 for d = 2, and the cases marked with * were not solved within 24 hours. We now compare the performance of the proposed heuristics on random kout, d-partite, d-uniform hypergraphs with d ∈ {3, 9} and n ∈ {1000, 10000}. We tested with k values equal to powers of two for k ≤ d log d. The results are summarized in Figure 1. For each (k, d, n) triplet, we create ten random instances and present the average performance of the heuristics on them. Further figures for d = 6 can be found in the accompanying technical report [START_REF] Dufossé | Effective heuristics for matchings in hypergraphs[END_REF]. The x-axis in each figure denotes k, and the y-axis reports the matching cardinality over n. As seen, Karp-Sipser-scaling and Karp-Sipser-mindegree have the best performance, comfortably beating the other alternatives. For d = 3 Karp-Sipser-scaling dominates Karp-Sipser-mindegree, but when d > 3 we see that Karp-Sipser-mindegree has the best performance. Karp-Sipser performs better than Greedy. However, their performances get closer as d increases. This is due to the fact that the conditions for Rule-1 and Rule-2 hold less often for larger d. Bipartite-reduction has worse performance than the others, and the gap in the performance grows as d increases. This happens, since at each step, we impose more and more conditions on the edges involved and there is no chance to recover from bad decisions.

Sparse random d-partite, d-uniform hypergraphs Here, we consider a random d-partite, d-uniform hypergraph H i that has i × n random hyperedges. The parameters used for these experiments are i ∈ {1, 3, 5, 7}, n ∈ {4000, 8000}, and d ∈ {3, 9}. Each H i is created by choosing the vertices of a hyperedge uniformly at random for each dimension. We do not allow duplicate hyperedges. Another random hypergraph H i+M is then obtained by planting a perfect matching to H i . We again generate ten random instances for each parameter setting. We do not present results for Bipartite-reduction as it was always worse than the others, as before. The average quality of different heuristics on these instances is shown in Figure 2 (the accompanying report [START_REF] Dufossé | Effective heuristics for matchings in hypergraphs[END_REF] contains further results). The experiments confirm that Karp-Sipser performs consistently better than Greedy. Furthermore, Karp-Sipser-scaling performs significantly better than Karp-Sipser. Karp-Sipser-scaling works even better than the local search heuristic, and it is the only heuristic that is capable of finding planted perfect matchings for a significant number of the runs. In particular when d > 3, it finds a perfect matching on H i+M s in all cases shown. For d = 3, it finds a perfect matching only when i = 1 and attains a near perfect matching when i = 3. Interestingly Karp-Sipser-mindegree outperforms Karp-Sipser-scaling on H i s but is dominated on H i+M s, where it is the second best performing heuristic. Sipser scaling minDegree i 4000 8000 4000 8000 4000 8000 4000 8000 4000 8000 4000 8000 4000 8000 4000 8000 4000 8000 4000 8000 1 0.43 0.42 0.47 0.47 0.49 0.48 0.49 0.48 0.49 0.48 0.75 0.75 0.93 0.93 1.00 1.00 1.00 1.00 1.00 1.00 3 0.63 0.63 0.71 0.71 0.73 0.72 0.76 0.76 0.78 0.77 0.72 0.71 0.82 0.81 0.81 0.81 0.99 0.99 0.92 0.92 5 0.70 0.70 0.80 0.80 0.78 0.78 0.86 0.86 0.88 0.88 0.75 0.74 0.84 0.84 0.82 0.82 0.94 0.94 0.92 0.92 7 0.75 0.75 0.84 0.84 0.81 0.81 0.94 0.94 0.93 0.93 0.77 0.77 0.87 0.87 0.83 0.83 0.96 0.96 0.94 0.94 (a) d = 3, without (left) and with (right) the planted matching

Evaluating algorithmic choices

Here, we evaluate the use of scaling and the importance of Rule-1 and Rule-2.

Scaling vs no-scaling

To evaluate and emphasize the contribution of scaling better, we compare the performance of the heuristics on a particular family of d-partite, d-uniform hypergraphs where their bipartite counterparts have been used before as challenging instances for the original Karp-Sipser g heuristic [START_REF] Dufossé | Two approximation algorithms for bipartite matching on multicore architectures[END_REF]. Let A KS be an n × n matrix. Let R 1 and C 1 be A KS 's first n/2 rows and columns, respectively, and R 2 and C 2 be the remaining n/2 rows and columns, respectively. Let the block R 1 × C 1 be full and the block R 2 × C 2 be empty. A perfect bipartite graph matching is hidden inside the blocks R 1 ×C 2 and R 2 ×C 1 by introducing a non-zero diagonal to each. In addition, a parameter t connects the last t rows of R 1 with all the columns in C 2 . Similarly, the last t columns in C 1 are connected to all the rows in R 2 . An instance from this family of matrices is depicted in Figure 3. Karp-Sipser g is impacted negatively when t ≥ 2 whereas Greedy g struggles even with t = 0 because random edge selections will almost always be from the dense R 1 × C 1 block. To adapt this scheme to hypergraphs/tensors, we generate a 3-dimensional tensor T KS such that the nonzero pattern of each marginal of the 3rd dimension is identical to that of A KS . Table 2 shows the performance of the heuristics (i.e., matching cardinality normalized with n) for 3-dimensional tensors with n = 300 and t ∈ {2, 4, 8, 16, 32}.

R 1 R 2 C 1 C 2 t t
The use of scaling indeed reduces the influence of the misleading hyperedges in the dense block R 1 ×C 1 , and the proposed Karp-Sipser-scaling heuristic always finds the perfect matching as does Karp-Sipser-mindegree. However, Greedy and Karp-Sipser perform significantly worse. Furthermore, Local-Search returns 0.99approximation in every case because it ends up in a local optima.

Rule-1 vs Rule-2

We finish the discussion on the synthetic data by focusing on Karp-Sipser. Recall from Section 3.2 that Karp-Sipser has two rules. In the bipartite case, a variant of Karp-Sipser g in which Rule-2 is not applied received more attention than the original version, because it is simpler to implement and easier to analyze. This simpler variant has been shown to obtain good results both theoretically [START_REF] Karp | Maximum matching in sparse random graphs[END_REF] and experimentally [START_REF] Dufossé | Two approximation algorithms for bipartite matching on multicore architectures[END_REF]. Recent work [START_REF] Anastos | Finding perfect matchings in random cubic graphs in linear time[END_REF] shows that both rules are needed to obtain perfect matchings in random cubic graphs.

We present a family of hypergraphs to demonstrate that using Rule-2 can lead to better performance than using Rule-1 only. We use Karp-Sipser R1 to refer to Karp-Sipser without Rule-2. As before, we describe first the bipartite case. Let A RF be a n × n matrix with (A RF ) i,j = 1 for 1 ≤ i ≤ j ≤ n, and (A RF ) 2,1 = (A RF ) n,n-1 = 1. That is, A RF is composed of an upper triangular matrix and two additional subdiagonal nonzeros. The first two columns and the last two rows have two nonzeros. Assume without loss of generality that the first two rows are merged by applying Rule-2 on the first column (which is discarded). Then in the reduced matrix, the first column (corresponding to the second column in the original matrix) will have one nonzero. Rule-1 can now be applied whereupon the first column in the reduced matrix will have degree one. The process continues similarly until the reduced matrix is a 2 × 2 dense block, where applying Rule-2 followed by Rule-1 yields a perfect matching. If only Rule-1 reductions are allowed, initially no reduction can be applied and randomly chosen edges will be matched, which negatively affects the quality of the returned matching.

For higher dimensions we proceed as follows. Let T RF be a d-dimensional n × • • • × n tensor. We set (T RF ) i,j,...,j = 1 for 1 ≤ i ≤ j ≤ n and (T RF ) 1,2,...,2 = (T RF ) n,n-1,...,n-1 = 1. By similar reasoning, we see that Karp-Sipser with both reduction rules will obtain a perfect matching, whereas Karp-Sipser R1 will struggle. We give some results in Table 3 that show the difference between the two. We test for n ∈ {1000, 2000, 4000} and d ∈ {2, 3, 6}, and show the quality of Karp-Sipser R1 and the number of times that Rule-1 is applied over n. We present the best result over 10 runs.

As seen in Table 3, Karp-Sipser R1 obtains matchings that are about 13-25% worse than Karp-Sipser. Furthermore, the larger the number of Rule-1 applications is, the higher the quality is.

Experiments with real-life tensor data

We also evaluate the performance of the proposed heuristics on some real-life tensors selected from FROSTT library [START_REF] Smith | FROSTT: The formidable repository of open sparse tensors and tools[END_REF]. The descriptions of the tensors are given in Table 4. For nips and Uber, a dimension of size 17 and 24 is dropped respectively, as they restrict the size of the maximum cardinality matching.

As described before, a d-partite, d-uniform hypergraph is obtained from a ddimensional tensor by associating a vertex for each dimension index, and a hyperedge for each nonzero. Unlike the previous experiments, the parts of the hypergraphs obtained from real-life tensors in Table 4 do not have an equal number of vertices. In this case, the scaling algorithm works along the same lines. Let n i = |V i | be the cardinality at the ith dimension, and n max = max 1≤i≤d n i be the maximum one. By slightly modifying Sinkhorn-Knopp, for each iteration of Karp-Sipser-scaling, we scale the tensor such that the marginals in dimension i sum up to n max /n i instead of one. The results in Table 4 resemble those from previous sections; Karp-Sipser-scaling has the best performance and is slightly superior to Karp-Sipser-mindegree. Greedy and Karp-Sipser are close to each other and when it is feasible, Local-Search is better than them. In addition we see that in these instances Bipartite-reduction exhibits a good performance: its performance is at least as good as Karp-Sipser-scaling for the first three instances, but about 10% worse for the last one.

Experiments with an independent set solver

We compare Karp-Sipser-scaling and Karp-Sipser-mindegree with the idea of reducing Max-d-DM to the problem of finding an independent set in the line graph of the given hypergraph. We show that this transformation can lead good results, but is restricted because line graphs can require too much space. We use KaMIS [START_REF] Lamm | Finding Near-Optimal Independent Sets at Scale[END_REF] to find independent sets in graphs. KaMIS uses a plethora of reductions and a genetic algorithm in order to return high cardinality independent sets. We use the default settings of KaMIS (where execution time is limited to 600 seconds) and generate the line graphs with efficient sparse matrixmatrix multiplication routines. We run KaMIS, Greedy, Karp-Sipser-scaling, and Karp-Sipser-mindegree on a few hypergraphs from previous tests. The results are summarized in Table 5. The run time of Greedy was less than one second in all instances. KaMIS operates in rounds, and we give the quality and the run time of the first round and the final output. We note that KaMIS considers the time-limit only after the first round has been completed. As can be seen, while the quality of KaMIS is always good and in most cases superior to Karp-Sipser-scaling and Karp-Sipser-mindegree, it is also significantly slower (its principle is to deliver high quality results). We also observe that the pseudo scaling of Karp-Sipsermindegree indeed helps to reduce the run time compared to Karp-Sipser-scaling.

The line graphs of the real-life instances from Table 4 are too large to be handled. We estimated (using known techniques [START_REF] Cohen | Structure prediction and computation of sparse matrix products[END_REF]) the number of edges in these graphs to range from 1.5 × 10 10 to 4.7 × 10 13 . The memory needed ranges from 126GB to 380TB if edges are stored twice (assuming 4 bytes per edge).

Conclusion and future work

We have proposed heuristics for the Max-d-DM problem by generalizing existing heuristics for the maximum cardinality matching in bipartite graphs. The experimental analyses on various hypergraphs/tensors show the effectiveness and

Fig. 1 :

 1 Fig. 1: The performance of the heuristics on k-out, d-partite, d-uniform hypergraphs with n vertices at each part. The y-axis is the ratio of matching cardinality to n whereas the x-axis is k. No Local-Search for d = 9.

Fig. 2 :

 2 Fig. 2: Performance comparisons on d-partite, d-uniform hypergraphs with n = {4000, 8000}. H i contains i × n random hyperedges, and H i+M contains an additional perfect matching.

  d

  uju j , . . . , v d ) : for all (v1, . . . , uj, . . . , v d ) ∈ E} memorize the hyperedges of uj

	12:	S.push(e, e , uju j , E )	Store the current merge
	13:	else
	14:	T ← Scale(adj(H))	Scale the adjacency tensor of H
	15:

e ← arg max (u 1 ,...,u d ) (Tu 1 ,...,u d ) Find the maximum entry in T 16: M ← M ∪ {e} Add e to the matching 17: Remove all hyperedges of u1, . . . , u d from E 18: V ← V \ {u1, . . . , u d } 19: while S = ∅ do 20: (e, e , uju j , E ) ← S.pop() Get the most recent merge 21: if uju j is not matched by M then 22: M ← M ∪ {e} 23: else 24:

Table 1 :

 1

The average maximum matching cardinalities of five random instances over n on random k-out, d-partite, d-uniform hypergraphs for different k, d, and n. No runs for k = d d-3 and d = 2; the problems marked with * were not solved within 24 hours.

  Fig. 3: A KS : A challenging instance for Karp-Sipser g .

		Local Karp-Karp-Sipser-Karp-Sipser-
	t Greedy Search Sipser	scaling minDegree
	2	0.53 0.99 0.53	1.00	1.00
	4	0.53 0.99 0.53	1.00	1.00
	8	0.54 0.99 0.55	1.00	1.00
	16	0.55 0.99 0.56	1.00	1.00
	32	0.59 0.99 0.59	1.00	1.00

Table 2 :

 2 Performance of the proposed heuristics on 3-partite, 3-uniform hypergraphs corresponding to T KS with n = 300 vertices in each part.

Table 3 :

 3 Quality of matching and the number r of the applications of Rule-1 over n in Karp-Sipser R1 , for hypergraphs corresponding to T RF . Karp-Sipser obtains perfect matchings.

Table 4 :

 4 The performance of the proposed heuristics on the hypergraphs corresponding to real-life tensors. No Local-Search for four dimensional tensor Enron.

	Local-Karp-Karp-Sipser-Karp-Sipser-Bipartite-

KaMIS

Karp-Sipser-