Divide and Conquer with Neural Networks

Alex Nowak, Joan Bruna

Abstract

Divide and Conquer Networks (DiCoNet) introduce a recursive neural architecture designed to solve algorithmic tasks by learning to partition problems into smaller sub-tasks and merging their solutions. By embedding the "divide and conquer" principle as an inductive bias, the model achieves superior generalization to large input sizes and enables optimization for computational efficiency. This approach bridges the gap between traditional algorithmic logic and neural pattern recognition, demonstrating significant performance gains in combinatorial and geometric tasks.

Introduction

Many fundamental algorithmic problems—such as sorting, finding a convex hull, or clustering—exhibit scale invariance. This property implies that the strategy used to solve a small instance of a problem can be applied recursively to solve much larger ones. However, standard neural networks like RNNs or CNNs often treat these tasks as "black-box" regression problems. This leads to two primary failures: a significant generalization gap where models fail on inputs larger than those seen during training, and a complexity mismatch where fixed architectures cannot scale their computation time to the problem's inherent difficulty.

DiCoNet addresses these issues by hard-coding the recursive structure of "divide and conquer" directly into the network's architecture, allowing the model to focus on learning the logic of the algorithm rather than memorizing specific patterns.

Methods: The DiCoNet Architecture

The DiCoNet architecture operates on a dynamic binary tree structure determined by the input itself. It consists of two primary, scale-invariant modules:

  1. The Split Module ($S_\theta$): This module takes a set of inputs and learns to partition them into two disjoint subsets. Because the splitting decision is discrete, the authors utilize Policy Gradient (REINFORCE) for training. To ensure the model remains permutation-invariant, the module is implemented using architectures like Graph Neural Networks (GNNs).
  2. The Merge Module ($M_\phi$): Once the base cases (leaves of the tree) are reached, the Merge module combines two partial solutions into a single, larger solution as it traverses back up the tree. This is typically implemented using Pointer Networks or GNNs.
The DiCoNet architecture illustrating the recursive split and merge process across a dynamic computation tree.

Complexity Regularization

A standout feature of this framework is the use of a regularization term that encourages "balanced" trees. In traditional algorithms, a balanced divide-and-conquer approach leads to $O(n \log n)$ complexity. By maximizing the variance of split probabilities, the network is incentivized to split sets into roughly equal halves, effectively optimizing for computational efficiency during the learning process.

Experimental Evaluation

The authors evaluated DiCoNet on several classic combinatorial and geometric tasks, including Planar Convex Hull, 0-1 Knapsack, and Euclidean TSP.

Key Results

The model demonstrated a remarkable ability to generalize to problem sizes far beyond its training data. In the Convex Hull task, DiCoNet significantly outperformed the standard Pointer Network baseline.

Performance comparison (accuracy %) on the Convex Hull task across varying input sizes (n). DiCoNet variants consistently outperform the baseline, especially as problem size increases.

As shown in the results, for $n=100$ points, DiCoNet achieved 80.0% accuracy compared to the baseline's 41.5%. Crucially, while the baseline's performance plummeted to 13.5% for $n=200$, the DiCoNet + Split Reg variant maintained a robust 67.2% accuracy. Similar trends were observed in the Knapsack problem and clustering tasks, where DiCoNet found better local optima than standard iterative algorithms like Lloyd’s for large numbers of clusters.

Conclusion

DiCoNet demonstrates that integrating algorithmic inductive biases into neural architectures is essential for solving scale-invariant problems. By learning to recursively split and merge, the network achieves a level of generalization unattainable by standard black-box models. While challenges remain regarding the stability of discrete optimization via REINFORCE, this work opens new avenues for neural-algorithmic reasoning and meta-learning.

Summary updated

Abstract

We consider the learning of algorithmic tasks by mere observation of input-output pairs. Rather than studying this as a black-box discrete regression problem with no assumption whatsoever on the input-output mapping, we concentrate on tasks that are amenable to the principle of divide and conquer, and study what are its implications in terms of learning. This principle creates a powerful inductive bias that we exploit with neural architectures that are defined recursively, by learning two scale-invariant atomic operators: how to split a given input into two disjoint sets, and how to merge two partially solved tasks into a larger partial solution. The scale invariance creates parameter sharing across all stages of the architecture, and the dynamic design creates architectures whose complexity can be tuned in a differentiable manner. As a result, our model is trained by backpropagation not only to minimize the errors at the output, but also to do so as efficiently as possible, by enforcing shallower computation graphs. Moreover, thanks to the scale invariance, the model can be trained only with only input/output pairs, removing the need to know oracle intermediate split and merge decisions. As it turns out, accuracy and complexity are not independent qualities, and we verify empirically that when the learnt complexity matches the underlying complexity of the task, this results in higher accuracy and better generalization in two paradigmatic problems: sorting and finding planar convex hulls.
BibTeX
@misc{nowak2016divide,
  author = {Alex Nowak and Joan Bruna},
  title = {{Divide and Conquer with Neural Networks}},
  year = {2016},
  eprint = {1611.02401},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1611.02401},
}
Figure