Learning to Sample Hard Instances for Graph Algorithms
  Hard instances, which require a long time for a specific algorithm to solve,
help (1) analyze the algorithm for accelerating it and (2) build a good
benchmark for evaluating the performance of algorithms. There exist several
efforts for automatic generation of hard instances. For example, evolutionary
algorithms have been utilized to generate hard instances. However, they
generate only finite number of hard instances. The merit of such methods is
limited because it is difficult to extract meaningful patterns from small
number of instances. We seek for a probabilistic generator of hard instances.
Once the generative distribution of hard instances is obtained, we can sample a
variety of hard instances to build a benchmark, and we can extract meaningful
patterns of hard instances from sampled instances. The existing methods for
modeling the hard instance distribution rely on parameters or rules that are
found by domain experts; however, they are specific to the problem. Hence, it
is challenging to model the distribution for general cases. In this paper, we
focus on graph problems. We propose HiSampler, the hard instance sampler, to
model the hard instance distribution of graph algorithms. HiSampler makes it
possible to obtain the distribution of hard instances without hand-engineered
features. To the best of our knowledge, this is the first method to learn the
distribution of hard instances using machine learning. Through experiments, we
demonstrate that our proposed method can generate instances that are a few to
several orders of magnitude harder than the random-based approach in many
settings. In particular, our method outperforms rule-based algorithms in the
3-coloring problem.
