Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions
Authors: Nikolaos Karalias
Joshua David Robinson
Andreas Loukas
Stefanie Jegelka
Venue: NeurIPS 2022 Accept (2022)
Keywords: deep learning
unsupervised learning
combinatorial optimization
algorithmic reasoning

Abstract: Integrating functions on discrete domains into neural networks is key to developing their capability to reason about discrete objects. But, discrete domains are (1) not naturally amenable to gradient-based optimization, and (2) incompatible with deep learning architectures that rely on representations in high-dimensional vector spaces. In this work, we address both difficulties for set functions, which capture many important discrete problems. First, we develop a framework for extending set functions onto low-dimensional continuous domains, where many extensions are naturally defined. Our framework subsumes many well-known extensions as special cases. Second, to avoid undesirable low-dimensional neural network bottlenecks, we convert low-dimensional extensions into representations in high-dimensional spaces, taking inspiration from the success of semidefinite programs for combinatorial optimization. Empirically, we observe benefits of our extensions for unsupervised neural combinatorial optimization, in particular with high-dimensional representations.

Neural Set Function Extensions:
Learning with Discrete Functions in High Dimensions
Nikolaos Karalias*
Joshua Robinson" MIT CSAIL joshrobomit t. edu
Andreas Loukas Prescient Design, Genentech, Roche andreas loukas@roche.com com
EPFL
nikolaos katalasss
Stefanie Jegelka MIT CSAIL
stefjeccsail mit.. edu
Abstract
Integrating functions on discrete domains into neural networks key to develop- ing their capability reason about discrete objects. But, discrete domains (I) not naturally amenable to gradient-based optimization. and (II) incompatible with deep learning architectures that rely representations in nigh-dimensional vector spaces. In this work, we address both difficulties for set functions, which capture many important discrete problems. First, develop framework for extending set functions onto low-dimensional continuous domains, where many extensions naturally defined. Our framework subsumes many well-known extensions as special cases. Second, to avoid undesirable low-dimensional neural network bottlenecks, convert low-dimensional extensions into representations in high-dimensional spaces, taking inspiration from the success semidefinite programs for combinatorial optimization. Empirically, we observe benefits our extensions for unsupervised neural combinatorial optimization, in particular with high-dimensional representations.
Introduction
While neural networks are highly effective at solving tasks grounded in basic perception (Chen et al., 2020; Vaswani et al., 2017), discrete algorithmic and combinatorial tasks such partitioning graphs, and finding optimal routes or shortest paths have proven more challenging. This is, in part, due to the diffieulty of integrating discrete operations into neural network architectures (Battaglia al., 2018; Bengio et al., 2021; Cappart et al., 202 One immediate difficulty with functions on discrete spaces amenable standard gradient-based training. Another is that discrete functions are typically expressed in terms of scalar (e.g., Boolean) variables for each item (e.g., node, edge to be selected), contrast to the nigh-dimensional and continuous nature of neural networks' internal representations. A natural approach to addressing these challenges is to carefully choose a function on continuous domain that extends the discrete function, and can be used as a drop-in replacement.
that they
There are several important desiderata that such an extension should satisfy in order to be suited to neural network training. First, an extension should be valid, i.e., agree with the discrete function on discrete points. should also be amenable to gradient- based optimization, and should avoid introducing spurious minima. Beyond these requirements, there one additional critical consideration. In both machine learning and optimization, it has been observed that high-dimensional representations make problems "easier". For instance, neural networks rely bigh-dimensional internal
Equal contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

representations for representational power and to allow information to flow through gradients, and performance suffers considerably when undesirable low-dimensional bottlenecks are introduced into network architectures (Belkin et al., 2019; Veličković & Blundell, 2021). In optimization, lifting to higher-dimensional spaces can make the problem more well-behaved (Goemans & Williamson, 1995; Shawe- Taylor et al., 2004; Du et al., 2018). Therefore, extending discrete functions to high- dimensional domains may be critical to the effectiveness of the resulting learning process, yet remains largely open problem.
With those considerations in mind, we propose a framework for constructing extensions of discrete set functions onto -ine-iimeniional continuous spaces. The core idea is to view a continuous point x in space as an expectation over a distribution (that depends on x) supported on a few carefully chosen discrete points. to retain tractability. To evaluate the discrete function at x, we compute the expected value of the set function over this distribution. The method resulting from a principled formalization of this idea is computationally efficient and addresses the key challenges of building continuous extensions. Namely, our extensions allow gradient- -aased optimization and address the dimensionality concerns, allowing any function on sets to be used as a computation step in neural network.
First, enable gradient computations, we present a method based on a linear programming (LP) relaxation for constructing extensions on continuous domains where exact gradients can be computed using standard automatic differentiation software (Abadi et al., 2016; Bastien et al., 2012; Paszke et al., 2019). Our approach allows task-specific considerations (e.g., a cardinalilty constraint) to be built into the extension design. While our initial LP formulation handles gradients, and is a natural formulation for explicitly building extensions, it replaces discrete Booleans with scalars in the unit interval [0. 1]. and hence does not yet address potential dimensionality bottlenecks. Second, to enable higher- dimensionl representations, we take inspiration from classical SDP relaxations, such as the celebrated Goemans-Willinn Williamson maximum cut algorithm (Goemans & Williamson, 1995), which recast low-dimensional problems in high-dimensions. Specifically, our key contribution is to develop an SDP analog of our original LP formulation, and show how to lift LP-based extensions into corresponding high-dimensional SDP-based extensions. Our general procedure for lifting low-dimensional representations into higher dimensions aligns with the neural algorithmic reasoning blueprint (Veličković & Blundell, 2021), and suggests that classical techniques such as SDPs may be effective tools for combining deep learning with algorithmic processes more generally.
2 Problem Setup
Consider a ground set [n]] = (1,..... n) and an arbitrary function f: 2 - U (oo} defined on subsets of (n]. For instance, f could determine if set of nodes edges in a graph has some structural property, such as being a path, tree, clique, or independent set (Bello et al., 2016; Cappart et al., 2021a). Our aim is to build neural networks that such discrete functions ff as intermediate layer or loss. In order to produce a model that is trainable using standard auto-differentiation software, we consider continuous domain X' onto which we would like to extend ʃ. with sets embedded into X' via an injective map e 2 nl + X. For instance, when X' = [0, 1j" we may take e(5) = 1s. the Boolean vector whose ith entry is if e S. and 0 otherwise. Our approach design an extension
F X - R
of f and consider the neural network NN, o & NN1 (if f used as a loss, NN₂ is simply the identity). To ensure that the extension is valid and amenable to automatic differentiation, we require that 1) agrees with f on all discrete points: (e((S) = J(S) for all S C [r]] with I(S) < co, and 2) 3 is continuous.
There is rich existing literature on extensions of functions on discrete domains, particularly in the context of discrete optimization (Lovász, 1983; Grötschel et al., 1981; Calinescu et al., 2011; Vondrák, 2008; Bach, 2019; Obozinski & Bach, 2012; Tawarmalani & Sahinidis, 2002). These works provide promising tools to reach our goal of neural network training. Building on these, our method is the first to use remi-definite programming (SDP) to combine neural networks with set functions. There are, however, different considerations in the neural network setting as compared to optimization. The optimization literature often focuses on a class of set functions and aims to build extensions with desirable optimization properties, particularly convexity. We do not focus on convexity, aiming instead to develop a formalism that is as flexible as possible. Doing so maximizes the applicability of our method, and allows extensions adapted to task-specific desiderata (see Section 3.1).

---

S(S.)
0:25
f(Sa)
7x
40%
25%
S(S.)
vB(x)
S3
S4
3(xx)
2556
x
[(Sg]
10
S
S2
X Egppp [1s]
f(x) Eg [f()]
Figure 1: SFEs; Fractional points x are reinterpreted as expectations x Es-p, [1s] over the distribution px (S) on sets. A value is assigned by exchanging the order of f and the expectation: (f Unlike f. the extension & is amenable to gradient-based optimization.
Scalar Set Function Extensions
We start by presenting general framework for extending set functions onto X' |0, 1]"h where set S C [ni] is viewed as the Boolean indicator vector e(S) 1s E {0, 1] whose ith entry is if E S and 0 otherwise. We call extensions onto [0, 1]" scalar since each item i represented by single scalar value-the ith coordinate of x E X. These scalar extensions will become the core building blocks in developing high-dimensional extensions in Section
classical approach to extending discrete functions on sets represented as Boolean indicator vectors 1s is by computing the convex-envelope, i.e., the point-wiss supremum over linear functions that lower bound f (Falk& Hoffman, 1976; Bach, 2019). Doing so yields a convex function whose value at point E [0, 1)"h is the solution of the following linear program (LP):
((x) = max {x z + b} subject to 1 + f(S) for all S S [n].
(primal LP)
XR
The set Py of all feasible solutions (z, b) is known as the (canonical) polyhedron of f (Obozinski & Bach, 2012) and can be seen to be non-empty by taking the coordinates of to be sufficiently small (possibly negative). Variants of this optimization program are frequently encountered in the theory of matroids and submodular functions (Edmonds, 2003) where P, is commonly known the submodular polyhedron (see Appendix for an extended discussion). By strong duality, we may solve the primal LP by instead solving its dual:
f(x) min tus s05
Σ SCin)
ysf(S) subject to Σ SCIm]
ysls =x,
Σ ys = = for all S C [m]] SCIm
(dual LP)
whose optimal value is the same as the primal LP. The dual LP is always feasible (see e.g., the Lovász extension Section 3. However, does not necessarily agree with on discrete points in general, unless the function is convex-extensible (Murota, 1998).
To address this important missing piece, relax goal from solving the dual LP to instead seeking a feasible solution to the dual LP that is an extension of f. Since the dual LP is defined for a fixed a feasible solution must be function ys Px(S) of x. If px differentiable in x then the value Es (S) attained by the dual I.P would also be continuous and a.e. differentiable in since gradients flow through the coefficients ys (S), while f(S) is treated as a constant x. This leads us to the following definition:
to be continuous and a.e.
Definition (Scalar SFE), A scalar SFE & I defined at point x E [0, 1]" by coefficients Px such that ys Px is a feasible solution to the dual LP. The extension value is given by
((x)
Σ (S)
SC(m]

---

and we require the following properties to hold for all S S [x]] 1) Px(() is a continuous function of x and 2) ((1s) f(S) for all S _ [n)].
Efficient evaluation of 3 requires that (S) is supported on a small collection of carefully chosen sets S. This choice is a key inductive bias of the extension, and Section 3.1 gives many examples with only (n) non-zero coefficients. Examples include well-known extensions, such as the Lovász extension, well number of novel extensions, illustrating the versatility of the SFE framework.
Thanks to the constraint Es ys interpretation. An SFE is defined by probability distribution Px such that fractional points x can be written as an expectation E.spp [1s] = x over discrete points using Px- The extension itself can be viewed as arising from exchanging f and the expectation operation: ((x) Es-p, [(()] This interpretation is summarized in Figure 1.
in the dual LP, scalar SFEs have a natural probabilistic
Scalar SFEs also enjoy the property of not introducing any spurious minima. That is, the minima of coincide with the minima of f up to convex combinations. This property is especially important when training models of the form f o NN1 (i.e., f is a loss function) since & will guide the network NN1 towards the same solutions as f.
Proposition 1 (Scalar SFEs have no bad minima). If 8 is a scalar SFE of then:
1. minxex 8(x) = minsgl) S(S)
2. arg min (x) C Hull( arg min s::S[ll f(S))
See Appendix for proofs.
Obtaining set solutions. Given an architecture & NN; and input problem instance G, we often wish to produce sets as outputs at inference time. To do this, we simply compute x x= NN, (G), and select the set S in supPs (P)) with the smallest value (S). This can be done efficiently if, as is typically the case, the cardinality of supps (Px())) is small.
3.1 Constructing Scalar Set Function Extensions
A key characteristic of scalar SFEs is that there are many potential extensions of any given f. In this section, provide examples of scalar SFEs, illustrating the capacity of the SFE framework for building knowledge about f into the extension. See Appendix C for all proofs and further discussion.
Lovász extension. Re-indexing the coordinates of x so that 01 2 T2... ..... 2
we define Px to
be supported on the sets S C S2 C C Sn with S; = (1,2,..., ... for = 1, 1,2, 2........ n. The coefficient are defined as ys, PS.) == I; -;-I and (S) = 0 for all other sets. The resulting as the Choquel integral in decision theory (Choquet, 1954; Marichal,
Lovász cetnasiionnowwwe 2000)-is is a key tool in combinatorial optimization due to seminal result: the Lovász extension is convex if and only if f is submodular (Lovász, 1983), implying that submodular minimization can be solved in corooomlll-imme (Grötschel et al., 1981).
Bounded cardinality Lovász extension. A collection {S.) of subsets of [n] can be encoded in an X matrix S E {0, | whose ith column is 1s,- In this notation, the dual LP constraint Esgii 1s = x can be written as Sp x, where the ith coordinate of p defines (S.). The bounded cardinality extension generalizes the Lovász extension to focus only on sets of cardinality at most h < n. Again, re-index x so that 2 22.... ... 2 Tn. Use the first k sets S C S2 C ... C Sk. where S, = {1. (1.,,.... i}. to populate the first columns of matrix S. We add further n k sets: Sa+; ii j E Sx) for i I..... n k, to fill the rest of S. Finally, Px (S.) can be analytically calculated from p = S s-xx, xx, where S is invertible since it is a Toeplitz banded upper triangular matrix.
Permutations and involutory extensions. We use the same S, p notation. Let S be an elementary permutation matrix. Then is involutory, i.e., SS I, and we may easily determine p Sx given S and x. Note that Px (S;) = p: must be non-negative since x and S are non-negative entry-wise. Finally, restricting x to the niddimensional Simplex guarantees that |||| < 1, which ensures /s is a probability distribution (any remaining mass is placed on the empty set). The extension property can be guaranteed on singleton sets as long as the chosen permutation admits a fixed point at the argmax of x. Any elementary permutation matrix S with such fixed point yields valid SFE.

---

Singleton extension. Consider set function f for which f(S) = oo unless S has cardinality one. To ensure & is finite valued, Px must be supported only on the sets S, {i}, = I......2. n. Assuming x is sorted so that 21 2 22 .... 2 In, define (x,) = Ii 1i+1- It is shown in Appendix C that this defines scalar SFE, except for the dual I.P feasibility. However, when using as loss function, minimization drives x towards the minima minx 3(x) which are dual feasible. So dual infeasibility is benign in this instance and we approach the feasible set from the outside.
Multilinear extension. The multilinear extension, widely used in combinatorial optimization (Calineseu al., 2011), supported on all sets with coefficients Px(S)= Thes I; [ xz). the product distribution. In general, evaluating the multilinear extension exactly requires 2 calls to f. but for several interesting set functions, e.g., graph cut, set cover, and facility location, it can be computed efficiently in O(n²) time (Iyer et al., 2014).
Neural Set Function Extensions
This section builds on the scalar SFE framework- where each item i in the ground set [n] is represented by single scalar-to develop extensions that use high-dimensional embeddings to avoid introducing low-dimensional bottlenecks into neural network architectures. The core motivation that lifting problems into higher dimensions can make them easier is not unique to deep learning. For instance, it also underlies kernel methods (Shawe- Taylor et al., 2004) and the lift-and-projes method for integer programming (Lovász & Schrijver, 1991).
Our method takes inspiration from prior successes of semi-definice programming for combinatorial optimization (Goemans & Williamson, 1995) by extending onto X' ST. the set of n positive semi-definite (PSD) matrices. With this domain, each item is represented by a vector, not scalar.
4.1 Lifting Set Function Extensions to Higher Dimensions
We embed sets into S via the map e(S) -1 To define extensions on this matrix domain, translate the linear programming approach of Section 3 into an analogous SDP formulation:
1 max (Tr(X' Z) + b) subject to _ TT((11 + +111s)1++++1+))) + +b J(S T T) for S, r S [x], ZZD
(primal SDP)
where we switch from lower case letters to upper case since we are now using matrices. Next, show that this choice of primal SDP is natural analog of the original LP that provides the right correspondences between vectors and matrices by proving that primal LP feasible solutions correspond to primal SDP feasible solutions with the same objective value (see Appendix A for discussion on the SDP and its dual). To state the result, note that the embedding e(S) = 1s is
particular case of the correspondence x E [0, 1]" + VXVX1.
/ with the square-rott taken entry-wise. Then, for any (z, b) e R2 x E that primal LP feasible, the pair (Z, b) where Z = diag(z), (z), is primal SDP feasible and the objective values agree: Tr(X Z)
Proposition 2. (Containment of LP in SDP) For any x E [], define X =
x.
Proposition 2 establishes that the primal SDP feasible set is a spectrahedral lift of the positive primal LP feasible set, i.e., feasible solutions of the primal LP lead feasible solutions the primal SDP. As with scalar SFES, to define neural SFEs we consider the dual SDP:
(sST((STT) subject to X X 20) S,TC[]]
min
Σ S,
2 (1s17 + 1715) and Σ Us.r = 1
S (dual SDP)
We demonstrate that for suitable X this SDP has feasible solutions via an explicit construction in Section 4.2. This leads to define neural SFE which, with scalar SFEs, is given by feasible solution to the dual SDP that satisfies the extension property whose coefficients are continuous in X: Definition (Neural SFE). A neural set function extension of f at point X S is defined
8(X) A
Σ ((S,T))(STT),
S.TCM
5

---

where Us. = (S, is a feasible solution to the dual SDP and for all S,T S [n]: 1) px (S. is continuous at X and 2) it is valid, i... 3(1s15) f(S) for all S = [n].
4.2 Constructing Neural Set Function Extensions
We constructed number of explicit examples of scalar SFEs in Section 3.1. For neural SFEs employ a different strategy. Instead of providing individual examples of neural SFES, we develop a single recipe for converting any scalar SFE into corresponding neural SFE. Doing allows to build on the variety of scalar SFEs and provides an additional connection between scalar and neural SFEs. In Section 5 show the empirical superiority of neural SFEs over their scalar counterparts.
Our construction is given in the following proposition:
Proposition 3. Let px induce scalar SFE of For X S4 consider decomposition X D Xxxix and fix
Px (S, = Σ X (5)px, for all S.T& S [m].
Then, /x defines a neural SFE 8 X.
See Appendix for proof. The choice of decomposition will give rise to different extensions. Here, we instantiate our neural extensions using the eigendecomposition of X. Since eigenvectors may not belong to [0, 1|"h we reparameterize by first applying a sigmoid function before computing the scalar extension distribution Px- In practice found that neural SFEs work just as well even without this sigmoid function-i.ee. allowing scalar SFEs to be evaluated outside of [0, I The continuity of the neural SFE 3 when using the cigendecomposition follows from variant of the Davis-Kahan theorem (Yu et al., 2015), which requires the additional assumption that the eigenvalues of x are distinct. For efficiency, in practice we do not use all n eigenvectors, and use only the with largest eigenvalue. This is justified by Figure 3, which shows that in practical applications X often has rapidly decaying spectrum.
Evaluating a neural SFE requires an accessible closed expression, the precise form of which de- pends on the underlying scalar SFE. Further, from the definition of Neural SFEs see that if scalar SFE is supported on sets with a property that is closed under intersection (e.g., bounded cardinality), then the supporting sets of the corresponding neural SFE will also inherit that property. This implies that the neural counterparts of the Lovász, bounded cardinality Lovász, and singleton/permutation extensions have the same support as their scalar counterparts. An immediate corollary is that we can casily compute the neural counterpart of the Lovász extension which has simple closed form:
Corollary For X E S consider the eigendecomposition X = E Axx,x._ Let Px; be as the Lovász extension: Px. (S.,) (II,,) a (x4.)+1), where is the sigmoid function, and is sorted so 24,1 2 ... 2 æi,n and Sij- .l......J .... with Px, (S) = 0 for all other sets. Then, the neural Lovász extension is:
5(X)= = Σ txxx (Sp) (St)
n
(px. (St)) +2 Σ Px (Sie) f(Si)). B:ンン
1,=1
Complexity and obtaining sets as solutions. In general, the neural SFE relies on all pairwise intersections S n T of the scalar SFE sets, requiring O(m²) evaluations of f when the scalar SFE supported on m sets. However, when the scalar SFE supported on a family of sets that is closed under intersection-ce requires only (m) function evaluations. Discrete solutions can be obtained efficiently by returning the best set out of all scalar SFEs Px;:
the Lovász and singleton extensions the corresponding neural SFE
5 Experiments
We experiment with SFES as loss functions in neural network pipelines on discrete objectives arising in combinatorial and vision tasks. For combinatorial optimization, SFEs network training with continuous version of the objective without supervision. For supervised image classification, they allow us to directly relax the training error instead of optimizing proxy like cross entropy.

---

Maximum Clique IMDB- BiDB-Binary
ENZYMES
PROTEINS
MUTAG
COLLAB
Straight-througg (Bengio et ul., 2013)
0. 0.725
0.722+0.20
0.927
0.965_0.162
0.856 221
Erdös (Karalias& Loukas, 2020)
0. 0..83
0.905 133
0.130
1.000=0.000
0.852 212
REINFORCE (Williams, 1992)
0.751 0.751 +0.301
0. 0.725 #0.285
0.88 0.881 40.240
1.000=0.000
0.781 316
Lovász scalar SFF Lovász neural SFE
0.
0. 0.77840.270
0.975
0.977
0.855
0.933
0. 0.926
0.961
1.000 0.000
0.864
Maximum Independent Set
ENZYMES
PROTEINS
IMDB-Binar Binary
MUTAG
COLLAB
Straight-through (Bengio et al., 2013)
0.505
20.22
0.701 #0.252
0.72 20.277
0.33 =0.200 260
Frdós (Karalias& & I Loukas, 2020)
0.821 10.124
0.90310.114
0.515
0.939 0.009
0.886
REINFORCE (Williams, 1992)
0.617
0.57920.340
0.899
0.744_0.121
0.053
Lovász scalar SFE
0.311 0.311 10.289
0.462 2,0.60
0.716
10.269
0.737_o.156
0.302 208
Lovász neural SFE
0.77510.155
0.729 20.205
0.679 1o.29_00.287
0.854_o.100
0.392 1.. 253
Table Unsupervised neural combinatorial optimization: Approximation ratios for combinatorial problems. Values closer to I are better (t). Neural SFEs are competitive with other methods, and consistently improve over vector SFEs.
5.1 Unsupervised Neural Combinatorial Optimization
We begin by evaluating the suitability of neural SFEs for unsupervised learning of neural solvers for combinatorial optimization problems on graphs. We use the ENZYMES, PROTEINS, IMDB, MUTAG, and COLLAB datasets from the TUDatasets benchmark (Morris et al., 2020), using 60/30/10 split for train/test/val. We test on two problems: finding maximum cliques, and maximum independent sets. We compare with three neural network based methods. We compare to two common approaches for backpropogating through discrete functions: the REINFORCE algorithm (Williams, 1992), and the Straight-Through estimator (Bengio al., 2013). The third is the recently proposed probabilistic penalty relaxation (Karalias & Loukas, 2020) for combinatorial optimization objectives. All methods the same GNN backbone, comprising single GAT layer (Veličković al., 2018) followed by multiple gated graph convolution layers Li et al. (2015).
In all cases, given an input graph G E) with [V|
nodes, GNN produces embedding for each node: X E Raxd, For scalar SFEs d = 1, while for neural SFEs we consider XX in order to produce an PSD matrix, which is passed as input the SFE 3. The set function used is problem dependent, which we discuss below. Finally, see Appendix F for training and hyper-parameter optimization details, and Appendix for details on data, hardware, and software.
Maximum Clique. A set S C V is a clique of G (V, E") if (i.j) E E for all i.j E S. The MaxClique problem is find the largest set S that a clique: i.e., f(S) = S 1(8 a clique].
Maximum Independent Set (MIS), set S C V is an independent set G = (V, if $ E for all i E S. The goal is to find the largest S in the graph that is independent, i.e., f(5) |S] 1{S an ind. set). MIS differs significantly from MaxClique due to its high heterophily.
Results. Table displays the mean and standard deviation of the approximation ratio J(S)/((S*) of the solver solution and an optimal S on the test set graphs. The neural Lovašz extension outper- forms its scalar counterpart in 8 out of 10 cases, often by significant margins, for instance improving a score of 0.778 on PROTEINS MaxClique to 0.926. The neural SFE proved effective at boosting poor scalar SFE performance, e.g., 0.311 on ENZYMES MIS, to the competitive performance of 0.775. Neural Lovašz outperformed or equalled and straight-through in 9 out of 10 cases, and the method of Karalias & Loukas (2020) in 6 out of 10.
5.2 Constraint Satisfaction Problems
Constraint satisfaction problems ask if there exists a set satisfying a given set of conditions (Kumar, 1992; Cappart et al., 2021b). In this section, we apply SFES to the k-clique problem: given a graph, determine if it contains clique of size & or more. We test on the ENZYMES and PROTEINS datasets. Since satisfiability is binary classification problem we evaluate using Fl score.
7

---

1.0
1.0
0.7
0.7
H1-score
IT ---scoree
0.8-
0.8
FI-sc0
0.6
0.6
0.5
0.5
0.6
0.6
0.4
0.4
0.4
0.4
0.3
2-
Lovioo Lowdz HEINPOOKE
Lowdsz Loves HEINFORLE
A-Loveer LovAs REINFORCE
condar
ROINPONCE
PROTEINS (k 3)
ENZYMES (K - 3)
PROTEINS (K = 4)
ENZYMES (k - 4)
Figure 2: k-clique constraint satisfaction: higher F1-score is better. The k-bounded cardinality Lovasz extension is better aligned with the task and significantly improves over the Lovász extension.
Approx, Ratio
1.0
ENZYMES
ENZYMES
Approx: Ratio
1.0
PROTEINS
PROTEINS
Pequent
0.8-
$1
2012
0.6
Dnn 10a
10
10
10
10 10
10
10
10
T0
Number Figonvectors
Eigenvalue Size
Eigenvactors
Eigenvalue Size
Figure 3: Left: Runtime and performance of neural SFEs on MaxClique using different numbers of cigenvectors. Right: Histogram of spectrum of matrix X, outputted by GNN trained on MaxClique.
Results. Figure 2 shows that by specifically searching over sets of size k using the cardinality constrained Lovász extension from Section 3.1, we significantly improve performance compared to the Lovász extension, and REINFORCE. This illustrates the value of SFEs in allowing task dependett considerations (in this case cardinality constraint) to be built into extension design.
5.3 Training Error as Classification Objective
Neural Lovász
During training the performance of classifier is typically assessed using the training error
Lovász (multiple)
E (1,, + h.x;)) Since training error itself is non non-differentiable, it is standard to train h to optimize differentiable surrogate such as the cross-entropy loss. Here we offer an alternative training method by continuously extending the -ififfferrenee map- ping y + 1 (ıs * 5). This map is a set function defined on single item sets, so we use the singleton extension (definition in Section 3.1). Our goal is to demonstrate that the resulting differentiable loss func- tion closely tracks the training error, and can be used to minimize We do not focus on test time gener- alization. Figure 6 shows the results. The singleton extension loss (left plot) closely tracks the true train- ing error at the same numerical scale, unlike other common loss functions (sce Appendix G for setup details). While we leave further consideration to future work, training error extensions may be useful for model calibration (Kennedy & O' O'Hagan, 2001) and uncertainty estimation (Abdar et al., 2021).
MaxClique
Lovász
DA 20
6.2
06
06
10
0.0
02
0.4
0.6
09
SIS
06
us
0.
08 PROTEINS
02
04
o'a
ENZYMES
Figure 4: Neural SFEs outperform naive alternative high-dimensional extension.
5.4 Ablations
Number of Eigenvectors. Figure compares the runtime and performance of neural SFEs using only the top-k eigenvectors from the eigendecomposition X = "n Xxx,,, with A E 21, 3, 4,5, 6) on the maximum clique problem. For both ENZYMES and PROTEINS, performance increases with c-casily outperforming scalar SFES and REINFORCE-O uuttl saturation around & = 4, while runtime grows linearly with k. Histograms of the eigenvalues produced by trained networks show a rapid decay in the spectrum, suggesting that the smaller eigenvalues have little effect on 3.
Comparison to Naive High-Dimensional Extension. We compare neural SFEs dimensional alternative which, given an n x d matrix X simply computes a scalar SFE on each column independently and sums them up. This naive function design is not an extension, and the dependence on the d dimensions is linearly separable, in contrast to the complex non-linear interactions between columns of X neural SFEs. Figure shows that this naive extension, whilst improving over one-dimensional extensions, performs considerably worse than neural SFEs.
naive high-

---

Singleton Extension
Cross Entropy
Exponential
MSE
Hinge
1.0
0.8-A
0.6
0.5
train loss
0.4
04-
0.4
train error
0.2
0.2
0.2
0.2
02-
0.0
0
50
100
0.C
50 Epochs
100
0.0
50 Epochs
100
0.0
0
50
100
0.0
50
100
Epochs
Epochs
Epochs
1.0
Singleton Extension
10-
Cross Entropy
1.0
Exponential
2.0
MSE
Hinge
0.8
0.8
0.5
0.8
0.8
0.6
0.6-
0.5-
0.6
0.6
train loss
0.4
04
0.4
0.4
0.4
orror
0.2
0.2
0.2-
0.-
0.2
0
50 Epochs
100
0.
50 Epochs
100
0.0
100
100
50
100
Epochs
Epochs
Epochs
Figure 5: Top: CIFARIO. Bottom: SVHN. The singleton extension loss (left) is the only loss that
approximates the true non-differentiable training error at the same numerical scale.
6 Related Work
Neural combinatorial optimization Our experimental setup largely follows recent work on un- supervised neural combinatorial optimization (Karalias & Loukas, 2020; Schuetz et al., 2022; Xu al., 2020; Toenshoff et al., 2021; Amizadeh et al., 2018), where continuous relaxations of discrete objectives are utilized. In that context, it is important to take into account the key conceptual and methodological differences of our approach. For instance, in the unsupervised Erdōs goes neural (EGN) framework from Karalias& & Loukas (2020), the probabilistic relaxation and the proposed choice of distribution can be viewed as instantiating multilinear extension. As explained earlier, this extension is costly in the general case (since must be evaluated 2 times, and summed) but can be computed efficiently closed form in certain cases. On the other hand, our extension framework offers multiple options for efficiently computable extensions without imposing any further conditions on the set function. For example, one could efficiently (linear time in n) compute the scalar and neural Lovász extensions of any set function with only black-box access to the function. This renders our framework more broadly applicable. Furthermore, EGN incorporates the problem constraints additively in the loss function. In contrast that, extension framework does not require any commitment to a specific formulation in order to obtain a differentiable loss. This provides more flex- ibility in modelling the problem, other ways (e.g., multiplicatively). For general background on neural combinatorial optimization, we refer the reader to the surveys (Bengio et al., 2021; Cappart et al., 2021a; Mazyavkina et al., 2021).
combine the cost function and the constraints in various
Goemans-Williamson Lifting to high-dimensional spaces. Neural SFEs are heavily inspired by the Goemans- Williamson (Goemans& & Williamson, 1995) algorithm and other SDP techniques (Iguchi et al., 2015). which lift problems onto higher dimensional spaces, solve them, and then project back down. Our approach to lifting set functions to high dimensions is motivated by the algorithmic alignment principle (Xu et al., 2019): neural networks whose computations emulate classical algorithms often generalize better with improved sample complexity (Yan et al., 2020; Li et al., 2020; Xu al., 2019). Emulating algorithmic and logical operations is the focus of Neural Algorithmic Reasoning (Veličković et al., 2019; Dudzik& & Veličković, 2022; Deac et al., 2021) and work on knowledge graphs (Hamilton et al., 2018; Ren et al., 2019; Arakelyan et al., 2020), which also emphasize operating in higher dimensions.
Extensions. Scalar SFES use an LP formulation of the convex closure (El Halabi, 2018, Def. 20), classical approach for defining convex extensions of discrete functions (Murota, 1998, Eq. 3,57). See Bach (2019) for study of extensions of submodular functions. The constraints of our dual LP arise in contexts from global optimization (Tawarmalani & Sahinidis, 2002) to barycentric approximation and interpolation schemes in computer graphics (Guessab, 2013; Hormann, 2014). Convex extensions have also been used for combinatorial penalties with structured sparsity (Obozinski & Bach, 2012, 2016), and general minimization algorithms for set functions (El Halabi & Jegelka, 2020).
Stochastic gradient estimation. SFEs produce gradients for / requiring only black-box access. There is a wide literature on sampling-based approaches to gradient estimation, for instance the REINFORCE algorithm (Williams, 1992) (i.e., score function estimator). However, sampling introduces noise which can cause unstable training and convergence issues, prompting significant

---

study of variance reducing control variates (Gu et al., 2017; Liu et al., 2018; Grathwohl et al., 2018; Wu al., 2018: Cheng et al., 2020). SFEs can avoid sampling (and noise) all-together, our extensions are differentiable and can be computed deterministically. A closely related, yet distinct, task to produce gradients through sampling operations, which introduce non-differentiable nodes in neural network computation graphs. The Straigh--Through Estimator (Bengio et al., 2013), arguably the simplest solution, treats sampling as the identity map in the backward pass, yiclding biased gradient estimates. The Gumbel-Softmax trick (Maddison et al., 2017; Jang et al., 2017), provides an alternative method to sample from categorical distributions (also benefiting from variance reduction (Paulus et al., 2020a)). The trick can be through the lens of the more general Perturb-and-Mo framework that treats sampling as a perturbed optimization program. This framework has since been used to generalize the trick to more complex distributions (Paulus et al., 2020b) and to differentiate through the parameters of exponential families for learning and combinatorial tasks (Niepert et al., 2021). Broadly, these techniques relax discrete distribution into continuous one by utilizing noise distribution and assuming access to a continuous loss function. SFEs are complementary to this setup, addressing the problem of designing continuous extensions.
Differentiating through convex programs and algorithms. Recent years have seen a surge of interest in combining neural networks with solvers (e.g.. LP solvers) and/or algorithms in differen- tiable end to end pipelines (A (Agrawal et al., 2019; Amos & Kolter, 2017; Paulus et al., 2021; Pogančić et al., 2019; Wang al., 2019). Whilst sharing the algorithmic alignment motivation of SFEs, the convex programming connection mostly cosmetic: these works directly embed solvers into network architectures, while SFEs use convex programs analytical tool, without requiring solver access.
Conclusion
We introduced Neural Set Function Extensions, framework that enables evaluating set functions continuous and high dimensional representations. We showed how to construct such extensions and demonstrated their viability in range of tasks including combinatorial optimization and image clas- sification. Notably, neural extensions deliver good results and improve over their scalar counterparts, further affirming the benefits of problem-solving in high dimensions.
Acknowledgements
NK would like thank Marwa El Halabi, Mario Sanchez, Mehmet Fatih Sahin, and Volkan Cevher for the feedback and fruitful discussions. NK and AL would like to thank the Swiss National Science Foundation for supporting this work the context of the project "Deep Learning for Graph-Structur Data" (grant number PZ0OP21799 19981). SJ and JR acknowledge support from NSF CAREER award 1553284. NSF award 1717610, and the NSF AI Institute TILOS.
10

---

References
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, et al. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint
04467, 2016.
Moloud Abdar, Farhad Pourpanah, Sadiq Hussain, Dana Rezazadegan, Li Liu, Mohammad Ghavamzadeh, Paul Fieguth, Xiaochun Cao, Abbas Khosravi, U Rajendra Acharya, et al. A review of uncertainty quantification in deep learning: Techniques, applications and challenges.
Information Fusion, 76:243-299 297, 2021.
Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J Zico Kolter. Differentiable convex optimization layers. Advances in Neural Information Processing Systems, 32:9562-9574, 2019.
Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. Learning to solve cireuit-sat: unsupervised differentiable approach. In International Conference on Learning Representations, 2018.
Brandon Amos and J Zico Kolter. Optnet: Differentiable optimization as layer in neural networks. In International Conference on Machine Learning, pp. 136-145. PMLR, 2017.
Erik Arakelyan, Daniel Daza, Pasquale Minervini, and Michael Cochez. Complex query answering with neural link predictors. In International Conference on Learning Representations, 2020.
Federico Ardila, Carolina Benedetti, and Jeffrey Doker. Matroid polytopes and their volumes.
Discrete & Computational Geometry, 43(4):841-854, 2010.
Francis Bach, Submodular functions: from discrete to continuous domains. Mathematical Program- ming, 175(1):419-45) 459, 2019.
Frédéric Bastien, Pascal Lamblin, Razvan Pascanu, James Bergstra, Ian Goodfellow, Arnaud Bergeron. Nicolas Bouchard, David Warde-Farley, and Yoshua Bengio. Theano: new features and speed improvements. arXiv preprint 12 2012.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonnzlez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 1xivv1806.012666 2018.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical variance trade-off. Proceedings of the National Academy of Sciences, 116(32):15849-15555 2019.
Irwan Bello. Hieu Pham, Quoc V Le. Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.
2016.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating propagating gradients through stochastic neurons for conditional computation. arXiv preprint /308.33333 2013.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d'horizon. European Journal of Operational Research, 290,2 2021.
Jeff Bilmes. Submodularity in machine learning and artificial intelligence. arXiv:2202.00/32. 2022.
arXiv preprint
G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák. Maximizing submodular set function subject to matroid constraint. SIAM J. Computing, 40(6), 2011.
Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. arXiv preprint arXiv:2102.09544, 202

---

Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. In Zhi-Hua Zhou (ed.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pp. 4348 4355. International Joint Conferences on Artificial Intelligence Organization, 8 b. doi: 244466//jcai.2221/559 httpttss:://de org/ 10. 24963/1jcccct //jes/iiiii./////// 2021/599.. Survey Track.
Ting Chen, Simon Korbllihh, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pp. 1597-1607. PMLR, 2020.
Ching-An Cheng. Xinyan Yan, and Byron Boots. Trajectory-wise control variates for variance reduction in policy gradient methods. In Conference Robot Learning, pp. 1379-1394. PMLR, 2020.
Gustave Choquet. Theory of capacities. In Annales de I l'institut Fourier, volume 5, pp. 131-295, 1954.
Andreea-loana Deac, Petar Veličković, Ognjen Milinkovic, Pierre-Luc Bacon, Jian Tang, and Mladen Nikolic. Neural algorithmic reasoners are implicit planners. In M. Ran- zato, A. Beygelzimer, Y. Dauphin, P.S. Liang. and Wortman Vaughan (eds.), Ad- vances in Neural Information Processing Systems, volume 34, pp- 15529-15542. Curran Associates, Inc., 2021. URL. https: http://pppeee....n.ee neurigs..euris.... htt.:/ppp....pppp////////.//..1. / 02498721266222011100992bb2222333
Paper pdf..
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.0205. 2018.
Andrew Dudzik and Petar Veličković. Graph neural networks are dynamic programmers. arXiv
preprint ar (wX.:::223.355444 2022.
Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial Optimiza- fion-Fureka, You Shrink!, pp. 11 11-26. Springer, 2003.
Marwa El Halabi. Learning with structured sparsity: From discrete to convex and back. Technical report, EPFL, 2018.
Marwa El Halabi and Stefanie Jegelka. Optimal approximation for unconstrained non-submodular minimization. In International Conference on Machine Learning, pp. 3961-3972 PMLR, 2020.
Marwa El Halabi, Francis Bach, and Volkan Cevher. Combinatorial penalties: Which structures are preserved by convex relaxations? International Conference on Artificial Intelligence and Statistics, pp. 1551-1560. PMLR, 2018
James E Falk and Karla R Hoffman. A successive underestimation method for concave minimization problems. Mathematics of operations research, 1(3):251-259, 1976.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. In ICLR (Workshop Representation Learning Graphs and Manifolds), volume 7, 2019.
Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6): 1115-1145, 1995.
Will Grathwohl, Dami Choi, Yuhuai Wu, Geoff Roeder, and David Duvenaud. Backpropagation through the void: Optimizing control variates for black-box gradient estimation. In International Conference on Learning Representations, 2018.
M. Grötschel, L. Lovász, and A. Schrijver. The ellipsoid algorithm and its consequences in combina- torial optimization. Combinatorica, 1:499-513. 513, 1981.
S Gu, T Lillicrap. Z Ghahramani, RE Turner, and S Levine. Q-prop: Sample-efficient policy gradient with an off-policy critic. In 5th International Conference on Learning Representations, ICLR 2017-Conference Track Proceedings, 2017.
12

---

Allal Guessab. Generalized barycentric coordinates and approximations of convex functions on arbitrary convex polytopes. Computers & Mathematics with Applications, 66(6):1120-1133 2013.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2021. URL https://www.
gurobi com.
com.
Will Hamilton, Payal Bajaj. Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding logical queries on knowledge graphs. Advances neural information processing systems, 31, 2018.
Kai Hormann. Barycentric interpolation. In Approximation Theory XIV: San Antonio 2013, pp- 197-218. Springer, 2014.
Takayuki Iguchi, Dustin Mixon, Jesse Peterson, and Soledad Villar. On the tightness of an sdp relaxation of k-means, arXiv preprint 1505047505.04778 2015.
Rishabh lyer, Stefanie Jegelka, and Jeff Bilmes. Monotone closure of relaxed constraints in submod- ular optimization: Connections between minimization and maximization: Extended version. In UAI, 2014.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameteriizaiion with gumbel-softmax. In Ini. Conf. on Learning Representations (ICLR), 2017.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. In NeurIPS, 2020.
Marc C Kennedy and Anthony O' O'Hagan. Bayesian calibration of computer models. Journal of the Royal Statistical Society: Series (Statistical Methodology), 63(3):425-464, 2001.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint MrXivv:412.6990 2014.
Vipin Kumar. Algorithms for constraint-satiisfaciion problems: A survey. Al magazine, 13(1):32-32, 1992.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural 2015.
networks. arXiv preprint
Yujia Li, Felix Gimeno, Pushmeet Kohli, and Oriol Vinyals. Strong generalization and efficiency in neural programs. arXiv preprint arXiv:2007.03629, 2020.
Hao Liu, Yihao Feng, Yi Mao, Dengyong Zhou, Jian Peng, and Qiang Liu. Action-dependent control variates for policy optimization via stein identity. In International Conference on Learning Representations, 2018.
László Lovász. Submodular functions and convexity. In Mathematical programming the state of the art, pp. 235-257. Springer, 1983.
László Lovász and Alexander Schrijver. Cones of matrices and set-functions and 0-1 optimization.
SIAM journal on optimization, 1(2):166 190, 1991.
Maddison, Mnih, and Teh. The concrete distribution: A continuous relaxation of discrete random variables. In Int. Conf. on Learning Representations (ICLR), 2017.
Maricha. An axiomatic approach of the discrete choquet integral as tool to aggregate interacting criteria. IEEE transactions on fuzzy systems, 8(6):800-807, 2000.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 134:105400 2021.
D.S. Meek. The inverses of toeplitz band matrices. Linear Algebra and its Applications. 49: 117-129, 1983. ISSN 0024-3795. doi: http:://wwwwssienceeeee. http://www.....c.acccaaaaaaaaaaa
URL
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663. 2020.
13

---

Kazuo Murota. Discrete convex analysis. Mathematical Programming, 83(1):313 1998.
Mathias Niepert, Pasquale Minervini, and Luca Franceschi. Implicit mle: Backpropagating through discrete exponential family distributions. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, Curran Associates, Inc., 2021. URL https: attpps:/ppooeee wttpr//eeee//essssee/eeee 444 pdf.
pp.
sechiinngnneuuiss..eeeee neurips cc/
Guillaume Obozinski and Francis Bach. Convex Relaxation for Combinatorial Penalties. PhD thesis,
INRIA, 2012.
Guillaume Obozinski and Francis Bach. A unified perspective convex structured sparsity: Hierar- chical, symmetric, submodular norms and beyond. 2016.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
Anselm Paulus, Michal Rolinek, Vit Musil, Brandon Amos, and Georg Martius. Comboptnet: Fit the right np-hard problem by learning integer programming constraints. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8443-8453. PMLR, 18-24 Jul 2021. URL https:/ ftttp::/pprceedingg/
mlr pra.s/press//v3 pttp///aalssaaaaaama html.
Max B Paulus, Chris J Maddison, and Andreas Krause. Rao-bblakkweliizing the stright-through gumbel-softmax gradient estimator. In International Conference on Learning Representations, 2020a.
Max Benedikt Paulus, Dami Choi, Daniel Tarlow, Andreas Krause, and Chris J Maddison. Gradient estimation with stochastic softmax tricks. In NeurIPS 2020, 2020b.
Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differenti- ation of blackbox combinatorial solvers. In International Conference on Learning Representations, 2019.
Hongyu Ren, Weihua Hu, and Jure Leskovee. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In International Conference Learning Representations, 2019.
Alexander Schrijver al. Combinatorial optimizaaiion: polyhedra and efficiency, volume 24. Springer, 2003.
Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4):367-377, 2022.
John Shawe-Taylor, Nello Cristianini, et al. Kernel methods for pattern analysis. Cambridge university press, 2004.
Mohit Tawarmalani and Nikolaos V Sahinidis. Convex extensions and envelopes of lower semi- continuous functions. Mathematical Programming, 93(2):247-263, 2002.
Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Graph neural networks for maximum constraint satisfaction. Frontiers in artificial intelligence, 3:98, 2021.
William F Trench. Inversion of toeplitz band matrices. Mathematics of computation, 28(128): 1099, 1974.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
14

---

Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. In International Conference on Learning Representations, 2019.
Petar Veličković and Charles Blundell. Neural algorithmic reasoning. Patterns, 2(7): 2021. ISSN 2666-3899.
J. Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In Symposium on Theory of Computing (STOC), 2008.
Po- Po-Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and logical reasoning using differentiable satisfiability solver. In International Conference on Machine Learning, pp. 6545-6554, PMLR, 2019.
Ronald J Williams. Simple statistical foolowng algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-255 1992.
Cathy Wu, Aravind Rajeswaran, Yan Duan, Vikash Kumar, Alexandre Bayen, Sham Kakade, Igor Mordatch, and Pieter Abbeel. Variance reduction for policy gradient with action-dependent factorized baselines. International Conference on Learning Representations, 2018.
Hao Xu, Ka-Hei Hui, Chi- Mhig Fu, and Hao Zhang. Tilingnn: learning to tile with self supervied graph neural network. ACM Transactions Graphics (TOG), (0(4):129-1) 2020.
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In International Conference on Learning Representations, 2019.
Yujun Yan, Kevin Swersky, Danai Koutra, Parthasarathy Ranganathan, and Milad Hashemi. Neural execution engines: Learning to execute subroutines. Advances in Neural Information Processing Systems, 33, 2020.
Yi Yu, Tengyao Wang, and Richard Samworth. useful variant of the davis-kahan theorem for statisticians. Biometrika, 102(2):315-322) 2015.
Li Yujia, Tarlow Daniel, Brockschmidt Mare, Zemel Richard, al. Gated graph sequence neural networks. In International Conference on Learning Representations, 2016
15


Reviews:
[{"review_id": "lBrB1cckjad", "reviewer": "Reviewer_Wk2P", "summary": "The paper is about training neural networks on discrete objects, and sets in particular. The set loss functions are typically non-differentiable, but the authors propose a method for extending the space of discrete set embeddings to continuous space. This means we can evaluate set loss functions on continuous outputs of a neural network, enabling training on non-differentiable losses. The extended set function is defined as a convex combination of the set function values at discrete points. The authors propose several ways of setting the weights of the convex combination and choosing which sets the function is evaluated on. The authors then extend the method to _matrix_ set embeddings (as opposed to vector embeddings), arguing that the increased dimensionality aids learning. The authors evaluate the method on a set of discrete optimization tasks.", "questions": "- Have authors measured the runtimes/memory requirements of the various variants of the proposed method? For example, does the runtime/memory use increase significantly when using neural SFE as opposed to the scalar SFE? How do both compare to REINFORCE/Erdos? \n\n- Consider re-naming figures 3-5 to have them go in order.", "limitations": "I believe the discussion on the limitations of the method could be extended (see the weaknesses and questions above).\n\nAuthors do not discuss potential negative societal impact of their work, but I consider them to be minor, albeit methods like these could potentially be used for mining social graphs.", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- A contribution to the important field of neural network learning in discrete spaces.\n- The paper is written well: the narrative is clear, the mathematical notation is crisp, the discussion of related literature is extensive.\n- Original work with a great deal of technical complexity: the authors lean on the discrete optimization literature, but adapt the ideas in the neural network learning context.\n- The theoretical motivation of the method is sound, and the empirical evaluation is extensive.\n- The method consistently beats a strong baseline (REINFORCE).\n\nWeaknesses:\n- Even though neural SFE is consistently beating the scalar SFE, the results of both methods are less impressive when compared to the strongest baseline (Erdos).\n- Given the previous point, a deeper discussion of the benefits/drawbacks of Erdos when compared to SFE and a more extensive empirical comparison of the two methods would make for a stronger contribution.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5D7h5_g0Ohf", "reviewer": "Reviewer_NU5a", "summary": "This paper proposes a framework for extending functions on discrete sets to continuous domains. They propose a method called \"neural set function extensions\" for approximating these function extensions with neural networks in a way that is amenable to standard gradient-based optimization techniques. The proposed framework is evaluated on a number of discrete combinatorial optimization problems such as finding maximum cliques in a graph on a number of existing graphical benchmarks.", "questions": "Can you give a clearer overview of the relevance of the problem area? Where is neural optimization of discrete graphical properties such as maximum cliques likely to be relevant to the broader community? Do existing models in the literature fail to address these cases? The results in table 1 don't seem to show that you convincingly outperform existing baselines - is there another way in which your proposed model is superior to existing methods?\n\nThe k-clique constraint satisfaction experiments did not compare against the Erdos model from table 1 - is this model not applicable for these experiments, or was there another reason it was omitted?\n\n", "limitations": "This is a technical paper and is unlikely to have any obvious negative social impacts.\n\nAs mentioned in previous sections, I think the paper would benefit from a clearer discussion of where the proposed method is applicable and why these applications are significant.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper proposes an interesting and novel framework for embedding functions on discrete sets into a differentiable framework that can be optimized using standard gradient-based techniques. The proposed techniques are mathematically interesting, and may allow neural models to be applied to regimes that were previously very difficult to optimize. \n\nMy primary concern with this work is with the significance of the proposed methods. It is unclear to me how relevant the problem settings addressed by the authors are, and whether they are addressed satisfactorily by existing methods. I think the paper would benefit from a clearer discussion of where these models could be applied, and how these applications are relevant to the wider machine learning community, as well as the degree to which existing methods fail in these regimes.\nThe empirical results in the paper also seem rather weak - on the maximum clique and maximum independent set experiments shown in table 1, the proposed model only outperformed existing baselines by statistically significant margins on 1 category out of 10 - in all others it was worse or within standard deviation of the baseline. On the maximum independent set task, the proposed model performed worse than the baselines on every dataset, sometimes by large margins.\nAll in all, I find the mathematical framework proposed by the paper to be quite interesting, but I am not entirely convinced by the significance of the contribution. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept