Variational Annealing on Graphs for Combinatorial Optimization
Sebastian Sanokowski Wilhelm Berghammer Sepp Hochreiter Sebastian Lehner
Several recent unsupervised learning methods use probabilistic approaches to
solve combinatorial optimization (CO) problems based on the assumption of
statistically independent solution variables. We demonstrate that this
assumption imposes performance limitations in particular on difficult problem
instances. Our results corroborate that an autoregressive approach which
captures statistical dependencies among solution variables yields superior
performance on many popular CO problems. We introduce subgraph tokenization in
which the configuration of a set of solution variables is represented by a
single token. This tokenization technique alleviates the drawback of the long
sequential sampling procedure which is inherent to autoregressive methods
without sacrificing expressivity. Importantly, we theoretically motivate an
annealed entropy regularization and show empirically that it is essential for
efficient and stable learning.