Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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. 

My 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.
The 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.
All 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. 
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?

The 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?


limitations: This is a technical paper and is unlikely to have any obvious negative social impacts.

As 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.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
- A contribution to the important field of neural network learning in discrete spaces.
- The paper is written well: the narrative is clear, the mathematical notation is crisp, the discussion of related literature is extensive.
- 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.
- The theoretical motivation of the method is sound, and the empirical evaluation is extensive.
- The method consistently beats a strong baseline (REINFORCE).

Weaknesses:
- 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).
- 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.
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? 

- 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).

Authors 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.
review_title: null

Meta-review: metareview: This paper proposes a new neural set function extensions methodology that allows approximating function on sets with neural networks in a way that is amenable to standard gradient-based optimization techniques. The proposed methodology 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.

Allowing neural networks (and other ML methods) to natively handle discrete functions is important in a variety of applications. This paper is a step towards a more robust solution to this problem and a worthy contributions to the conference.
confidence: Certain
Decision: Accept