# Neural Models for Output-Space Invariance in Combinatorial Problems

arXiv: https://arxiv.org/abs/2202.03229 · HTML: https://mlsanity.com/paper/2202.03229/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 32 references that are in the map.
- First posted on arXiv 7 Feb 2022.

## Builds on (most cited first, 16 of 16)

- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Averaging Weights Leads to Wider Optima and Better Generalization](https://mlsanity.com/paper/1803.05407/) (2018)
- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [Learning Explanatory Rules from Noisy Data](https://mlsanity.com/paper/1711.04574/) (2017)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver](https://mlsanity.com/paper/1905.12149/) (2019)
- [Value Iteration Networks](https://mlsanity.com/paper/1602.02867/) (2016)
- [Neural Logic Machines](https://mlsanity.com/paper/1904.11694/) (2019)
- [From Local Structures to Size Generalization in Graph Neural Networks](https://mlsanity.com/paper/2010.08853/) (2020)
- [Size-Invariant Graph Representations for Graph Classification Extrapolations](https://mlsanity.com/paper/2103.05045/) (2021)
- [Recurrent Relational Networks](https://mlsanity.com/paper/1711.08028/) (2017)
- [PDP: A General Neural Framework for Learning Constraint Satisfaction Solvers](https://mlsanity.com/paper/1903.01969/) (2019)
- [Neural Learning of One-of-Many Solutions for Combinatorial Problems in Structured Output Spaces](https://mlsanity.com/paper/2008.11990/) (2020)
- [Transfer of Deep Reactive Policies for MDP Planning](https://mlsanity.com/paper/1810.11488/) (2018)
- [DeepLogic: Towards End-to-End Differentiable Logical Reasoning](https://mlsanity.com/paper/1805.07433/) (2018)

## Built on by (most cited first, 1 of 1)

- [A Solver-Free Framework for Scalable Learning in Neural ILP Architectures](https://mlsanity.com/paper/2210.09082/) (2022)

## Abstract (arXiv)

Recently many neural models have been proposed to solve combinatorial puzzles by implicitly learning underlying constraints using their solved instances, such as sudoku or graph coloring (GCP). One drawback of the proposed architectures, which are often based on Graph Neural Networks (GNN), is that they cannot generalize across the size of the output space from which variables are assigned a value, for example, set of colors in a GCP, or board-size in sudoku. We call the output space for the variables as 'value-set'. While many works have demonstrated generalization of GNNs across graph size, there has been no study on how to design a GNN for achieving value-set invariance for problems that come from the same domain. For example, learning to solve 16 x 16 sudoku after being trained on only 9 x 9 sudokus. In this work, we propose novel methods to extend GNN based architectures to achieve value-set invariance. Specifically, our model builds on recently proposed Recurrent Relational Networks. Our first approach exploits the graph-size invariance of GNNs by converting a multi-class node classification problem into a binary node classification problem. Our second approach works directly with multiple classes by adding multiple nodes corresponding to the values in the value-set, and then connecting variable nodes to value nodes depending on the problem initialization. Our experimental evaluation on three different combinatorial problems demonstrates that both our models perform well on our novel problem, compared to a generic neural reasoner. Between two of our models, we observe an inherent trade-off: while the binarized model gives better performance when trained on smaller value-sets, multi-valued model is much more memory efficient, resulting in improved performance when trained on larger value-sets, where binarized model fails to train.