Graph Neural Networks for Maximum Constraint Satisfaction

Understand

Many combinatorial optimization problems can be phrased in the language of constraint satisfaction problems.

• We introduce a graph neural network architecture for solving such optimization problems.
• The architecture is generic; it works for all binary constraint satisfaction problems.
• Training is unsupervised, and it is sufficient to train on relatively small instances; the resulting networks perform well on much larger instances (at least 10-times larger).