  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.
