Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions
This addresses a key bottleneck in enabling neural networks to reason about discrete objects, which is important for applications like combinatorial optimization.
The paper tackles the challenge of integrating discrete set functions into neural networks by developing a framework that extends them to continuous domains and converts them to high-dimensional representations, showing empirical benefits for unsupervised neural combinatorial optimization.
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.