Pruning Edges and Gradients to Learn Hypergraphs from Larger Sets
Authors: David W Zhang
Gertjan J. Burghouts
Cees G. M. Snoek
Venue: ICLR 2022 Submitted (2022)
Keywords: set-to-hypergraph

Abstract: This paper aims for set-to-hypergraph prediction, where the goal is to infer the set of relations for a given set of entities. This is a common abstraction for applications in particle physics, biological systems and combinatorial optimization. We address two common scaling problems encountered in set-to-hypergraph tasks that limit the size of the input set: the exponentially growing number of hyperedges and the run-time complexity, both leading to higher memory requirements. We make three contributions. First, we propose to predict and supervise the \emph{positive} edges only, which changes the asymptotic memory scaling from exponential to linear. Second, we introduce a training method that encourages iterative refinement of the predicted hypergraph, which allows us to skip iterations in the backward pass for improved efficiency and constant memory usage. Third, we combine both contributions in a single set-to-hypergraph model that enables us to address problems with larger input set sizes. We provide ablations for our main technical contributions and show that our model outperforms prior state-of-the-art, especially for larger sets.

Under review as a conference paper at ICLR 2022
PRUNING EDGES AND GRADIENTS TO LEARN HYPERGRAPHS FROM LARGER SETS
Anonymous authors Paper under double-blind review
ABSTRACT
This paper aims for set-to-hypergraph prediction, where the goal is to infer the set of relations for a given of entities. This is a common abstraction for applica- tions in particle physics, biological systems and combinatorial optimization. We address two common scaling problems encountered in -yppeerggg tasks that limit the size of the imput set: the exponentially growing number of hyperedges and the run-time complexity, both leading to higher memory requirements. We make three contributions. First, we propose to predict and supervise the posi- tive edges only, which changes the asymptotic memory scaling from exponential to linear. Second, we introduce training method that encourages iterative re- finement of the predicted hypergraph, which allows us to skip iterations the backward pass for improved efficiency and constant memory usage. Third, we combine both contributions in a single thyperrrpegg model that enables us to address problems with larger input set sizes. We provide ablations for our main technical contributions and show that our model outperforms prior ofate-of-the-art, especially for larger sets.
INTRODUCTION
Inferring the relational structure for a given set of entities is a common abstraction for many appli- cations, including vertex reconstruction in particle physics (Shlomi al., 2020a; Serviansky et al., 2020), inferring higher-order interactions in biological and social systems (Brugere et al., 2018; Battiston al., 2020) or combinatorial optimization problems, such as finding the convex hull or Delaunay triangulation ( (Vinyals et al., 2015; Serviansky et al., 2020). The wide spectrum of different application areas underlines the expressivity of this abstract task, which known in machine learn- prediction (Serviansky et al., 2020). Here, the hypergraph generalizes the
ing as cet-to-hypergen pairwise relations in a graph to multi-way relations, k.a hyperedges. We distinguish this task from the related, but different, task of link prediction that aims to discover the missing edges in graph, given the set of vertices and subset of the edges (Lü & Zhou, 2011). For the set-to-hypergraph problem considered in this paper, we start with set of nodes without any edges.
common approach to set-to-hypergraph problems is to decide for every edge, whether it exists or not (Serviansky et al., 2020). For set of nodes, the number of all possible hyperedges grows in O(2"), which already becomes intractable for moderately sized n. This is the scaling prob- lem of set-to-hypergraph prediction that we will address in this paper. Combinatorial optimization challenges, like set-to-hypergraph prediction, introduce the additional problem of complexity. For example, convex hull finding in d dimensions has a run time complexity of O(n log(n) + nIăl) (Chazelle, 1993). This means that larger input sets require more compute regardless of the quality of the hypergraph prediction algorithm. Indeed, it was observed in (Serviansky et al., 2020) that for larger set sizes performance was worse. In this paper we aim to address the scaling and complexity problems in order to predict hypergraphs from larger sets.
We make three contributions in this paper. First, in Section 2 we improve the scalability of hy- pergraph representations for serrrahhy tasks, by pruning the non-existing edges. We prove that during training it suffices to supervise the existing edges only, thus improving the asymptotic memory requirements from O(2") O(m)). that is linear in the input set size. Second, to ad- dress the complexity problem, we introduce in Section 3 a training method that encourages iterative refinement of the predicted hypergraph with memory requirements scaling constant in the number

---

Under review as a conference paper at ICLR 2022
of refinement steps. This addresses the need for more compute by complex problems in scalable manner. Third, we combine in Section 4 the efficient representation from the first contribution with the requirements of the scalable training method from the second contribution in recurrent model that performs iterative refinement on a pruned hypergraph. Our model handles different input set sizes and varying numbers of edges, while respecting the permutation symmetry of both. In our experiments in Section 5, we provide an in-depth ablation on each of our technical contributions and compare our model against prior work on common he-po-hhypeggaph benchmarks.
1.1 PRELIMINARY
Hypergraphs generalize normal graphs by replacing the normal edges that connect exactly two nodes with hyperedges that connect an arbitrary number of nodes. Since we only consider the general version, shorten hyperedges we treat the input set as the set of nodes of a hypergraph and aim to learn a function f that predicts the corresponding set of edges. For example, the input set could consist of objects in image and the edges would represent their relations.
edges in the remainder of the paper. In hypergrrpp tasks,
Next, we provide an overview of the Se12Graph neural network (Serviansky al., 2020). We focus on it because most previous networks follow similar structure. In Set2Graph, f is split into a col- lection of set-to-k-edge functions F* where k-edges connect exactly k nodes. All 1* are composed of three steps: a set-to-set model maps the input set to a latent set, a broadcasting step forms all pos- sible k-tuples from the latent set elements, and final graph-to-gran tor-tgo-grphhhho model that predicts for each k-edge whether it exists or not. Serviansky et al. (2020) show that this can approximate any con- tinuous set-to-k-edge function, and by extension the family of 1o functions can approximate any continuous hhherrrppp function. Since the asymptotic memory scaling of F is in O(r²), modeling k-edges beyond > 2 already becomes intractable in many scttings and one has to apply heuristics to recover higher-order edges from pairwise edges (Serviansky et al., 2020).
2 SCALING BY PRUNING THE NON-EXISTING EDGES
In this section, we propose solution for the memory scaling problem encountered in set-to- hypergraph tasks. The goal is to learn a model f(X)= = H that maps a set X of input vectors to the hypergraph H. The choice on how represent the hypergraph H can already drastically impact the asymptotic complexity of f, as we saw for Set2Graph. In what follows, we explain how we represent the nodes and edges of H to learn a pruned incidence matrix, and we will motivate why that is necessary for scaling to problems with more nodes.
Nodes. Each input element æ E X gets an "identity" as a node in the hypergraph, meaning if a subset of the nodes are connected by an edge then there exists relation between the corresponding input elements. We differentiate between the input elements and the nodes of the hypergraph, as we expect the latter to be represented latent vectors V of dy dimensions. The importance of this becomes clear in the discussion on the training objective later on.
Edges. The set of all possible edges can be expressed using the power set P(V) \ {Ø), that the set of all subsets of V minus the empty set. Different from the situation with the nodes, we do not know which edge will be part of the hypergraph, since this is what we want to predict. Listing out all 2 V possible edges and deciding for each edge whether exists or not, becomes intractable very quickly. Furthermore, we observe that in many cases the number of existing edges is much smaller than the total number of possible edges. We leverage this observation by keeping only a fixed number of edges m that is sufficient to cover all (or most) hypergraphs for given task. Thus, we improve the memory requirement from O lgg) to ((dde), where dg is the vector size of the edge representations
E. All possible edges that do not have an edge representation in E are implicitly predicted to not exist. After specifying the training objective, we provide more formal argument on why pruning all but m edges from sound.
Incidence matrix. Since both the nodes and edges are represented by latent vectors, we require an additional component for specifying the connections. Different from previous approaches, we use the incidence matrix over adjacency tensors (Serviansky al., 2020; Ouvrard et al., 2017). The two
2

---

Under review as a conference paper at ICLR 2022
differ in that incidence describes whether edge is connected to node, while adjacency describes whether an edge between a subset of nodes exists. The rows of the incidence matrix I correspond to the edges and the columns to the nodes. Thus, an entry Iij [O, 1] represents the probability of the i-th edge being incident to the j-th node. Theoretically we can express any hypergraph in both representations, but pruning edges becomes especially simple in the incidence matrix, where we just remove the corresponding rows. We interpret the pruned edges e & & that have no corresponding row in the pruned I as having zero probability of being incident to any node.
Loss function. We apply the loss function only on the incidence probability matrix I. For effi- cieney purposes, we would like to train each incidence value separately as a binary classification and apply constant threshold (>> 0.5) on I at inference time to get the discrete incidence ma- trix I' In probabilistic terms, this translates to a factorization of the joint distribution X as, II. p (X). In order to still be able to model interrelations between different incidence proba- bilities, we impose a requirement on the model f: the probability Lij) produced by f depends on e, and v.. This highlights the importance of the latent node and edge representations, which enable us model the dependencies in the output while still being efficient at training and inference time. Furthermore, this changes our assumption on the incidence probabilities from that of independence to conditional independence on e; and Vj. and we apply the binary cross-entropy loss on each I.j-
The binary classification over Ii highlights yet another reason for picking the incidence represen- tation over the adjacency. When we prune all non-existing edges, learning binary classifier in the adjacency case would no longer work due to the lack of negative examples. In contrast, an existing edge in the incidence matrix contains both ones and zeros (except for the edge connecting all nodes), ensuring that a binary incidence classifier sees both positive and negative examples. However, an adjacency tensor has the advantage that the order of the entries is fully decided by the order of the nodes, which are given by the input X in our case. In the incidence matrix, the row order of the incidence matrix depends on the edges, which are orderless.
When comparing the predicted incidence matrix with a ground-truth matrix, we need to account for the orderless nature of the edges and the given order of the nodes. Hence, we require a loss function that is invariant towards reordering over the rows of the incidence matrix, but equivariant to reordering over the columns. We achieve this by matching every row in I with a row the pruned ground-truth -tuth incidence matrix I' (containing the existing edges), such that the binary cross-entropy loss H over all entries is minimal:
C(I.I')
min Σ (I Ii.)) HEll 3.
Finding a permutation n that minimizes the total loss is known as the linear assignment problem and solve it with efficient variant of the Hungarian algorithm (Kuhn, 1955; Jonker & Volgenant, 1987). We discuss the implications on the computational complexity of this in Appendix B.
Having established the training objective in Equation 1, can now offer more formal argument on the soundness of supervising existing edges only while pruning the non-existing ones, where J can be understood as the full incidence matrix (proof in Appendix A):
Proposition 1 (Supervising only existing edges). Let J E [c, (), -1)xn be matrix with at most m rows for which Ej: Jıj > e, with a small e >> 0. Similarly, let J E {0, (2"""11)x be a matrix with at most m rows for which 3j Jij 1. Let prune(.) denote the function that maps from (2 - 1) x n matrix to a k x n. matrix, by removing (2n - 1) - k rows where all values are S c. Then, for a constant = (2"-1- H(,, 0) and all such and J":
C(J,J')
+
The matrix pr)ne(J) can be understood as the pruned incidence matrix that we defined earlier and prune(J*) the pruned ground-truth. In practice, the corresponds to lower bound on the log in the entropy computation, like 110 in PyTorch (Paszke et al., 2019). Since the losses in Equation equivalent up to additive constant, the gradients of the parameters are exactly equal in both the pruned and non- non-pruned cases. Thus, pruming the non-existing edges does not affect learning, while significantly reducing the asymptotic memory requirements.
3

---

Under review as a conference paper at ICLR 2022
Summary. In cettto-hypergraph tasks, the number of different edges that can be predicted grows exponentially with the imput set size. We address this computational limitation by representing the edge connections with the incidence matrix and pruning all non-existing edges before explicitly deciding for each edge whether it exists or not. We show that pruning the edges is sound, when the loss function respects the permutation symmetry in the edges.
3 SCALING BY PRUNING THE NON-ESSENTIAL GRADIENTS
Next, we consider how to learn the pruned incidence matrix. Some tasks may require more compute than others, which can result worse performance or intractable models if not properly addressed. A naive approach would increase the number of parameters, either by increasing the number of hidden dimensions or the depth of the neural network, which is clearly not scalable. Furthermore, the memory requirement of backprop would also grow with greater depth. Instead, we would like to increase the amount of sequential computation by reusing parameters. That is, we want the model f be recurrent, H' = f(x; H'). Recurrent models are commonly applied to sequential data, where the input varies for each time step t (Lipton et al., 2015). In our case, we use the same input X at every step. Using a recurrent model, we can increase the total number of iterations to scale the amount of sequential computation steps without increasing the number of parameters. However, the recurrency does not address the growing memory requirements of backprop, since the activations of each iteration still need to be kept in memory.
Iterative refinement. the rest of this section, we present an efficient training algorithm that scale to any number of iterations at constant memory cost. We build the idea that if each iteration applies a small refinement, then it becomes unnecessary to backprop through every iteration. We can define an iterative refinement as reducing the loss (by a little) after every iteration, I') < C(1 "-' I*). Thus, the long-term dependencies between H. for i's that are far apart can also be ignored, since I only needs to improve the current H." We can encourage f' to iteratively refine the prediction H¹, by applying the loss L after each iteration. This has the effect that ʃ learns to move the H. in the direction of the negative gradient of L, making it similar to a gradient descent update.
Backprop with skips. Similar to previous works that encourage iterative refinement through (indi- rect) supervision on the intermediate steps (Jastrzeb- ski et al., 2018), we expect the changes each step to be small. Thus, it stands to reason that supervising every step is unnecessary and redundant. This leads us to more efficient training algorithm that skips iterations in the backward-pane of backprop. Al- gorithm describes the training procedure in pseu- docode (in syntax similar to PyTorch (Paszke et al., 2019)). We perform total of N gradient updates per mini-batch. Each gradient update consist of two phases, first iterations without gradient accumula- tion and then B iterations that add up the losses for backprop. Through these hyperparameters we control the amount of resources used during training- Increasing hyperparameter B allows for models that do not strictly decrease the loss after every step and require supervision over multiple subsequent steps. Note that having the input X at every refinement step is important so that the model does not forget the initial problem.
Algorithm 1: Backprop with skips
Input: X, B, H + initiialize())
for s S:
with no ().grd)(():
for l in range (s)
H (x H))
1-0 0
for in range (B)
H. H H.
1+1+L(A I")
backward (I)
gradiennt.teeppanddeeetll ()
Summary. Motivated by the need for more compute to address complex problems, we propose a method that increases the amount of sequential compute of the neural network without increasing the memory requirement at training time. Our training algorithm requires the model f to perform iterative refining of the hypergraph, for which we present method in the next section.
4

---

Under review as a conference paper at ICLR 2022
4 SCALING THE SET-TO-HYPERGRAPH PREDICTION MODEL
In Section and Section 3 we proposed two methods overcome the memory scaling problems that appear for sey-to-hypergraph tasks. To put these methods into practice, we need to specify model f that fulfills the required properties. In what follows, we propose a specific implementation for each such property.
Initialization. As the starting point for the iterative refinement, we initialize the nodes v from the imput set as of ww;+ +b, where W Ráyxdx, b E 18 learnable parameters. The affine map allows for hidden dimensions dy that are different from the input feature dimensions dx. An informed initialization similar the nodes is not available for the edges and the incidence matrix, since these are what we aim to predict. Instead, we choose initialization scheme that respects the permutation symmetry set of edges while also ensuring that each edge starts out differently. The last point is necessary for permutation-cqqivariin operations to distinguish between different edges. The random initialization eς ~ ((H, diag(or)), with shared learnable parameters E R and a E Re fulfills both these properties, as is highly unlikely for two samples to be identical.
Conditional independence. We want the incidence probabilities I to be conditionally indepen- dent of each other given e; and vy. A straightforward way model this by concatenating both vectors (denoted with [-) and applying an MLP with sigmoid activation on the scalar output:
r = MLP ([e--t.0)-
The superscripts point out that produce new incidence matrix for step based on the edge and node vectors from the previous step. Note that we did not specify an initialization for the incidence matrix, since directly replace it in the first step.
Iterative refinement. The training algorithm in Section 3 assumes that f performs iterative re- finement on H', but leaves open the question how design such model. Instead of iteratively refining the incidence matrix, i.e., the only term that appears in the loss (Equation 1), we focus on refining the edges and nodes.
A refinement step for some node v, E V needs to account for the rest of the hypergraph, which also changes with each iteration. For this purpose apply the permutation-equivarian DeepSets (Zaheer et al., 2017) to produce node updates dependent on the full set of nodes from the previous iteration y The input order; thus it is sensible refer to of as the updated version of the same node of- from the previous step. Furthermore, we concatenate the aggregated neighboring edges weighted by the incidence probabilities PE ve (j.t) Σt= ==1 ee to incorporate the relational structure between the nodes. This aggregation works akin to message passing in graph neural networks (Gilmer al., 2017). An indispensable input, required for adding skips in the backward pass during training, are the input features X. Instead of directly concatenating the raw features T,, we use the initial nodes v.. Finally, we express the refinement part for the nodes as:
of DeepSets means that the output set retains the
v DeepSets (f[o)- 1PE-" -PE-V (J.t), o, = 1...n
(4)
The updates to the edges E¹ mirror that of the nodes, except for the injection of the input set. Together with the aggregation function PV-E (i,t) = Ez=1 I f-1 "f we can update the edges as: (i, ,V-L By sharing the parameters between different refinement steps, we naturally obtain a recurrent model. Previous works on recurrent models (Locatello et al., 2020) saw improvements in training conver- gence by including layer normalization (Ba et al., 2016) between each iteration. Shortcut connec- tions in ResNets (He et al., 2016) have been shown to encourage iterative refinement of the latent vector (Jastrzebski et al., 2018). We add both shortcut connections and layer normalization to the updates in Equation 4 and Equation 5. Although we prune the negative edges, still want to pre- dict a variable number thereof. To achieve that we simply extend the incidence model in Equation? with existence indicator:
g DeepSets a (f[e)-1, ,
A:)
(5)
o This can be seen as factorizing the probability into "p(e, incident to v,)) p(e, exists)" and replaces the aggregation weights in PE--V and Py-EE.
(6)
5

---

Under review as a conference paper at ICLR 2022
Table 1: Particle partitioning results. On three jet types performance measured in Fl score and adjusted rand index (ART) for 11 different seeds. Our method outperforms the baselines on bottom and charm jets, while being competitive on light jets.
bottom jets
charm jets
light jets
Model
Fi
ARI
F1
ARI
F1
ARI
Se12Graph
1..46
0. 20.00
0. 7.777 oo
0.457 20.004
0.972.0.00
0.931
Set Transformer
0.630 one
0.464 nor
U.747 ora
0.466
0.970
0.9222
Slot Attention
0.600as 012
0.411
0. 2.728
0.429
0.9632..om
0.895
Ours
0.679 use
0.548
0. 0.763gmmm om
0.499 tw0
0.972gn
0.926
Summary. We propose model that fulfills the requirements of our scalable hetpe--hppergraph training framework from Section 2 and Section 3. By adding shortcut connections, we encourage it to perform iterative refinements on the hypergraph while being permutation equivariant with respect to both the nodes and the edges.
5 EXPERIMENTS
In this section, we evaluate our approach on multiple set-to-hypergraph tasks, in order to compare to prior work and examine the main design choices. We refer Appendix C for further details, results and ablations. Code is included in the supplementary material.
5.1 SCALING SET-TO- PREDICTION
First, we compare our model from Section 4 on three different sey-to-hypergraph tasks against the state-of-the-ar model. This allows us to see the difference between predicting the incidence matrix and predicting the adjacency tensors.
Baselines. Our main comparison is against Set2Graph (Serviansky et al., 2020), which is a strong and representative baseline for approaches that predict the adjacency structure, which we generally refer to as adjacency-basee approaches. Serviansky et al. (2020) modify the task in two of the benchmarks, to avoid storing an intractably large adjacency tensor. We explain in Appendix C how this affects the comparison. Additionally, we compare to Set Transformer (Lee et al., 2019) and Slot Attention (Locatello et al., 2020), which we adapt to the set-to-hyyeerrapph setting by treating the output the pruned set of edges and producing the incidence matrix with the MLP from Equation 3. We refer to these two as incidence- based approaches that also include our model.
Particle partitioning. Particle colliders are important tool for studying the fundamental parti- cles of nature and their interactions. During a collision, several particles are emanated and measured by nearby detectors, while some particles decay beforehand. Identifying which measured particles share a common progenitor is an important subtask in the context of vertex reconstruction (Shlomi al., 2020b).
We can treat this as a set-to-hypergraph task: the set of measured particles is the input set and the common progenitors are the edges of the hypergraph. We use simulated dataset of 0.9M data- sample with the default train/validation/tes. split (Serviansky et al., 2020; Shlomi et al., 2020b). Each data-sample is generated from on one of three different distributions for which we report the results separately: bottom jets, charm jets and light jets. The ground-truth target is the incidence matrix that can also be interpreted as partitioning of the input elements, since every particle has exactly one progenitor (edge).
In Table we report the performances on each type jets as the score and Adjusted Rand Index (ARI). Our method outperforms all alternatives on bottom and charm jets, while being competitive on light jets.
Convex hull. The convex hull of a finite set of d-dimensional points can be efficiently represented as the set of simplices that enclose all points. In the 3D case, each simplex consists of points that together form triangle. For the general d-dimensional case, the valid incidence matrices limited to those with incident vertices per edge. Finding the convex hull is an important and well- understood task in computational geometry, with optimal exact solutions (Chazelle, 1993; Preparata

---

Under review as a conference paper at ICLR 2022
Table 2: Convex hull results measured as Fl score. Our method outperforms all baselines consid- erably for all settings and set sizes (n).
Spherical
Gaussian
Model
n=33
n=50
ne nE|20..100 100
n==30
n=50
n 20. 100)
Se(2Graph
0.780
0.686
0.535
0.707
0.661
0.552
Set Transformer
0.773
0.752
0.703
0.741
0.727
0.686
Slot Attention
0.668
0.629
0.495
0.062
0.665
0.620
Ours
0.892
0.868
0.823
0.851
0.831
0.809
Table 3: Delaunay triangulation results for different set sizes (n). Se12Graph all metries.
Our method outperforms
n==50
ne (20..80) 80)
Model
Acc
Pre
Rec
F1
Acc
Pre
Rec
F1
Set2Graph
0.984
0.927
0.926
0.926
0.947
0.736
0.934
0.799
Ours
0.989
0.953
0.946
0.950
0.987
0.945
0.942
0.943
& Shamos, 2012). Nonetheless, predicting the convex hull for a given set of points poses a challeng- ing problem for current machine learning methods, especially when the number of points increases (Vinyals et al., 2015; Serviansky et al., 2020). We generate an input set by drawing n 3-dimensional vectors from one of two distributions: Gaussian or spherical. For the Gaussian setting, points are sampled i..d. from standard normal distribution. For the spherical setting, we additionally nor- malize each point to lie on the unit sphere. Following Serviansky et al. (2020), we use n=30, n=50 and ne(20 100), where in the latter case the input set size varies between 20 and 100.
Table 2 shows our results. Our method consistently outperforms all the baselines by considerable margin. In contrast to Se12Graph, our model does not suffer from drastic performance decline when increasing the input set size from to 50. Furthermore, based on results the Gaussian setting, we also observe that all the incidence- approaches handle varying input sizes much better than the adjacency-bast based approach.
Delaunay triangulation. A Delaunay triangulation of a finite set of 2D points is a of triangles for which the circumcircles of all triangles have no point lying inside. When there exists more than one such set, Delaunay triangulation aims to maximize the minimum angle of all triangles. We consider the same learning task and setup as Serviansky et al. (2020), who frame Delaunay triangulation as mapping from a set of 2D points to the set of Delaunay edges, represented by the adjacency matrix. Since this is essentially a set-to-graph problem instead of set-to-hypergran we adapt our method for efficiency reasons, as we describe in Appendix C. We generate the input sets of size by sampling 2-dimensional vectors uniformly from the unit square, with 5=50 or n E [2]..80].
one,
In Table 3, report the results for Set2Graph (Serviansky et al., 2020) and our adapted method. Our method again outperforms Set2Graph on all metrics.
Summary. By predicting the positive edges only, we can significantly reduce the amount of re- quired memory for set- set-to-hypergraph tasks. On three different benchmarks, we observe performance improvements when using this incidence-based approach, compared to the adjacency-basee base- line. Interestingly, our method does nof see large discrepancy in performance between different input set sizes, both convex hull finding and Delaunay triangulation. We attribute this to the recurrence of our iterative refinement scheme, which we look into next.
5.2 ABLATIONS
Effects of increasing (time) complexity. The intrinsic complexity of finding convex hull for d-dimensional set of n points is in On log(n) + nl (Chazelle, 1993). This scaling behav- ior offers an interesting opportunity to study the effects of increasing (time) complexity on model performance. The time complexity implies that any algorithm for convex hull finding scales super- linearly with the input set size. Since our learned model is not considered an algorithm that (exactly) solves the convex hull problem, the implications become less clear. In order assess the relevancy
7

---

Under review as a conference paper at ICLR 2022
of the problem's complexity for our approach, examine the relation between the number of re- fining steps and increases in the intrinsic resource requirement. The following experiments are all performed with standard backprop, in order to not introduce additional hyperparameters that may affect the conclusions.
First, examine the performance of our approach with 3 iter- ations, trained on increasing set sizes ne [10.. .5).. In Figure observe monotone drop in performance when training with the same number of iterations. The negative correlation between the set size and the performance confirms a relation- ship between the computational complexity and the difficulty of the learning task. Next, we examine the performance for varying number of iterations and set sizes. We refer to the set- ting, where the number of iterations as the base case. All other set sizes and number of iterations are chosen such that the performance matches the base case as closely as possible. In Figure 1, observe that the required number of iterations increases with the input set size, further number of iterations actually suffices in counteracting the performance decrease. Furthermore, observe that the number of refinement steps scales sub-linearly with the set size, different from what we would expect based on the complexity of the problem. We speculate this is due the paralleliza- tion of our edge finding process, differing from incremental approaches that produce one edge at time.
t
Increasing C...
50
60
set
and set size n=10,
Figure 1: Increasing complexity. Increasing the iterations counter- acts the performance decline from larger set sizes.
highlighting that an increase in the
Efficiency of backprop with skips. To assess the efficiency of backprop with skips, we compare to truncated backpropagation through time (TBPTT) (Williams & Peng, 1990). We consider two variants of our training algorithm: 1. Skipping iterations at fixed time steps and 2. Skipping randomly sampled time steps. In both the fixed and random skips ver- sions, skip half of the total iterations. We train all models on convex hull finding in 3-dimensions for 30 spherically distributed points. In addition, in- clude baselines trained with standard backprop that contingently inform us about performance degrada- tion incurred by our method or TBPTT. Standard backprop increases the memory footprint linearly with the number of iterations T, inevitably exceed- ing the available memory at some threshold. Hence, deliberately choose small set size in order to accommodate training with backprop for Te(4, 16, 32} number of iterations. We illustrate the differences between standard backprop, TBPTT and our backprop with skips in Figure 4 in the Appendix.
0.9
0.8
Training Algorithm
Standard backpmp
TEPTT
Backprop with fixed skips
0.7
Backprop with random skips
2
4
6
Relative training time
Figure Training time of backprop with skips. Relative training time and perfor- mance for different [ 16, 32]. All runs require the same memory, except standard backprop ['6 32), which require more.
The results in Figure 2 demonstrate that skipping half of the iterations in the backward-pass, sig- nificantly decreases the training time without hurting predictive performance. When the memory budget is constricted to iterations in the backward-pase both TBPTT and backprop with skips outperform standard backprop considerably.
Recurrent vs. stacked. Recurrence plays a crucial role in enabling more computation without an increase in the number of parameters. By training the recurrent model using backprop with skips, we can further reduce the memory cost during training training algorithm from Section 3 encourages iterative refinement akin to gradient descent, it is natural to believe that the weight-tying aspect of recurrence is a good inductive bias for modelling this. A reason for thinking so, is that the "gradient" should be the same for the same I, no matter at which iteration is computed. Hence, we compare the recurrent model against a non-weinee won-weight--ne -ied (stacked) version that applies different parameters at each iteration. First, compare the models trained for to 9 refinement steps. In Figure 3a, we show that both cases benefit from increasing the iterations. Adding more iterations beyond 6 only slightly improves the performance of the stacked
constant amount. Since our proposed
8

---

Under review as a conference paper at ICLR 2022
0.8
0.4
Stacked
Slacked
Recurrent
Recurrent
of Iteratioons
set size
Figure 3: Recurrent vs. stacked. (a) Performance for different numbers of iterations. (b) Extrap- olation performance on we[11. .0] for models trained with set size n=10. We stop training the recurrent model early, to match the validation performance of the stacked on n=10. The recurrent model derives greater benefits from adding iterations and generalizes better.
model, while the recurrent version still benefits, leading to absolute difference of 0.03 in Fl score for 9 iterations. Next, we train both versions with 15 iterations until they achieve a similar validation performance, by stopping training early on the recurrent model. The results in Figure 3b show that the recurrent variant performs better when tested at larger set sizes than trained, indicating an improved generalization ability.
RELATED WORK
Adjacency prediction. Set2Graph (Serviansky et al., 2020) is a family of maximally expressive permutation equivariant neural networks that map from an input set to (hyper)graphs. They show that their method outperforms many popular alternatives, including Siamese networks (Zagoruyko & Komodakis, 2015) and graph neural networks (Morris et al., 2019) applied to a k-NN induced graph. (Serviansky et al., 2020) extend the general idea, of applying scalar-valued adjacency indicator function on all pairs of nodes (Kipf & Welling, 2016), to the (-edge case (edges that connect I nodes). In Set2Graph, for each I the adjacency structure is modeled by I-tensor, requiring memory in On'). This becomes intractable already for small and moderate set sizes. By pruning the negative edges, our approach scales in Onn)), making it applicable even when I-n.
Set prediction. Recent works on set prediction map a learned initial set (Zhang et al., 2019; Lee al., 2019) randomly initialized set (Locatello al., 2020; Carion al., 2020; Zhang al., 2021) to the target space. Out of these, the closest one to our hypergraph refining approach is Slot Attention (Locatello al., 2020), which recurrently applies the Sinkhorn operator (Adams Zemel, 2011) in order to associate each element in the input set with single slot (hyperedge). None of the prior works on set prediction consider the -o---rrryprr task, but some can be naturally extended by mapping the input set to the set of positive edges, an approach similar to ours.
7 CONCLUSION AND FUTURE WORK
By representing and supervising the set of positive edges only. we substantially improve the asymp- totic scaling and enable learning tasks with higher-order edges. On common benchmarks, have demonstrated that our method outperforms previous works, while offering a more favorable asymp- totic scaling behavior. In further evaluations, we have highlighted the importance of recurrence for addressing the intrinsic complexity of problems.
Efficient set loss. We identify the Hungarian matching (Kuhn, 1955) as the main computational bottleneck during training. Replacing the Hungarian matched loss with a faster alternative, like learned energy function (Zhang et al., 2021), would greatly speed up training for tasks with large maximum number of edges.
Larger input dimensions. Our empirical analysis is limited to datasets on with low dimensional inputs. Learning on higher dimensional input data might require extensions to the model that can make larger changes to the latent hypergraph than feasible with small iterative refinement steps. The idea here is similar to the observation from Jastrzebski et al. (2018) for ResNets (He et al., 2016) that also encourage iterative refinement: earlier residual blocks apply large changes to the intermediate features while later layers perform (small) iterative refinements.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
We propose methods to deal with the scaling issues encountered set-to-hypergraph tasks and evaluate it largely synthetic datasets. Our contributions enable larger input set sizes due to better asymptotic memory scaling. This may enable applications on data with many nodes and sparse connections, including amongst others social networks (e.g., clique prediction for a new group of users) scientific data (e.g,, vertex reconstruction for more particles). In the context of applying machine learning methods in social networks, is good to mindful about biases relating human ethnicity, gender or groups that experience frequent discrimination (Torralba & Efros, 201 1; Mehrabi al., 2021).
REPRODUCIBILITY STATEMENT
The proof is included in Appendix A. Additional results and experiment descriptions are in Ap- pendix C. We provide the code for reproducing the experiments in the supplementary material.
REFERENCES
Ryan Prescott Adams and Richard S Zemel. Ranking via sinkhorn propagation. arXiv: /925, 2011.
arXiv preprint
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey Hinton. Layer normalization. arXiv preprint
arXiv:1607.066550 2016.
Federico Battiston, Giulia Cencetti, lacopo lacopini, Vito Latora, Maxime Lucas, Alice Patania, Jean-Gabriel Young, and Giovanni Petri. Networks beyond pairwise interactions: structure and dynamics. Physics Reports, 2020.
Ivan Brugere, Brian Gallagher, and Tanya Y Berger-Wolf. Network structure inference, survey: Motivations, methods, and applications. ACM Computing Surveys, 51(2):1-39, 2018.
Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In European Conference on Computer Vision, 2020.
Bernard Chazelle. An optimal convex hull algorithm in any fixed dimension. Discrete & Computa- fional Geometry, 1993.
David F Crouse.
On implementing 2d rectangular assignment algorithms. IEEE Transactions on Aerospace and Electronic Systems, 2016.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Conference on Computer Vision and Pattern Recognition, 2016.
Stanislaw Jastrzebski, Devansh Arpit, Nicolas Ballas, Vikas Verma, Tong Che, and Yoshua Bengio. Residual connections encourage iterative inference. International Conference on Learning Representations, 2018
Roy Jonker and Anton Volgenant. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, 1987.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Thomas N Kipf and Max Welling. Variational graph auto-cncoders. 161.:300, 2016.
arXiv preprint
Harold W Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2):83-97, 1955.
10

---

Under review as a conference paper at ICLR 2022
Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention-based permutation invariant neural networks. In Interna- tional Conference on Machine Learning, 2019.
Zachary C Lipton, John Berkowitz, and Charles Elkan. A critical review of recurrent neural networks for sequence learning. arXiv preprint arXiv:1506. 00019, 2015.
Francesco Locatello, Dirk Weissenborn, Thomas Unterthiner, Aravindh Mahendran, Georg Heigold, Jakob Uszkoreit, Alexey Dosovitskiy, and Thomas Kipf. Object-centric learning with slot atten- tion. In Advances in Neural Information Processing Systems, 2020.
Linyuan Lü and Tao Zhou. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications, 39006;:150-11170 2011.
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM Comput. Surv., 54(6), 2021.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
Xavier Ouvrard, Jean-Marie Le Goff, and Stéphane Marchand-Maille Adjacency and tensor rep- resentation in general hypergraphs part I: e-adjacency tensor uniformisation using homogeneous polynomials. arXiv preprint arXiv: 2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, pp.
2019.
Franco Preparata and Michael Shamos. Computational geometry: an introduction. Springer Science & Business Media, 2012.
Stefano Rebay. Efficient unstructured mesh generation by means of delaunay triangulation and bowyer-watson algorithm. Journal of Computational Physics, 106(1): 1993.
Hadar Serviansky, Nimrod Segol, Jonathan Shlomi, Kyle Cranmer, Eilam Gross, Haggai Maron, and Yaron Lipman. Set2graph: Learning graphs from sets. In Advances in Neural Information Processing Systems, 2020.
Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant. Graph neural networks in particle physics. Machine Learning: Science and Technology, 2020a.
Jonathan Shlomi, Sanmay Ganguly, Filam Gross, Kyle Cranmer, Yaron Lipman, Hadar Serviansky, Haggai Maron, and Nimrod Segol. Secondary vertex finding in jets with neural networks. arXiv preprint arXiv: arXiv:2008.0288 02831, 2020b.
Antonio Torralba and Alexei A. Efros. Unbiased look at dataset bias. Conference on Computer Vision and Pattern Recognition, 2011.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in Neural Information Processing Systems, 2015.
Pauli Virtanen, Ralf Gommers, Travis F. Oliphant, Matt Haberland, Tyler Reddy, David Courna- peau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. Nel- son, Eric Jones, Robert Kern, Eric Larson, C J Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mul- bregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nauur Methods, 2020.
11

---

Under review as a conference paper at ICLR 2022
Ronald Williams and Jing Peng. An efficient gradient-based algorithm for on-line training of recurrent network trajectories. Neural computation, 1990.
Sergey Zagoruyko and Nikos Komodakis. Learning to compare image patches via convolutional neural networks. In Conference on Computer Vision and Pattern Recognition, 2015.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. In Advances in Neural Information Processing Systems, 2017.
David W Zhang, Gertjan Burghouts, and Cees G M Snock. Set prediction without imposing struc- ture as conditional density estimation. In International Conference on Learning Representations, 2021.
Yan Zhang, Jonathon Hare, and Adam Brineel-Benett.. Deep set prediction networks. In Advances in Neural Information Processing Systems, 2019.
12

---

Under review as a conference paper at ICLR 2022
A PROOF: SUPERVISING POSITIVE EDGES ONLY SUFFICES
Proposition 1 (Supervising only existing edges), Let J E (e, 1)(22)))11)11)) -1)xn be matrix with at most m rows for which Ej: Jij > 6, with a small e > O. Similarty, let J 10. be a matrix with at most m rows for which 3j Júj = 1. Let prune(.) denote the function that maps from (2 1) x n matrix to a k x n matrix, by removing (2 - 111 rows where all values are S t.
Then, for a constant c= (2 -1- (e, O) and all such J and J":
((J,J)) ((prune(J), ((ruuee(()ppruue(() +
(2)
Proof. We shorten the notation with I=prune(J) and [==prune(J)", making the relation to the incidence matrix I defined in Section 2 explicit. Since L is invariant to permutations over the rows of its input matrices, we can assume w.l.o.g. that the not-pruned rows are the first rows, J,x = I and J I". For improved readability, let (Jx())) J() = Σ; (()x()),) Jig)) denote the element-wise binary cross-entropy, thus the loss Equation 1 can be rewritten as [(J,J")=mins
E, (Jm(s))
First, we show that there exists an optimal assignment between J. that assigns the first rows equally to an optimal assignment between I,I" More formally, for an optimal as- signment E arg min E, (Im()))) we show that there exists an optimal assignment E arg min E, (Jr())) J[) such that Visisk: xy (i)= If (i) for all isisk then the assignment for the first ls rows is also optimal for I, So we only need to show that there exists Ty such that ( for all Isisk. Let my be optimal assignment that maps i< to ky> Since my is bijection, there also exists a j<k that rr (j)>k assigns to. The corresponding loss terms are lower bounded as follows:
HJJ.. + (3)
=]](J,,)) + Jī)
(8)
Σ log(1 Ja.) + log(t) (1 (1-10 (1-Jj,)log(1 log(1-o)
Σ
(1 (ز, log(1 - Jr.)) + JJ, log(e) + (1 - Jj,,) log(1 e))
(10)
1=1
(1 | log(1 - Jaa) + JHH log (J.,) + (1- (1-Jj) Jr.1) log(1 - c)
(11)
1=1
=]](J, - Σ (1 Jj.)) log(1 -
(12)
1=1
2A(,),);)) Σ log(1 c)
(13)
1=1
-f((J., + (),
(14)
Equality of Equation holds since all rows with index >k are e-vectors in J and zero-vectors in J" The incquality in Equation 11 holds since all values in J are lower bounded by e. Thus, we have shown that either there exists no optimal assignment æy that maps from a value <k to a value >k (which is the case when (J., Jr + A[ ())))))) > HJ), + fi(e, 0)) or that there exists an equally good assignment that does not mix between the rows below and above k. Since the pruned rows are all identical, any assignment between these result in the same value (2--1-k) (e, -)- (c, 0) that only depends on the number of pruned rows 2
and number of columns n.
13

---

Under review as a conference paper at ICLR 2022
B COMPUTATIONAL COMPLEXITY
The space complexity of the hypergraph representation presented in Section 2 is in (nm)), offering an efficient representation for hypergraphs when the maximal number of edges m low, relative to the number of all possible edges m < 2". Problems that involve edges connecting many vertices benefit from this choice of representation, as the memory requirement is independent of the maximal connectivity of an edge. This differs from the adjacency- -aaeeceyy-eed approaches that not only depend on the maximum number of nodes an edge connects, but scale exponentially with In practice, this improvement from (O)(2") to (m)) is important even for moderate set sizes because the amount of required memory determines whether it is possible to use efficient hardware like GPUs. We showcase this in Appendix C.4.
Backprop with skips, introduced Section 3, further scales the memory requirement by factor of B that is the number of iterations to backprop through in single gradient update step. Notably, this scales constantly in the number gradient update steps N and iterations skipped during backprop E; St. Hence, we increase the number of recurrent steps adapt the model the problem complexity (which is important, as we show in Section 5.2), at a constant memory footprint.
To compute the loss in Equation we apply a modified Jonker- Jonker-Volgenant algorithm (Jonker & Volgenant, 1987; Crouse, 2016; Virtanen et al., 2020) that finds the minimum assignment between the rows of the predicted and the ground truth incidence matrices in O(m²). ). In practice, this can be the main bottleneck of the proposed method when the number of edges becomes large. For problems with m < n, the runtime complexity is especially efficient since independent of the number of nodes.
C EXPERIMENTAL DETAILS
In this section, we provide further details on the experimental setup and additional results.
C.1 PARTICLE PARTITIONING
The problem considers the case where particles are collided at high energy, resulting in multiple particles shooting out from the collision. Each example in the dataset consists of the input set, which corresponds to the measured outgoing particles, and the ground truth partition of the input set. Each element in the partition a subset of the input set and corresponds to some intermediate particle that was not measured, because it decayed into multiple particles before it could reach the sensors. The learning task consists of inferring which elements the input set originated from the same intermediate particle. Note that the particle partitioning task bears resemblance to the classical clustering setting. It can be understood as a meta-learning clustering task, where both the number of clusters and the similarity function depend the context that is given by X. That is why clustering algorithms such as k-means cannot be directly applied to this task. For more information on how this task fits into the area of particle physies more broadly, we refer to Shlomi al. (2020a).
Dataset. We use the publicly available dataset of 0.9M data-sample with the default train/validationntest split (Serviansky et al., 2020; Shlomi et al., 2020b). The input sets consist of 2 to 14 particles, with each particle represented by 10 features. The target partitioning indicate the common progenitors and restrict the valid incidence matrices to those with a single incident edge per node.
Setup. While Se12Graph is only one instance of an adjacency-basee approach, (Serviansky et al., 2020) show that it outperforms many popular alternatives: Siamese networks, graph neural net- works and non-learnable geometric-basee bascline. All adjacency-basee based approaches incur pro- hibitively large memory cost when predicting edges with high connectivity. In the case of particle partitioning, Set2Graph resorts only predicting edges with at most 2 connecting nodes, followed by an additional heuristic to infer the partitions (Serviansky et al., 2020). In contrast to that, all the incidence based approaches do not require the additional post-proce post-processing step at the end.
We simplify the hyperparameter search by choosing the same number of hidden dimensions d for the latent vector representations of both the nodes dy and the edges de. In all runs dedicated to
14

---

Under review as a conference paper at ICLR 2022
searching d, set the number of total iterations T=3 and backpropagate through all iterations. We start with d-=22 and double it, until an increase yields no substantial performance gains on the validation set. resulting in d==128. In our reported runs, we use ==16 total iterations, B=4 backprop iterations, N gradient updates per mini-batch, and a maximum of 10 edges.
We apply the same d-128 both the Slot Attention and Set Transformer baselines. Similar to the original version (Locatello et al., 2020), we train Slot Attention with iterations. Attempts with more than iterations resulted in frequent divergences in the training losses. We attribute this behavior to the recurrent sinkhorn operation, that acts as contraction map, forcing all slots to the same vector in the limit.
We train all models using the Adam optimizer (Kingma & Ba, 2014) with learning rate of 0.0003 for 400 epochs and retain the parameters corresponding to the lowest validation loss. All models additionally minimize a soft F1 score (Serviansky et al., 2020). Since each particle can only be part of single partition, we choose the one with the highest incidence probability test time. Our model has 268166 62 trainable parameters, similar to 251906 for the Slot Attention baseline, but less than 517250 for Set Transformer and 461289 for Set2Graph (Serviansky et al., 2020). The total training time is less than 12 hours on single GTX 1080 Ti and 10 CPU cores.
The maximum number of edges set to m = 10.
Further results. For completeness, we also report the results for the rand index (RI) in Table 4.
Table 4: Additional particle partitioning results. On three jet types performance measured as rand index (RI). Our method outperforms the baselines on bottom and charm jets, while being competitive on light jets.
bottom jets
charm jets
light jets
Model
RI
RI
RI
Set2Graph
0.736 pos
0.727 20.003
0.970
Set Transformer
0.734 004
0. 20.
0.96720.0m
Slot Attention
0.703 o1a
0.714 00.000
0.958
Ours
0.781 1 1: oo8
0.751 20.001
0.96920.001
C.2 CONVEX HULL FINDING
On convex hull finding in 3D, we compare our method to the same baselines as on the particle partitioning task.
Setup. Set2Graph learns map the set of 3D points to the 3rd order adjacency tensor. Since storing this tensor in memory is not feasible, they instead concentrate on local version of the problem, which only considers the k-nearest neighbors for each point (Serviansky We train our method with 48, T NBPTT=6 and set equal to the highest number of triangles in the training data. At test time, prediction admits an edge e; if its existence indicator o; > 0.5. Each edge is incident to the three nodes with the highest incidence probability. We apply the same hyperparameters, architectures and optimizer as in the particle partitioning experiment, except for: T-48, B=4, N-6. Since we do not change the model, the number of parameters remains at 268162 for our model. This notably differs to Set2Graph, which reports an increased parameter count of 11 166689 (Serviansky et al., 2020). We train our method until we observe no improvements on the F1 validation performance for 20 epochs, with a maximum of 1000 epochs. The set-to-set baselines are trained for 4000 epochs, and retain the parameters resulting in the highest fl score on the validation set. The total training time is between 14 and 50 hours on a single GTX 1080 Ti and 10 CPU cores.
al., 2020).
We set the maximum number of edges m equal to the maximum number of triangles of any example in the training data. For the spherically distributed point sets, m is constant that is (n-4)2++ for n 2 4. This can be seen from the fact that all points lie on the convex hull in this case. Note that the challenge lies not with finding which points lie on the convex hull, but in finding all the facets
15

---

Under review as a conference paper at ICLR 2022
that constitute the convex hull. For the Gaussian distributed point sets, m varies between different samples. For n = 30 most examples have < 40 edges, for n = 50 most examples have < 50 edges, and for 100 most examples have < 60 edges.
C.3 DELAUNAY TRIANGULATION
The problem of Delaunay triangulation is, similar to convex hull finding a well-studied problem in computational geometry and has exact solutions in On log (1)) (Rebay, 1993). We consider the same learning task as Serviansky et al. (2020), who frame Delaunay triangulation as mapping from a set of 2D points to the set of Delaunay edges, represented by the adjacency matrix. Note that this edge no longer remembers which triangles it is part of.
differs from finding the set of triangles, Thus, this reduces to a set-to-graph task, instead of -htperrhyyprg task.
Model adaptation. The goal in this task is to predict the adjacency matrix of an ordinary graph a graph consisting of edges that connect two nodes - where the number of edges are greater than the number of nodes. One could recover the adjacency matrix based on the matrix product of I' I. by clipping all values above back to 1 and setting the diagonal to O. This approach is inefficient, since in this case the incidence matrix is actually larger than the adjacency matrix. Instead of applying our method directly, we consider simple adaptation of our approach to the graph setting. We replace the initial set of edges with the (smaller) set of nodes and apply the same node refinements on both sets. This change results in E = for the prediction and effectively reduces the incidence matrix to an adjacency matrix, since it is computed based on all pairwise combinations of & and V. We further replace the concatenation for the MLP modelling the incidence probability with a sum, to ensure that the predicted adjacency matrix is symmetric and represents an undirected graph. Two of the main design choices of our approach remain in this adaptation: Iterative refining of the complete graph with a recurrent neural network and BPTT with gradient skips. We train our model with T2-2, B=4 and N=4. At test-time, an edge between two nodes exists if the adjacency value is greater than 0.5.
Setup. We increase the latent dimensions to d=256, resulting in 595201 trainable parameters. This notably differs to Set2Graph, which increases the parameter count to 5918742 (Serviansky et al., 2020), an order of magnitude larger. The total training time is less than 9 hours on a single GTX 1080 Ti and 10 CPU cores.
C.4 LEARNING HIGHER-ORDER EDGES
The particle partitioning experiment exemplifies a case where single edge can connect up to 14 vertices. Set2Graph (Serviansky et al., 2020) demonstrates that in this specific case it possible to approximate the hypergraph with graph. They leverage the fact that any vertex is incident to ex- actly one edge and apply a post-processing step that constructs the edges from noisy cliques. Instead, consider task for which no straightforward graph based approximation exists. Specifically, consider convex hull finding in 10-dimensional space for 13 standard normal distributed points. We train with 7=32, 4 and B=4. The test performance reaches F1 score of 0.75, clearly demon- strating that the model managed to learn. This result demonstrates the improved scaling behavior can be leveraged for tasks that are computationally out of reach for adjacency- -based approaches.
We demonstrated that the improved scaling behavior of our proposed method can be leveraged for tasks that are computationally out of reach for adjacency based approaches. The number of points and dimensions were chosen in conjunction, such that the corresponding adjacency tensor would require more storage than is feasible with current GPUs (available to us). For 13 points in 10 dimensions, explicitly storing the full adjacency tensor using 32-bit floating-poin numbers would already require more than 500 GB. We intentionally kept the number of points and dimensions low, to highlight that the asymptotic scaling issue cannot be met by hardware improvements, since small numbers already pose a problem. Note that Set2Graph already struggles with convex hull finding in 3D, where the authors report that storing 3-rd order tensors in memory is not feasible. Instead, they consider a local version of the problem and take the k-Nearest- Nearest-Neiihhors out of the set of points that part of the convex hull, with lo 10. While we limited our calculation of the storage requirement to the adjacency tensor itself, a typical implementation of a neural network also requires storing the intermediate activations, further exacerbating the problem for adjacency based approaches.
16

---

Under review as a conference paper at ICLR 2022
C.5 BACKPROP WITH SKIPS
We compare backprop with skips to TBPTT (Williams & Peng, 1990) with B-4 every 4 iterations. which the setting that is most similar ours with regard training time. In general, TBPTT allows for overlaps between subsequent BPTT applications, as we illustrate in Figure 4. We con- strict both TBPTT and backprop with skips to a fixed memory budget, by limiting any backward pass to the most recent B=4 iterations, for T' (E{16, 32). The standard backprop results serve as reference point to answer the question: "What if we apply backprop more frequently, resulting in a better approximation to the true gradients?", without necessitating grid search over all possible hyperparameter combinations for TBPTT. The results on standard backprop appear to indicate that performance worsens when increasing the number of iterations from 16 to 32. We observe that applying backprop on many iterations leads to increasing gradient norms the course of training, complicating the training process. The memory limited versions did not exhibit similar behavior, evident from the improved performance, when increasing the iterations from 16 to 32.
Figure 4: Adding gradient skips to backprop (a) Standard backprop (b) TBPTT, applying backprop on itera- tions every 2nd iteration (c) Backprop
(a)
(b)
with skips at iterations 1, 6, 7, 8, which effectively reduces the training time, while retaining the same number of re- finement steps.
(c)
40
17


Reviews:
[{"review_id": "j9IOl_fLqTT", "reviewer": "Reviewer_d3zQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The set-to-hypergraph prediction is an interesting problem. The graph size is indeed the bottleneck of this problem. The paper focuses on this point and proposes its solutions. From the experimental results, the method is effective in performance. However, there are some critical defects in this paper.\n\n1, The proof of Proposition 1 (Supervising positive edges only) should be the key to pruning negative edges. However, I find the first sentence of the proof in Appendix A is \"For the sake of rigor, we first summarize the relevant assumptions from ??. \". This statement directly hinders me from understanding the whole proof. This kind of typo is fatal. I hope the authors can revise them in detail.\n\n2, Some sentences are confusing. For example, on Page2 \"if an edge connects every node in V ⊂ V then there exists a relation between the input elements {xi ∈ X|vi ∈ V }. \". I am confused about how an edge can connect every node? One edge at most connects two nodes, right?\n\n3, The paper claims that specifying a maximum number of edges k is sufficiently large to cover all (or most) hypergraphs of interest. I think k should be a hyper-parameter and is very important. There is no content about how to determine and tune k, and the parameter analysis of k.\n\n4, The core work of the paper is to scale the set-to-hypergraph prediction. I am curious about why there is no absolute training time comparison shown in the experimental section. The relative training time shown in Figure 2 is hard to understand for me.\n", "summary_of_the_paper": "This paper improves the asymptotic scaling and enables the learning task to have higher-order edges by only representing and supervising a set of positive edges. In common benchmark tests, this paper has proved that the proposed method is superior to previous work while providing more favorable asymptotic scaling behavior. In further evaluation, this paper emphasizes the importance of repetition in solving the inherent complexity of the problem.", "summary_of_the_review": "The paper works on a critical problem and proposes a reasonable solution. However, there are some fatal typos and confusing statements. The experimental section lacks some critical results like absolute running time and only tests on one dataset. The authors should solve my doubts above and modify the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "d9StyTzQYSg", "reviewer": "Reviewer_ezwC", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I find it hard to assess the contribution of this paper because I feel like I don't understand it. The English is good but there is a lack of definitions and explanations regarding the considered task, terminology, and mathematical notation, which makes it hard to make sense of the proposed method. In addition, the few mathematical definitions which are given do not seem to be complete. For example, the proposed loss function has a trivial solution and functions which are introduced later are not part of the loss (see comments below). Likewise, the experimental setting is not detailed. How the hyperparameters and the optimization parameters are tuned/set is not described for the proposed method and the competitors. As a result, I believe that the most actionable approach for the authors is that I list all the questions and issues I have in the following, to make clear where this paper needs improvement.\n\n# Questions & Issues:\n## Section 1 - Introduction:\n* From what or on the basis of what is the hypergraph learned from the set? What exactly is the input?\n* Based on what do you decide whether an edge exists or not? \n* The terminology of negative edges being also called non-existent should be introduced before this terminology is used in this section.\n## Section 2 - Scaling by pruning non-existing edges:\n* Why do non-existing edges have to be pruned, why are they modeled in the first place?\n* How is a hypergraph defined? How is a hyperedge defined?\n* What is $V\\subset \\mathcal{V}$?\n* What does it mean to \"remove excess rows\" from the incidence matrix? What is an excess row? I would expect that removing the row decreases the dimensionality of the incidence matrix. This is however not reflected in the mathematical notation.\n* What does it mean to \"supervise\" an incidence $I_{ji}$?\n* \"a positive edge in the incidence matrix contains both zeros and ones\" (-> what does that mean? Further:) \"ensuring that the binary classifier sees both positive and negative examples\"(->what is a pos/neg example?)\n* \"the order of the entries is fully decided by the order of the nodes\" -> why, what does that mean?  \n* Mid Sec. 2 the ground truth appears and the loss is defined as sum of cross entropies $H(I_{i,j},I^*_{i,j})$. This loss function has a trivial minimum for $I=I^*$. I guess that some constraints are needed there. Also, where does the ground truth come from? Is this part of the input?\n* \"Since the losses are equivalent up to an additive constant, the gradients are exactly equal\" -> I don't think that's true, $\\nabla_I\\mathcal{L}(I,I^*)\\neq \\nabla_J\\mathcal{L}(J,J^*)$ already because $I$ and $J$ don't necessarily have the same dimensionality.\n\n## Section 3 - Scaling by Pruning non-essential gradients\n* Here, neural networks are mentioned for the first time, but the reader doesn't know here for what the NN is used and how it fits into the considered task.\n* What is model $f$ representing? How do time steps fit into the considered task? Where is $f$ in the objective?\n* What does it mean to supervise an iteration or step?\n* In Alg. 1, the updates in the for $t$ loops do not depend on $t$.\n\n## Section 4 - Scaling set-to-hypergraph prediction\n* What is $x_i$?\n* Introduce the abbrev. MLP, how is function $\\texttt{MLP}$ defined?\n* How is function $\\texttt{DeepSets}$ defined?\n* What is the existence indicator $\\sigma$? How can Eq. (6) be seen as factorizing the probability?\n\n## Section 5 - Experiments\n* How are parameters tuned, and what are the optimization parameter settings (step-size etc.). How are parameters set for competitors?\n* How is inference performed by the set-to-hypergraph models? \n* How is the sd computed in Table 1? Are multiple runs compared or multiple datasets/test splits?\n* How does the ML task to predict the convex hull differ from the one in computational geometry? Why is this task challenging for ML models but well understood in computational geometry?\n* Why does \"pruning the edges\" improve the predictive performance?\n* How is the number of iterations determined in the experiments?\n* How does the proposed optimization relate to TBPTT? How can TBPTT and backprop with skips improve the performance in comparison to backprop? When would it not help to apply this?\n* How does the run time of the proposed method relate to the one of competitors? \n\n## Section 6 - Related work\n* I would put this section earlier to introduce the competitors in the experiments.\n\n## Section 7 - Conclusion and Future Work\n* Nice, that you point out the limitations. But how does the input dimension exactly influence the feasibility of the proposed model?\n\n\n", "summary_of_the_paper": "The authors propose a set-to-hypergraph model where the hypergraph is represented by an incidence matrix in contrast to the usually used adjacency tensors. The incidence matrix is an edge times node matrix, which reflects only existing edges and is hence suitable to reduce the memory requirement when the amount of existing edges is sparse. The authors propose for the optimization of the proposed model\n an SGD scheme where a batch update is performed on the hypergraph which is returned by a recurrent neural network after a varying amount of time steps. \nThe experiments compare the proposed approach with 3 competitors on four datasets.  ", "summary_of_the_review": "Very unaccessible paper which might be understandable by experts in the field but not by a wider audience. Presentation needs to be improved, mathematical notation needs to be completed and experimental analysis needs to be clarified before I would consider this paper eligible for acceptance. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "P994aXgMgG", "reviewer": "Reviewer_am1Q", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pro:\n1. Predicting the set to hypergraph is a very difficult task as the solution space is O(2^n). This paper provides many tricks to increase the performance and decrease the complexity in training the models. For example, backprop with skip, recurrent training instead of stacking, reducing the solution space to O(kn). \n2. This paper trains only on positive edges. They proved this loss is similar to the overall loss. This step could greatly increase the efficiency as reduced training space.\n3. They benchmarked on three different tasks and showed a performance increase. The ablation study also revealed the proposed tricks could help training.\n\nCon:\n1. The writing and the structure of the paper are a little confusing. Though the author took lots of effort in introducing the background. But I still fail to understand what is the overall f function to construct the hypergraph? And since only trained on positive edges, how did the author select the predicted hyperedges from the overall k edges?\n2. The proposed tricks are quite heuristic and do not provide theoretical insights for performance increase.\n3. The introduction of the Hungarian algorithm in selecting the edges does not make sense to me. Though the orderless nature of the edge in the hypergraph is important, the introduction of the algorithm greatly limited the generalization of the methods. And bring bias in the performance, since the Hungarian algorithm selects the number of edges and best corresponding edges to train the model. When ground truth is not available, I don't know how the proposed algorithm will choose the number of edges and best edges to construct the hypergraph, i.e., how the model generalizes in a broader case rather than fitting the ground truth data. And I suspect the Hungarian algorithm put an unfair advantage of the proposed model in comparing with other methods. I would suggest the author remove the Hungarian algorithm and only try to derive the incidence matrix I with the proposed model. \n4. Following comment 3, the author could introduce more detail about the input, output, prerequisites of the model. Specifically, the author could explain how they choose the number of edges, how to select predicted edges.\n\n\n\n\n\n     \n\n ", "summary_of_the_paper": "This paper proposed an efficient algorithm to tackle the set to hypergraph problem by utilizing recurrent training, pruning negative edges and backprop with skips. It then benchmarked the performance with prior works on the particle partitioning, convex hall and delaunay triangulation tasks. The proposed method showed a performance increase over previous methods.\n\n", "summary_of_the_review": "This paper proposes a sufficient method to predict hypergraphs from sets and showed performance increase. Currently, it lacks sufficient detail, and may require further evaluation to justify the claims.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "9UsSblgPd45", "reviewer": "Reviewer_hMC3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n*  Proposition 1 is an interesting finding. \n\n* There are plenty of experimental results to show the empirical advantages. \n\nWeaknesses:\n* The technical contributions of this work seem not to be very novel. Proposition 1 seems to be the most novel argument but I think it is problematic (see the later criticism). The Hungarian loss to compare sets and the skip connection are standard techniques. \n\n* The proposed method suffers from high complexity. May I know how many rows of the incidence matrix I? Moreover, how to predefine the number of hyperedges/ the row # of I? The Hungarian loss has complexity O(#row(I)^2*#column(I)) or O(#row(I)*#column(I)^2) which could be high if we have a large number of rows or columns (nodes).\n\n* My biggest concern is proposition 1. This is the most important technique argument. However, proposition 1 is not stated in a rigorous way at all. What is the definition of c? Can the authors highlight some intuition between the proof in the main text? I also checked the proof. It seems that the argument is not rigorous. There are quite a lot approximations, assumptions, etc. I do not even believe prop 1 is theoretically right. \n\n* In experimental details, the authors should discuss how big the k can cover the datasets. \n", "summary_of_the_paper": "This paper addressed two scaling problems in set-to-hypergraph prediction by pruning edges and gradients. The authors made an assumption that the maximum number of edges is k to reduce the memory complexity from O(2^n) to O(kn). Backpropagation with skips was also used to reduce the computation complexity. A series of experiments were done to show the method is empirically better than the baselines.", "summary_of_the_review": "Though the set-to-hypergraph prediction is an important topic, the technical contributions of this paper are limited. The main statement is not rigorous and well explained. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes techniques for improving the scalability of set-to-hypergraph models.
The main issue with the submission is that all reviewers found the clarity of the paper to be problematic including the proofs, the experimental conditions, and many other parts.
The authors responded but some reviewers explicitly state that their questions have only partially been answered and some reviewers did not respond to the authors. Unfortunately, given the number of clarity issues raised by the reviewers it makes more sense to re-submit this paper after re-writing based on all the suggestions from the reviewers.
Decision: Reject